Matpic
mathematics, in pictures
Concept

Cardinality

The size of a collection, measured by whether its members can be matched one to one with another collection's.

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

Also named here as countability — the same set of essays touches all of them, so they are one junction rather than several.

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.

logic · diagonalisation [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.

logic · cardinality

Named alongside it

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

BijectionCountabilityChain decompositionConstructionDiagonal argumentHilbert hotelInjectionIntervalPower setProof by contradictionReal numbersSelf reference

All concepts