Namespaces
Variants
Actions

Difference between revisions of "Categoricity in cardinality"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207301.png" />''
+
{{TEX|done}}
 +
''$\kappa$''
  
The property of a class of algebraic systems (models) requiring that all systems of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207302.png" /> of the class be isomorphic. A first-order theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207303.png" /> is said to be categorical in cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207304.png" /> if all models of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207305.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207306.png" /> are isomorphic. For a countable complete theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207307.png" />, categoricity in countable cardinality (in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207308.png" />) holds if and only if there exists, for any natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c0207309.png" />, a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073010.png" /> of formulas of the language of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073011.png" /> with free variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073012.png" /> such that any formula of the language with free variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073013.png" /> is equivalent in the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073014.png" /> to one of the formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073015.png" />. The collection of axioms:
+
The property of a class of algebraic systems (models) requiring that all systems of cardinality $\kappa$ of the class be isomorphic. A first-order theory $T$ is said to be categorical in cardinality $\kappa$ if all models of cardinality $\kappa$ of $T$ are isomorphic. For a countable complete theory $T$, categoricity in countable cardinality (in $\aleph_0$) holds if and only if there exists, for any natural number $n$, a finite set $F_n$ of formulas of the language of $T$ with free variables $x_1,\ldots,x_n$ such that any formula of the language with free variables $x_1,\ldots,x_n$ is equivalent in the theory $T$ to one of the formulas of $F_n$. The collection of axioms:
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073016.png" />,
+
1) $x<y\to\neg(y<x)$,
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073017.png" />,
+
2) $(x<y\&y<z)\to x<z$,
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073018.png" />,
+
3) $x<y\lor x=y\lor y<x$,
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073019.png" />, defines a theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073020.png" /> of dense linear orderings which is categorical in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073021.png" />, but is non-categorical in all uncountable cardinalities. The theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073022.png" /> of algebraically closed fields of characteristic zero is categorical in all uncountable cardinalities, but is not categorical in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073023.png" />. The following general theorem holds: If a first-order countable theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073024.png" /> is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities. This result generalizes to uncountable theories <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073025.png" /> on replacing the condition of uncountable cardinality by cardinality greater than that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073026.png" />. By a quasi-identity one means the universal closure of a formula
+
4) $\exists u\exists v\exists t(x<y\to u<x<v<y<t)$, defines a theory $T_0$ of dense linear orderings which is categorical in $\aleph_0$, but is non-categorical in all uncountable cardinalities. The theory $T_1$ of algebraically closed fields of characteristic zero is categorical in all uncountable cardinalities, but is not categorical in $\aleph_0$. The following general theorem holds: If a first-order countable theory $T$ is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities. This result generalizes to uncountable theories $T$ on replacing the condition of uncountable cardinality by cardinality greater than that of $T$. By a quasi-identity one means the universal closure of a formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073027.png" /></td> </tr></table>
+
$$(Q_0\&\ldots\&Q_n)\to P,$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073029.png" /> are atomic formulas. For countable theories <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073030.png" /> which are axiomatized by means of quasi-identities, there is an even smaller distribution of possible categoricities: If such a theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073031.png" /> is categorical in countable cardinality, then it is categorical in all infinite cardinalities. If one appends to the axiom of the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073032.png" /> axioms for constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073033.png" />:
+
where $Q_i$ and $P$ are atomic formulas. For countable theories $T'$ which are axiomatized by means of quasi-identities, there is an even smaller distribution of possible categoricities: If such a theory $T'$ is categorical in countable cardinality, then it is categorical in all infinite cardinalities. If one appends to the axiom of the theory $T_0$ axioms for constants $c_i$:
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073034.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073035.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073036.png" /> runs through the natural numbers, then the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073037.png" /> so obtained has exactly three countable models (up to isomorphism), since only three cases are possible: the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073038.png" /> has no upper bound, has an upper bound but no least upper bound, or has a least upper bound. If for two countable models <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073040.png" /> of the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073041.png" /> the same one of the above three cases applies, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073042.png" /> is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073043.png" />. Among theories which are categorical in uncountable cardinalities it is impossible to obtain an analogue of the above example. Thus, if a first-order theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073044.png" /> is categorical in uncountable cardinality, then the number of countable models of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020730/c02073045.png" /> (up to isomorphism) is either 1 or infinite.
+
$5_i$) $c_i<c_{i+1}$, where $i$ runs through the natural numbers, then the theory $T_3$ so obtained has exactly three countable models (up to isomorphism), since only three cases are possible: the set $\{c_0,c_1,\ldots\}$ has no upper bound, has an upper bound but no least upper bound, or has a least upper bound. If for two countable models $M_1$ and $M_2$ of the theory $T_3$ the same one of the above three cases applies, then $M_1$ is isomorphic to $M_2$. Among theories which are categorical in uncountable cardinalities it is impossible to obtain an analogue of the above example. Thus, if a first-order theory $T$ is categorical in uncountable cardinality, then the number of countable models of $T$ (up to isomorphism) is either 1 or infinite.
  
 
====References====
 
