RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1979 Volume 88, Pages 137–162 (Mi znsl3109)

This article is cited 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.

UDC: 510.66


 English version:
Journal of Soviet Mathematics, 1982, 20:4, 2337–2350

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025