Namespaces
Variants
Actions

Categoric system of axioms

From Encyclopedia of Mathematics
Jump to: navigation, search

categorical system of axioms

Any system of axioms $\Sigma$ for which all models of the signature of $\Sigma$ satisfying these axioms are isomorphic. It follows from the Mal'tsev–Tarski theorem on elementary extensions that models of a categorical first-order system $\Sigma$ of axioms have finite cardinality. The converse also holds: For any finite model $A$ there exists a categorical first-order system $\Sigma$ of axioms whose models are isomorphic to $A$. Let $\Sigma_0$ be the set of universal closures of the formulas

1) $0\neq x+1$;

2) $x+1=y+1\rightarrow x=y$;

3) $x+0=x$;

4) $x+(y+1)=(x+y)+1$;

5) $x\cdot0=0$;

6) $x\cdot(y+1)=(x\cdot y)+x$;

7) $(\phi(0)\&\forall x(\phi(x)\rightarrow\phi(x+1)))\rightarrow\forall x\phi(x)$, where $\phi(x)$ is any formula of signature $\langle +,\cdot,0,1\rangle$.

This system of axioms $\Sigma_0$ is known under the name of Peano arithmetic. The model $N=\langle\mathbf N,+,\cdot,0,1\rangle$ of natural numbers is a model for $\Sigma_0$. However, there exists a model of $\Sigma_0$ that is not isomorphic to $N$. Let $\Sigma_1$ be the system obtained from $\Sigma_0$ by replacing the scheme of elementary induction 7) by the axiom of complete induction

$$\forall P((P(0)\&\forall x(P(x)\rightarrow P(x+1)))\rightarrow\forall xP(x)),$$

written in a second-order language. Then the system $\Sigma_1$ is categorical and all models of $\Sigma_1$ are isomorphic to $N$. Another method of categorical description of $N$ consists in appending to $\Sigma_0$ the following infinite axiom (of the language $L_{\omega_1\omega}$):

$$\forall x(x=0\lor\dots\lor x=n\lor\dots),$$

when $n$ is short for the sum $1+\dots+1$ of $n$ ones.

References

[1] J.R. Shoenfield, "Mathematical logic" , Addison-Wesley (1967)
How to Cite This Entry:
Categoric system of axioms. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Categoric_system_of_axioms&oldid=43466
This article was adapted from an original article by E.A. Palyutin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article