Truth in the limit

Marcin Mostowski


We consider sl-semantics in which first order sentences are interpreted in potentially infinite domains. A potentially innite domain is a growing sequence of infinite  models. We prove the completeness theorem for first order logic under this semantics. Additionally we characterize the logic of such domains as having a learnable, but not recursive, set of axioms. The work is a part of author's research devoted to computationally motivated foundations of mathematics

Słowa kluczowe: finite models, sl–semantics, completeness theorem, potential infinity, finite arithmetics

[1] Aristotle, Physics, circa 360 B.C. translated by R. P. Hardie and R. K. Gaye, available at: 

[2] B.Bolzano, Paradoxiendesunendlichen, 1851. AvailableatGoogleBooks,fragments translated into English in [4]. 

[3] Euclid, Elements, circa 300 B.C. Commented English translation [10], original text based on the edition by J. L. Heiberg (1883–1884), and English translation by Richard Fitzpatrick, 2008, is available at 

[4] W. B. Ewald, From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 volumes, Oxford University Press, 1996. 

[5] K. Gödel, Über die Vollständigkeit des Logikkalküls, Monatshefte für Mathematik und Physik 37 (1930), 349–360. English translation in [7]. 

[6] K. Gödel, Über formal unentscheidbare Sätze der principia mathematica und verwandter Systeme i, Monatshefte für Mathematik und Physik 38 (1931), 173–198. English translation in [7]. 

[7] K. Gödel, Collected works, volume 1, Oxford University Press, 1986.

[8] E. M. Gold, Limiting recursion, The Journal of Symbolic Logic 30 (1965), 28–48. 

[9] E.M.Gold, Languageidentificationinthelimit, Information and Control10(1967), 447–474. 

[10] T.L.Heath, ThirteenBooksofEuclid’sElements, volumes1–3, DoverPublications, 1956. second edition, originally published in Cambridge, by the University Press 1908. 

[11] L. Henkin, The completeness of the first-order functional calculus, The Journal of Symbolic Logic 14 (1949), 159–166. 

[12] D. Hilbert, Über das Unendliche, Mathematische Annalen 95 (1926), 161–190. English translation in [4]. 

[13] L. Kronecker, Über den Zahlbegriff, Journal für reine und angewandte Mathematik 101 (1887), 261–274. Fragments translated into English in [4]. 

[14] M. Krynicki, M. Mostowski, and K. Zdanowski, Finite arithmetics, Fundamenta Informaticae 81 (2007), 183–202. 

[15] M.Krynicki, J.Tomasik, andK.Zdanowski, Theoriesofinitialsegmentsofstandard models of arithmetics and their complete extensions, Theoretical Computer Science 412 (2011), 3975–3991. 

[16] M. Krynicki and K. Zdanowski, Theories of aritmetics in finite models, The Journal of Symbolic Logic 70 (2005), 1–28. 

[17] M. Mostowski, On representing concepts in finite models, Mathematical Logic Quarterly 47 (2001), 513–523. 

[18] M. Mostowski, On representing semantics in finite models, In A. Rojszczak, J. Cachro, and G. Kurczewski, editors, Philosophical dimensions of logic and science, pp. 15–28. Kluwer Academic Publishers, 2003. 

[19] M. Mostowski and A. Wasilewska, Arithmetic of divisibility in finite models, Mathematical Logic Quarterly 50 (2004), 169–174. 

[20] M.MostowskiandK.Zdanowski, FM–representabilityandbeyond, InS.B.Cooper, B. Löwe, and L. Torenvliet, editors, Computations in Europe, LNCS 3526, pp. 358– 367. Springer–Verlag, 2005. 

[21] J. Mycielski, Analysis without actual infinity, The Journal of Symbolic Logic 46 (1981), 625–633. 

[22] J. Mycielski, Locally finite theories, The Journal of Symbolic Logic 51 (1986), 59–62. 

[23] H. Putnam, Trial and error predicates and the solution to a problem of Mostowski, Journal of Symbolic Logic 30:1 (1965), 49–57.

[24] A. Tarski, Pojęcie prawdy w językach nauk dedukcyjnych, Nakładem Towarzystwa Naukowego Warszawskiego, 1933. English version in [25]. 

[25] A. Tarski, The concept of truth in formalized languages, In J. H. Woodger, editor, Logic, semantics, metamathematics, pp. 152–278. Oxford at The Clarendon Press, 1956. Translated from German version by J. H. Woodger.