Level B1 · Intermediate

Formal Logic

"God, grant me the serenity to accept the things I cannot change, courage to change the things I can, and wisdom to know the difference." The Serenity Prayer, Reinhold Niebuhr

Level B1 is where the language stops being descriptive and becomes a tool for competent thought: propositional and predicate logic get built rigorously, symbol by symbol, and models turn syntax into something that can be checked against a semantics — culminating in Gödel's two most famous theorems.

What you'll learn

1. From speaking to thinking

The formalization of logic itself — turning it into an object of mathematical study — was a defining project at the turn of the 20th century: Frege, Russell and Whitehead's Principia Mathematica, and Hilbert's program, all aimed at rigorous axiomatic systems for logic strong enough to rebuild the whole of mathematics. At Level B1, the book follows the same path: propositional formulas are defined by exactly three rules (every variable is a formula; combinations under $\neg,\land,\lor,\to$ are formulas; nothing else is), and everything from there — derivability, soundness, completeness — is built strictly on top of that syntax.

The payoff is a genuine shift in what the language can do. Up through Level A2, $\Math$ described things. Now it can certify that a description follows from other descriptions — the difference between being able to speak a language and being able to reason competently in it.

2. Consistent if and only if it has a model

A theory is consistent if no formula and its negation are both derivable from it; it is satisfiable if it has a model — some structure in which all of its theorems come out true. These sound like different properties: one is about proofs, the other about semantics. Gödel's Completeness Theorem for predicate logic says they're the same property, stated as a single criterion.

Gödel's Completeness Theorem (as a criterion)
A theory is consistent if and only if it is satisfiable (has a model).

The two directions of this criterion have very different weights. Gödel proved the substantial one, left-to-right — consistent $\Rightarrow$ satisfiable — by building a model out of nothing but the language's own terms: every constant symbol goes into the universe, and every true existential formula contributes a "witness" term expressible in the language itself. The converse, right-to-left, is comparatively trivial: it follows directly from the soundness of predicate calculus with respect to models — if every axiom of a theory is true in some structure, then by induction on the length of a derivation, every formula derivable from those axioms is true there too, so a theory with a model can never derive both $\varphi$ and $\neg\varphi$.

An equivalent formulation of the same criterion: $\Gamma\Vdash\varphi$ is equivalent to $\Gamma\vdash\varphi$ — semantic consequence and syntactic derivability turn out to be exactly the same relation in classical predicate logic.

Incompleteness then draws the boundary: pure predicate logic, the theory of orders, of equality, of groups — all consistent and complete relative to the metatheory. The moment a theory can talk about its own provability (as Peano Arithmetic can, via Gödel numbering), completeness is lost — a fact independent formulas like the Axiom of Choice relative to $\mathsf{ZF}$, or Euclid's fifth postulate relative to absolute geometry, turn out to instantiate again and again.

3. Try it yourself

The first five exercises from the chapter's problem set, from the English edition.

  1. Determine which of the following are tautologies (always true):
    1. $(A \to B) \to (\neg B \to \neg A)$;
    2. $((A \to B) \to A) \to A$ (Peirce's Law);
    3. $(A \to B) \lor (B \to A)$ (Linearity of implication);
    4. $(A \land B) \to (A \lor B)$.
  2. Find a valuation (assignment of $0/1$ to $A, B, C$) that makes the following formulas false:
    1. $(A \lor B) \to (A \land B)$;
    2. $(A \to B) \to A$;
    3. $(A \lor B) \land C \to A \land (B \lor C)$.
  3. Using De Morgan's laws and double negation, simplify:
    1. $\neg(A \lor \neg B)$;
    2. $\neg(A \to (B \land \neg C))$;
    3. $\neg(\forall x \exists y (\varphi(x, y) \to \neg \psi(x)))$.
  4. Following the book's convention, free variables (parameters) are denoted by letters $a, b, c$, and bound variables by $x, y, z$. Rewrite the following "raw" formulas to comply with this convention:
    1. $\forall k (P(k) \to Q(m))$;
    2. $(\forall x P(x)) \land Q(x)$ (hint: the second $x$ is free);
    3. $\exists z (u < z \to \forall u (u = z))$ (hint: resolve the collision of $u$);
    4. $\int_0^x t^2\,dt$ (interpret the upper limit as a parameter).
  5. Let $\varphi = \exists y (a < y)$ (where $a$ is free).
    1. Perform the substitution $\varphi[a/b]$.
    2. Perform the substitution $\varphi[a/S(b)]$.
    3. Explain why the substitution $\varphi[a/y]$ is forbidden (invalid) in our logic.

Level B1 has 20 exercises in total, each with a full worked solution in the book's appendix.

The rest of Level B1 — and two more levels

This digest skips the full construction of the propositional and predicate languages with parenthesis- reduction rules, the deduction theorem, the axioms of equality and congruence, the recipe for building a formal theory from scratch, and worked examples — theories of orders, equality, semigroups and groups. Levels B2 and C1 apply this exact machinery to Peano Arithmetic and then to the full universe of sets.

← Level A2 — At the Threshold of Logic Level B2 — The Foundations of Mathematics →