A Modal Logic of a Truth Definition for Finite Models

• Autorzy: Czarnecki Marek , Zdanowski Konrad

Identyfikatory

DOI

10.3233/FI-2019-1770

• Języki publikacji: EN

Abstrakty

EN

The property of being true in almost all finite, initial segments of the standard model of arithmetic is ∑⁰₂ –complete. Thus, it admits a kind of a truth definition. We define such an arithmetical predicate. Then, we define its modal logic SL and prove a completeness theorem with respect to finite models semantics. The proof that SL is the modal logic of the approximate truth definition for finite arithmetical models is based on an extension of SL by a fixed-point construction.

Słowa kluczowe

EN

finite models; modal logic; truth definition

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 4
• Strony: 299--325
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Czarnecki Marek

• Institute of Philosophy, University of Warsaw, Krakowskie Przedmieście 3, 00-047 Warsaw, Poland

autor

Zdanowski Konrad

• Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszynski University, Wóycickiego 1/3, 01-938 Warszawa, Poland

Bibliografia

• [1] Immerman N. Descriptive Complexity. Springer; 1999. URL http://dx.doi.org/10.1007/978-1-4612-0539-5.
• [2] Mostowski M, Zdanowski K. FM-representability and beyond. In: Cooper SB, Löwe B, Torenvliet L, editors. New Computational Paradigms. First Conference on Computability in Europe. Springer; 2005. p.29-47. URL http://dx.doi.org/10.1007/11494645_45.
• [3] Mostowski M. On representing concepts in finite models. Mathematical Logic Quarterly. 2001;47:513-523. URL http://dx.doi.org/10.1002/1521-3870(200111)47:4<513::AID-MALQ513>3.0.CO;2-J.
• [4] Segerberg K. On the Logic of “To-morrow”. Theoria. 1967;33(1):45-52. URL http://dx.doi.org/10.1111/j.1755-2567.1967.tb00609.x. doi:10.1111/j.1755-2567.1967.tb00609.x.
• [5] Segerberg K. Modal logics with functional alternative relations. Notre Dame J Formal Logic. 1986; 27(4):504-522. URL http://dx.doi.org/10.1305/ndjfl/1093636763. doi:10.1305/ndjfl/1093636763.
• [6] Lemmon EJ. An Introduction to Modal Logic: The Lemmon Notes. B. Blackwell; 1977.
• [7] Visser A. On the completenes principle: A study of provability in heyting’s arithmetic and extensions. Annals of Mathematical Logic. 1982;22(3):263-295. URL http://www.sciencedirect.com/science/article/pii/0003484382900249. doi:https://doi.org/10.1016/0003-4843(82)90024-9.
• [8] Visser A. Substitutions of Σ01 -sentences: explorations between intuitionistic propositional logic and intuitionistic arithmetic. Annals of Pure and Applied Logic. 2002;114(1-3):227-271. URL https://doi.org/10.1016/S0168-0072(01)00081-1. doi:10.1016/S0168-0072(01)00081-1.
• [9] Litak T, Visser A. Lewis meets Brouwer: Constructive strict implication. Indagationes Mathematicæ. 2018;29(1):36-90. Special Issue: L.E.J. Brouwer, fifty years later. URL http://www.sciencedirect.com/science/article/pii/S0019357717301167. doi:https://doi.org/10.1016/j.indag.2017.10.003.
• [10] Boolos G. The logic of Provability. Cambridge University Press; 1993.
• [11] Franzén T. Inexhaustibility. A Non-Exhaustive Treatment. vol. 16 of Lecture Notes in Logic. A K Peters, Ltd., Wellesley; 2004.
• [12] Ebbinghaus HD, Flum J, Thomas W. Mathematical Logic. Undergraduate Texts in Mathematics. Springer New York; 1996.
• [13] Shoenfield JR. Recursion Theory. Lectures Notes in Logic. Springer-Verlag; 1993.
• [14] Hájek P. On a new notion of partial conservativity. In: Börger E, Oberschelp W, Richter MM, Schinzel B, Thomas W, editors. Computation and Proof Theory: Proceedings of the Logic Colloquium held in Aachen, July 18-23, 1983 Part II. Berlin, Heidelberg: Springer Berlin Heidelberg; 1984. p. 217-232. URL http://dx.doi.org/10.1007/BFb0099487. doi:10.1007/BFb0099487.
• [15] Solovay RM. Provability interpretations of modal logic. Israel Journal of Mathematics. 1976;25(3):287-304. URL http://dx.doi.org/10.1007/BF02757006. doi:10.1007/BF02757006.
• [16] Smoryński C. Self-Reference and Modal Logic. Universitext. Springer New York; 1985. URL http://dx.doi.org/10.1007/978-1-4613-8601-8.
• [17] Hájek P, Pudlák P. Metamathematics of First-Order Arithmetic. Springer-Verlag; 1993. URL http://projecteuclid.org/euclid.pl/1235421926.
• [18] Feferman S. Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae. 1960;49:35-92.
• [19] Visser A. Peano’s smart children: a provability logical study of systems with built-in consistency. Notre Dame J Formal Logic. 1989 03;30(2):161-196. URL http://dx.doi.org/10.1305/ndjfl/1093635077. doi:10.1305/ndjfl/1093635077.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).