Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-19T06:48:27.705Z Has data issue: false hasContentIssue false
  • English
  • Français

Theories of arithmetics in finite models

Published online by Cambridge University Press:  12 March 2014

Michał Krynicki  and
Konrad Zdanowski
Michał Krynicki
Affiliation:
Cardinal Stefan Wyszyński University, Warszawa, Poland, E-mail: [email protected]
Konrad Zdanowski
Affiliation:
Institute of Mathematics, Polish Academy of Science Śniadeckich 8, 00–956 Warszawa, Poland, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ2–theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ1–theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation.

We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.

Keywords

Finite modelsarithmeticdefinabilityspectrumcomplexity
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 1 , March 2005 , pp. 1 - 28
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Atserias, A. and Kolaitis, Ph., First order logic vs. fixed point logic on finite set theory, 14th IEEE Symposium on Logic in Computer Science (LICS), vol. 14, 1999, pp. 275–284.Google Scholar
[2]Barrington, D. A. Mix, Immerman, N., and Straubing, H., On uniformity within NC1, Journal of Computer and System Science, vol. 41 (1990), pp. 274–306.CrossRefGoogle Scholar
[3]Bennett, J. H., On spectra, Ph.D. thesis, Princeton University, 1962.Google Scholar
[4]Bés, W., On Pascal triangles modulo a prime power, Annals of Pure and Applied Logic, vol. 89 (1997), pp. 17–35.CrossRefGoogle Scholar
[5]Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[6]Davis, M., Hubert's tenth problem is unsolvable, American Mathematical Monthly, vol. 80 (1973), pp. 233–269.CrossRefGoogle Scholar
[7]Dawar, A., Doets, K., Lindell, S., and Weinstein, S., Elementary properties of the finite ranks, Mathematical Journal Quarterly, vol. 44 (1998), pp. 349–353.Google Scholar
[8]Ebbinghaus, H.-D., Flum, J., and Thomas, W., Mathematical logic, second ed., Springer-Verlag, 1994.CrossRefGoogle Scholar
[9]Hájek, P. and Pudlák, P., Metamathematics of first-order arithmetic, Springer-Verlag, 1993.CrossRefGoogle Scholar
[10]Kołodziejczyk, L. A., private communication.Google Scholar
[11]Korec, I., Elementary theories of structures containing generalized Pascal triangles modulo a prime, Proceedings of the 5th Conference on Discrete Mathematics and Applications, Blagoevrad (Shtrakov, S. and Marchev, I., editors), 1995, pp. 91–105.Google Scholar
[12]Lee, T., Arithmetical definability over finite structures, Mathematical Logic Quarterly, vol. 49 (2003), pp. 385–393.CrossRefGoogle Scholar
[13]Mostowski, M., On representing concepts in finite models, Mathematical Logic Quarterly, vol. 47 (2001), pp. 513–523.3.0.CO;2-J>CrossRefGoogle Scholar
[14]Mostowski, M., On representing semantics in finite models, Philosophical Dimensions of Logic and Science (Rojszczak, A.†, Cachro, J., and Kurczewski, G., editors), Kluwer Academic Publishers, 2003, pp. 15–28.CrossRefGoogle Scholar
[15]Mostowski, M. and Wasilewska, A., Elementary properties of divisibility infinite models, Mathematical Logic Quarterly, vol. 50 (2004), pp. 169–174.CrossRefGoogle Scholar
[16]Mostowski, M. and Zdanowski, K., FM-representability and beyond, in preparation.Google Scholar
[17]Mycielski, J., Analysis without actual infinity, this Journal, vol. 46 (1981), pp. 625–633.Google Scholar
[18]Mycielski, J., Locally finite theories, this Journal, vol. 51 (1986), pp. 59–62.Google Scholar
[19]Nathanson, M. B., Elementary methods in number theory. Springer, 2000.Google Scholar
[20]Quine, W., Concatenation as a basis for arithmetic, this Journal, vol. 11 (1946), pp. 105–114.Google Scholar
[21]Schweikardt, N., On the expressive power of first-order logic with built-in predicates, Ph.D. thesis, Johannes Gutenberg-Universität, Mainz, 2001.Google Scholar
[22]Semenov, A. L., Logical theories of one-place functions on the set of natural numbers, Izv. Akad. Nauk SSSR ser. Mat., vol. 47 (1983), pp. 623–658.Google Scholar
[23]Shoenfield, J. R., Recursion theory, Lecture Notes in Logic, Springer-Verlag, 1993.CrossRefGoogle Scholar
[24]Smoryński, C., Logical number theory I, Springer, 1981.Google Scholar
[25]Zdanowski, K., Arithmetic in finite but potentially infinite worlds, Ph.D. thesis, Warsaw University, 2004.Google Scholar