7.4 Theories and Their Models

Section 7.2 called a structure in which three sentences are true a model of them. Mathematics works this way all the time: a list of axioms describes a kind of structure, and a theorem about that kind is whatever follows from the axioms. This section makes that precise, and answers the chapter’s first question: the axioms of a partial order do not prove that any two elements are comparable.

The plan has five steps. First, theories and their models are defined. A gallery follows: equivalence relations, orders, groups and fields, each written as axioms, each with a model and a non-model. Then one theorem is derived from the group axioms, to show what a theorem of a theory is. Then comes consistency, which a single model proves. Last comes independence, which two models prove.

7.4.1. Theories and their models

Fix the symbols (constants, function and predicate symbols) that the axioms will use, as in Definition 7.1.1.

A theory is a collection of sentences taken as axioms; its theorems are what can be derived from finitely many of them.

Definition 7.4.1 (Theory)

A theory $T$ is a set of sentences in the chosen symbols, called its axioms; the set may be finite or infinite. A sentence $\sigma$ is derivable from $T$ , written $T \vdash \sigma$ , if $\varphi_1, \dots, \varphi_n \vdash \sigma$ for some finite list $\varphi_1, \dots, \varphi_n$ of axioms of $T$ ( $n \ge 0$ ); such a $\sigma$ is a theorem of $T$ .

In words: a derivation is finite, so it uses finitely many axioms, even when $T$ has infinitely many. So “ $T \vdash \sigma$ ” reads Definition 1.2.3 through a finite list, and needs nothing new. The case $n = 0$ says that a sentence derivable from no premises at all is a theorem of every theory. At the other end, each axiom is a theorem of its own theory: the derivation whose only line is the axiom, as a premise, has it as its last line. The theorems are everything in between: what the axioms, used finitely often, force.

A model of a theory is a structure in which every axiom is true.

Definition 7.4.2 (Model of a Theory)

A structure $\mathfrak{M}$ for the symbols of $T$ is a model of $T$ , written $\mathfrak{M} \models T$ , if every axiom of $T$ is true in $\mathfrak{M}$ . A sentence $\sigma$ is a semantic consequence of $T$ , written $T \models \sigma$ , if $\sigma$ is true in every model of $T$ .

The axioms are sentences, so no assignment is needed: by Lemma 7.1.1 each axiom is true or false in $\mathfrak{M}$ outright. And “every model of $T$ ” is the theory’s version of “every structure satisfying $\Gamma$ ” in Definition 7.1.4.

Quick check. Let $T$ be the three sentences of the strict order with no largest element (Section 7.2). Is $(\{ 0 \}, <)$ a model of $T$ ? Is the set $\mathbb{Q}_{>0}$ of positive rationals with $<$ ?

Solution. Not the first: $\forall x\, \neg(x < x)$ and transitivity hold, but $\forall x\, \exists y\, (x < y)$ fails at $0$ , since nothing is above it. The second is a model: no rational is below itself, $<$ is transitive, and for each positive $d$ the witness $d + 1$ is again positive and above $d$ .

7.4.2. A gallery of theories

Each theory below is given by its axioms, written as sentences and named, with a model and a non-model. A non-model is checked by naming the axiom that fails and where. The names in parentheses are local to this chapter, except the field clauses (F1)–(F9), which keep their series-wide numbering; none of them is one of the clauses (S1)–(S7) of Definition 7.1.3.

Example (Axioms, Models and Non-models)

Equivalence relations. One two-place predicate symbol $R$ , and three axioms: $\begin{aligned} &\text{(Refl)} && \forall x\, R(x, x), \\ &\text{(Sym)} && \forall x\, \forall y\, (R(x, y) \to R(y, x)), \\ &\text{(Trans)} && \forall x\, \forall y\, \forall z\, \bigl( (R(x, y) \wedge R(y, z)) \to R(x, z) \bigr). \end{aligned}$ A model: $D = \{ a, b, c \}$ , with $R^{\mathfrak{M}}$ relating $a$ and $b$ both ways and every element to itself (Figure A, left). Each loop gives (Refl); the only pairs of different elements are $(a, b)$ and $(b, a)$ , which give (Sym); and every chain of two arrows ends where a loop or one of these pairs already is, which gives (Trans). In numbers: “ $x$ and $y$ have the same parity” on $\mathbb{Z}$ . A non-model: on $\mathbb{Z}$ , read $R(x, y)$ as $\left| x - y \right| \le 1$ . It is reflexive and symmetric, and (Trans) fails at $0, 1, 2$ : $\left| 0 - 1 \right| \le 1$ and $\left| 1 - 2 \right| \le 1$ , but $\left| 0 - 2 \right| = 2$ .

Partial and linear orders. One two-place symbol $\le$ . The axioms (Refl) and (Trans), written with $\le$ , together with $\text{(Antisym)} \quad \forall x\, \forall y\, \bigl( (x \le y \wedge y \le x) \to x = y \bigr),$ make the theory of a partial order. Adding $\text{(Conn)} \quad \forall x\, \forall y\, (x \le y \vee y \le x)$ gives the theory of a linear order. A model of the first and not the second: divisibility on $\{ 1, 2, 3, 6 \}$ (the right panel of Figure F in Section 7.1), where $2$ and $3$ are incomparable, so (Conn) fails at $(2, 3)$ . A model of both: $(\mathbb{N}, \le)$ . Smallest of all, the antichain $D = \{ a, b \}$ with $\le^{\mathfrak{M}} = \{ (a, a), (b, b) \}$ (Figure A, right) is a partial order: the loops give (Refl), and (Antisym) and (Trans) only ever meet pairs $(d, d)$ . (Conn) fails at $(a, b)$ .

