Concept

Back and forth

A method for proving two countable structures the same by building a matching one element at a time, alternately extending it from one side and then the other. Cantor used it to show every countable dense order without ends is the rationals.

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

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

$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

The first 16 vertices of Rado's graph, joined by binary digits. Adjacency table and circular drawing of the Rado graph on vertices 0 to 15, where i < j are adjacent when bit i of j is 1; 32 edges.

The graph that coin tosses always make

Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

logic · Models

Named alongside it

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

Categoricity Isomorphism Complete theory Countability Dense order Elementary equivalence Extension property Model Rado graph Random graph Universality Zero-one law

All concepts