Matpic
mathematics, in pictures
Concept

Countability

The property of a collection whose members can be arranged in a single numbered list. The rationals have it and the reals do not, which is what the diagonal argument establishes — and the two facts together are what make most numbers unnameable.

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

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.

logic · Diagonalisation A closed interval and an open one, matched point for point. Two number lines, one closed and one open, with arrows showing the countable sequence of points that has to move.

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 The fractions, put in a line. A grid whose rows are numerators and columns denominators, walked by antidiagonals, with the place each fraction takes in the list written in its cell and the repeats left blank.

The arithmetic that loses subtraction

Adding one to an infinite collection changes nothing, and neither does doubling it, or squaring it. What that costs is the two operations that were doing the work — an equation between infinite sizes cannot be cancelled, and how many are left stops being a question.

logic · Cardinality The algebraic numbers, arriving in finite batches. A stretch of the number line with the roots of integer polynomials marked, each at the height of the smallest polynomial that catches it, and the count of polynomials at each height.

Countable, and everywhere

The numbers a polynomial can catch arrive in finite batches, so they can be listed. They are also in every interval, however short. Being listable turns out to say nothing whatever about being sparse.

logic · Cardinality The numbers to 18 in hereditary base 2, and their ordinals. A table of small whole numbers written in hereditary base notation beside the ordinal obtained by replacing the base with omega.

Every ordinal in base omega

Every ordinal below a certain point is a descending sum of powers of ω, in exactly one way. That notation makes comparison mechanical, it is what hereditary base notation becomes when the base is replaced, and it stops at the first ordinal it cannot name.

logic · Ordinals Limit ordinals and the sequences that approach them. Several ordinals with the first terms of their fundamental sequences, and the successors marked as having a predecessor instead.

Reached from below, or not at all

Every limit ordinal anybody meets is the end of an increasing sequence — ω, ω·2, ω^ω, all of them approached one step at a time. The first uncountable ordinal is not, and the reason it is not constrains the size of the continuum.

logic · Ordinals The rationals covered by intervals of total length 0.1800. Intervals of rapidly shrinking length placed around the rationals of the unit interval in the order they are listed, with the union of them drawn as a single band beneath.

Covering a set from outside

To say how long a set is, cover it with intervals and add their lengths, then take the smallest total any covering achieves. That definition is short, obviously right for an interval, and gives the rationals a length of nothing.

analysis · Measure The classes, a selection from them, and the translates that cannot have a length. Points of several classes of the unit interval under translation by rationals, drawn one class per row, above rows showing rational translates of a selection that never overlap.

A set that has no size at all

Slide the unit interval along itself by every rational and the points fall into classes. Choose one point from each and the resulting set has no length — not zero, not positive, none: countably many disjoint copies of it would have total length nought or infinity, and the union needs something in between.

analysis · Measure Every positive rational, in one sequence. The first 32 terms of Stern's diatomic sequence as bars, with the ratios of consecutive terms beneath. Every ratio is in lowest terms, no two agree, and each term counts the hyperbinary representations of its index.

Every rational in one sequence

The tree lists every positive fraction once and needs a tree to do it. One recursion on the whole numbers lists them in a single row — and each term of it counts something nobody was asking about, which is why the enumeration works.

number · Stern brocot A countable structure grown by adding witnesses. Stages of a structure built from 0 and 1 by adding sums, products, negatives and roots of quadratics: 2, 4, 12, 158 elements between −3 and 3.

A countable field that passes for the line

The real numbers are uncountable, and every first-order sentence about their addition, multiplication and order is also true of a countable field inside them — the real algebraic numbers. Löwenheim and Skolem showed this is no quirk of the reals: every theory with an infinite model has a countable one, including set theory, which then contains sets it calls uncountable.

logic · Models Adjectives that describe themselves, and the one that cannot exist. A grid of 8 adjectives against the same adjectives as written words, marked where the property holds of the spelling; the diagonal marks self-describing adjectives, and a flipped diagonal row labelled heterological matches no row.

The word that cannot describe itself

Some adjectives describe themselves — 'short' is short — and some do not — 'lengthy' is not lengthy. Call the second kind heterological, and ask whether 'heterological' is heterological. It is exactly when it is not. The diagonal that beat every list of numbers, every set of sets and every provability predicate has been turned on words that describe words, and it proves that no language can contain a word for its own notion of describing, naming or truth.

logic · Diagonalisation The rationals and the dyadic fractions, matched 12 times without a crossing. Two number lines from 0 to 1, rationals above and dyadic fractions below, with 12 back-and-forth matchings: 1/2↔1/2, 1/3↔1/4, 2/3↔3/4, 1/4↔1/8, 3/4↔7/8, 2/5↔3/8, 1/5↔1/16, 3/5↔5/8, 4/5↔15/16, 2/7↔3/16, 1/6↔1/32, 3/8↔5/16.

Two lists that are one order

The rationals and the fractions with a power of two below are different sets of numbers, and as orders they are exactly the same — any two countable orders that are dense and have no ends can be matched, point for point, keeping every comparison. The proof is a zigzag, and it settles every question the language of order can ask.

logic · Models Three sizes of infinity, and the collections that have each. ℵ₀: the fractions, the algebraic numbers, every finite text, every definition of a number; 2^ℵ₀: the real numbers, the continuous functions, the open sets, the closed sets, the Borel sets; 2^(2^ℵ₀): all functions, all sets of reals, the non-Borel sets, the measurable sets.

What counting can prove exists

There are only as many continuous functions as points of a line, only as many Borel sets, only countably many definitions — and more sets of reals than any of those. So counting proves that discontinuous functions, non-Borel sets and undefinable numbers exist without exhibiting one. It cannot prove that a set with no length exists, because the sets that have a length are exactly as numerous as all sets, and that difference turns out to be the difference between what the axioms force and what they merely allow.

logic · Cardinality 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

Named alongside it

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

CardinalityBijectionMeasure zeroAxiom of choiceOrdinalAlgebraic numberCantor setDense setDiagonal argumentElementary equivalenceHilbert hotelInterval

All concepts