|
Zapiski Nauchnykh Seminarov LOMI, 1979, Volume 88, Pages 137–162
(Mi znsl3109)
|
|
|
|
This article is cited in 31 scientific papers (total in 31 papers)
Lower bounds for lengthening of proofs after cut-elimination
V. P. Orevkov
Abstract:
Let $C_k^*$ be the formula
\begin{align}
\forall b_0((\forall w_0\exists v_0 P(w_0,b_0,v_0)
&\&\forall uvw(\exists y(P(y,b_0,u)\&\exists z(P(v,y,z)\notag\\
&\& P(z,y,w)))\supset P(v,u,w)))\supset\exists v_k(P(b_0,b_0,v_k)\notag\\
&\&\exists v_{k+1}(P(b_0,v_k,V_{k-1})\&\dots\exists v_0 P(b_0,v_1,v_0)\dots))).\notag
\end{align}
and let $LK$ be the Gentzen system for classical predicate calculus. Given a sequent calculus $\mathfrak P$ let $\mathfrak P\vdash_nS$ mean that $S$ has a proof in $\mathfrak P$ of at most $n$, sequent occurrences.
The main aim of the paper is to show that
(a) there is a linear function $l$ such that $LK\vdash_{l(k)}C_k^*$,
(b) there is no Kalmar elementary function $f$ with $(LK-\operatorname{cut})\vdash_{f(k)}C_k^*$.
In particular $LK\vdash_{253}C_6^*$ but $\rceil C_6^*$ does not have a refutation in resolution method with less than $10^{19200}$ clauses.
Citation:
V. P. Orevkov, “Lower bounds for lengthening of proofs after cut-elimination”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 137–162; J. Soviet Math., 20:4 (1982), 2337–2350
Linking options:
https://www.mathnet.ru/eng/znsl3109 https://www.mathnet.ru/eng/znsl/v88/p137
|
Statistics & downloads: |
Abstract page: | 279 | Full-text PDF : | 103 |
|