Logic as a Mathematical Model of Deduction

Symbolic logic is a mathematical model of deductive thought.¹ It stands to reasoning roughly as probability theory stands to chance: a precise mathematical structure that captures some features of a messy real phenomenon and ignores the rest. The phenomenon here is the logically correct deduction — the kind of inference a working mathematician makes when asserting that a sentence follows from the axioms. The subject builds a formal object that mirrors those inferences closely enough to study them with the tools of mathematics.

The word logic sometimes names remedial thinking; that is not the sense in use here. The subject does not aim to improve anyone's reasoning. It turns reasoning into an object — a thing with a definition, subject to theorems — and proves things about it.

The modeling stance

A model is made by selection. Begin with a real object, an airplane, and choose which of its properties to represent. Its shape is essential to how it flies, so the model keeps the shape; its full size is irrelevant to a wind-tunnel test, so the model discards the size. Whether the model serves its purpose depends entirely on that choice of what to keep and what to throw away.

Modeling is selection: a scale model keeps an airplane's shape and drops its size, exactly as sentential and first-order logic keep the form of a deduction and drop its subject matter.

The real objects of logic are certain correct deductions. The property to be kept is their form; the property to be discarded is their content. A precise version of that criterion — correct by form, independent of content — is the first thing the model must deliver, and pinning it down is what motivates the turn to mathematics.

Validity is a property of form

Consider the standard example.

The inference is valid by its shape alone; replacing the words with nonsense preserves the validity, so the correctness cannot depend on what the words mean.

We recognize that the conclusion follows from the premises. That recognition does not draw on any fact about Socrates, and it does not need the meaning of mortal — only the meaning of all. Replace every content word with nonsense and it remains valid: from all borogoves are mimsy and this thing is a borogove it still follows that this thing is mimsy. Correctness is due to form and is independent of content.

The criterion is vague, and that vagueness is what forces a formal model. Axiomatic mathematics is a long chain of such deductions laid end to end. When a mathematician says a sentence follows from the axioms of set theory, the claim is that the deduction can be translated into the model. Giving follows from and translated into the model a mathematical meaning is the whole task.

Two models, coarse and fine

The book presents two models, in order of increasing fidelity.

Sentential logic is the coarse model. It resolves a compound sentence into atomic parts joined by connectives (not, and, or, if–then), and tracks how truth of the whole depends on truth of the parts. It preserves only crude properties of real deductions and is inadequate for interesting mathematics, but it is simple enough to analyze completely.
First-order logic is the fine model. It adds quantifiers (for all, there exists), variables, predicates, and equality, and is well suited to the deductions that arise in mathematics. Most of the subject works in this model because of that expressive reach.

The first-order language reaches statements the sentential one cannot. The set-theoretic principle of extensionality — if the same things are members of one object as of another, those objects are equal — translates to

\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y),

and the calculus definition of a limit — for every positive $ε$ there is a positive $δ$ such that any $x$ within $δ$ of $a$ has $f (x)$ within $ε$ of $b$ — translates to

\forall ε (ε > 0 \to \exists δ (δ > 0 \land \forall x (d x a < δ \to d f x b < ε))) .

Neither statement is expressible in the coarse sentential model; both are routine in the fine one. The language of sentential logic is where the coarse model is built; first-order languages begin the fine one.

The difference between the two models shows in a single inference. The Socrates syllogism is valid, yet the coarse model cannot see why.

Worked example. Formalize All men are mortal; Socrates is a man; therefore Socrates is mortal in each model, and locate where the validity becomes visible.

Sentential logic reads three unanalyzed atomic sentences:

A : all men are mortal, B : Socrates is a man, C : Socrates is mortal .

The argument is ${A, B}$ with conclusion $C$ . Nothing ties the three atoms together, so the assignment making $A$ and $B$ true and $C$ false meets both premises while denying the conclusion. The coarse model therefore rates the inference invalid; it cannot look inside the sentences.

First-order logic analyzes that internal structure. Take a one-place predicate $M x$ for $x$ is a man, $H x$ for $x$ is mortal, and a constant $s$ naming Socrates:

{\forall x (M x \to H x), M s} ⊨ H s .

Every structure satisfying both premises satisfies $H s$ : instantiate the universal premise at $s$ to get $M s \to H s$ , then detach using $M s$ . The fine model rates the inference valid, matching the informal judgment that the form alone forces the conclusion.

The detachment step — from $φ \to ψ$ and $φ$ infer $ψ$ — already lives in the coarse model as a tautology, a schema true under every assignment of truth values.

Worked example. Verify that $((P \to Q) \land P) \to Q$ is a tautology by evaluating it on all four assignments to $P$ and $Q$ .

$P$	$Q$	$P \to Q$	$(P \to Q) \land P$	$((P \to Q) \land P) \to Q$
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