====References====

Revision as of 14:46, 8 August 2014

$\kappa$

The property of a class of algebraic systems (models) requiring that all systems of cardinality $\kappa$ of the class be isomorphic. A first-order theory $T$ is said to be categorical in cardinality $\kappa$ if all models of cardinality $\kappa$ of $T$ are isomorphic. For a countable complete theory $T$, categoricity in countable cardinality (in $\aleph_0$) holds if and only if there exists, for any natural number $n$, a finite set $F_n$ of formulas of the language of $T$ with free variables $x_1,\ldots,x_n$ such that any formula of the language with free variables $x_1,\ldots,x_n$ is equivalent in the theory $T$ to one of the formulas of $F_n$. The collection of axioms:

1) $x<y\to\neg(y<x)$,

2) $(x<y\&y<z)\to x<z$,

3) $x<y\lor x=y\lor y<x$,

4) $\exists u\exists v\exists t(x<y\to u<x<v<y<t)$, defines a theory $T_0$ of dense linear orderings which is categorical in $\aleph_0$, but is non-categorical in all uncountable cardinalities. The theory $T_1$ of algebraically closed fields of characteristic zero is categorical in all uncountable cardinalities, but is not categorical in $\aleph_0$. The following general theorem holds: If a first-order countable theory $T$ is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities. This result generalizes to uncountable theories $T$ on replacing the condition of uncountable cardinality by cardinality greater than that of $T$. By a quasi-identity one means the universal closure of a formula

$$(Q_0\&\ldots\&Q_n)\to P,$$

where $Q_i$ and $P$ are atomic formulas. For countable theories $T'$ which are axiomatized by means of quasi-identities, there is an even smaller distribution of possible categoricities: If such a theory $T'$ is categorical in countable cardinality, then it is categorical in all infinite cardinalities. If one appends to the axiom of the theory $T_0$ axioms for constants $c_i$:

$5_i$) $c_i<c_{i+1}$, where $i$ runs through the natural numbers, then the theory $T_3$ so obtained has exactly three countable models (up to isomorphism), since only three cases are possible: the set $\{c_0,c_1,\ldots\}$ has no upper bound, has an upper bound but no least upper bound, or has a least upper bound. If for two countable models $M_1$ and $M_2$ of the theory $T_3$ the same one of the above three cases applies, then $M_1$ is isomorphic to $M_2$. Among theories which are categorical in uncountable cardinalities it is impossible to obtain an analogue of the above example. Thus, if a first-order theory $T$ is categorical in uncountable cardinality, then the number of countable models of $T$ (up to isomorphism) is either 1 or infinite.

References

[1] G.E. Sacks, "Saturated model theory" , Benjamin (1972)
[2] E.A. Palyutin, "Description of categorical quasivarieties" Algebra and Logic , 14 (1976) pp. 86–111 Algebra i Logika , 14 (1975) pp. 145–185
[3] S. Shelah, "Categoricity of uncountable theories" , Proc. Tarski Symp. , Proc. Symp. Pure Math. , 25 : 2 (1974) pp. 187–203


Comments

The definition of a quasi-identity can also be found in Algebraic systems, quasi-variety of.

The "general theorem" mentioned in the text was conjectured by J. Łoś [a1], to whom the term "categoricity" is due, and proved by M.D. Morley [a2].

References

[a1] J. Łoś, "On the categoricity in power of elementary deductive systems and some related problems" Colloq. Math. , 3 (1954) pp. 58–62
[a2] M. Morely, "Categoricity in power" Trans. Amer. Math. Soc. , 114 (1965) pp. 514–538
[a3] C.C. Chang, H.J. Keisler, "Model theory" , North-Holland (1973)
[a4] S. Shelah, "Classification theory and the number of non-isomorphic models" , North-Holland (1978)
How to Cite This Entry:
Categoricity in cardinality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Categoricity_in_cardinality&oldid=17925
This article was adapted from an original article by E.A. Palyutin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article