OctoInformBeta

OpenAI preprint, September 2026 · §5. A bound on uncountable base orders and categoricity on a tail

Lemma 5.1: An extensional relation with decreasing ordinal tags below δ\delta is well-founded and collapses injectively into VδV_\delta, ranks bounded by tags

Ordinal tags bound the ranks of the Mostowski collapse.

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

Let QQ be a set and RR a binary relation on QQ; for x∈Qx \in Q, the points yy with yRxy \mathrel{R} x are the RR-predecessors of xx. When RR is well-founded, its Mostowski collapse FF is the map from QQ to the sets defined by recursion along RR: F(x)F(x) is the set of the values F(y)F(y) for the RR-predecessors yy of xx. Two questions are asked of FF: when it is one-to-one, and how high in the von Neumann hierarchy (Vα)α(V_\alpha)_\alpha its values lie when every point of QQ carries an ordinal that drops along RR.

Extensional Relations and Ordinal Tags

A relation RR on a set QQ is extensional when any two points of QQ with the same RR-predecessors are equal: (∀z∈Q)(zRx⇔zRy)⟹x=y(x,y∈Q).(\forall z \in Q)\,(z \mathrel{R} x \iff z \mathrel{R} y) \implies x = y \qquad (x, y \in Q).(1)

A system of ordinal tags for a relation RR on a set QQ is a function ρ\rho from QQ to the ordinals that strictly decreases along RR: yRx⟹ρ(y)<ρ(x)(x,y∈Q).y \mathrel{R} x \implies \rho(y) < \rho(x) \qquad (x, y \in Q).(2) The ordinal ρ(x)\rho(x) is the tag of xx.

The Claim

Theorem 1. Let RR be a relation on a set QQ. If ρ\rho is a system of ordinal tags for RR, then RR is well-founded: $$\rho \text{ satisfies } \eqref{eq:tags} \implies R \text{ is well-founded}.$$(3)✦ Let RR be well-founded, and let FF be its Mostowski collapse. For every x∈Qx \in Q, F(x)={F(y):yRx}.F(x) = \{F(y) : y \mathrel{R} x\}.(4)✦ If RR is extensional, then for all x,y∈Qx, y \in Q, F(x)=F(y)⟹x=y.F(x) = F(y) \implies x = y.(5)✦ If ρ\rho is a system of ordinal tags for RR, then for every x∈Qx \in Q, rank⁡F(x)≤ρ(x).\operatorname{rank} F(x) \le \rho(x).(6)✦ If RR is extensional and ρ\rho is a system of ordinal tags for RR whose values all lie below an ordinal δ\delta, then F:Q→Vδ is injective.F \colon Q \to V_\delta \text{ is injective}.(7)✦

In the paper, the result reads: for a set QQ with an extensional relation RR and a function ρ:Q→ω1\rho \colon Q \to \omega_1 with yRx⇒ρ(y)<ρ(x)y \mathrel{R} x \Rightarrow \rho(y) < \rho(x), there is an injection F:Q→Vω1F \colon Q \to V_{\omega_1} with F(x)={F(y):yRx}F(x) = \{F(y) : y \mathrel{R} x\} and F(x)∈Vρ(x)+1F(x) \in V_{\rho(x)+1}.

What Is Checked

The claim is stated over the Mostowski collapse FF of a well-founded relation RR on a set QQ, under the hypotheses that RR is extensional and that it has a system of ordinal tags ρ\rho, bounded by an ordinal δ\delta for the injection into VδV_\delta.