OctoInformBeta

OpenAI preprint, September 2026 · §2. Countable diagrams and their tests

Lemma 2.2: At most 2ℵ02^{\aleph_0} diagrams on nn positions, and an injection of all positive-arity diagrams, arity recorded, into the colors

Under the continuum hypothesis, colors code diagrams of positive arity.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

How many diagrams are there on a set of nn positions, and can one map send the diagrams on {0,…,n}\{0, \dots, n\}, for all nn at once, injectively to colors, so that diagrams on different numbers of positions never share a color? Lemma 2.2 settles both under the continuum hypothesis (CH), the statement that the cardinal 2ℵ02^{\aleph_0} of the continuum equals ℵ1\aleph_1, the least uncountable cardinal.

Colors

A binary sequence is a map a:ℕ→{0,1}a \colon \mathbb{N} \to \{0, 1\}, and 2ω2^\omega is the set of binary sequences.✦

Two binary sequences aa and bb are equal outside a finite set, written a=*ba =^{*} b, when the set of places where they differ is finite: a=*b⇔{n∈ℕ:a(n)≠b(n)} is finite.a =^{*} b \iff \{\, n \in \mathbb{N} : a(n) \neq b(n) \,\} \text{ is finite}.(1)✦

The palette S=2ω/=*S = 2^\omega/{=^{*}} is the quotient of 2ω2^\omega by =*=^{*}; its elements are the colors, and the color of a sequence aa is its class [a][a].✦

Diagrams

A label on a set AA of positions is a pair (J,i)(J, i) of a nonempty finite subset JJ of AA and a natural number ii; the labels on AA form the set L(A)={(J,i):J⊆A finite and nonempty,i∈ℕ}.L(A) = \{\, (J, i) : J \subseteq A \text{ finite and nonempty},\ i \in \mathbb{N} \,\}.(2)✦

A diagram DD on a set AA of positions is a triple (E,R,ρ)(E, R, \rho) of two binary relations EE and RR on the set L(A)L(A) of labels (2) and a map ρ:L(A)→ω1\rho \colon L(A) \to \omega_1 that gives each label a tag, a countable ordinal.✦

The diagrams on AA form the set 𝒟(A)\mathcal{D}(A), and a diagram of arity n+1n + 1 is a diagram on the positions {0,…,n}\{0, \dots, n\}.

The Claim

Theorem 1. Assume CH. For every natural number nn, the set of diagrams on the nn positions {0,…,n−1}\{0, \dots, n - 1\} has cardinality at most 2ℵ02^{\aleph_0}: |𝒟({0,…,n−1})|≤2ℵ0.\bigl|\mathcal{D}(\{0, \dots, n - 1\})\bigr| \le 2^{\aleph_0}.(3)✦ Moreover, there is an injection code\mathrm{code}, the code of diagrams, that sends each pair (n,D)(n, D) with DD a diagram of arity n+1n + 1 to a color: code:⨆n∈ℕ𝒟({0,…,n})↪S.\mathrm{code} \colon \bigsqcup_{n \in \mathbb{N}} \mathcal{D}(\{0, \dots, n\}) \hookrightarrow S.(4)✦

In the paper, the result reads: for each k≥1k \ge 1 there is an injection ιk\iota_k from the diagrams of arity kk into SS, and the ranges of the ιk\iota_k are pairwise disjoint.

The maps D↦code(n,D)D \mapsto \mathrm{code}(n, D) on the diagrams of arity n+1n + 1 are injections ιn+1\iota_{n+1} of this kind, with pairwise disjoint ranges.

What Is Checked

The claims (3) and (4) are stated over the continuum hypothesis, the diagrams on the finite sets {0,…,n−1}\{0, \dots, n - 1\} of positions with their labels and their tags in ω1\omega_1, and the palette SS of binary sequences modulo equality outside a finite set.

Of these constructions, the library proves that equality outside a finite set (1) is an equivalence relation on 2ω2^\omega.✦