Matpic
mathematics, in pictures
Concept

Consistency

The property of a set of assumptions from which no statement and its own negation can both be derived. It is what a model establishes, by exhibiting a world in which every assumption holds at once.

Named by 13 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

logic · Models Does this set contain that one — and the row that is missing. A membership table with the diagonal marked, and beneath it the complement of the diagonal, which is not among the rows.

A list that cannot contain itself

The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.

logic · Diagonalisation The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

The sentence that says it has no proof

Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

logic · Diagonalisation 3 consistent judges, and a majority that is not. A table of judges against three questions, every judge's row internally consistent, with the majority answer to each question underneath forming a combination no judge holds.

The court that contradicts itself

Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole endorses a combination no member of it holds, and no rearrangement of the procedure removes the problem.

applied · Judgement aggregation The tower of sizes, and the gap in it. A tower of infinite sizes, each the number of sub-collections of the one below, with the space between the first two marked as the one no proof decides.

The size that cannot be pinned down

There is no largest infinity, because no collection has as many members as it has sub-collections. What is not settled is whether anything sits between the first two — and that is not an open problem but a proved absence of an answer.

logic · Cardinality A model whose worlds are sets of sentences. Worlds labelled by which of a fixed finite set of formulas they accept, with an arrow wherever every boxed formula accepted by one has its inside accepted by the other.

Worlds built out of sentences

A Kripke model needs worlds, and nothing so far has said where worlds come from. They can be made of the syntax: a world is a set of formulas it commits to, one world sees another when the boxed commitments line up, and in the model that results every formula is true exactly where it was assumed.

logic · Modal logic 16 rules, and none that survives. A table of every systematic anonymous aggregation rule for 3 judges: one row per rule, showing the verdict it gives at each count of yes-votes, whether it decides every proposition, and whether it is consistent. No row has both.

No rule escapes the doctrinal paradox

A court whose members each hold a consistent position can reach an inconsistent verdict by majority. One such case is easy to build, which invites the hope that a better rule would avoid it — and every rule that responds to the votes at all fails somewhere.

applied · Judgement aggregation Where the two procedures part company. A table of 3 judges' verdicts on two premises and the conclusion each is committed to, with the two majorities at the foot disagreeing about the conclusion.

Deciding the premises or the conclusion

A body that cannot be both decisive and coherent has to choose which. The two live options are to vote on the reasons and let the verdict follow, or to vote on the verdict and let the reasons look after themselves — and they reach opposite answers on exactly the profiles the impossibility identifies.

applied · Judgement aggregation 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'.

logic · Models A countable closed set stripped of its isolated points, 3 times. Cantor–Bendixson derivatives of the set of sums of up to 2 reciprocals: sizes 750, 40, 1, 0 in the truncation, ending empty.

Closed sets obey the continuum hypothesis

Whether some set of reals is bigger than the whole numbers and smaller than the line is a question the axioms cannot answer. For closed sets it has an answer, found in 1883: strip away the isolated points, again and again, and what is left is either nothing or a perfect set, which is as large as the line — so every closed set is countable or of the line's size. The same answer holds for Borel and analytic sets, and fails to be provable exactly one step further up.

logic · Cardinality Three truth values, two of which count as holding. Truth tables of negation, conjunction and disjunction in the logic of paradox, with the values that count as holding — both and true — shaded.

A contradiction that stays where it is

In classical logic one contradiction proves everything: from p and not-p, any q at all. Add a third truth value — both true and false — and count it as holding, and the explosion stops. The classical laws all survive as laws; what goes is exactly the reasoning that carries a contradiction somewhere it was not. Run the other way, the same three tables make a logic of gaps instead of gluts.

logic · Non classical logic Ackermann's function as one polymorphic term. A : N → N → N; A(0,0)=1 in 6 steps, A(0,1)=2 in 6 steps, A(0,2)=3 in 6 steps, A(0,3)=4 in 6 steps, A(0,4)=5 in 6 steps, A(0,5)=6 in 6 steps, A(1,0)=2 in 10 steps, A(1,1)=3 in 13 steps, A(1,2)=4 in 16 steps, A(1,3)=5 in 19 steps, A(1,4)=6 in 22 steps, A(1,5)=7 in 25 steps, A(2,0)=3 in 17 steps, A(2,1)=5 in 33 steps, A(2,2)=7 in 55 steps, A(2,3)=9 in 83 steps, A(2,4)=11 in 117 steps, A(2,5)=13 in 157 steps, A(3,0)=5 in 37 steps, A(3,1)=13 in 191 steps, A(3,2)=29 in 881 steps, A(3,3)=61 in 3795 steps, A(3,4)=125 in 15765 steps.

One type for every use

In the simply typed calculus a numeral must be told in advance what kind of thing it will iterate, and with input and output of one type it computes only polynomials with tests. Let a single type stand for every type — a numeral is then a term of type ∀X. (X → X) → X → X, used at whatever type each occasion needs — and the same few symbols compute subtraction, exponentials and Ackermann's function, which grows faster than anything built from primitive recursion. Every run still finishes, and the proof that it does lies just beyond the reach of second-order arithmetic.

logic · Proof systems Three widows and the Mishna's table. The Mishna's division of estates of 100, 200 and 300 among claims of 100, 200 and 300: 33⅓ each; 50, 75, 75; 50, 100, 150.

The debts the Mishna divided

A man dies owing his three wives 100, 200 and 300. The Mishna divides an estate of 100 equally, of 300 in proportion, and of 200 as 50, 75 and 75, and for nearly two thousand years nobody could say why. The table is the nucleolus of a cooperative game, and the only division in which every pair splits its share as two people split a contested garment.

applied · The core

Named alongside it

The objects these essays reach for when they reach for this one.

ModelAggregationAxiomExhaustive searchIndependenceMajorityVoting ruleCardinalityCompactnessDiagonal argumentImpossibilityJudgement aggregation

All concepts