RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy MIAN:
Year:
Volume:
Issue:
Page:
Find






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


Tr. Mat. Inst. Steklova, 2003, Volume 242, Pages 77–97 (Mi tm406)  

This article is cited in 3 scientific papers (total in 3 papers)

Variants of Realizability for Propositional Formulas and the Logic of Weak Excluded Middle

N. K. Vereshchagina, D. P. Skvortsovb, E. Z. Skvortsovac, A. V. Chernovca

a M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b All-Russian Institute for Scientific and Technical Information of Russian Academy of Sciences
c M. V. Lomonosov Moscow State University

Abstract: It is unknown whether the logic of propositional formulas that are realizable in the sense of Kleene has a finite or recursive axiomatization. In this paper, another approach to the realizability of propositional formulas is studied. This approach is based on the following informal idea: a formula is realizable if it has a “simple” realization for each substitution. More precisely, logical connectives are interpreted as operations on the sets of natural numbers, and a formula is interpreted as a combined operation; if some sets are substituted for variables, then elements of the result are called realizations. A realization (a natural number) is simple if it has low Kolmogorov complexity, and a formula is called realizable if it has at least one simple realization whatever sets are substituted. Similar definitions can be formulated in arithmetic terms. A few “realizabilities” of this kind are considered, and it is proved that all of them give the same finitely axiomatizable logic, namely, the logic of weak excluded middle. The proof uses characterizations of superintuitionistic logics with an intuitionistic positive fragment that was obtained in 1960s by Medvedev and Yankov.

Full text: PDF file (338 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2003, 242, 67–85

Bibliographic databases:

UDC: 510.642+510.25+517.1
Received in December 2002

Citation: N. K. Vereshchagin, D. P. Skvortsov, E. Z. Skvortsova, A. V. Chernov, “Variants of Realizability for Propositional Formulas and the Logic of Weak Excluded Middle”, Mathematical logic and algebra, Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov, Tr. Mat. Inst. Steklova, 242, Nauka, MAIK Nauka/Inteperiodika, M., 2003, 77–97; Proc. Steklov Inst. Math., 242 (2003), 67–85

Citation in format AMSBIB
\Bibitem{VerSkvSkv03}
\by N.~K.~Vereshchagin, D.~P.~Skvortsov, E.~Z.~Skvortsova, A.~V.~Chernov
\paper Variants of Realizability for Propositional Formulas and the Logic of Weak Excluded Middle
\inbook Mathematical logic and algebra
\bookinfo Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov
\serial Tr. Mat. Inst. Steklova
\yr 2003
\vol 242
\pages 77--97
\publ Nauka, MAIK Nauka/Inteperiodika
\publaddr M.
\mathnet{http://mi.mathnet.ru/tm406}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2054486}
\zmath{https://zbmath.org/?q=an:1079.03016}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2003
\vol 242
\pages 67--85


Linking options:
  • http://mi.mathnet.ru/eng/tm406
  • http://mi.mathnet.ru/eng/tm/v242/p77

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Chernov, “Complexity of Sets Obtained as Values of Propositional Formulas”, Math. Notes, 75:1 (2004), 131–139  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    2. A. V. Chernov, “Finite problems and the logic of the weak law of excluded middle”, Math. Notes, 77:2 (2005), 263–272  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    3. Plisko V., “A Survey of Propositional Realizability Logic”, Bulletin of Symbolic Logic, 15:1 (2009), 1–42  crossref  mathscinet  zmath  isi  scopus
  •    . . .  Proceedings of the Steklov Institute of Mathematics
    Number of views:
    This page:307
    Full text:74
    References:21

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019