Finite Arithmetics

• Autorzy: Krynicki M. , Mostowski M. , Zdanowski K.
• Języki publikacji: EN

Abstrakty

EN

The paper presents the current state of knowledge in the field of logical investigations of finite arithmetics. This is an attempt to summarize the ideas and results in this area. Some new results are presented - these are mainly generalizations of the earlier results related to properties of sl-theories and some nontrivial cases of FM-representability theorem.

Słowa kluczowe

EN

finite model; arithmetic; finite arithmetic; interpretation; complete sets; FM-representability; truth definition

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 183--202
• Opis fizyczny: bibliogr. 37 poz.

Twórcy

autor

Krynicki M.

autor

Mostowski M.

autor

Zdanowski K.

• Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Warsaw, Poland,

Bibliografia

• [1] A. Atserias and Ph. Kolaitis. First order logic vs. fixed point logic on finite set theory. In 14th IEEE Symposium on Logic in Computer Science (LICS), volume 14, pages 275-284, 1999.
• [2] D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. Journal of Computer and System Science, 41:274-306, 1990.
• [3] J. L. Bell and A. B. Slomson. Models and ultraproducts. North Holland, 1971.
• [4] J. H. Bennett. On Spectra. PhD thesis, Princeton University, 1962.
• [5] A. Bes. A survey of arithmetical definability. In A tribute to Maurice Boffa, Special Issue of Belg. Math. Soc., pages 1-54, 2002.
• [6] W. Bés and D. Richard. Undecidable extensions of Skolem arithmetic. Journal of Symbolic Logic, 63(2):379-401, 1998.
• [7] A. Dawar, K. Doets, S. Lindell, and S. Weinstein. Elementary properties of the finite ranks. Mathematical Logic Quarterly, 44:349-353, 1998.
• [8] R. Fagin. Generalized first order spectra and polynomial-time recognizable sets. In SIAM - AMS Proceedings, volume 7, pages 43-73, 1974.
• [9] K. Gödel. Űber formal unentscheidbare Sätze der "PrincipiaMathematica" und verwandter Systeme. Monatshefte für Mathematik und Physik, 38:173-198, 1931.
• [10] E. M. Gold. Limiting recursion. The Journal of Symbolic Logic, 30:28-48, 1965.
• [11] E. M. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
• [12] C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12:576-583, 1969.
• [13] W. Hodges. Model theory. Encyclopedia of mathematics and its applications. Cambridge University Press, 1993.
• [14] L. Kołodziejczyk. A finite model-theoretical proof of a property of bounded query classes within ph. The Journal of Symbolic Logic, 69:1105-1116, 2004.
• [15] L. Kołodziejczyk. Truth definitions in finite models. The Journal of Symbolic Logic, 69:183-200, 2004.
• [16] L. A. Kołodziejczyk. Truth definitions and higher order logics in finite models. PhD thesis, Warsaw University, 2005.
• [17] M. Krynicki, J. Tomasik, and K. Zdanowski. Theory of initial segments of standard models of arithmetics and their complete extensions. in manuscript, 2005.
• [18] M. Krynicki and K. Zdanowski. Theories of arithmetics in finite models. Journal of Symbolic Logic, 70(1):1-28, 2005.
• [19] T. Lee. Arithmetical definability over finite structures. Mathematical Logic Quarterly, 49:385-393, 2003.
• [20] M. Mostowski. Truth-definitions in finite models. in manuscript, 1993.
• [21] M.Mostowski. On representing concepts in finite models. Mathematical Logic Quarterly, 47:513-523, 2001.
• [22] M. Mostowski. On representing semantics in finite models. In A. Rojszczak†, J. Cachro, and G. Kurczewski, editors, Philosophical Dimensions of Logic and Science, pages 15-28. Kluwer Academic Publishers, 2003.
• [23] M. Mostowski. On representability in finite arithmetics, 2007. in manuscript.
• [24] M.Mostowski and A.Wasilewska. Arithmetic of divisibility in finite models. Mathematical Logic Quarterly, 50(2):169-174, 2004.
• [25] M. Mostowski and K. Zdanowski. Coprimality in finite models. In Luke Ong, editor, Computer Science Logic: 19th International Workshop, CSL 2005, volume 3634 of Lecture Notes in Computer Science, pages 263-275. Springer, 2005.
• [26] M. Mostowski and K. Zdanowski. FM-representability and beyond. In B. Cooper, B. Loewe, and L. Torenvliet, editors, Proceedings of the conference Computability in Europe, volume 3526 of Lecture Notes in Computer Science, pages 358-367. Springer, 2005.
• [27] J. Mycielski. Analysis without actual infinity. Journal of Symbolic Logic, 46:625-633, 1981.
• [28] J. Paris and C. Dimitracopoulos. Truth definitions for_0 formulae. In Logic and algorithmic, L'enseignement Mathematique No 30, Geneve, 1982.
• [29] W. Quine. Concatenation as a basis for arithmetic. Journal of Symbolic Logic, 11:105-114, 1946.
• [30] N. Schweikardt. On the Expressive Power of First-Order Logic with Built-In Predicates. PhD thesis, Johannes Gutenberg-UniversitätMainz, 2001.
• [31] N. Schweikardt. Arithmetic, first-order logic, and counting quantifiers. ACM Transactions on Computational Logic (ACM ToCL), 6(3):634-671, 2005.
• [32] J. R. Shoenfield. Recursion Theory. Lectures Notes in Logic. Springer-Verlag, 1993.
• [33] L. W. Szczerba. Interpretability of elementary theories. In Butts and Hintikka, editors, Proceedings 15th ICALP 88, Logic, foundations of mathematics and computability theory, pages 129-145. Reidel Publishing, 1977.
• [34] A. Tarski. Pojęcie prawdy w językach nauk dedukcyjnych. Nakładem Towarzystwa Naukowego Warszawskiego, 1933. English version in [35].
• [35] A. Tarski. The concept of truth in formalized languages. In J. H. Woodger, editor, Logic, semantics, metamathematics, pages 152 - 278. Oxford at The Clarendon Press, 1956. translated from German by J. H. Woodger.
• [36] C. Wrathall. Rudimentary predicates and relative computation. SIAM Journal on Computing, 7:194-209, 1978.
• [37] K. Zdanowski. Arithmetics in finite but potentially ifinite worlds. PhD thesis, Warsaw University, 2005.