Strict and dense orders. One two-place symbol $<$ . The axioms $\begin{aligned} &\text{(Irrefl)} && \forall x\, \neg(x < x), \\ &\text{(Trans)} && \forall x\, \forall y\, \forall z\, \bigl( (x < y \wedge y < z) \to x < z \bigr) \end{aligned}$ make a strict order; with $\text{(Tri)} \quad \forall x\, \forall y\, (x < y \vee x = y \vee y < x)$ a strict linear order; and with $\text{(Dense)} \quad \forall x\, \forall y\, \bigl( x < y \to \exists z\, (x < z \wedge z < y) \bigr)$ a dense one. A model of all four: $(\mathbb{Q}, <)$ , where $(p + q)/2$ lies between $p < q$ . A non-model of (Dense): $(\mathbb{Z}, <)$ , at $0 < 1$ , since no integer lies strictly between.

Groups. A two-place function symbol $\cdot$ and a constant $e$ , with $\begin{aligned} &\text{(Assoc)} && \forall x\, \forall y\, \forall z\, \bigl( (x \cdot y) \cdot z = x \cdot (y \cdot z) \bigr), \\ &\text{(Id)} && \forall x\, (x \cdot e = x \wedge e \cdot x = x), \\ &\text{(Inv)} && \forall x\, \exists y\, (x \cdot y = e \wedge y \cdot x = e). \end{aligned}$ A model: $(\mathbb{Z}; +, 0)$ , with $\cdot$ read as $+$ and $e$ as $0$ ; the inverse of $d$ is $-d$ . A non-model: $(\mathbb{N}; +, 0)$ , where (Inv) fails at $1$ , since no natural number added to $1$ gives $0$ . Commutativity, $\text{(Comm)} \quad \forall x\, \forall y\, (x \cdot y = y \cdot x),$ is not an axiom; the next example shows why.

Fields. Constants $0$ , $1$ and two-place function symbols $+$ , $\cdot$ , with ten axioms, the nine (F1)–(F9), numbered as in the field axioms used throughout this series, and $(1 \ne 0)$ : $\begin{aligned} &\text{(F1)} && \forall x\, \forall y\, (x + y = y + x), &&\text{(F2)} && \forall x\, \forall y\, \forall z\, \bigl( (x + y) + z = x + (y + z) \bigr), \\ &\text{(F3)} && \forall x\, (x + 0 = x), &&\text{(F4)} && \forall x\, \exists y\, (x + y = 0), \\ &\text{(F5)} && \forall x\, \forall y\, \forall z\, \bigl( (x \cdot y) \cdot z = x \cdot (y \cdot z) \bigr), &&\text{(F6)} && \forall x\, \forall y\, (x \cdot y = y \cdot x), \\ &\text{(F7)} && \forall x\, (x \cdot 1 = x), &&\text{(F8)} && \forall x\, \bigl( \neg(x = 0) \to \exists y\, (x \cdot y = 1) \bigr), \\ &\text{(F9)} && \forall x\, \forall y\, \forall z\, \bigl( x \cdot (y + z) = x \cdot y + x \cdot z \bigr), &&(1 \ne 0) && \neg(0 = 1). \end{aligned}$ Models: $\mathbb{Q}$ and $\mathbb{R}$ , with the usual operations, and the two-element field, with domain $\{ 0, 1 \}$ and the tables $\begin{array}{c|cc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad\qquad \begin{array}{c|cc} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array}$ (the sum of two equal elements is $0$ ; the products are the usual ones). A non-model: $\mathbb{Z}$ , where (F8) fails at $2$ : no integer $y$ has $2y = 1$ .

Diagram. Labels: small an equivalence relation, small the antichain: a partial order, not linear

Figure A. Left: an equivalence relation on $\{ a, b, c \}$ , whose classes are $\{ a, b \}$ and $\{ c \}$ . Right: the antichain on $\{ a, b \}$ .

The non-models are as instructive as the models: a non-model with every axiom but one true shows exactly what that one axiom adds.

Quick check. In the two-element field, which element is the additive inverse of $1$ , and which is the reciprocal of $1$ ? Why does the field axiom for reciprocals ask nothing of $0$ ?

Solution. $1$ in both cases: $1 + 1 = 0$ and $1 \cdot 1 = 1$ . The axiom (F8) reads $\forall x\, \bigl( \neg(x = 0) \to \exists y\, (x \cdot y = 1) \bigr)$ , and at $0$ its hypothesis fails, so the implication holds by (S5).

The groups part promised a model of the group axioms in which (Comm) is false. Every group of numbers under addition or multiplication is commutative, so the model comes from geometry.

Example (The Six Symmetries of a Triangle)

Label the corners of an equilateral triangle $1$ , $2$ , $3$ (Figure T). A symmetry is a motion that puts the triangle back on itself, recorded by where it sends each corner. There are six:

$e$ : nothing moves;
$r$ : a turn by a third, $1 \mapsto 2$ , $2 \mapsto 3$ , $3 \mapsto 1$ ;
$q$ : a turn by two thirds, $1 \mapsto 3$ , $2 \mapsto 1$ , $3 \mapsto 2$ ;
the flips $a$ (fixing $1$ , swapping $2$ and $3$ ), $b$ (fixing $2$ ) and $c$ (fixing $3$ ).

Read $x \cdot y$ as “first $x$ , then $y$ ”. For instance $a \cdot r$ sends $1$ to $1$ and then to $2$ ; $2$ to $3$ and then to $1$ ; $3$ to $2$ and then to $3$ . It fixes $3$ and swaps $1$ , $2$ , so $a \cdot r = c$ . Computed in the same way, the whole table, with row $x$ , column $y$ and entry $x \cdot y$ , is $\begin{array}{c|cccccc} \cdot & e & r & q & a & b & c \\ \hline e & e & r & q & a & b & c \\ r & r & q & e & b & c & a \\ q & q & e & r & c & a & b \\ a & a & c & b & e & q & r \\ b & b & a & c & r & e & q \\ c & c & b & a & q & r & e \end{array}$ Take the domain $\{ e, r, q, a, b, c \}$ , the table as the meaning of $\cdot$ , and $e$ as the meaning of the constant $e$ . Check the group axioms.

