Matpic
mathematics, in pictures
Field

Logic

What can be said in a system, what follows from it, and what it cannot settle about itself.
000001010011100101110111(p ∨ q) ∧ ¬r on the 3-cube of assignments — 3 of 8 cornerscorners next to each other differ in one variable, which every edge here was checkedagainst

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

 keeps 0keeps 1monotoneself-dualaffineenough alone?∧ and✓✓✓··no∨ or✓✓✓··no¬p not p···✓✓no↑ nand·····yes⊕ exclusive or✓···✓no→ implication·✓···no6 connectives against Post's five classes — a tick means the connective stays insidenand escapes all five, and is therefore enough alone

One connective is enough

Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.

 rspq00011110000111101110111011110010((p ∧ q) ∨ (r ∧ s)) ∨ (¬p ∧ ¬r) covered by 3 of its 6 primeimplicantsr∧s ∨ ¬p∧¬r ∨ p∧q — checked against the formula on all 16assignments

The map that puts neighbours side by side

Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.

 ABCDABABCBCDADCDABCD4 circles cut the plane into 14 pieces — Euler's count is 1414 of the 16 patterns appear; missing: A¬BC¬D, ¬AB¬CD

Four circles cannot do it

Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.

 AAAEAIAOEAEEEIEOIAIEIIIOOAOEOIOO1·A1·E1·I1·O2·A2·E2·I2·O3·A3·E3·I3·O4·A4·E4·I4·Ovalid: AAA-1 AII-1 EAE-1 EIO-1 AEE-2 AOO-2 EAE-2 EIO-2 AII-3 EIO-3 IAI-3 OAO-3 AEE-4 EIO-4 IAI-4valid only with existential import: AAI-1 EAO-1 AEO-2 EAO-2 AAI-3 EAO-3 AAI-4 AEO-4 EAO-4256 forms — 15 valid outright, 9 more if every term is assumed to have memberseach cell is one mood in one figure, and the verdict was reached by trying all 256 occupancies

Twenty-four out of two hundred and fifty-six

Aristotle's syllogisms are four sentence forms in four arrangements, which makes 256 patterns of argument. Fifteen of them are valid. Nine more become valid if you assume the things being talked about exist, and the gap between those numbers is a two-thousand-year-old disagreement.

 ji123456123456∀i ∃j : trueevery row carries at least one mark∃j ∀i : falsesome one column is marked all the way downthe relation "j is one more than i, counting round", on 6 rows and 6 columnsevery row has a mark: yes · some column is all marks: no

Every row, or one column

For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.

 ¬(((p → q) ∧ (q → r)) → (p → r))(p → q) ∧ (q → r)¬(p → r)p → qq → rp¬r¬p×q¬q×r×assume the formula false, then take it apart: ((p → q) ∧ (q → r)) → (p → r)every branch closes, so the assumption is impossible — the formula is valid

The tree that closes

To prove a formula, assume it false and take it apart. Every branch ends in a contradiction, or one of them describes exactly how it could have been false — and either way the tree is the answer, drawn.

 Pone line, one point off it, and 4 lines through the point that never meet itevery arc here meets the rim at a right angle, and every miss was checked for crossingsinside the disc

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.

 every node has at most 3 children and the tree reaches level 416 nodes on the bottom row; the marked walk takes a surviving child at every step

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.

 x10110101000x21101010000x30011111000x41010100000x50001001000x60111110000x71110011001x8010100000110011001neweach row is a number between 0 and 1, written in binary; the marked squares are thediagonalthe row underneath is the number that differs from the nth in its nth binary digit — so thelist is missing a number, and it was an arbitrary list

The row that is not on the list

Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.

 S1S2S3S4S5S6S7S1S2S3S4S5S6S7Rthe sets that do not contain themselvesrow i, column j is marked when set i contains set j — the diagonal asks whether a set contains itselfthe row beneath is the complement of the diagonal, and it is not one of the rows above it

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.

 φ10110101000φ21101010000φ30011111000φ41010100000φ50001001000φ60111110000φ71110011001φ8010100000110011001neweach row is a sentence, and whether it says yes to each numbered question; the markedsquares are the diagonalthe row underneath is the sentence that answers each question the opposite way to theone asked about it — so the answers cannot all be given by a sentence on the list

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.

 [0, 1](0, 1)01½0 goes to a half and 1/n goes to 1/(n+2); every other point of [0, 1] stays where it is8 moved points drawn, all distinct, all inside (0, 1) — and the two endpoints are gone

Two injections make a bijection

If each of two collections fits inside the other without collisions, they are the same size. That sounds obvious and is not, because neither injection needs to be onto — and the proof is a rule for deciding which of the two to follow, one chain at a time.

 basevaluein hereditary baseordinal242^2ω^ω3263^2·2 + 3·2 + 2ω^2·2 + ω·2 + 24414^2·2 + 4·2 + 1ω^2·2 + ω·2 + 15605^2·2 + 5·2ω^2·2 + ω·26836^2·2 + 6 + 5ω^2·2 + ω + 571097^2·2 + 7 + 4ω^2·2 + ω + 481398^2·2 + 8 + 3ω^2·2 + ω + 391739^2·2 + 9 + 2ω^2·2 + ω + 21021110^2·2 + 10 + 1ω^2·2 + ω + 11125311^2·2 + 11ω^2·2 + ω1229912^2·2 + 11ω^2·2 + 11G(4) written in hereditary base b, the base bumped to b+1, then one subtractedthe integers keep rising, and the ordinals fall at every single step — which is why it has to stop

A sequence that explodes and still stops

Goodstein's sequence starting at 4 climbs past any number you care to name and reaches zero after about ten to the hundred and twenty million steps. The proof that it stops is a second sequence, running alongside it, that goes down.

 U¬UU ∪ ¬U¬¬UU is an interval with 1 point taken out; ¬U is the inside of what is leftU and ¬U together miss the endpoints, and ¬¬U hands them back — so U ∨ ¬U is not everything and ¬¬U is not U

The middle that is not excluded

Either it is raining or it is not. Drop that as an axiom and what is left is still a logic — one with models made of open sets and of stages of knowledge, in which a set and its negation between them miss the boundary.

All essays