Models and Theories

The axioms of a partial order say that $\le$ is reflexive, antisymmetric and transitive. Do they prove that any two elements are comparable, $\forall x\, \forall y\, (x \le y \vee y \le x)$ ? A search for a derivation stalls, and a stalled search proves nothing. Two dots settle it: a domain $\{ a, b \}$ in which each element is $\le$ itself and nothing else. All three axioms are true there and comparability is false, so, by a statement of Section 7.2, no derivation exists. What does “true there” mean, and why does one picture rule out every derivation? This chapter answers both, and then uses such pictures on whole theories: in Section 7.4, “is every group commutative?” is answered by the six symmetries of a triangle.

How to read this chapter. First reading: Sections 7.1, 7.2 and 7.4, and Section 7.5 up to “Isomorphic structures”. Second pass: the rest of Section 7.5. Optional: Sections 7.3 and 7.6. The statement that a counter-model rules out every derivation is on the trunk, in Section 7.2; its proof is optional, in Section 7.3. Nothing on the first-reading list uses anything off it.

Before you start: five tempting claims. Each is a claim this chapter corrects; decide each now, and check again at the section named.

Quick check.

“ $\forall x\, \exists y\, (x < y)$ is true.”
“A search for a derivation of $\Gamma \vdash \varphi$ stalled, so $\Gamma \nvdash \varphi$ .”
“If $\sigma$ is true in $(\mathbb{N}, <)$ , then $\sigma$ is derivable.”
“Every group is commutative: the integers under addition are.”
“ $(\mathbb{N}, <)$ and the even numbers with $<$ can be told apart by some sentence, since one is part of the other.”

Second readingAnswers

Not until a structure is fixed: true in $(\mathbb{N}, <)$ , false in $(\{ 1, 2, 3 \}, <)$ (Section 7.1).
No. A stalled search proves nothing; a counter-model does (Section 7.2).
No. Derivable sentences are true in every structure; $\forall x\, \exists y\, (x < y)$ is true in $(\mathbb{N}, <)$ and false in a three-element order (Section 7.2).
No. The six symmetries of a triangle form a group in which two motions done in the two orders differ (Section 7.4).
No. Doubling matches them element for element and order for order, and matched structures satisfy the same sentences (Section 7.5, second pass).

What you need. Chapters 1–6, above all the semantics of Chapter 4 (rows, $\models$ , soundness) and the quantifier rules of Chapter 5. Section 7.5’s second half uses functions and bijections in their everyday sense.

Time. About 20 hours on the core track (Sections 7.1, 7.2, 7.4 and the first half of 7.5: all of A, one B and one C per section, the exit checks); about 45 hours for everything.

Minimum before Sets, Relations, and Cardinality. Chapters 1–6 and 8, core; Sections 7.1–7.2 before its Chapter 3; Sections 7.4–7.5 recommended.

Roadmap

Structures and Satisfaction. A domain and a meaning for every symbol, an assignment for the free variables, clauses that decide every formula; finite structures drawn; proofs by meaning.
Counter-models. Three pictures, a procedure for finding one, small domains by expansion, each side condition of Chapter 5 broken, and the statement that a counter-model rules out every derivation.
Soundness for Predicate Logic (optional). The proof of that statement, by Chapter 4’s induction.
Theories and Their Models. Axioms as sentences, consistency by a model, independence by two models.
Definability and Isomorphism. A formula defines a set; $\exists$ is a projection. Second pass: isomorphic structures satisfy the same sentences; automorphisms move what is not definable.
What First-Order Logic Can and Cannot Say (optional). Completeness, compactness, non-standard numbers, undecidability, all stated without proof.

Named moves

Refute with a model. One structure with the premises true and the conclusion false. (Section 7.2)
Prove by meaning, clause by clause. Unwind the premises and the conclusion through (S1)–(S7). (Section 7.1)
Search for a counter-model. Start from the counterexample set, meet the existential demands first, add only forced elements. (Section 7.2)
Expand over a small domain. On two or three elements a quantifier is a long $\wedge$ or $\vee$ . (Section 7.2)
Consistent by a model; independent by two models. (Section 7.4)
Define by a formula. (Section 7.5)
An automorphism moves what cannot be defined. (Section 7.5, second pass)

Where this goes. Sets, Relations, and Cardinality, Chapter 1 develops the sets, pairs and functions that Sections 7.1 and 7.5 use in their everyday sense, and its Chapter 3 builds a counter-model by Section 7.2’s procedure; its Chapter 2 studies the relations of Section 7.4.

Summary

A structure fixes a domain and a meaning for every symbol, an assignment fixes the free variables, and seven clauses decide every formula (Definition 7.1.3); a sentence is true or false in a structure, never “true” alone. A counter-model makes the counterexample set true; by soundness for predicate logic (stated in Section 7.2, proved in the optional Section 7.3) it rules out every derivation: the stalled searches of Chapters 5 and 6 become theorems of non-derivability, and each side condition of the quantifier rules is shown needed. A theory is a set of axioms (Definition 7.4.1); a model shows it consistent (Proposition 7.4.2), and two models show a sentence independent of it (Proposition 7.4.3), as the antichain does for comparability and the triangle for commutativity. Formulas define sets (Definition 7.5.1), and, on the second pass, isomorphic structures satisfy the same sentences (Theorem 7.5.1).

Proved: the semantics, and every non-derivability result the chapter gets from a counter-model, given the soundness statement. Stated without proof: the undecidability of derivability (Church and Turing; Section 7.2, again in 7.6) and the $2^k$ bound on counter-models of monadic claims (Section 7.2); in the optional Section 7.6, completeness (every consistent theory has a model), compactness, the Löwenheim–Skolem theorem and the decidability of monadic sentences; and, in the solution to Exercise R2 of Section 7.5, that $P \wedge Q$ cannot be derived from its premise without $\mathrm{RAA}$ (nothing depends on it). Beyond this volume: why no consistent theory whose axioms a procedure can list, and which derives the basic facts of arithmetic, decides every sentence about $\mathbb{N}$ (Gödel’s incompleteness theorem, named in Section 7.6). Chapter 8 turns derivations into the prose of mathematics.

Terms

assignment: a value for each variable (Definition 7.1.2).
automorphism: an isomorphism onto itself (Definition 7.5.2).
consistent, inconsistent theory: no finite list of axioms derives $\bot$ (Definition 7.4.3).
counter-model: premises true, conclusion false (Definition 7.1.4).
definable set: the elements where a formula holds (Definition 7.5.1).
domain: what a structure’s quantifiers range over (Definition 7.1.1).
independent sentence: neither derivable nor refutable (Proposition 7.4.3).
isomorphism of structures: a bijection respecting every symbol (Definition 7.5.2).
model of a theory: a structure with every axiom true (Definition 7.4.2).
satisfaction, $\mathfrak{M}, \ell \models \varphi$ : the clauses (S1)–(S7) (Definition 7.1.3).
semantic entailment, $\Gamma \models \varphi$ : no counter-model (Definition 7.1.4).
structure: a domain and a meaning for every symbol (Definition 7.1.1).
theory, $T \vdash \sigma$ : a set of axioms; derivable from finitely many (Definition 7.4.1).
true in a structure, $\mathfrak{M} \models \sigma$ : satisfied under every assignment (Section 7.1).