(Id): the $e$ row and the $e$ column repeat the column and row heads.
(Inv): each row contains $e$ , and in the same place as its column does. So $r \cdot q = e = q \cdot r$ , and each flip undoes itself: $a \cdot a = b \cdot b = c \cdot c = e$ .
(Assoc): “first $x$ , then $y$ , then $z$ ” is one sequence of motions, however it is bracketed. The fold below says this once more, carefully.

Now $a \cdot r = c$ and $r \cdot a = b$ , so (Comm) fails at $(a, r)$ . So this is a model of the group axioms in which (Comm) is false.

Two elements would not do: in a group $\{ e, g \}$ , every product with $e$ is fixed by (Id), and $g \cdot g$ commutes with itself, so (Comm) holds.

Figure T. The corners $1$ , $2$ , $3$ ; the turn $r$ about the center, carrying $1$ to $2$ , $2$ to $3$ and $3$ to $1$ ; and the line of the flip $a$ , through corner $1$ and the midpoint of the opposite side.

Second readingWhy the table is associative without 216 checks

Checking (Assoc) entry by entry would mean $6 \cdot 6 \cdot 6 = 216$ triples $(x, y, z)$ , each needing four look-ups in the table. There is a shorter way. A symmetry is a rearrangement of the corners, and $x \cdot y$ is the rearrangement that applies $x$ and then $y$ to each corner. Follow one corner $i$ through $(x \cdot y) \cdot z$ : first $x \cdot y$ sends it to where $y$ sends the place $x$ sent it, and then $z$ moves it on. Through $x \cdot (y \cdot z)$ : first $x$ moves it, and then $y \cdot z$ applies $y$ and then $z$ . Either way, corner $i$ goes through $x$ , then $y$ , then $z$ , and lands in the same place. The two products send every corner to the same corner, so they are the same symmetry. The table only records the results, so it is associative because composing rearrangements is.

Quick check. From the table, what is $a \cdot a$ ? What is $r \cdot r \cdot r$ , bracketed either way?

Solution. $a \cdot a = e$ . And $(r \cdot r) \cdot r = q \cdot r = e$ , while $r \cdot (r \cdot r) = r \cdot q = e$ : three turns by a third bring every corner home.

7.4.3. A theorem of a theory

A theorem of a theory is derived from finitely many of its axioms with the rules of Chapters 1, 2 and 5; nothing else is used. Section 5.4 has already derived one, in Exercise (B5: Derive or break: properties of a relation, used later) (c): from (Irrefl) and (Trans), a strict order is asymmetric. Here is a theorem of the group axioms.

Proposition 7.4.1 (A Group Has Only One Identity)

From (Id), the sentence $\forall x\, \bigl( \forall y\, (y \cdot x = y \wedge x \cdot y = y) \to x = e \bigr)$ is derivable: an element that acts as an identity on every element is $e$ .

Proof. The plan: fix $x_0$ and assume that it acts as an identity; apply that assumption at $e$ , and (Id) at $x_0$ . The two give two values of the one product $x_0 \cdot e$ , and $\mathrm{{=}E}$ equates them.

\forall x\, (x \cdot e = x \wedge e \cdot x = x)

x_0

\forall y\, (y \cdot x_0 = y \wedge x_0 \cdot y = y)

asm, for

\mathrm{{{\to}}I}

e \cdot x_0 = e \wedge x_0 \cdot e = e

\mathrm{{\forall}E}

x_0 \cdot e = e

\mathrm{{\wedge}E}

x_0 \cdot e = x_0 \wedge e \cdot x_0 = x_0

\mathrm{{\forall}E}

x_0 \cdot e = x_0

\mathrm{{\wedge}E}

x_0 = e

\mathrm{{=}E}

6, 4

\forall y\, (y \cdot x_0 = y \wedge x_0 \cdot y = y) \to x_0 = e

\mathrm{{{\to}}I}

2–7

\forall x\, (\forall y\, (y \cdot x = y \wedge x \cdot y = y) \to x = e)

\mathrm{{\forall}I}

2–8

Line 7 is $\mathrm{{=}E}$ with $\varphi$ the formula $z = e$ : line 4 is $\varphi[x_0 \cdot e / z]$ , and line 6 says $x_0 \cdot e = x_0$ , so the rule gives $\varphi[x_0 / z]$ . At line 9, $x_0$ appears in no premise, in no open assumption, and not in line 9.

So in every group the identity is the only element that acts as one, by the soundness statement of Section 7.2, without checking any group. In $(\mathbb{Z}; +, 0)$ , $0$ is the only integer $x$ with $d + x = d$ and $x + d = d$ for every $d$ ; in the triangle group, only the $e$ row and the $e$ column repeat the heads. Only (Id) was used. A theorem of a theory says something about all its models at once; that is what a theory is for.

7.4.4. Consistency

Section 3.2 called a list of formulas inconsistent when it derives $\bot$ (Definition 3.2.1). A theory may be infinite, so its version goes through finite lists.

Definition 7.4.3 (Inconsistent Theory)

A theory $T$ is inconsistent if $T \vdash \bot$ , that is, if $\varphi_1, \dots, \varphi_n \vdash \bot$ for some finite list of axioms of $T$ ; otherwise $T$ is consistent.

An inconsistent theory derives every sentence, since $\mathrm{\bot E}$ turns $\bot$ into anything. So it says nothing, and consistency is the least one asks of axioms. Deriving $\bot$ shows inconsistency: one derivation is enough. Consistency is harder to show by derivations, since it says that no derivation from the axioms ends with $\bot$ , and there are infinitely many derivations to rule out. Section 7.2 met the same difficulty with non-derivability, and solved it with a counter-model. A model does the same here: it rules out every derivation of $\bot$ at once.

Proposition 7.4.2 (A Theory with a Model Is Consistent)

If some structure is a model of $T$ , then $T$ is consistent.

Proof. Let $\mathfrak{M} \models T$ , and suppose $\varphi_1, \dots, \varphi_n \vdash \bot$ for axioms $\varphi_i$ of $T$ . By the soundness statement of Section 7.2 (proved in the optional Section 7.3), $\varphi_1, \dots, \varphi_n \models \bot$ . Each $\varphi_i$ is true in $\mathfrak{M}$ , so $\mathfrak{M}, \ell \models \bot$ for any assignment $\ell$ , which (S3) forbids. So no such list exists.

