nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

16. Models of Arithmetic and Independence Results

verfasst von : David Marker

Erschienen in: An Invitation to Mathematical Logic

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Paris–Harrington variant of Ramsey’s Theorem is proved independent of Peano Arithmetic by model theoretic methods. As a warm-up, we give model theoretic arguments bounding the growth rates of provably total computable functions in weak fragments of arithmetic. We conclude with a brief survey of some of the core results on models of arithmetic.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Peano Arithmetic and

In Exercise 8.46 we looked at even weaker theory where we only allow induction for quantifier-free formulas and showed that that theory is too weak to prove that $\sqrt {2}$ is irrational.

Parikh’s original proof was proof theoretic. This model theoretic argument seems to be folklore.

Indeed, we have not ruled out the possibility that there is a nonstandard $\mathcal {M}\models \mathrm {I}\Delta _0$ with $p\in M$ a nonstandard prime such that $\mathcal {M}/(p)$ is an algebraically closed field. If we weaken the axioms to allow only induction over quantifier-free formulas this is possible [61].

Semiregular cuts are an analog of regular cardinals in set theory.

p is an example of a definable type, i.e., for any formula $\phi (v,w)$ there is a formula $d\phi (w)$ such that $\phi (x,a)\in p$ if and only if $\mathcal {M}\models d\phi (a)$. Here the formula $d\phi (w)$ is

$$\displaystyle \begin{aligned} \exists u\forall v>u\ (v\in S_{i+1}\rightarrow \phi(v,w)),\end{aligned}$$

where $\phi =\phi _i$. Definable types play a major role in modern model theory but were first introduced in this context by Gaifman.

34.

Graham, R., Rothschild, B., Spencer, J.: Ramsey Theory. Wiley, New York (1980)

35.

Hájek, P., Pudlák, P.: Metamathematics of First-order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin (1993)

39.

Jockusch, C.: Ramsey’s theorem and recursion theory. J. Symbolic Logic 37, 268–280 (1972)MathSciNetCrossRef

41.

Kanamori, A., McAloon, K.: On Gödel incompleteness and finite combinatorics. Ann. Pure Appl. Logic 33, 23–41 (1987)MathSciNetCrossRef

44.

Katz, M., Reimann, J.: An Introduction to Ramsey Theory. Student Mathematical Library, 87. American Mathematical Society, Providence (2018)

45.

Kaye, R.: Models of Peano Arithmetic. Oxford Logic Guides, 15. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1991)

48.

Ketonen, J., Solovay, R.: Rapidly growing Ramsey functions. Ann. Math. (2) 113(2), 267–314 (1981)

51.

Kirby, L., Paris, J.: Initial segments of models of Peano’s axioms. In: Set Theory and Hierarchy Theory, pp. 211–226. Lecture Notes in Mathematics, vol. 619. Springer, Berlin (1977)

54.

Kossak, R., Schmerl, J.: The Structure of Models of Peano Arithmetic. Oxford Logic Guides, 50. Oxford Science Publications, The Clarendon Press, Oxford University Press, Oxford (2006)

61.

Macintyre, A., Marker, D.: Primes and their residue rings in models of open induction. Ann. Pure Appl. Logic 43(1), 57–77 (1989)MathSciNetCrossRef

63.

Marker, D.: Model Theory: An Introduction. Graduate Texts in Mathematics, 217. Springer, New York (2002)

75.

Parikh, R.: Existence and feasibility in arithmetic. J. Symbolic Logic 36, 494–508 (1971)MathSciNetCrossRef

76.

Paris, J., Harrington, L.: A mathematical incompleteness in Peano arithmetic. In: Handbook of Mathematical Logic, pp. 1133–1142. Studies in Logic and the Foundations of Mathematics, 90. North-Holland, Amsterdam (1977)

77.

Paris, J., Wilkie, A., Woods, A.: Provability of the pigeonhole principle and the existence of infinitely many primes. J. Symbolic Logic 53(4), 1235–1244 (1988)MathSciNetCrossRef

91.

Schwichtenberg, H., Wainer, S.: Proofs and Computations. Perspectives in Logic. Cambridge University Press, Cambridge; Association for Symbolic Logic, Chicago (2012)

Titel: Models of Arithmetic and Independence Results
verfasst von: David Marker
Verlag: Springer Nature Switzerland
Buch: An Invitation to Mathematical Logic
Print ISBN: 978-3-031-55367-7

Electronic ISBN: 978-3-031-55368-4

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-55368-4_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner