Matpic
mathematics, in pictures
Series

Models — the series

8 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A line, a point, and many parallels. A disc whose lines are arcs meeting the boundary at right angles, showing several lines through one point that never meet a given line.

    Two worlds that both obey the rules

    A statement is independent of a list of axioms when there is a structure satisfying the axioms where it holds and another where it fails. That is not a claim about what nobody has managed to prove — it is a proof that nobody can.

    part 1 · logic
  2. A tree branching at most 3 ways, to depth 4, and the path through it. A tree drawn level by level, with the nodes that die out faint and a highlighted path that always steps to a node with descendants at the bottom.

    An infinite tree has an infinite path

    A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.

    part 2 · logic
  3. The order type of a nonstandard model of arithmetic. The ordinary numbers as a run of dots, followed by 9 galaxies — copies of the integers — at the positions of c/2 up to 2c, ordered densely like the rationals, with c² beyond. Infinitely many more galaxies lie between those drawn.

    A number larger than every number

    Ask for a number bigger than 0, bigger than 1, bigger than 2, and so on for ever. Every finite piece of that request is granted by an ordinary number, so compactness grants all of it at once — in a structure that satisfies every sentence true of the whole numbers and still contains something beyond all of them. Nothing in first-order logic can say 'and nothing else'.

    part 3 · logic
  4. A countable structure grown by adding witnesses. Stages of a structure built from 0 and 1 by adding sums, products, negatives and roots of quadratics: 2, 4, 12, 158 elements between −3 and 3.

    A countable field that passes for the line

    The real numbers are uncountable, and every first-order sentence about their addition, multiplication and order is also true of a countable field inside them — the real algebraic numbers. Löwenheim and Skolem showed this is no quirk of the reals: every theory with an infinite model has a countable one, including set theory, which then contains sets it calls uncountable.

    part 4 · logic
  5. The rationals and the dyadic fractions, matched 12 times without a crossing. Two number lines from 0 to 1, rationals above and dyadic fractions below, with 12 back-and-forth matchings: 1/2↔1/2, 1/3↔1/4, 2/3↔3/4, 1/4↔1/8, 3/4↔7/8, 2/5↔3/8, 1/5↔1/16, 3/5↔5/8, 4/5↔15/16, 2/7↔3/16, 1/6↔1/32, 3/8↔5/16.

    Two lists that are one order

    The rationals and the fractions with a power of two below are different sets of numbers, and as orders they are exactly the same — any two countable orders that are dense and have no ends can be matched, point for point, keeping every comparison. The proof is a zigzag, and it settles every question the language of order can ask.

    part 5 · logic
  6. The first 16 vertices of Rado's graph, joined by binary digits. Adjacency table and circular drawing of the Rado graph on vertices 0 to 15, where i < j are adjacent when bit i of j is 1; 32 edges.

    The graph that coin tosses always make

    Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

    part 6 · logic
  7. Which Paley graphs answer every small request. size 2: first passes at 13; size 3: first passes at 29; size 4: first passes at 89; primes checked up to 113.

    The squares that answer every request

    Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.

    part 7 · logic
  8. Three countable models of one theory, different only above the constants. Models A (cₙ = n), B (cₙ = −1/(n+1), supremum 0), C (cₙ = 1, 7/5, 41/29, … rising to √2, no supremum) of the theory of a dense order with increasing constants.

    Three models and never two

    Take the theory of a dense order and add constants c₀ < c₁ < c₂ < … running upward for ever. The theory is complete — it decides every sentence — and yet it has exactly three countable models, told apart only by what lies above all the constants: nothing, a least point, or a gap with no least point. Vaught proved in 1961 that no complete theory has exactly two, and the proof builds this theory's third model out of its other two.

    part 8 · logic

All series