So each model in the gallery proves its theory consistent. The converse, that every consistent theory has a model, is also true; it is the completeness theorem for predicate logic, stated without proof in the optional Section 7.6. Consistent is a word about derivations, and has a model (satisfiable) is one about structures. The two are never swapped, and where they agree the text says which theorem makes them agree.

The same reasoning shows that a sentence is not a theorem. To show $T \nvdash \sigma$ , make the counterexample set $T, \neg\sigma$ true (Definition 1.1.3): find a model of $T$ in which $\sigma$ is false.

Warning. A model in which $\sigma$ is true shows nothing about $T \vdash \sigma$ . Comparability, (Conn), is true in $(\mathbb{N}, \le)$ , a model of the partial order axioms, and it is not a theorem of them, as the next subsection shows.

Quick check. Is the theory $\{ \exists x\, P(x), \ \forall x\, \neg P(x) \}$ consistent?

Solution. No. Open an $\mathrm{\exists E}$ box on the first axiom, with witness $x_0$ and assumption $P(x_0)$ ; $\mathrm{\forall E}$ on the second gives $\neg P(x_0)$ , and $\mathrm{\neg E}$ gives $\bot$ , which $\mathrm{\exists E}$ carries out of the box, since $x_0$ is not in $\bot$ , in the first axiom or in a premise. (Equally, no structure is a model; but that alone would not show inconsistency without the completeness theorem.)

7.4.5. Independence

One model with $\sigma$ false shows that $\sigma$ is not a theorem. Two models, one each way, show more.

Proposition 7.4.3 (Independence by Models)

Let $T$ be a theory and $\sigma$ a sentence.

(a) If some model of $T$ makes $\sigma$ false, then $T \nvdash \sigma$ .
(b) If, besides, some model of $T$ makes $\sigma$ true, then $T \nvdash \neg\sigma$ as well; $\sigma$ is then independent of $T$ : neither it nor its negation is a theorem.

Proof.

(a) If $\varphi_1, \dots, \varphi_n \vdash \sigma$ for axioms of $T$ , then $\varphi_1, \dots, \varphi_n \models \sigma$ by the soundness statement of Section 7.2 (proved in the optional Section 7.3). The model satisfies every $\varphi_i$ , so it satisfies $\sigma$ , against the hypothesis. (b) Apply (a) to $\neg\sigma$ , which the second model makes false, by (S4).

Now the chapter’s question. The antichain of Figure A is a model of the partial order axioms in which (Conn) is false, and $(\mathbb{N}, \le)$ is one in which it is true. So comparability is independent of the axioms of a partial order: they neither prove nor refute it. That is why “linear order” needs (Conn) as an axiom of its own.

The same goes for groups. $(\mathbb{Z}; +, 0)$ and the triangle group are models of the group axioms; (Comm) is true in the first and false in the second. So commutativity is independent of the group axioms. Mathematicians call the groups that satisfy it abelian, and study the others too.

Finding the two models. The model in which $\sigma$ is true is usually the one the axioms were written for, such as $(\mathbb{N}, \le)$ or $(\mathbb{Z}; +, 0)$ . The model in which $\sigma$ is false is a counter-model in the sense of Section 7.2, and it is found by the same backward reading: write down what $\neg\sigma$ demands, then what each axiom demands, and build the smallest structure meeting both. For (Conn) the demand is two incomparable elements, and the axioms of a partial order then ask only for a loop at each; that is the antichain.

Independence also tells whether an axiom list has a spare member: an axiom that follows from the others could be dropped from the list without changing the theorems. The three axioms of an equivalence relation have none.

Example (Reflexive, Symmetric, Transitive: Each Independent of the Other Two)

Three structures for one two-place symbol $R$ (Figure I). The first two are the counter-readings (d) and (f) of Exercise (B5: Derive or break: properties of a relation, used later), now as models, with $a$ , $b$ in place of $0$ , $1$ .

Not reflexive: $D = \{ a, b \}$ , $R^{\mathfrak{M}} = \{ (a, a) \}$ . Symmetric and transitive, since the only pair is $(a, a)$ ; (Refl) fails at $b$ .
Not symmetric: $D = \{ a, b \}$ , $R^{\mathfrak{M}} = \{ (a, a), (b, b), (a, b) \}$ . Reflexive; transitive, since every chain of two arrows has a loop as one of them; (Sym) fails at $(a, b)$ , since $(b, a)$ is missing.
Not transitive: $D = \{ a, b, c \}$ , $R^{\mathfrak{M}}$ the loops at $a$ , $b$ , $c$ together with $(a, b)$ , $(b, a)$ , $(b, c)$ , $(c, b)$ . Reflexive; symmetric, since the arrows between different elements come in pairs; (Trans) fails at $a, b, c$ , since $(a, b)$ and $(b, c)$ are in $R^{\mathfrak{M}}$ and $(a, c)$ is not.

By Proposition 7.4.3 (a), no one of the three axioms follows from the other two.

Diagram. Labels: small not reflexive, small not symmetric, small not transitive

Figure I. Three relations, each with exactly two of the three properties of an equivalence relation.

Warning. A tempting “proof” that a symmetric and transitive relation is reflexive: “ $R(x, y)$ gives $R(y, x)$ by symmetry, and the two give $R(x, x)$ by transitivity.” The step from nothing to $R(x, y)$ is the error: it needs some $y$ related to $x$ . In the first structure above, $b$ is related to nothing, and $R(b, b)$ fails. Section 5.4 broke the claim with this reading, Exercise (B5: Derive or break: properties of a relation, used later) (d), and here it is a model of (Sym) and (Trans) in which (Refl) is false.

Quick check. Show that (Dense) is independent of the strict linear order axioms.

