|
Zapiski Nauchnykh Seminarov LOMI, 1979, Volume 88, Pages 197–208
(Mi znsl3114)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Preservation of the equivalence of proofs under reduction of the formula depth
S. V. Solov'ev
Abstract:
The derivability of a sequent is the invariant of the following transformation decreasing the formula depth of the sequent. If $S$ is a sequent and $\Phi[F]$ is any $S$-formula then we replace $\Phi[F]$ by $\Phi[p]$ and add a new formula $\Psi$ into antecedent of $S$. If $F$ is positive in $S$ then $\Psi=F\supset p$ and $\Psi=p\supset F$ otherwise, where $p$ is a new propositional variable.
We prove that a natural extension of this transformation to derivations is univalent, i.e. two derivations are equivalent (i.e. have the same normal form) if and only if the transformed ones are equivalent.
We call sequent $S$ the "$R$-sequent" if and only if the succedent of $S$ is a variable and antecedent formulas of $S$ are of the form $b$, $b\&c$, $b\supset c$, $(b\supset c)\supset d$, $(b\&c)\supset d$, $b\supset(c\&d)$ where $b,c,d$ – are variables.
By an iteration of transformation described above a sequent $S$ can be transformed into $R$-sequent $S$. This result permits us to restrict consideration to $R$-sequents in proofs of many theorems. By an iteration of transformation described above a sequent $S$ can be transformed into $R$-sequent $S'$.This result permits us to restrict consideration to $R$-sequents in proofs of many theorems. From the point of wiev of the category theory (cf. [1], [2]) our transformation is an univalent functor $\mathfrak{A}\colon\mathbb C\to\mathbb C$ where $\mathbb C$, is a free cartesian closed category.
Citation:
S. V. Solov'ev, “Preservation of the equivalence of proofs under reduction of the formula depth”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 197–208; J. Soviet Math., 20:4 (1982), 2370–2376
Linking options:
https://www.mathnet.ru/eng/znsl3114 https://www.mathnet.ru/eng/znsl/v88/p197
|
Statistics & downloads: |
Abstract page: | 138 | Full-text PDF : | 66 |
|