Examples of theories

This is an extended quotation from An Invitation to Mathematical Logic, by David Marker.

Below, I also added an extended quotation from A Course on Mathematical Logic, by Shashi Mohan Srivastava.

Marker: Theories

Let $\mathcal {L}$ be a language. An $\mathcal {L}$-theory T is simply a set of $\mathcal {L}$-sentences. We say that $\mathcal {M}$ is a model of T and write $\mathcal {M}\models T$ if $\mathcal {M}\models \phi $ for all sentences $\phi \in T$.

The set $T=\{\forall x \ x=0, \exists x \ x\ne 0\}$ is a theory. Because the two sentences in T are contradictory, there are no models of T. We say that a theory is satisfiable if it has a model.

We say that a class of $\mathcal {L}$-structures $\mathcal K$ is an elementary class if there is an $\mathcal {L}$-theory T such that $\mathcal {K}=\{\mathcal {M}: \mathcal {M}\models T\}$.

One way to get a theory is to take Th($\mathcal {M}$), the full theory of an $\mathcal {L}$-structure $\mathcal {M}$. In this case, the elementary class of models of Th($\mathcal {M}$) is exactly the class of $\mathcal {L}$-structures satisfying exactly the same sentences as $\mathcal {M}$. More typically, we have a class of structures in mind and try to write a set of properties T describing these structures. We call these sentences axioms for the elementary class.

We give a few basic examples of theories and elementary classes that we will return to frequently.

Example 1.33 (Infinite Sets)

Let $\mathcal {L}=\emptyset $. Consider the $\mathcal {L}$-theory where we have, for each n, the sentence $\phi _n$ given by

$\displaystyle \begin{aligned} \exists x_1\exists x_2\dots\exists x_n \bigwedge_{i<j\le n}x_i\ne x_j.\end{aligned}$

The sentence $\phi _n$ asserts that there are at least n distinct elements, and an $\mathcal {L}$-structure $\mathcal {M}$ with universe M is a model of T if and only if M is infinite.

Example 1.34 (Linear Orders)

Let $\mathcal {L}=\{ < \}$, where $<$ is a binary relation symbol. The class of linear orders is axiomatized by the $\mathcal {L}$-sentences

• $\forall x \ \neg (x< x)$
• $\forall x\forall y\forall z\ ((x<y\land y<z)\rightarrow x<z)$
• $\forall x\forall y \ (x<y \lor x=y \lor y<x)$

There are a number of interesting extensions of the theory of linear orders. For example, we could add the sentence

$\displaystyle \begin{aligned} \forall x \forall y \ (x<y\rightarrow \exists z\ (x<z\land z<y))\end{aligned}$

to get the theory of dense linear orders, or we could instead add the sentence

$\displaystyle \begin{aligned} \forall x\exists y \ (x<y \land \forall z (x<z\rightarrow (z=y \lor y<z)))\end{aligned}$

to get the theory of linear orders where every element has a unique successor. We could also add sentences that either assert or deny the existence of top or bottom elements.

Example 1.35 (Equivalence Relations)

Let $\mathcal {L}=\{ E\}$, where E is a binary relation symbol. The theory of equivalence relations is given by the sentences

• $\forall x \ E(x,x)$
• $\forall x\forall y\ (E(x,y)\rightarrow E(y,x))$
• $\forall x\forall y\forall z\ ((E(x,y)\land E(y,z))\rightarrow E(x,z))$

If we added the sentence

$\displaystyle \begin{aligned} \forall x\exists y\ (x\ne y\land E(x,y)\land \forall z \ (E(x,z)\rightarrow (z=x\lor z=y)))\end{aligned}$

we would have the theory of equivalence relations where every equivalence class has exactly two elements. If, instead, we added the sentence

$\displaystyle \begin{aligned} \exists x\exists y (\neg E(x,y)\land \forall z (E(x,z)\lor E(y,z)))\end{aligned}$

and for each n the sentence

$\displaystyle \begin{aligned} \forall x\exists x_1\exists x_2\dots\exists x_n\left ( \bigwedge_{i<j\le n} x_i\ne x_j \land \bigwedge_{i=1}^n E(x,x_i)\right)\end{aligned}$

we would axiomatize the class of equivalence relations with exactly two classes, both of which are infinite.

Example 1.36 (Graphs)

Let $\mathcal {L}=\{R\}$ where R is a binary relation. We think of the elements of the structure as the vertices of the graph and R as the edge relation. We restrict our attention to undirected, irreflexive graphs. These are axiomatized by the two sentences

• $\forall x\ \neg R(x,x)$
• $\forall x\forall y \ (R(x,y)\rightarrow R(y,x))$

Example 1.37 (Groups)