Solution. $(\mathbb{Q}, <)$ is a strict linear order in which (Dense) holds; $(\mathbb{Z}, <)$ is one in which it fails, at $0 < 1$ . Apply Proposition 7.4.3.

Remark (Looking ahead). Sets, Relations, and Cardinality, Chapter 2 studies equivalence relations and partial orders as relations on a set, with their maximal and greatest elements; Algebraic Preliminaries, Chapters 2 and 3 take fields and groups as theories and study their models.

7.4.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a theory, a model of a theory, and $T \vdash \sigma$ .
(b) Why does Definition 7.4.3 say “finite list of axioms”?
(c) In the proof of Proposition 7.4.3 (a), where is the soundness statement used? Why does a model in which $\sigma$ is true not show $T \vdash \sigma$ ?
(d) What two models show $\sigma$ independent of $T$ ?
(e) True or false: every theory with a finite model is consistent.

Solution. (a) A theory is a set of sentences, its axioms (Definition 7.4.1). A model of $T$ is a structure in which every axiom of $T$ is true (Definition 7.4.2). $T \vdash \sigma$ means $\varphi_1, \dots, \varphi_n \vdash \sigma$ for some finite list of axioms of $T$ .

(b) A derivation has finitely many lines, so it uses finitely many premises, and a theory may be infinite.

(c) To pass from $\varphi_1, \dots, \varphi_n \vdash \sigma$ to $\varphi_1, \dots, \varphi_n \models \sigma$ . A model in which $\sigma$ is true is compatible with $T \vdash \sigma$ and with $T \nvdash \sigma$ alike: comparability is true in $(\mathbb{N}, \le)$ and is not a theorem of the partial order axioms.

(d) A model of $T$ in which $\sigma$ is false, and one in which it is true.

(e) True, by Proposition 7.4.2: a finite model is a model.

Exercise (A2: Drill)

Each part takes a line or two. The parts run from reading an axiom, through deciding axioms in a given structure, to judging claims about theories and building a model.

(a) Write “ $R$ is symmetric” as a sentence.
(b) Which axiom of a partial order fails in $(\mathbb{Z}, <)$ , with $\le$ read as $<$ ?
(c) In the triangle table, what are $q \cdot a$ and $a \cdot q$ ?
(d) Is $D = \{ a, b \}$ , $R^{\mathfrak{M}} = \{ (a, b), (b, a) \}$ a model of the equivalence relation axioms? Which of the three hold?
(e) Is $(\mathbb{Q} \setminus \{ 0 \}; \cdot, 1)$ , with the group’s $\cdot$ read as multiplication and $e$ as $1$ , a model of the group axioms?
(f) On $D = \{ a \}$ , which relations make a model of the strict order axioms? Of the partial order axioms?
(g) On $D = \{ a, b \}$ with $(a, b) \in R^{\mathfrak{M}}$ , add the fewest pairs that make $R^{\mathfrak{M}}$ an equivalence relation.
(h) Give a model of the dense strict linear order axioms other than $(\mathbb{Q}, <)$ .
(i) True or false: if $\sigma$ is false in some structure, then $T \nvdash \sigma$ .
(j) Is the empty theory consistent?
(k) Is the theory with the two axioms $\forall x\, \neg R(x, x)$ and $\forall x\, \forall y\, R(x, y)$ consistent?
(l) Give a model of the partial order axioms with three elements in which exactly one pair of different elements is comparable.

Solution.

(a) $\forall x\, \forall y\, (R(x, y) \to R(y, x))$ : whenever $x$ is related to $y$ , $y$ is related to $x$ .
(b) (Refl): $0 < 0$ is false.
(c) $q \cdot a = c$ and $a \cdot q = b$ .
(d) No. (Sym) holds; (Refl) fails, since there are no loops; (Trans) fails, since $(a, b)$ and $(b, a)$ are in $R^{\mathfrak{M}}$ and $(a, a)$ is not.
(e) Yes: multiplication is associative, $1$ is an identity, and each $d$ has the inverse $1/d$ , again a non-zero rational.
(f) Strict order: exactly $<^{\mathfrak{M}} = \emptyset$ . The loop $(a, a)$ breaks (Irrefl), and with no pairs (Trans) has no chain to check. Partial order: exactly $\le^{\mathfrak{M}} = \{ (a, a) \}$ ; with $\emptyset$ , (Refl) fails at $a$ .
(g) $(a, a)$ , $(b, b)$ and $(b, a)$ .
(h) $(\mathbb{R}, <)$ , or the rationals strictly between $0$ and $1$ with $<$ .
(i) False: the structure must be a model of $T$ . With $T = \{ \forall x\, R(x, x) \}$ and $\sigma$ the same sentence, $\sigma$ is false in every structure with $R^{\mathfrak{M}} = \emptyset$ , yet $T \vdash \sigma$ in one line.
(j) Yes: every structure is a model of it, so Proposition 7.4.2 applies.
(k) No: $\mathrm{\forall E}$ twice on the second axiom gives $R(x_0, x_0)$ , $\mathrm{\forall E}$ on the first gives $\neg R(x_0, x_0)$ , and $\mathrm{\neg E}$ gives $\bot$ . (Any variable or constant may be the term.)
(l) $D = \{ a, b, c \}$ , $\le^{\mathfrak{M}}$ the three loops and $(a, b)$ .

B. Practice

Exercise (B1: Construct a relation, or show none exists, used later)

On $D = \{ 1, 2, 3, 4 \}$ , give a relation that is:

(i) reflexive and transitive, but neither symmetric nor antisymmetric;
(ii) symmetric and transitive, not reflexive, with $1$ , $2$ and $3$ each related to something;
(iii) irreflexive, symmetric, transitive and non-empty; or show that no domain has one.
(iv) Which of your answers refutes the “proof” in the last warning of this section, and at which element?

Solution.

