Categoricity

Categoricity is a term from model theory , a branch of mathematical logic . A theory is called categorically in a certain infinite power if it essentially has only one model of this power. The term "categorical" comes from Oswald Veblen , who borrowed it from Kant .

Definitions

To make it more precise, we understand a theory to be a set of sentences, that is, statements without free variables , a language of first-order predicate logic that is closed under the inference relation ; that means for every sentence it follows from already . If , then the set of all propositions which can be derived from is an example of a theory. ${\displaystyle T}$ ${\displaystyle L_{I}^{S}}$ ${\displaystyle \vDash }$ ${\displaystyle \varphi }$ ${\displaystyle T\vDash \varphi }$ ${\displaystyle \varphi \in T}$ ${\displaystyle \Phi \subset L_{I}^{S}}$ ${\displaystyle \Phi ^{\vDash }:=\{\varphi \in L_{I}^{S};\,\varphi {\mbox{ Satz}},\Phi \vDash \varphi \}}$ ${\displaystyle \Phi }$

If one has a theory with infinite models, then, according to the Löwenheim-Skolem theorem , there are also models of arbitrary infinite power; in particular, not every two models are necessarily isomorphic. However, it could happen that the theory has exactly one model of power for a given infinite cardinal number up to isomorphism . Then the theory is called -categorical. ${\displaystyle T}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$

Morley's theorem

→ Main article : Morley's theorem (model theory)

An important result is the following sentence, which goes back to Michael D. Morley :

• If a countable theory is -categorical for an uncountable , then it is -categorical for every uncountable . ${\displaystyle T}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$

There are therefore only four possibilities for a countable theory in terms of categoricity. In fact, these all occur, as demonstrated by the examples below.

Ryll-Nardzewski theorem

The omega-categorical theory characterizes -kategorische theories. He says that countable theories are -categorical if and only if the set of types over any finite sets is finite. ${\displaystyle \aleph _{0}}$ ${\displaystyle \aleph _{0}}$

Vaught criterion

An important application of the term presented here is the Vaught criterion (also: Łoś – Vaught test), which is a sufficient but not necessary condition for the completeness of a theory.

• If a countable theory without finite models that is -categorical for a cardinal number , then this theory is complete. ${\displaystyle T\varsubsetneq L_{I}^{S}}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$
• In a more general form it reads: If a theory without finite models, which is -categorical for a cardinal number that is at least as large as the thickness of the signature, then this theory is complete. ${\displaystyle T\varsubsetneq L_{I}^{S}}$ ${\displaystyle \kappa }$

Both statements are corollaries to the Löwenheim-Skolem theorem.

As an important application example, we get the completeness of the theory of the algebraically closed fields of the characteristic 0 or . ${\displaystyle p}$

Examples

ℵ ₀ -categorical and ℵ ₁ -categorical: tautologies

A very simple example is the set of all tautologies of language , that is, the set of all sentences that do not require any further preconditions. The models for power are nothing more than the quantities of power and the isomorphisms are precisely the bijective mappings. Therefore, two models of the same thickness are isomorphic, that is, the theory of tautologies is -categorical. ${\displaystyle L_{I}=L_{I}^{\emptyset }}$ ${\displaystyle \emptyset ^{\vDash }}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$

ℵ ₀ -categorical and not ℵ ₁ -categorical: Dense orders

The theory of the dense linear order without extrema consists of all statements of the language that are valid in. One can show that two countable models are isomorphic. However, it is not isomorphic to (with the lexicographical order ), since in the latter model there is not always an uncountable number of points between two points. The theory is therefore -categorical, but not categorical in uncountable cardinal numbers. ${\displaystyle L_{I}^{\{<\}}}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} \times \mathbb {Q} }$ ${\displaystyle \aleph _{0}}$

Not ℵ ₀ -categorical and ℵ ₁ -categorical

Algebraically closed bodies

The theory of the algebraically closed bodies can be described in the language by a set of axioms which, in addition to the usual body axioms, also the infinite series of axioms ${\displaystyle L_{I}^{\{0,1,+,\cdot \}}}$ ${\displaystyle \Phi }$

${\displaystyle \forall y_{0}\,y_{1}\ldots y_{n-1}\,\exists x\,(x^{n}+y_{n-1}\cdot x^{n-1}+\ldots +y_{1}\cdot x+y_{0}\equiv 0)}$

for each , which obviously means in terms of content that each polynomial has a zero. This is an abbreviated notation for the k-fold product ; note that exponentiation does not belong to the language chosen here. Then is the theory of algebraically closed fields. Furthermore, let the theorem (p times the sum of 1, p prime ). Then axiomatize the theory of algebraically closed fields of characteristic and the theory of algebraically closed fields of characteristic 0. ${\displaystyle n>0}$ ${\displaystyle x^{k}}$ ${\displaystyle x\cdot \ldots \cdot x}$ ${\displaystyle \Phi ^{\vDash }}$ ${\displaystyle \varphi _{p}}$ ${\displaystyle 1+\ldots +1\equiv 0}$ ${\displaystyle \Phi _{p}:=\Phi \cup \{\varphi _{p}\}}$ ${\displaystyle p}$ ${\displaystyle \Phi _{0}:=\Phi \cup \{\neg \varphi _{p};\,p{\mbox{ Primzahl}}\}}$