Let $\mathcal {L}=\{\cdot ,e\}$, where $\cdot$ is a binary function symbol and e is a constant symbol. We will write $x\cdot y$ rather than $\cdot (x,y)$. The class of groups is axiomatized by

• $\forall x\ e\cdot x=x\cdot e=x$.
• $\forall x\forall y\forall z \ x\cdot (y\cdot z)=(x\cdot y)\cdot z$.
• $\forall x\exists y\ x\cdot y=y\cdot x=e$.

We could also axiomatize the class of Abelian groups by adding

$\displaystyle \begin{aligned} \forall x\forall y\ x\cdot y=y\cdot x.\end{aligned}$

Let $\phi _n(x)$ be the $\mathcal {L}$-formula

$$ \begin{aligned} \underbrace{x \cdot x \cdots x}_{n\text{ times}} = e, \end{aligned} $$

which asserts that $x^n=e$.

We could axiomatize the class of torsion-free groups by adding

$\displaystyle \begin{aligned} \{\forall x \ (x=e\lor\neg\phi_n(x)):n \ge 2\}\end{aligned}$

to the axioms for groups. Alternatively, we could axiomatize the class of groups where every element has order at most N by adding to the axioms for groups the sentence

$\displaystyle \begin{aligned} \forall x \ \bigvee_{n\le N} \phi_n(x).\end{aligned}$

Note that similar ideas will not work to axiomatize the class of torsion groups because the corresponding sentence would be infinitely long. In Chap. 5, we will see that the class of torsion groups is not elementary.

Let $\psi _n(x,y)$ be the formula

$$ \begin{aligned} \underbrace{x \cdot x \cdots x}_{n\text{ times}} = y, \end{aligned} $$

which asserts that $x^n=y$. We can axiomatize the class of divisible groups by adding the axioms $\{\forall y\exists x\ \psi _n(x,y): n\ge 2\}$.

It will often be useful to deal with additive groups instead of multiplicative groups. The class of additive groups is the collection structures in the language $\mathcal {L}=\{+,0\}$, axiomatized as above replacing $\cdot$ by $+$ and e by 0.

Example 1.38 (Ordered Abelian Groups)

Let $\mathcal {L}=\{+,<,0\}$, where $+$ is a binary function symbol, $<$ is a binary relation symbol, and 0 is a constant symbol. The axioms for ordered groups are

• The axioms for additive groups
• The axioms for linear orders
• $\forall x\forall y\forall z (x<y\rightarrow x+z<y+z)$

Example 1.39 (Rings and Fields)

Let ${\mathcal {L}_{\mathrm {r}}}$ be the language of rings $\{+,-,\cdot ,0,1\}$, where $+$, $-$, and $\cdot$ are binary function symbols and 0 and 1 are constants. The axioms for rings are given by

• The axioms for additive commutative groups
• $\forall x \forall y\forall z \ (x-y=z \leftrightarrow x=y+z)$
• $\forall x \ x\cdot 0=0$
• $\forall x\forall y \forall z \ (x\cdot (y\cdot z)=(x\cdot y)\cdot z)$
• $\forall x \ x\cdot 1=1\cdot x=x$
• $\forall x\forall y\forall z \ x\cdot (y+z)=(x\cdot y)+(x\cdot z)$
• $\forall x\forall y\forall z \ (x+y)\cdot z= (x\cdot z)+(y\cdot z)$

The second axiom is only necessary because we include $-$ in the language (this will be useful later). We axiomatize the class of fields by adding the axioms

• $\forall x\forall y\ x\cdot y=y\cdot x$.
• $\forall x\ (x\ne 0\rightarrow \exists y\ x\cdot y=1)$.

We axiomatize the class of algebraically closed fields by adding to the field axioms the sentences

$\displaystyle \begin{aligned} \forall a_0\dots\forall a_{n-1}\exists x \ x^n+\sum_{i=0}^{n-1} a_i x^i=0\end{aligned}$

for $n=1,2,\dots$. Let ACF be the axioms for algebraically closed fields.

Let $\psi_p$ be the ${\mathcal {L}_{\mathrm {r}}}$-sentence which asserts that a field has characteristic p. For $p>0$ a prime, let $ACF_p = ACF \cup {\psi \_p}$ and $ACF_0 = ACF \cup {\neg \psi \_p: p>0}$ be the theories of algebraically closed fields of characteristic p and characteristic zero, respectively.

Example 1.40 (Ordered Fields)

Let ${\mathcal {L}_{\mathrm {or}}}={\mathcal {L}_{\mathrm {r}}}\cup \{<\}$. The class of ordered fields is axiomatized by the axioms for fields,

• The axioms for linear orders
• $\forall x \forall y \forall z\ (x<y\rightarrow x+z<y+z)$
• $\forall x\forall y \forall z \ ((x<y\land z>0)\rightarrow x\cdot z<y\cdot z)$

Example 1.41 (Boolean Algebras)

Let $\mathcal {L}=\{+,\cdot ,-,0,1\}$ where $+$ and $\cdot$ are binary function symbols and $-$ is a unary function symbol. The theory of Boolean algebras is given by the following axioms.

• $\forall x\forall y \ (x+y=y+x \land x\cdot y=y\cdot x)$
• $\forall x\forall y\forall z\ (x+(y+z)=(x+y)+z \land x\cdot (y\cdot z)=(x\cdot y)\cdot z)$
• $\forall x\ (x+0=x\land x\cdot 1=x)$
• $\forall x\forall y\forall z( x+(y\cdot z)=(x+y)\cdot (x+z)\land x\cdot (y+z)=(x\cdot y)+(x\cdot z))$
• $\forall x ( x\cdot -x= 0\land x+-x=1)$

Example 1.42 (Peano Arithmetic)

Let $\mathcal {L}=\{+,\cdot ,s,0\}$, where $+$ and $\cdot$ are binary functions, s is a unary function, and 0 is a constant. We think of s as the successor function $x\mapsto x+1$. The Peano axioms for arithmetic are the sentences

• $\forall x \ s(x)\ne 0$.
• $\forall x \ (x\ne 0\rightarrow \exists y \ s(y)=x)$.
• $\forall x\ x+0=x$.
• $\forall x\ \forall y \ x+s(y)=s(x+y)$.
• $\forall x\ \ x\cdot 0=0$.
• $\forall x\forall y \ x\cdot s(y)= (x\cdot y) + x$,

and the axioms Ind($\phi $) for each formula $\phi (v,\overline w)$, where Ind($\phi $) is the sentence

$\displaystyle \begin{aligned} \forall \overline w\ [(\phi(0,\overline w) \land \forall v\ (\phi(v,\overline w)\rightarrow \phi(s(v),\overline w)))\rightarrow\forall x \ \phi(x,\overline w)]. \end{aligned}$

The axiom Ind($\phi $) formalizes an instance of induction. It asserts that if $\overline a\in M$, $X=\{m\in M: \mathcal {M}\models \phi (m,\overline a)\}$, $0\in X$, and $s(m)\in X$ whenever $m\in X$, then $X=M$.

Srivastava: First-Order Theories

A first-order theory, or simply a theory, $T$ consists of a first-order language $L$ and a set of formulas of $L$. These formulas are called nonlogical axioms of $T$. By terms or formulas of $T$, we shall mean terms or formulas respectively of the language of $T$. The language of $T$ will also be denoted by $L(T)$. A theory is called countable if its language is countable. It is finite if the set of all nonlogical symbols is finite. In general, a theory $T$ whose set of all nonlogical symbols is of cardinality at most $\kappa$, with $\kappa$ an infinite cardinal, is called a $\kappa$-theory.

Example 1.4.1.

The theory of infinite sets has no nonlogical symbols and its axioms are the sentences $A_n$, $n\geq 2$, where $A_n$ is the formula $\exists {x}_{1}\cdots \exists {x}_{n} {\wedge }_{1\leq i<j\leq n}{x}_{i}\neq {x}_{j}.$

Example 1.4.2.

Group theory is a theory whose nonlogical symbols are a constant symbol $e$ and a binary function symbol $\cdot$ and whose nonlogical axioms are the following formulas (below, $x$, $y$, and $z$ denote the first three variables):

1. $\forall x\forall y\forall z(x\cdot(y\cdot z)=(x\cdot y)\cdot z),$

2. $\forall x(x\cdot e=x\wedge e\cdot x=x),$

3. $\forall x\exists y(x\cdot y=e\wedge y\cdot x=e).$

Example 1.4.3.

The theory of abelian groups is a theory whose nonlogical symbols are a constant symbol $0$ and a binary function symbol $+$ and whose nonlogical axioms are the following formulas:

1. $\forall x\forall y\forall z(x+(y+z)=(x+y)+z),$

2. $\forall x(x+0=x\wedge 0+x=x),$

3. $\forall x\exists y(x+y=0\wedge y+x=0),$

4. $\forall x\forall y(x+y=y+x).$

Example 1.4.4.

The language of the theory of rings with identity has two constant symbols, $0$ and $1$, and two binary function symbols, $+$ and $\cdot$. The nonlogical axioms of this theory are axioms 1–4 of abelian groups together with the following axioms:

5. $\forall x\forall y\forall z(x\cdot(y\cdot z)=(x\cdot y)\cdot z),$

6. $\forall x(x\cdot 1=x\wedge 1\cdot x=x),$

7. $\forall x\forall y\forall z(x\cdot(y+z)=x\cdot y+x\cdot z),$

8. $\forall x\forall y\forall z((y+z)\cdot x=y\cdot x+z\cdot x).$

We define the theory of commutative rings with identity by adding

9. $\forall x\forall y(x\cdot y=y\cdot x)$

as a nonlogical axiom.

Example 1.4.5.

Field theory has the same language as the theory of rings with identity. Its nonlogical axioms are axioms 1–9 of the theory of commutative rings with identity together with the following axiom:

10. $\forall x(\neg(x=0)\rightarrow\exists y(x\cdot y=1\wedge y\cdot x=1)).$

Example 1.4.6.

Let $L$ be a language with only one nonlogical symbol – a binary relation symbol $<$. The theory $LO$ (the theory of linearly ordered sets) is a theory whose language is $L$ and whose nonlogical axioms are as follows:

1. $\forall x\neg(x<x),$

2. $\forall x\forall y\forall z((x<y\wedge y<z)\rightarrow x<z),$

3. $\forall x\forall y(x<y\vee x=y\vee y<x).$

Example 1.4.7.

The theory of ordered abelian groups, denoted by $OG$, has a constant symbol $0$, a binary function symbol $+$, and a binary relation symbol $<$. Its axioms are the axioms of abelian groups, axioms of linear order, and the following axiom:

$\forall x\forall y\forall z(x<y\rightarrow x+z<y+z).$

Example 1.4.8.

The theory of dense linearly ordered sets, denoted by $DLO$, is obtained from $LO$ by adding the following axioms:

4. $\forall x\forall y((x<y)\rightarrow\exists z(x<z\wedge z<y)),$

5. $\forall x\exists y(y<x),$

6. $\forall x\exists y(x<y).$

Exercise 1.4.9.

Express the axioms of an equivalence relation as formulas of a suitable first-order language.

Example 1.4.10.

Let $F$ be the theory of fields.

Let $p>1$ be a prime number. The theory obtained by adding

$\wedge_{m=1}^{p-1}(\underline{m}\neq 0)\wedge(\underline{p}=0)$

to the axiom of $F$ is called the theory of fields of characteristic p.

For each $m\geq 1$, let $A_m$ be the formula $\underline{m}\neq 0.$ The theory obtained by adding each $A_m$ to the set of axioms of $F$ as an axiom is called the theory of fields of characteristic 0.

Example 1.4.11.

Let $F$ be the theory of fields. Let $L$ be an extension of the language for the theory of rings with identity obtained by adding a new binary predicate symbol $<$. Consider the theory $OF$ whose language is $L$ and whose nonlogical axioms are all the nonlogical axioms of $F$ and the following axioms:

11. $\forall x\neg(x<x),$

12. $\forall x\forall y\forall z((x<y\wedge y<z)\rightarrow x<z),$

13. $\forall x\forall y(x<y\vee x=y\vee y<x),$

14. $\forall x\forall y(x<y\rightarrow\forall z(x+z<y+z)),$

15. $\forall x\forall y((0<x\wedge 0<y)\rightarrow 0<x\cdot y).$

The theory $OF$ is known as the theory of ordered fields.

Example 1.4.12.

We now give some axioms of number theory, which plays an important role in logic. We denote this theory by $N$. The nonlogical symbols of $N$ are a constant symbol $0$, a unary function symbol $S$ (which designates the successor function), two binary function symbols $+$ and $\cdot$, and a binary relation symbol $<$. The nonlogical axioms of $N$ are as follows:

1. $\forall x(\neg(Sx=0)),$

2. $\forall x\forall y(Sx=Sy\rightarrow x=y),$

3. $\forall x(x+0=x),$

4. $\forall x\forall y(x+Sy=S(x+y)),$

5. $\forall x(x\cdot 0=0),$

6. $\forall x\forall y(x\cdot Sy=(x\cdot y)+x),$

7. $\forall x(\neg(x<0)),$

8. $\forall x\forall y(x<Sy\leftrightarrow(x<y\vee x=y)),$

9. $\forall x\forall y(x<y\vee x=y\vee y<x).$

For any nonnegative integer n, the term
$$\underbrace{{S\cdots S }}_{m\ \mathrm{times}}0$$
will be denoted by k_n . Such terms are called numerals. Note that k_0 is the constant symbol 0.

Example 1.4.13.

Peano arithmetic is the theory obtained from N by deleting the last axiom and adding the following axiom schema, called an induction axiom schema: for every formula A[v], the formula
$${A}_{v}[0] \rightarrow \forall v(A \rightarrow {A}_{v}[Sv]) \rightarrow A$$
is called an induction axiom. This theory will be denoted by PA.