Warianty tytułu
Abstrakty
CONTENTS
0. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1. Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
2. On conservativity in L. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
3. A family of Kripke models. . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4. Finite credibility extent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5. The strong disjunction property and steady formulae. . . . . .33
6. $Σ_1$-ill theories of infinite credibility extent. . . . . . . . . . . . 41
7. $Σ_1$-sound theories. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
8. An application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57
9. A question of arithmetical complexity. . . . . . . . . . . . . . . . . . .59
10. Arbitrary subalgebras. $Σ_1$-ill theories. . . . . . . . . . . . . . 66
11. Arbitrary subalgebras. $Σ_1$-sound theories. . . . . . . . . . 74
References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
0. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1. Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
2. On conservativity in L. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13
3. A family of Kripke models. . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4. Finite credibility extent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5. The strong disjunction property and steady formulae. . . . . .33
6. $Σ_1$-ill theories of infinite credibility extent. . . . . . . . . . . . 41
7. $Σ_1$-sound theories. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
8. An application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57
9. A question of arithmetical complexity. . . . . . . . . . . . . . . . . . .59
10. Arbitrary subalgebras. $Σ_1$-ill theories. . . . . . . . . . . . . . 66
11. Arbitrary subalgebras. $Σ_1$-sound theories. . . . . . . . . . 74
References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
Słowa kluczowe
Tematy
Miejsce publikacji
Warszawa
Copyright
Seria
Rozprawy Matematyczne
tom/nr w serii:
323
Liczba stron
82
Liczba rozdzia³ów
Opis fizyczny
Dissertationes Mathematicae, Tom CCCXXIII
Daty
wydano
1993
otrzymano
1991-08-04
Twórcy
autor
- Steklov Mathematical Institute, Russian Academy of Sciences, Vavilova 42, 117966 Moscow, Russia
- Department of Mechanics and Mathematics, Moscow State University, 119899 Moscow, Russia
- Department of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands
Bibliografia
- [1] Z. Adamowicz, A recursion-theoretic characterization of instances of $BΣ_{n}$ provable in $Π_{n+1}(N)$, Fund. Math. 129 (1988), 231-236.
- [2] С. Н. Артёмов [S. N. Artemov], Арифметически полные модальные теории, в кн. Семиотика и информатика, вып. 14, ВИНИТИ, Москва 1979/80, 115-133 (English transl.: Arithmetically complete modal theories, Amer. Math. Soc. Transl. Ser. 2 135 (1987), 39-54).
- [3] С. Н. Артёмов [S. N. Artemov], О модальных логиках, аксиоматизирующих доказуемость, Изв. АН СССР, Сер. матем. 49 (1985), 1123-1154 (English transl.: On modal logics axiomatizing provability, Math. USSR-Izv. 27 (1986), 401-429).
- [4] С. Н. Артёмов [S. N. Artemov], О локальной табличности пропозициональных логик доказуемости (On local tabularity in propositional provability logics), в кн.: Логические методы построения эффективных алгоритмов, Калининский государственный университет, 1986, 9-13.
- [5] Л. Д. Беклемишев [L. D. Beklemishev], О классификации пропозициональных логик доказуемости (Classifying propositional provability logics), Изв. АН СССР, Сер. матем. 53 (1989), 915-943.
- [6] L. D. Beklemishev, For whom the doorbell rings or the provability logic with a constant for an infinitely credent $Π_1$ sentence over PA, manuscript, Moscow 1990.
- [7] F. Bellissima, On the modal logic corresponding to diagonalizable algebra theory, Boll. Un. Mat. Ital. B (5) 15 (1978), 915-930.
- [8] C. Bernardi, On the equational class of diagonalizable algebras ( the algebraization of the theories which express Theor; VI), Studia Logica 34 (1975), 321-331.
- [9] C. Bernardi and M. Mirolli, Hyperdiagonalizable algebras, Algebra Universalis 21 (1985), 89-102.
- [10] M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322-336.
- [11] G. Boolos, The Unprovability of Consistency. An essay in modal logic, Cambridge University Press, Cambridge 1979.
- [12] G. Boolos, Extremely undecidable sentences, J. Symbolic Logic 47 (1982), 191-196.
- [13] A. Carbone, Provable fixed points in $IΔ_0+Ω_1$, ITLI Prepublication Series ML-89-09, Institute for Language Logic and Information, University of Amsterdam, 1989.
- [14] A. Carbone and F. Montagna, Much shorter proofs: a bimodal investigation, Z. Math. Logik Grundlag. Math. 36 (1990), 47-66.
- [15] А. В. Чагров [A. V. Chagrov], Неразрешимые своиства расширений логики доказуемости (Undecidable properties of extensions of provability logic), Алгебра и логика 29 (1990), 350-367.
- [16] S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960), 35-92.
- [17] K. Fine, Logics containing K4. Part I, J. Symbolic Logic 34 (1974), 31-42.
- [18] K. Fine, Logics containing K4. Part II, ibid. 50 (1985), 619-651.
- [19] H. Friedman, The disjunction property implies the numerical existence property, Proc. Nat. Acad. Sci. U.S.A. 72 (1975), 2877-2878.
- [20] Z. Gleit and W. Goldfarb, Characters and fixed points in provability logic, Notre Dame J. Formal Logic 31 (1990), 26-36.
- [21] Р. Ш. Григолия [R. Sh. Grigolia], Свободные алгебры Магари с конечным числом образующих (Finitely generated free Magari algebras), в кн.: Логико-методологические исследования, Мецниереба, Tbilisi 1983, 135-149.
- [22] Р. Шh. Григолия [R. Sh. Grigolia], Свободные алгебры неклассических логик (Free Algebras of Non-Classical Logics), Мецниереба, Tbilisi 1987.
- [23] D. Guaspari, Partially conservative extensions of arithmetic, Trans. Amer. Math. Soc. 254 (1979), 47-68.
- [24] P. Hájek and A. Kuųera, On recursion theory in $ IΣ_1$, J. Symbolic Logic 54 (1989), 576-589.
- [25] D. Jensen and A. Ehrenfeucht, Some problem in elementary arithmetics, Fund. Math. 92 (1976), 223-245.
- [26] D. de Jongh and F. Montagna, Provable fixed points, Z. Math. Logik Grundlag. Math. 34 (1988), 229-250.
- [27] M. Jumelet, On Solovay's completeness theorem, ITLI Prepublication Series X-88-01, Institute for Language Logic and Information, University of Amsterdam, 1988.
- [28] A. Macintyre and H. Simmons, Gödel's diagonalization technique and related properties of theories, Colloq. Math. 28 (1973), 165-180.
- [29] R. Magari, The diagonalizable algebras ( the algebraization of the theories which express Theor.: II), Boll. Un. Mat. Ital. (4) 12 (1975) suppl. fasc. 3, 117-125.
- [30] R. Magari, Representation and duality theory for diagonalizable algebras ( the algebraization of theories which express Theor; IV), Studia Logica 34 (1975), 305-313.
- [31] Г. Е. Минц [G.E. Mints], Бескванторные и однокванторные системы в кн.: Исследования по конструктивной математике и математической логике. IV, Ю. В. Матиясевич и А. О. Слисенко (red.), Записки научных семинаров, t. 20, Наука, Ленинград 1971, 115-133 (English transl.: Quantifier-free and one-quantifier systems, J. Soviet Math. 1 (1973), 211-226).
- [32] F. Montagna, On the diagonalizable algebra of Peano arithmetic, Boll. Un. Mat. Ital. B (5) 16 (1979), 795-812.
- [33] F. Montagna, Iterated extensional Rosser's fixed points and hyperhyperdiagonalizable algebras, Z. Math. Logik Grundlag. Math. 33 (1987), 293-303.
- [34] F. Montagna, Shortening proofs in arithmetic by modal rules: polynomial shortenings and exponential shortenings, Rapporto Matematico N.129, Dipartimento di Matematica, Università di Siena, 1990.
- [35] F. Montagna and G. Sommaruga, Rosser and Mostowski sentences, Arch. Math. Logic 27 (1988), 115-133.
- [36] R. Parikh, Existence and feasibility in arithmetic, J. Symbolic Logic 36 (1971), 494-508.
- [37] J. B. Paris and L. A. S. Kirby, $Σ_n$-collection schemas in arithmetic, in: Logic Colloquium'77, A. Macintyre, L. Pacholski and J. Paris (eds.), North-Holland, Amsterdam 1978, 199-209.
- [38] M. B. Pour-El and S. Kripke, Deduction-preserving ``recursive isomorphisms" between theories, Fund. Math. 61 (1967), 141-163.
- [39] H. Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York 1967.
- [40] В. В. Рыбаков [V. V. Rybakov], О допустимости правил вывода в модальной системе G ( On admissibility of interference rules in the modal system G), в кн.: Математическая логика и алгоритмические проблемы, Ю. Л. Ершов (ред.), Труды Института Математики, т. 12, Наука, Новосибирск 1989, 120-138.
- [41] K. Segerberg, An Essay in Classical Modal Logic, Filosofiska Studier nr 13, Filosofiska Fóreningen och Filosofiska Institutionen vid Uppsala Universitet, Uppsala 1971.
- [42] V. Yu. Shavrukov, Subalgebras of diagonalizable algebras of theories containing arithmetic, ITLI Prepublication Series X-91-03, Institute for Language Logic and Information, University of Amsterdam, 1991.
- [43] H. Simmons, Large discrete parts of the E-tree, J. Symbolic Logic 53 (1988), 980-984.
- [44] T. J. Smiley, The logical basis of ethics, Acta Philos. Fenn. 16 (1963), 237-246.
- [45] C. Smoryński, Avoiding self-referential statements, Proc. Amer. Math. Soc. 70 (1978), 181-184.
- [46] C. Smoryński, Beth's theorem and self-referential sentences, in: Logic Colloquium'77, A. Macintyre, L. Pacholski and J. Paris (eds.), North-Holland, Amsterdam 1978, 253-261.
- [47] C. Smoryński, Calculating self-referential statements, Fund. Math. 109 (1980), 189-210.
- [48] C. Smoryński, Fifty years of self-reference in arithmetic, Notre Dame J. Formal Logic 22 (1981), 357-374.
- [49] C. Smoryński, Self-Reference and Modal Logic, Springer, New York 1985.
- [50] R. M. Solovay, Provability interpretations of modal logic, Israel J. Math. 25 (1976), 287-304.
- [51] A. Visser, Aspects of Diagonalization & Provability, dissertation, Utrecht 1981.
- [52] A. Visser, The provability logics of recursively enumerable theories extending Peano arithmetic at arbitrary theories extending Peano arithmetic, J. Philos. Logic 13 (1984), 97-113.
Języki publikacji
EN |
Uwagi
1991 Mathematics Subject Classification: Primary 03F40, 03G25; Secondary 03F30, 03B45.
Identyfikator YADDA
bwmeta1.element.zamlynska-88a718e0-555a-4089-a866-160bf5d44e12
Identyfikatory
ISBN
83-85116-75-3
ISSN
0012-3862
Kolekcja
DML-PL