The final column is constant $T$ , so the schema holds under every assignment. Being a tautology depends only on the connectives, never on what $P$ and $Q$ mean. This is the part of the syllogism the coarse model does capture; the quantifier step it misses.

The choice to model mathematical deduction, rather than reasoning in general, fixes the scope. Many-valued, modal, and intuitionistic logics make different selections of which properties of real deductions to keep, and none of them appears here.

The four questions

Once the model exists, four questions organize everything that follows.

What does it mean for one sentence to follow logically from others? This is the semantic question: it is answered by defining truth in a structure and calling $φ$ a consequence of $Γ$ when every structure making all of $Γ$ true also makes $φ$ true.
If a sentence does follow, what methods of proof establish it? This is the syntactic question: it is answered by a deductive calculus with axioms and rules, giving a notion of formal proof.
Is there a gap between what an axiom system can prove and what is true? For arithmetic, this asks whether provability and truth coincide.
What is the connection between logic and computability? This asks which logical questions can be settled by an algorithm.

The four questions and the theorems that answer them, in the order the subject develops; questions 1 and 2 are tied together by soundness and completeness, questions 3 and 4 by the incompleteness and undecidability results.

Questions 1 and 2 are linked. Semantics gives a relation $Γ$ semantically implies $φ$ ; the deductive calculus gives a relation $Γ$ proves $φ$ . The soundness theorem shows every proof yields a genuine consequence, and the completeness theorem shows every consequence has a proof, so the two relations coincide. Questions 3 and 4 have a sharper edge: for arithmetic, provability and truth do not coincide (incompleteness), and validity is not decidable by any algorithm, drawing the boundary the recursive functions make precise.

Question 1 pins consequence to truth in a structure, and that truth is computed one quantifier at a time. The same sentence can come out true on one structure and false on another.

The set-theoretic toolkit

The model is built inside ordinary mathematics, and its raw material is sets.² The notation below is standard and appears without further comment throughout. Each piece is used where it is needed: Zorn's lemma in the completeness proof, cardinals in the Löwenheim–Skolem theorems.

Sets and extensionality. A set is determined solely by its members. Formally, if $A$ and $B$ have exactly the same elements, then $A = B$ :

(\forall t (t \in A \leftrightarrow t \in B)) ⟹ A = B .

Basic constructions follow: the empty set $\emptyset$ , the singleton ${x}$ , the finite set ${x_{1}, \dots, x_{n}}$ , union $A \cup B$ , intersection $A \cap B$ , and the power set $P A = {x ∣ x \subseteq A}$ of all subsets of $A$ . For a set $A$ whose members are themselves sets, $⋃ A$ collects everything belonging to some member, and $⋂ A$ everything belonging to all members. Two sets are disjoint when $A \cap B = \emptyset$ , and a collection is pairwise disjoint when any two of its members are disjoint.

Ordered tuples and sequences. An unordered pair satisfies ${x, y} = {y, x}$ , so it cannot record order. The ordered pair $⟨ x, y ⟩$ is defined so that it recovers both components in order:

⟨ x, y ⟩ = ⟨ u, v ⟩ iff x = u and y = v .

Any construction with this property serves; the standard one is $⟨ x, y ⟩ = {{x}, {x, y}}$ . Triples reduce to pairs by $⟨ x, y, z ⟩ = ⟨⟨ x, y ⟩, z ⟩$ , and $n$ -tuples recursively by $⟨ x_{1}, \dots, x_{n + 1} ⟩ = ⟨⟨ x_{1}, \dots, x_{n} ⟩, x_{n + 1} ⟩$ , with the convention $⟨ x ⟩ = x$ . A finite sequence (or string) over $A$ is an $n$ -tuple $⟨ x_{1}, \dots, x_{n} ⟩$ with each $x_{i} \in A$ ; expressions in a formal language will be exactly such strings.

The reduction of tuples to nested pairs carries one hazard, and unique readability of formulas later depends on avoiding it.

The lemma says a shorter tuple can equal a longer one only when the first component of the shorter is itself a sequence of the extra entries. The consequence used repeatedly: if no member of $A$ is a finite sequence of other members of $A$ , then $⟨ x_{1}, \dots, x_{m} ⟩ = ⟨ y_{1}, \dots, y_{n} ⟩$ with all entries in $A$ forces $m = n$ and $x_{i} = y_{i}$ . A well-designed alphabet has this no symbol is a string of symbols property, which is why the parsing of formulas is unambiguous.

