Complexity and (Un)decidability of Fragments of 〈ωωλ;×〉

• Autorzy: Bès Alexis , Choffrut Christian

Identyfikatory

DOI

10.3233/FI-2019-1752

• Języki publikacji: EN

Abstrakty

EN

We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential fragment of 〈ω^{ω λ}; ×,ω,ω+1,ω²+1〉 for every ordinal λ. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ∃*∀⁶-fragment of 〈ω^{ω λ}; ×〉 is undecidable for every ordinal λ.

Słowa kluczowe

EN

existential fragment; first-order logic; ordinal multiplication

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 1
• Strony: 1--15
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Bès Alexis

• Université Paris-Est, LACL (EA 4219), UPEC, Créteil, France

autor

Choffrut Christian

• IRIF, CNRS and Université Paris 7 Denis Diderot, France

Bibliografia

• [1] Bès A. Definability and decidability results related to the elementary theory of ordinal multiplication. In Fund.Math., 2002;171:197-211. URL https://hal.archives-ouvertes.fr/hal-00091581.
• [2] Büchi JR. Transfinite automata recursions and weak second order theory of ordinals, Logic Methodology Philos. Sci., Proc. 1964 Int. Congr. 3-23 (1965) pp. 767-770. doi:10.1007/978-1-4613-8928-6_24.
• [3] Cégielski P. Théorie élementaire de la multiplication des entiers naturels, Model Theory and Arithmetic, Proc., Paris 1979/80, Lect. Notes Math. 1981;890:44-89.
• [4] Choffrut C. Elementary Theory of Ordinals with Addition and Left Translation by omega, DLT 2001, Werner Kuich, Grzegorz Rozenberg and Arto Salomaa (Editors), LNCS vol. 2295, Vienna, Austria 2002, pp. 15-20. doi:10.1007/3-540-46011-X_2.
• [5] Church A. An unsolvable problem of elementary number theory, American journal of mathematics, 1936;58(2):345-363. URL http://links.jstor.org/sici?sici=0002-9327%28193604%2958%3A2%3C345%3AAUPOEN%3E2.0.CO%3B2-1.
• [6] Doner JE, Mostowski A, and Tarski A. The elementary theory of well-ordering - a metamathematical study, Proc.Logic colloquium ’77, Stud. Logic Found. Math. 1978;96:1-54. URL https://doi.org/10.1016/S0049-237X(08)71988-8.
• [7] Ehrenfeucht A. An application of games to the completeness problem for formalized theories, Fundamenta Math. 1961;49:129-141.
• [8] Hodgson BR. On direct products of automaton decidable theories, TCS 1982;19(3):331-335. URL https://doi.org/10.1016/0304-3975(82)90042-1.
• [9] Jacobsthal E. Über der Aufbau der transfiniter Arithmetik, Math. Ann. 1909;66:145-194.
• [10] Lechner A, Ouaknine J, and Worrell J. On the Complexity of Linear Arithmetic with Divisibility. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, 667-676, 2015. doi:10.1109/LICS.2015.67.
• [11] Lipshitz L. The Diophantine problem for addition and divisibility. Trans. Amer. Math. Soc., 1978;235: 271-283. doi:10.2307/1998219.
• [12] Makanin GS. ”The problem of solvability of equations in a free semigroup.” Sbornik: Mathematics 1977;32(2):129-198. URL http://stacks.iop.org/0025-5734/32/i=2/a=A01.
• [13] Matijasevič Y. Enumerable sets are Diophantine, Mathematical Logic In The 20th Century, 2003, pp. 269-273.
• [14] Maurin F. Ehrenfeucht games and ordinal addition, Ann. Pure Appl. Logic 1997;89(1):53-73. URL https://doi.org/10.1016/S0168-0072(97)00005-5.
• [15] Mostowski A. On direct products of theories, J. Symbolic Logic 1952;17(1):1-31. doi:10.2307/2267454.
• [16] Mostowski A, and Tarski A. Arithmetical classes and types of well-ordered systems, Bull.Amer.Math.Soc. 1949;55 p.65.
• [17] Rabin MO. Decidable theories, in: Handbook of mathematical logic (Barwise J., ed.), Studies in Logic and the Foundations of Mathematics Vol. 90, 1978 pp. 595-629. URL https://doi.org/10.1016/S0049-237X(08)71116-9.
• [18] Rosenstein JG. Linear Orderings. Academic Press, New York, 1982.
• [19] Sierpinski W. Cardinal and Ordinal Numbers, PSW Warsaw, 2nd edition, 1965.
• [20] Skolem T. Über gewisse Satzfunktionen in der Arithmetik, Skr. Norske Videnskaps-Akademie i Oslo, 7 (1930).

Uwagi

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