A model of these theories is determined by the power of a transcendence basis down to isomorphism. For a model of power (with ) the power of a transcendence base must already be, for a countable model the power of the transcendence base can be any finite number or countably infinite. The theories and are therefore -categorical, but not -categorical. ${\displaystyle \kappa }$ ${\displaystyle \kappa >\aleph _{0}}$ ${\displaystyle \kappa }$ ${\displaystyle \Phi _{0}^{\vDash }}$ ${\displaystyle \Phi _{p}^{\vDash }}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{0}}$

Q vector spaces

${\displaystyle \mathbb {Q} }$- Vector spaces can be described in the first-level predicate logic by the signature , where 0 is a constant symbol ( zero vector ), + a two-digit function symbol ( vector addition ) and each is a single-digit function symbol ( scalar multiplication with ). It is clear that with these symbols one can write down the axioms for -vector spaces. Note, however, that you cannot quantify over all scalar multiplications ; you have to work with infinite sequences of axioms instead, for example ${\displaystyle S=\{\mathbf {0} ,+,\mathbb {Q} \}}$ ${\displaystyle r\in \mathbb {Q} }$ ${\displaystyle r}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle r\in \mathbb {Q} }$

${\displaystyle \forall x\,y\,(r+x\,y\equiv +\,rx\,ry)}$

for each function symbol , what is more suggestive of course than ${\displaystyle r}$

${\displaystyle \forall x\,y\,(r(x+y)=rx+ry)}$

writes. This gives the theory , where the set of all the above axioms is the vector spaces. ${\displaystyle T_{\mathbb {Q} V}=\Phi ^{\vDash }}$ ${\displaystyle \Phi }$ ${\displaystyle \mathbb {Q} }$

For natural numbers are and two non-isomorphic models of the same thickness , the theory is therefore not -kategorisch. but is -categorical for every cardinal number , because one can show that bases of -vector spaces of cardinality also have this cardinality and the isomorphism classes of vector spaces are uniquely determined by the cardinality of the basis. ${\displaystyle 0<n<m}$ ${\displaystyle \mathbb {Q} ^{n}}$ ${\displaystyle \mathbb {Q} ^{m}}$ ${\displaystyle T_{\mathbb {Q} V}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle T_{\mathbb {Q} V}}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa >\aleph _{0}}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle \kappa >\aleph _{0}}$

Not ℵ ₀ -categorical and not ℵ ₁ -categorical: Discrete orders

A theory that has no finite models and is incomplete is not categorical in any cardinal number according to Vaught's criterion (see below). A complete theory that is not categorical in any cardinal number is the theory of discrete order with no extrema. It consists of all statements of the language that apply in. ${\displaystyle L_{I}^{\{<\}}}$ ${\displaystyle \mathbb {Z} }$

${\displaystyle \mathbb {Z} \times \mathbb {Z} }$and are two non-isomorphic countable models. and are two non-isomorphic models of power . (Each with the lexicographical order, is a well-ordered ordinal number .) ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {R} \times \mathbb {Z} }$ ${\displaystyle 2^{\omega }\times \mathbb {Z} }$ ${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle 2^{\omega }}$

An incomplete but categorical theory with no finite models

This example shows that the countability requirement cannot be dispensed with in Vaught's criterion. Be an uncountable index set . For every natural number let the proposition ${\displaystyle I}$ ${\displaystyle a,b\notin I}$ ${\displaystyle n}$ ${\displaystyle \varphi _{\geq n}}$

${\displaystyle \varphi _{\geq n}:=\exists x_{1},\dots ,x_{n}\bigwedge _{1\leq k<l\leq n}\neg x_{k}\doteq x_{l}}$,

which states that there are at least different elements. ${\displaystyle n}$

That of the uncountable set

${\displaystyle \{(c_{a}\doteq c_{b}\rightarrow (c_{a}\doteq c_{j}\wedge c_{i}\doteq c_{j}))\wedge (\neg c_{a}\doteq c_{b}\rightarrow \neg c_{i}\doteq c_{j})|i,j\in I,i\neq j\}\,\cup \,\{\varphi _{\geq n}|n\in \mathbb {N} \}}$

The generated theory has no finite models and is -categorical, because in a countable model all constants must be interpreted in the same way. However, the theory is not complete since the statement ${\displaystyle \omega }$

${\displaystyle c_{a}\doteq c_{b}}$

can neither be refuted nor proven.

Generalizations

The spectral function assigns the number of non-isomorphic models of this cardinal number to a theory and a cardinal number. The spectral problem is to find the values ​​of this function. So it is not only investigated when a theory is categorical, but also asked how many non-isomorphic models of a certain thickness a theory has. ${\displaystyle \mathrm {I} (\lambda ,\mathrm {T} )}$

Individual evidence

1. ^ Wilfrid Hodges:  First Order Model Theory. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
2. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 (comment after chapter 5.2).
3. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 (remark according to chapter 5.2, example 4).
4. ↑ Wolfgang Rautenberg : Introduction to Mathematical Logic . Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 (comment after chapter 5.5, sentence 5.2).