Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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.
English version:
Journal of Soviet Mathematics, 1982, Volume 20, Issue 4, Pages 2337–2350
DOI: https://doi.org/10.1007/BF01629444
Bibliographic databases:
UDC: 510.66
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Ore79}
\by V.~P.~Orevkov
\paper Lower bounds for lengthening of proofs after cut-elimination
\inbook Studies in constructive mathematics and mathematical logic. Part~VIII
\serial Zap. Nauchn. Sem. LOMI
\yr 1979
\vol 88
\pages 137--162
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl3109}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=556226}
\zmath{https://zbmath.org/?q=an:0429.03033|0492.03023}
\transl
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2337--2350
\crossref{https://doi.org/10.1007/BF01629444}
Linking options:
  • https://www.mathnet.ru/eng/znsl3109
  • https://www.mathnet.ru/eng/znsl/v88/p137
  • This publication is cited in the following 31 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:279
    Full-text PDF :103
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024