(i) $R$ = the four loops together with $(1, 2)$ , $(2, 1)$ , $(1, 3)$ , $(2, 3)$ . Reflexive: the loops. Transitive: the chains $(x, y), (y, z)$ of two non-loop pairs ( $x \ne y$ and $y \ne z$ ) are $(1, 2), (2, 1)$ , giving $(1, 1)$ ; $(2, 1), (1, 2)$ , giving $(2, 2)$ ; $(1, 2), (2, 3)$ , giving $(1, 3)$ ; and $(2, 1), (1, 3)$ , giving $(2, 3)$ ; all in $R$ , and a chain through a loop gives back its other pair. Not symmetric: $(1, 3)$ without $(3, 1)$ . Not antisymmetric: $(1, 2)$ and $(2, 1)$ with $1 \ne 2$ .
(ii) $R = \{ (1, 1), (1, 2), (2, 1), (2, 2), (3, 3) \}$ : symmetric and transitive (the classes $\{ 1, 2 \}$ and $\{ 3 \}$ ), not reflexive at $4$ .
(iii) None, on any domain. If $(d, e) \in R$ , symmetry gives $(e, d)$ , and transitivity applied to $(d, e), (e, d)$ gives $(d, d)$ , against irreflexivity.
(iv) (ii), at $4$ , which is related to nothing, so the “proof” has no $y$ to start from.

Used later: Section 7.5 comes back to the relation of (ii).

Marking scheme. (10 points) - 3: (i), a relation with all four properties checked, transitivity by listing the chains. - 2: (ii). - 3: (iii), the argument from an arbitrary pair. - 2: (iv). Fatal error (0 for (iii)): an argument that assumes every element is related to something.

Exercise (B2: A sentence true in one structure and false in the other)

For each pair, find a sentence true in the first structure and false in the second, and read it back in words.

(a) $(\mathbb{Z}; +, 0)$ and $(\mathbb{N}; +, 0)$ .
(b) $(\mathbb{Q}; \cdot, 0, 1)$ and $(\mathbb{Z}; \cdot, 0, 1)$ .
(c) $\mathfrak{M}_1$ : $D = \{ a, b, c \}$ , $R^{\mathfrak{M}_1} = \{ (a, b), (b, c) \}$ ; and $\mathfrak{M}_2$ : $D = \{ a, b, c \}$ , $R^{\mathfrak{M}_2} = \{ (a, b), (a, c) \}$ (drawn below).
(d) $\mathfrak{M}_2$ and $\mathfrak{M}_1$ , in that order.

Diagram: B2: A sentence true in one structure and false in the other. Labels: mathfrak M_1, mathfrak M_2

Solution. (a) $\forall x\, \exists y\, (x + y = 0)$ , “every element has an additive inverse”: true in $\mathbb{Z}$ , with $y = -x$ ; false in $\mathbb{N}$ at $1$ .

(b) $\forall x\, \bigl( \neg(x = 0) \to \exists y\, (x \cdot y = 1) \bigr)$ , “every non-zero element has a reciprocal”: true in $\mathbb{Q}$ , with $y = 1/x$ ; false in $\mathbb{Z}$ at $2$ .

(c) $\exists x\, \exists y\, \exists z\, (R(x, y) \wedge R(y, z))$ , “there is a path of two arrows”: in $\mathfrak{M}_1$ , $a$ , $b$ , $c$ ; in $\mathfrak{M}_2$ no arrow leaves $b$ or $c$ , so no path of two arrows exists.

(d) $\exists x\, \exists y\, \exists z\, (R(x, y) \wedge R(x, z) \wedge \neg(y = z))$ , “some element has arrows to two different elements”: in $\mathfrak{M}_2$ , $a$ , $b$ , $c$ ; in $\mathfrak{M}_1$ each element has at most one outgoing arrow.

Any other correct sentence earns full marks.

Marking scheme. (10 points) - 2.5 per part: 1 for a sentence true in the first structure (checked), 1 for false in the second (with the failing element), 0.5 for the reading back. Fatal error (0 for the part): a formula with a free variable.

Exercise (B3: Derive a theorem of a theory)

From the three group axioms, derive $\forall x\, (x \cdot x = x \to x = e)$ : the only element equal to its own square is the identity. Which axioms did you use? Show by a model that (Inv) cannot be left out.

Solution. Plan. Fix $x_0$ and assume $x_0 \cdot x_0 = x_0$ . Take an inverse $y_0$ by $\mathrm{\exists E}$ , multiply the assumption by $y_0$ on the left, and regroup: in words, $e = y_0 \cdot x_0 = y_0 \cdot (x_0 \cdot x_0) = (y_0 \cdot x_0) \cdot x_0 = e \cdot x_0 = x_0$ .

\forall x\, \forall y\, \forall z\, ((x \cdot y) \cdot z = x \cdot (y \cdot z))

\forall x\, (x \cdot e = x \wedge e \cdot x = x)

\forall x\, \exists y\, (x \cdot y = e \wedge y \cdot x = e)

x_0

x_0 \cdot x_0 = x_0

asm, for

\mathrm{{{\to}}I}

\exists y\, (x_0 \cdot y = e \wedge y \cdot x_0 = e)

\mathrm{{\forall}E}

y_0

x_0 \cdot y_0 = e \wedge y_0 \cdot x_0 = e

asm, for

\mathrm{{\exists}E}

y_0 \cdot x_0 = e

\mathrm{{\wedge}E}

\forall y\, \forall z\, ((y_0 \cdot y) \cdot z = y_0 \cdot (y \cdot z))

\mathrm{{\forall}E}

\forall z\, ((y_0 \cdot x_0) \cdot z = y_0 \cdot (x_0 \cdot z))

\mathrm{{\forall}E}

(y_0 \cdot x_0) \cdot x_0 = y_0 \cdot (x_0 \cdot x_0)

\mathrm{{\forall}E}

(y_0 \cdot x_0) \cdot x_0 = y_0 \cdot x_0

\mathrm{{=}E}

4, 10

e \cdot x_0 = y_0 \cdot x_0

\mathrm{{=}E}

7, 11

e \cdot x_0 = e

\mathrm{{=}E}

7, 12

x_0 \cdot e = x_0 \wedge e \cdot x_0 = x_0

\mathrm{{\forall}E}

