Subalgebras of diagonalizable algebras of theories containing arithmetic

Shavrukov, Vladimir Yu.

Książka - szczegóły

Tytuł książki

Subalgebras of diagonalizable algebras of theories containing arithmetic

Autorzy

Vladimir Yu. Shavrukov

Seria

Rozprawy Matematyczne tom/nr w serii: 323 wydano: 1993

Zawartość

Pełne teksty:

http://matwbn.icm.edu.pl/ksiazki/rm/rm323/rm32301.pdf [zdalny]

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

Słowa kluczowe

Tematy

Kategoryzacja MSC:

Wydawca

Instytut Matematyczny Polskiej Akademii Nauk

Miejsce publikacji

Warszawa

Seria

Rozprawy Matematyczne tom/nr w serii: 323

Liczba stron

Liczba rozdzia³ów

Opis fizyczny

Dissertationes Mathematicae, Tom CCCXXIII

Daty

wydano

1993

otrzymano

1991-08-04

Twórcy

autor

Vladimir Yu. Shavrukov

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

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

Zawartość książki

rozwiń roczniki