Relations and functions. The Cartesian product $A \times B$ is the set of pairs $⟨ x, y ⟩$ with $x \in A$ and $y \in B$ , and $A^{n}$ is the set of $n$ -tuples over $A$ . A relation is a set of ordered pairs; an $n$ -ary relation on $A$ is a subset of $A^{n}$ . Its domain, range, and field are the sets of first components, second components, and both together. A function $F$ is a single-valued relation: each $x \in dom (F)$ has exactly one $y$ with $⟨ x, y ⟩ \in F$ , written $y = F (x)$ . We write $F : A \to B$ when $dom (F) = A$ and $ran F \subseteq B$ ; the map is onto when $ran F = B$ and one-to-one when each value comes from a single argument. An $n$ -ary operation on $A$ is a function $A^{n} \to A$ ; a subset $B \subseteq A$ is closed under $f$ when $f (b_{1}, \dots, b_{n}) \in B$ whenever every $b_{i} \in B$ . Every inductive definition in the subject, well-formed formulas included, is built by closure under a family of operations.

Properties of relations. For a binary relation $R$ on $A$ :

Reflexive on $A$ : $⟨ x, x ⟩ \in R$ for every $x \in A$ .
Symmetric: $⟨ x, y ⟩ \in R$ implies $⟨ y, x ⟩ \in R$ .
Transitive: $⟨ x, y ⟩ \in R$ and $⟨ y, z ⟩ \in R$ imply $⟨ x, z ⟩ \in R$ .
Trichotomy on $A$ : for all $x, y \in A$ , exactly one of $⟨ x, y ⟩ \in R$ , $x = y$ , $⟨ y, x ⟩ \in R$ holds.

An equivalence relation on $A$ is reflexive on $A$ , symmetric, and transitive. An ordering relation on $A$ is transitive and satisfies trichotomy.

Equivalence relations and partitions

Equivalence relations recur throughout the subject: identifying provably equal terms in the completeness proof, and identifying sentences with the same truth conditions, both work by passing to equivalence classes.

The correspondence runs both ways. Every equivalence relation carves $A$ into disjoint classes that cover it; every partition of $A$ into disjoint blocks defines an equivalence relation, $x$ and $y$ lie in the same block.

An equivalence relation cuts a set into disjoint classes that together cover it; two elements are related exactly when they fall in the same class.

Cardinality

Size is compared by matching, not counting. Sets $A$ and $B$ are equinumerous, written $A \sim B$ , when some one-to-one function maps $A$ onto $B$ . This is reflexive, symmetric, and transitive, and it agrees with ordinary counting on finite sets while extending to infinite ones.

Two facts about countability are used constantly when the language is countable.

The proof codes a sequence $⟨ a_{0}, \dots, a_{m} ⟩$ by the number $2^{f (a_{0}) + 1} 3^{f (a_{1}) + 1} \dots p_{m}^{f (a_{m}) + 1}$ , a product of prime powers whose exponents recover the entries. The same prime-power coding, scaled up, is the mechanism behind the arithmetization of syntax in the incompleteness theorems. Since a formal language has countably many expressions, its set of formulas and its set of finite proofs are both countable.

Not everything is countable. To be dominated by $B$ , written $A ⪯ B$ , is to be equinumerous with a subset of $B$ ; a set is countable exactly when $A ⪯ N$ . The cardinals are ordered: for any $κ$ and $λ$ , either $κ \leq λ$ or $λ \leq κ$ , and any nonempty set of cardinals has a least member. The finite cardinals $0, 1, 2, \dots$ are followed by the least infinite cardinal $ℵ_{0} = card N$ , and Cantor's theorem gives a strictly larger one:

ℵ_{0} < 2^{ℵ_{0}} = card R .

The reals are uncountable. So is $P (N)$ , which has the same size $2^{ℵ_{0}}$ . The distinction between countable and uncountable is why the Löwenheim–Skolem theorems have force: a first-order theory cannot constrain its models to a single size across that gap.

The size ladder used throughout: naturals, integers, and rationals all share the countable cardinality below Cantor's gap; the reals and the power set of the naturals sit at the uncountable size above it.

The axiom of choice and Zorn's lemma

A handful of arguments need a nonconstructive principle: given infinitely many nonempty sets, a single function can select one member from each. This is the axiom of choice. Its uses in this subject can usually be eliminated when the language is restricted to be countable, but stating the general theorems cleanly is easier with it. The form that appears in proofs is Zorn's lemma. Call a collection $C$ of sets a chain when any two of its members are comparable under $\subseteq$ .

The pattern is always the same. Order some family of good sets by inclusion; check that unions of chains stay good; conclude a maximal good set exists. In the completeness theorem the good sets are the consistent sets of sentences, and the maximal one is a maximal consistent set from which a model is read off.

Enderton, Introduction — logic as a mathematical model of deductive thought, the airplane analogy for model-building, validity as form independent of content, and the four organizing questions. ↩
Enderton, Ch. 0 — Useful Facts about Sets: extensionality, ordered tuples and Lemma 0A, relations and functions, equivalence relations and partitions, countability (Theorem 0B), cardinal comparison and Cantor's theorem, the axiom of choice and Zorn's lemma. ↩