e \cdot x_0 = x_0

\mathrm{{\wedge}E}

x_0 = e

\mathrm{{=}E}

15, 13

x_0 = e

\mathrm{{\exists}E}

5, 6–16

x_0 \cdot x_0 = x_0 \to x_0 = e

\mathrm{{{\to}}I}

4–17

\forall x\, (x \cdot x = x \to x = e)

\mathrm{{\forall}I}

4–18

The four $\mathrm{{=}E}$ steps, each with its $\varphi$ : line 11 with $\varphi$ the formula $(y_0 \cdot x_0) \cdot x_0 = y_0 \cdot w$ , line 10 being $\varphi[x_0 \cdot x_0 / w]$ ; line 12 with $w \cdot x_0 = y_0 \cdot x_0$ , line 11 being $\varphi[y_0 \cdot x_0 / w]$ ; line 13 with $e \cdot x_0 = w$ , line 12 being $\varphi[y_0 \cdot x_0 / w]$ ; line 16 with $w = e$ , line 13 being $\varphi[e \cdot x_0 / w]$ . At line 17, $y_0$ is not in $x_0 = e$ , not in line 5, in no premise and in no open assumption. At line 19, $x_0$ is in no premise, in no assumption open outside its box, and not in line 19.

All three axioms are used. (Inv) cannot be left out: $(\{ 0, 1 \}; \cdot, 1)$ , with the usual product and $e$ read as $1$ , satisfies (Assoc), since multiplication of numbers is associative, and (Id), since $0 \cdot 1 = 1 \cdot 0 = 0$ and $1 \cdot 1 = 1$ . But $0 \cdot 0 = 0$ and $0 \ne 1$ , so the theorem fails at $0$ . By Proposition 7.4.3 (a), it does not follow from (Assoc) and (Id) alone.

Marking scheme. (10 points) - 2: the plan (fix $x_0$ , assume $x_0 \cdot x_0 = x_0$ , take an inverse by $\mathrm{\exists E}$ ). - 3: the chain of equations, with each $\mathrm{{=}E}$ naming its $\varphi$ . - 2: the $\mathrm{\exists E}$ and $\mathrm{\forall I}$ side conditions checked: $\mathrm{\exists E}$ , $y_0$ not in $x_0 = e$ , not in $\exists y\, (x_0 \cdot y = e \wedge y \cdot x_0 = e)$ , in no premise and in no open assumption; $\mathrm{\forall I}$ , $x_0$ in no premise, in no assumption open outside its box, and not in $\forall x\, (x \cdot x = x \to x = e)$ . - 1: the axioms named. - 2: the model without (Inv), with (Assoc) and (Id) checked and the theorem failing at $0$ . Fatal errors (0 for the derivation): an $\mathrm{{=}E}$ step that replaces a term the line does not contain; using $y_0$ outside its $\mathrm{\exists E}$ box.

C. Going deeper

Exercise (C1: Describe every model)

Describe every model of each sentence, and prove your description.

(a) $\forall x\, \forall y\, (x = y)$ .
(b) $\exists x\, \exists y\, \neg(x = y) \wedge \forall x\, \forall y\, \forall z\, (x = y \vee x = z \vee y = z)$ .
(c) $\forall x\, \forall y\, R(x, y)$ .
(d) $\forall x\, \exists y\, \bigl( R(x, y) \wedge \forall z\, (R(x, z) \to z = y) \bigr)$ .

Solution. (a) “Any two elements are equal”: exactly the structures with one element. If $D$ has $d \ne e$ , then (S6) at $d$ and $e$ meets the equation $x = y$ with different values, which (S2) rejects. With one element, every equation between its values holds. Domains are non-empty, so “at most one element” is “exactly one”.

(b) “There are two different elements, and among any three, two are equal”: exactly the structures with two elements. The first conjunct gives two different elements $d \ne e$ . If a third $f$ differed from both, then $x, y, z$ at $d, e, f$ would make all three equations false. Conversely, in a two-element domain the two elements witness the first conjunct, and any three values repeat one of them.

(c) “Everything is related to everything”: exactly the structures with $R^{\mathfrak{M}} = D \times D$ , on any non-empty $D$ . By (S6) twice, every pair $(d, e)$ must be in $R^{\mathfrak{M}}$ , and if every pair is, the sentence holds.

(d) “Each element is related to exactly one element”: exactly the structures in which $R^{\mathfrak{M}}$ is the graph of a function from $D$ to $D$ , that is, each $d$ has exactly one $e$ with $(d, e) \in R^{\mathfrak{M}}$ . For each $d$ , (S7) gives an $e$ with $(d, e) \in R^{\mathfrak{M}}$ , and the inner $\forall z$ says that any $f$ with $(d, f) \in R^{\mathfrak{M}}$ is $e$ . Conversely, if each $d$ has exactly one such $e$ , that $e$ is the witness, and the inner clause holds by uniqueness.

Marking scheme. (10 points) - 2.5 per part: 1 for the description, 1.5 for both directions (every model is of this kind; every structure of this kind is a model). Fatal error (0 for (a)): forgetting that domains are non-empty, so that “at most one” is “exactly one”.

Exercise (C2: The partial order axioms are independent)

Show that each of (Refl), (Antisym) and (Trans), for $\le$ , is independent of the other two.

Solution. For (a) of Proposition 7.4.3, three structures:

Not (Refl): $D = \{ a, b \}$ , $\le^{\mathfrak{M}} = \{ (a, b) \}$ . Antisymmetric and transitive, vacuously: there is no pair $(b, a)$ and no chain of two arrows. No loops.
Not (Antisym): $D = \{ a, b \}$ , all four pairs. Reflexive and transitive; $a \le b$ and $b \le a$ with $a \ne b$ .
Not (Trans): $D = \{ a, b, c \}$ , the loops together with $(a, b)$ and $(b, c)$ . Reflexive; antisymmetric, since no two different elements are related both ways; $(a, c)$ is missing.

For (b), each axiom is also true in a model of the other two, for instance in $(\mathbb{N}, \le)$ , where all three hold. So each axiom is independent of the other two.

