nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

5. Compactness and Complete Theories

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 Compactness theorem and some of its consequences are studied. The Upward Löwenheim–Skolem is proved and used to deduce Vaught’s result on the completeness of categorical theories. We show that the full theory of the field of complex numbers is axiomatized as the theory of algebraically closed fields of characteristic zero and give several consequences. Countable categoricity allows us to study dense linear orders and random graphs.

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 Gödel’s Completeness Theorem

Nächstes Kapitel Ultraproducts

In [63] 2.1 I give a Henkin style argument proving the Compactness Theorem directly without appealing to the Completeness Theorem. In Chap. 6 we will give another proof of the Compactness Theorem using ultraproducts.

The first proof of the existence of a nonstandard model was given by Skolem [94] using something like the ideas of Chap. 6 (see Exercise 6.32) and building an ultraproduct using an ultrafilter on the definable sets. Interestingly, Gödel [30], in his review of Skolem’s paper, pointed out that the existence of a nonstandard model of Peano Arithmetic also followed from his Incompleteness Theorem but did not note that it follows also from compactness. It took Malcev to unleash the full power of compactness.

For example, the Four Color Theorem says that every finite planar graph can be four colored.

Of course “completeness” has a different meaning in Chap. 4 and, ideally, we would chosen a different adjective for “complete theories” but, for better or worse, this is the standard terminology in the subject.

If \(\mathcal {L}\) is finite and \(\mathcal {M}\) is a finite \(\mathcal {L}\)-structure, then it is possible to find a sentence \(\phi \) such that \(\mathcal {N}\models \phi \) if and only if \(\mathcal {N}\cong \mathcal {M}\). See Exercise 5.31.

This is still true when we consider the ordered additive groups \(({\mathbb R},+,<)\) and \(({\mathbb Q},+,<)\). We will discuss this in Chap. 7.

We do not need \(\mathcal {L}\)-finite, it would be enough to have an algorithm to decide if a string of symbols is formula of \(\mathcal {L}\).

This method of proving a theory is decidable ends up with highly impractical algorithms. For most of the theories we are proving decidable there are much better explicit algorithms. However, even in the simplest cases, these computations are unfeasible and these were some of the first problems that computer scientists could show were provably hard. For example Fischer and Rabin [23] proved that the decision problem for DAG is exponentially hard.

We will study the theory of the real numbers in Chap. 8.

So far we have given examples of theories that are \(\kappa \)-categorical for all infinite \(\kappa \) (the theory of an infinite set), categorical only in \(\aleph _0\) (DLO) and categorical for all \(\kappa >\aleph _1\). There are also many theories such as Peano Arithmetic or the theory of the real field that are not \(\kappa \)-categorical for any \(\kappa \). For example, in Exercise 7.42 we show that there are \(2^\kappa \) non-isomorphic ordered divisible abelian groups of cardinality \(\kappa \) for each infinite cardinal \(\kappa \). In a result that was the beginning of modern model theory Morley [71] showed that these are the only possible patterns. If T is a complete theory in a countable language, then T is \(\kappa \)-categorical for some uncountable cardinal \(\kappa \) if and only if T is \(\kappa \)-categorical for every uncountable cardinal \(\kappa \). For a proof see [63] Chapter 6.

These are sometimes called the Alice’s Restaurant axioms because you can get anything you want.

Vaught showed that if T is a complete theory in a countable language, then the number of non-isomorphic countable models is not exactly 2 (see [63] Theorem 4.4.6).

Ax, J.: The elementary theory of finite fields. Ann. Math. (2) 88, 239–271 (1968)

Bollobás, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge (2001)

Borel, A.: Injective endomorphisms of algebraic varieties, Arch. Math. 20, 531-537 (1969)MathSciNetCrossRef

23.

Fischer, M., Rabin, M.: Super-exponential complexity of Presburger arithmetic. In: Complexity of computation (Proc. SIAM-AMS Sympos., New York, 1973), pp. 27–41. SIAM-AMS Proc., Vol. VII. American Mathematical Society, Providence (1974)

24.

Fagin, R.: Probabilities on finite models. J. Symbolic Logic 41(1), 50–58 (1976)MathSciNetCrossRef

30.

Gödel, K.: Review of Skolem [Skloem, T.: Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems. Norsk Matematisk forenings skrifter 10, 73–82 (1933)]. Zentralblatt für Mathematik und ihre Grenzgebiete 7, 193–194 (1933)

42.

Kang, M.C.: Injective morphisms of affine varieties. Proc. Am. Math. Soc. 119(1), 1–4 (1993)MathSciNetCrossRef

58.

Lang, S.: Algebra. Addison-Wesley, Reading (1971)

63.

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

71.

Morley, M.: Categoricity in power. Trans. Am. Math. Soc. 114, 514–538 (1965)MathSciNetCrossRef

84.

Rudin, W.: Injective polynomial maps are automorphisms. Am. Math. Mon. 102, 540–543 (1995)MathSciNetCrossRef

87.

Serre, J.-P., How to use finite fields for problems concerning infinite fields. In: Arithmetic, Geometry, Cryptography and Coding Theory, pp. 183–193. Contemporary Mathematics, 487. American Mathematical Society, Providence (2009)

94.

Skloem, T.: Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems. Norsk Matematisk forenings skrifter 10, 73–82 (1933)

96.

Spencer, J.: The Strange Logic of Random Graphs. Algorithms and Combinatorics, 22. Springer, Berlin (2001)

97.

Tarski, A.: Sur les ensembles définissables de nombres réels. Fundamenta Mathematicae 17(1), 210–239 (1931)CrossRef

99.

Tarski, A.: A decision method for elementary algebra and geometry. The Rand Corporation, Santa Monica (1948)

Titel: Compactness and Complete Theories
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_5

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