Matpic
mathematics, in pictures
Ladder

Diagonalisation — the ladder

3 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    rung 1 · logic
  2. 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.

    rung 2 · logic
  3. φ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.

    rung 3 · logic

All ladders