Marking scheme. (10 points) - 3 per axiom: the structure 1, the two other axioms checked 1, the failing pair 1. - 1: independence cited correctly, including that each axiom is true in some model of the other two. Fatal error (0 for the axiom): a structure in which one of the “other two” fails.

Exercise (C3: Exit check: a theory checked three ways)

Let $T$ be the theory of a strict linear order with a least element: (Irrefl), (Trans), (Tri), and $\text{(Least)} \quad \exists x\, \forall y\, (x = y \vee x < y).$

(a) Show that $T$ is consistent.
(b) Show that (Dense) is independent of $T$ .
(c) Derive from $T$ that the least element is unique: $\forall x\, \forall y\, \bigl( (L(x) \wedge L(y)) \to x = y \bigr)$ , where $L(x)$ abbreviates $\forall z\, (x = z \vee x < z)$ . You may use $\mathrm{TAUT}$ on the propositional skeleton.

Solution. (a) $(\mathbb{N}, <)$ is a model: no number is below itself, $<$ is transitive, any two numbers are equal or one is below the other, and $0$ is a least element. By Proposition 7.4.2, $T$ is consistent.

(b) In $(\mathbb{N}, <)$ , (Dense) fails at $0 < 1$ . The non-negative rationals with $<$ are a model of $T$ (no rational is below itself, $<$ is transitive, any two rationals are equal or one is below the other, and $0$ is least, since no non-negative rational is below it), in which (Dense) holds: between $p < q$ lies $(p + q)/2$ . By Proposition 7.4.3, (Dense) is independent of $T$ .

(c) Written out, $L(x_0)$ is $\forall z\, (x_0 = z \vee x_0 < z)$ . The plan: fix $x_0$ , $y_0$ , assume both are least, instantiate each at the other, and let a TAUT step combine the two disjunctions with (Irrefl) and (Trans) at $x_0$ , $y_0$ .

\forall x\, \neg(x < x)

\forall x\, \forall y\, \forall z\, ((x < y \wedge y < z) \to x < z)

x_0

y_0

\forall z\, (x_0 = z \vee x_0 < z) \wedge \forall z\, (y_0 = z \vee y_0 < z)

asm, for

\mathrm{{{\to}}I}

\forall z\, (x_0 = z \vee x_0 < z)

\mathrm{{\wedge}E}

\forall z\, (y_0 = z \vee y_0 < z)

\mathrm{{\wedge}E}

x_0 = y_0 \vee x_0 < y_0

\mathrm{{\forall}E}

y_0 = x_0 \vee y_0 < x_0

\mathrm{{\forall}E}

\neg(x_0 < x_0)

\mathrm{{\forall}E}

\forall y\, \forall z\, ((x_0 < y \wedge y < z) \to x_0 < z)

\mathrm{{\forall}E}

\forall z\, ((x_0 < y_0 \wedge y_0 < z) \to x_0 < z)

\mathrm{{\forall}E}

(x_0 < y_0 \wedge y_0 < x_0) \to x_0 < x_0

\mathrm{{\forall}E}

y_0 = x_0

asm, for

\mathrm{{{\to}}I}

y_0 = y_0

\mathrm{{=}I}

x_0 = y_0

\mathrm{{=}E}

12, 13

y_0 = x_0 \to x_0 = y_0

\mathrm{{{\to}}I}

12–14

x_0 = y_0

\mathrm{TAUT}

6, 7, 8, 11, 15

(\forall z\, (x_0 = z \vee x_0 < z) \wedge \forall z\, (y_0 = z \vee y_0 < z)) \to x_0 = y_0

\mathrm{{{\to}}I}

3–16

\forall y\, ((\forall z\, (x_0 = z \vee x_0 < z) \wedge \forall z\, (y = z \vee y < z)) \to x_0 = y)

\mathrm{{\forall}I}

3–17

\forall x\, \forall y\, ((\forall z\, (x = z \vee x < z) \wedge \forall z\, (y = z \vee y < z)) \to x = y)

\mathrm{{\forall}I}

3–18

Line 14 is $\mathrm{{=}E}$ with $\varphi$ the formula $z = y_0$ : line 13 is $\varphi[y_0 / z]$ , and line 12 says $y_0 = x_0$ , so the rule gives $\varphi[x_0 / z]$ . The TAUT step on line 16 reads the skeleton with the letters $A$ for $x_0 = y_0$ , $B$ for $x_0 < y_0$ , $C$ for $y_0 = x_0$ , $D$ for $y_0 < x_0$ and $E$ for $x_0 < x_0$ . From $A \vee B$ , $C \vee D$ , $\neg E$ , $(B \wedge D) \to E$ and $C \to A$ , the letter $A$ follows in every row: if $A$ is false, then $B$ is true; $C \to A$ makes $C$ false, so $D$ is true; then $E$ is true, against $\neg E$ . At line 18, $y_0$ is in no premise, no assumption is open outside its box, and $y_0$ is not in line 18; at line 19 the same holds for $x_0$ . Only (Irrefl) and (Trans) were used.

Marking scheme. (10 points) - 2: (a), a model with every axiom checked. - 3: (b), two models of $T$ (the axioms checked for the new one), with (Dense) checked in each. - 4: (c), the derivation: the case $y_0 = x_0$ closed, by symmetry of $=$ via $\mathrm{{=}I}$ and $\mathrm{{=}E}$ or by $\mathrm{{=}E}$ into $x_0 < y_0$ (1), the instance of (Trans) at $x_0$ , $y_0$ , $x_0$ , reached by three $\mathrm{\forall E}$ steps (1), the cases combined, by a TAUT step whose skeleton is a tautology or by an equivalent $\mathrm{\vee E}$ and $\mathrm{\bot E}$ case analysis (1), the $\mathrm{\forall I}$ side conditions (1). - 1: names the axioms used. Fatal error (0 for (c)): a TAUT step that needs $y_0 = x_0$ and $x_0 = y_0$ to be the same letter (they are not).