Variants of Realizability for Propositional Formulas and the Logic of the Weak Law of Excluded Middleстатья

Дата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.

Работа с статьей

[1] Variants of realizability for propositional formulas and the logic of the weak law of excluded middle / A. V. Chernov, D. P. Skvortsov, E. Z. Skvortsova, N. K. Vereshchagin // Computer Science Logic, 16th International Workshop, CSL 2002, 11th Annual Conference of the EACSL, Edinburgh, Scotland, UK, September 22-25, 2002, Proceedings. — Vol. 2471 of Lecture Notes in Computer Science. — Springer, 2002. — P. 74–88. 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 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 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 may be formulated in arithmetical 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 the weak law of excluded middle. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть