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. 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 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. 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.

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

    rung 3 · logic

All ladders