Matpic
mathematics, in pictures
Concept

Equivalence class

The set of all objects that a given equivalence relation counts as the same as one particular object. The classes split the whole collection into disjoint pieces, and many constructions treat each class as a single new object.

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

6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

computation · De bruijn Infinitely many guessers, finitely many wrong. Three rows over the first 40 places: the hats worn, the chosen representative of their class, and a row of marks showing each guess right or wrong. The 5 wrong guesses all fall within the first 14 places, up to a marked place; every later guess is right.

Infinitely many guessers, finitely many wrong

An infinite line of people each wears a black or white hat, sees every hat in front and none of their own, and must guess their own colour. With a finite line, each guesser is right half the time whatever they agree in advance. With an infinite line and the axiom of choice, they can agree a strategy under which all but finitely many are right — and nobody can carry it out.

logic · Axiom of choice

Named alongside it

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

Axiom of choiceChoice functionCounting argumentDe bruijn sequenceEulerian pathExhaustive searchGreedy algorithmIndependenceInfinityLexicographic orderLyndon wordNecklace

All concepts