Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The concrete product-limit Friedman--Stanley hierarchy

Definition
FSCofinalityHierarchy20261102

by username · Nov 2, 2026 · Mathlib c5ea003 (Lean v4.30.0)

borel-reducibilitycountable-structuresdescriptive-set-theoryfriedman-stanleymodel-theory

The bottom benchmark is equality on Cantor space. The countable-set jump uses sequence codes and a separate empty-set code; two nonempty codes are equivalent exactly when each member of either sequence is equivalent to some member of the other. Repetitions and order are ignored. At a countable nonzero limit, use the coordinatewise product along one fixed strictly increasing cofinal sequence. The file constructs these sequences and the ordinal recursion. Only stages below the first uncountable ordinal are used by the mission; total-function defaults outside that range are specified explicitly. All measurable spaces are actual sequence or disjoint-sum code spaces, not quotient spaces.

Definition code
import Definitions.Def_FSCofinalityStructures20261102
import Mathlib.SetTheory.Ordinal.FundamentalSequence

set_option autoImplicit false
noncomputable section
attribute [local instance] Classical.propDecidable
open Set Order Ordinal

namespace FSCofinality

/-- Equality of represented countable sets, including a distinct empty-set
code. Repetitions and enumeration order are ignored. -/
def CountableSetJumpRelation {X : Type} (E : X → X → Prop)
    (x y : Option (ℕ → X)) : Prop :=
  match x,y with
  | none,none => True
  | some u,some v => (∀ i, ∃ j, E (u i) (v j)) ∧ (∀ j, ∃ i, E (u i) (v j))
  | _,_ => False

/-- The countable-set jump uses the actual option/sequence measurable
space, rather than a quotient space of countable sets. -/
def setJump (E : CodedRelation) : CodedRelation where
  Carrier := Option (ℕ → E.Carrier)
  measurableSpace := MeasurableSpace.comap
    (fun x : Option (ℕ → E.Carrier) => match x with
      | none => Sum.inl ()
      | some u => Sum.inr u)
    (inferInstance : MeasurableSpace (Unit ⊕ (ℕ → E.Carrier)))
  rel := CountableSetJumpRelation E.rel

/-- Coordinatewise product on the actual dependent sequence code space. -/
def countableProduct (E : ℕ → CodedRelation) : CodedRelation where
  Carrier := ∀ n, (E n).Carrier
  measurableSpace := inferInstance
  rel := fun x y => ∀ n, (E n).rel (x n) (y n)

/-- Equality on Cantor space is the bottom Friedman--Stanley benchmark. -/
def cantorEquality : CodedRelation where
  Carrier := ℕ → Bool
  measurableSpace := inferInstance
  rel := Eq

/-- A countable nonzero limit ordinal has an increasing cofinal natural
sequence. This supplies the indexing data of the concrete limit products. -/
theorem exists_nat_fundamental_sequence (a : Ordinal.{0})
    (ha : IsSuccLimit a) (hc : a < Ordinal.omega 1) :
    ∃ q : ℕ → Ordinal.{0},
      (∀ n, q n < a) ∧ StrictMono q ∧ ∀ b < a, ∃ n, b ≤ q n := by
  have hcof : a.cof.ord = Ordinal.omega0 := by
    rw [Ordinal.cof_eq_aleph0_of_isSuccLimit ha hc, Cardinal.ord_aleph0]
  obtain ⟨f,hf⟩ := Ordinal.exists_isFundamentalSeq hcof
  refine ⟨fun n => (f ⟨n,Ordinal.natCast_lt_omega0 n⟩).val,
    fun n => (f ⟨n,Ordinal.natCast_lt_omega0 n⟩).property, ?_, ?_⟩
  · intro n m hnm
    apply hf.strictMono
    change (n : Ordinal) < (m : Ordinal)
    exact_mod_cast hnm
  · intro b hb
    obtain ⟨_,⟨i,rfl⟩,hi⟩ := hf.isCofinal_range ⟨b,hb⟩
    obtain ⟨n,hn⟩ := Ordinal.lt_omega0.mp i.property
    refine ⟨n,?_⟩
    have heq : i = ⟨n,Ordinal.natCast_lt_omega0 n⟩ := Subtype.ext hn
    simpa only [heq] using hi

/-- One fixed choice of fundamental sequence at every countable nonzero
limit ordinal. Values outside the countable range are harmless defaults;
the mission's tower is used only below omega one. -/
def fundamentalSequence (a : Ordinal.{0}) (ha : IsSuccLimit a) : ℕ → Ordinal.{0} :=
  if hc : a < Ordinal.omega 1 then
    Classical.choose (exists_nat_fundamental_sequence a ha hc)
  else fun _ => 0

theorem fundamentalSequence_lt (a : Ordinal.{0}) (ha : IsSuccLimit a) (n : ℕ) :
    fundamentalSequence a ha n < a := by
  unfold fundamentalSequence
  split
  · rename_i hc
    exact (Classical.choose_spec (exists_nat_fundamental_sequence a ha hc)).1 n
  · exact bot_lt_iff_ne_bot.mpr ha.ne_bot

theorem fundamentalSequence_strictMono (a : Ordinal.{0}) (ha : IsSuccLimit a)
    (hc : a < Ordinal.omega 1) : StrictMono (fundamentalSequence a ha) := by
  unfold fundamentalSequence
  rw [dif_pos hc]
  exact (Classical.choose_spec (exists_nat_fundamental_sequence a ha hc)).2.1

theorem fundamentalSequence_cofinal (a : Ordinal.{0}) (ha : IsSuccLimit a)
    (hc : a < Ordinal.omega 1) (b : Ordinal.{0}) (hb : b < a) :
    ∃ n, b ≤ fundamentalSequence a ha n := by
  unfold fundamentalSequence
  rw [dif_pos hc]
  exact (Classical.choose_spec (exists_nat_fundamental_sequence a ha hc)).2.2 b hb

/-- The concrete product-limit Friedman--Stanley tower from the manuscript:
Cantor equality at zero, countable-set jump at successors, and coordinatewise
countable products along the fixed fundamental sequences at limits. -/
def fsTower (a : Ordinal.{0}) : CodedRelation :=
  Ordinal.limitRecOn a cantorEquality (fun _ E => setJump E)
    (fun b hb rec => countableProduct (fun n =>
      rec (fundamentalSequence b hb n) (fundamentalSequence_lt b hb n)))

@[simp] theorem fsTower_zero : fsTower 0 = cantorEquality := by
  unfold fsTower
  rw [Ordinal.limitRecOn_zero]

@[simp] theorem fsTower_add_one (a : Ordinal.{0}) : fsTower (a+1) = setJump (fsTower a) := by
  unfold fsTower
  rw [Ordinal.limitRecOn_add_one]

theorem fsTower_limit (a : Ordinal.{0}) (ha : IsSuccLimit a) :
    fsTower a = countableProduct (fun n => fsTower (fundamentalSequence a ha n)) := by
  unfold fsTower
  rw [Ordinal.limitRecOn_limit _ _ _ _ ha]

end FSCofinality
Source
Friedman--Stanley cofinality and Borel completeness: A proposed negative answer to the Friedman--Stanley question, supplied research draft dated 2 November 2026, FriedmanStanleyQuestion.tex, Section 2.3; Section 4 opening, lines 835--847: V_0, successor countable sets, and product limits.
Read-back

What the Lean code literally says, in plain math · Codex (GPT-6 family; exact runtime model identifier not exposed to auditor)

Read-back of Definitions/Def_FSCofinalityHierarchy20261102.lean, using only that file and its imported Definitions/Def_FSCofinalityStructures20261102.lean. Exact model identity is unavailable: the runtime does not expose an exact model identifier to this auditor.

The imported bundle CodedRelation, used below, consists of a small type XXX, a specified measurable-space structure Σ\SigmaΣ on XXX, and an arbitrary binary relation R⊆X×XR\subseteq X\times XR⊆X×X. It does not require XXX to be nonempty, countable, standard Borel, or Polish, and it does not require RRR to be an equivalence relation or to have a measurable graph. All ordinal variables below range over the ordinals of universe zero; the bounds by ω1\omega_1ω1​, the first uncountable ordinal, occur only where explicitly stated.

CountableSetJumpRelation. For every small type XXX, every relation E⊆X×XE\subseteq X\times XE⊆X×X, and every two codes x,y∈{none}⊔{some(u):u ⁣:N→X}x,y\in\{\mathtt{none}\}\sqcup\{\mathtt{some}(u):u\colon\mathbb N\to X\}x,y∈{none}⊔{some(u):u:N→X}, the defined proposition is true when both codes are none\mathtt{none}none; when x=some(u)x=\mathtt{some}(u)x=some(u) and y=some(v)y=\mathtt{some}(v)y=some(v), it is exactly (∀i∈N  ∃j∈N  E(u(i),v(j)))∧(∀j∈N  ∃i∈N  E(u(i),v(j)))(\forall i\in\mathbb N\;\exists j\in\mathbb N\;E(u(i),v(j)))\land(\forall j\in\mathbb N\;\exists i\in\mathbb N\;E(u(i),v(j)))(∀i∈N∃j∈NE(u(i),v(j)))∧(∀j∈N∃i∈NE(u(i),v(j))); and when exactly one code is none\mathtt{none}none, it is false. The witnesses in the two directions need not constitute a function, an injection, a bijection, or a single common matching. Repeated entries are permitted. Every actual sequence has nonempty range, so none\mathtt{none}none supplies a separate empty code, including when XXX is empty and no sequence into XXX exists. No measurable structure, countability assumption on XXX, or equivalence-relation hypothesis on EEE occurs. Thus the formula literally describes two-sided coverage by EEE; interpreting it as equality of represented sets requires properties of EEE that this declaration does not assume.

setJump. For every coded relation E=(X,Σ,R)E=(X,\Sigma,R)E=(X,Σ,R), this definition produces a coded relation with carrier {none}⊔{some(u):u ⁣:N→X}\{\mathtt{none}\}\sqcup\{\mathtt{some}(u):u\colon\mathbb N\to X\}{none}⊔{some(u):u:N→X}. Its measurable structure is the pullback, under the map sending none\mathtt{none}none to the left-hand singleton and some(u)\mathtt{some}(u)some(u) to the right-hand uuu, of the standard measurable disjoint sum {∗}⊔XN\{*\}\sqcup X^{\mathbb N}{∗}⊔XN; XNX^{\mathbb N}XN carries the product measurable structure induced by Σ\SigmaΣ and the singleton carries its usual measurable structure. Its relation is true on two none\mathtt{none}none codes, false when exactly one code is none\mathtt{none}none, and on two sequences u,vu,vu,v is (∀i∈N  ∃j∈N  R(u(i),v(j)))∧(∀j∈N  ∃i∈N  R(u(i),v(j)))(\forall i\in\mathbb N\;\exists j\in\mathbb N\;R(u(i),v(j)))\land(\forall j\in\mathbb N\;\exists i\in\mathbb N\;R(u(i),v(j)))(∀i∈N∃j∈NR(u(i),v(j)))∧(∀j∈N∃i∈NR(u(i),v(j))). The carrier is the actual option/sequence space, with repetitions and enumeration orders retained as distinct codes, rather than a quotient by the relation. No extra assumptions on the carrier or relation are imposed.

countableProduct. For every family En=(Xn,Σn,Rn)E_n=(X_n,\Sigma_n,R_n)En​=(Xn​,Σn​,Rn​) of coded relations indexed by all natural numbers nnn, this definition produces a coded relation whose carrier is the dependent product ∏n∈NXn\prod_{n\in\mathbb N}X_n∏n∈N​Xn​, whose measurable structure is the product measurable structure of the Σn\Sigma_nΣn​, and whose relation on any two product elements x,yx,yx,y is exactly ∀n∈N  Rn(x(n),y(n))\forall n\in\mathbb N\;R_n(x(n),y(n))∀n∈NRn​(x(n),y(n)). Each coordinate is required, including coordinate zero. The factors need not be equal types, nonempty, countable, standard Borel, or Polish, and the coordinate relations need not be equivalence relations or measurable. In particular, an empty factor makes the carrier empty.

cantorEquality. This is the coded relation with carrier all functions x ⁣:N→Boolx\colon\mathbb N\to\mathrm{Bool}x:N→Bool, equipped with the usual product measurable structure from the discrete two-element Boolean space, and with relation equality of those functions. Thus two codes are related exactly when their Boolean entries agree at every natural-number coordinate. All Boolean sequences occur, including the two constant sequences; no restriction on their ranges or on infinitely many entries is imposed.

exists_nat_fundamental_sequence. For every ordinal aaa, for every hypothesis that aaa is a nonzero limit ordinal, and for every hypothesis a<ω1a<\omega_1a<ω1​, there exists a function q ⁣:N→Ordinalq\colon\mathbb N\to\mathrm{Ordinal}q:N→Ordinal satisfying all three conditions: q(n)<aq(n)<aq(n)<a for every natural number nnn; q(n)<q(m)q(n)<q(m)q(n)<q(m) for all natural numbers n,mn,mn,m with n<mn<mn<m; and for every ordinal b<ab<ab<a, there exists a natural number nnn such that b≤q(n)b\le q(n)b≤q(n). The final inequality is non-strict and does not require q(n)=bq(n)=bq(n)=b. The hypotheses exclude zero, every successor ordinal, and every uncountable ordinal. Neither a prescribed value of q(0)q(0)q(0) nor uniqueness of qqq is asserted.

fundamentalSequence. For every ordinal aaa supplied with a proof that it is a nonzero limit ordinal, this definition returns a function qa ⁣:N→Ordinalq_a\colon\mathbb N\to\mathrm{Ordinal}qa​:N→Ordinal. If a<ω1a<\omega_1a<ω1​, it selects, by classical choice, one function whose values all lie below aaa, which is strictly increasing, and for which every ordinal b<ab<ab<a satisfies b≤qa(n)b\le q_a(n)b≤qa​(n) for some natural number nnn. If a≥ω1a\ge\omega_1a≥ω1​, it instead returns the constant zero function qa(n)=0q_a(n)=0qa​(n)=0 for every natural number nnn. Hence the definition accepts uncountable nonzero limits as well as countable ones; strict increase and cofinality are part of the selected witness only in the countable branch. The proof argument is a proof of a proposition, not additional mathematical indexing data, and the choice does not specify which qualifying sequence is selected or its first term.

fundamentalSequence_lt. For every ordinal aaa, every proof that aaa is a nonzero limit ordinal, and every natural number nnn, the value qa(n)q_a(n)qa​(n) of the function just defined satisfies qa(n)<aq_a(n)<aqa​(n)<a. No hypothesis a<ω1a<\omega_1a<ω1​ is required here. In the countable case the function is the classically chosen increasing cofinal sequence; outside that range it is the constant zero function, so this assertion there is 0<a0<a0<a, supplied by the nonzero-limit hypothesis.

fundamentalSequence_strictMono. For every ordinal aaa, every proof that aaa is a nonzero limit ordinal, and every hypothesis a<ω1a<\omega_1a<ω1​, the function qa ⁣:N→Ordinalq_a\colon\mathbb N\to\mathrm{Ordinal}qa​:N→Ordinal selected by fundamentalSequence is strictly increasing: for all natural numbers n,mn,mn,m, if n<mn<mn<m, then qa(n)<qa(m)q_a(n)<q_a(m)qa​(n)<qa​(m). The theorem includes no uncountable ordinal under its hypotheses; the constant-zero default outside the countable range is not asserted to be strictly increasing.

fundamentalSequence_cofinal. For every ordinal aaa, every proof that aaa is a nonzero limit ordinal, every hypothesis a<ω1a<\omega_1a<ω1​, every ordinal bbb, and every hypothesis b<ab<ab<a, there exists a natural number nnn such that b≤qa(n)b\le q_a(n)b≤qa​(n), where qaq_aqa​ is the classically selected function in fundamentalSequence. The witness may depend on bbb; neither equality nor the strict inequality b<qa(n)b<q_a(n)b<qa​(n) is stated. This assertion requires the countability bound on aaa.

fsTower. For every ordinal aaa, this definition gives a coded relation TaT_aTa​ by ordinal recursion. At zero, its carrier is BoolN\mathrm{Bool}^{\mathbb N}BoolN, its measurable structure is the product structure of the discrete Boolean factors, and its relation is equality. At a successor b+1b+1b+1, if Tb=(Xb,Σb,Rb)T_b=(X_b,\Sigma_b,R_b)Tb​=(Xb​,Σb​,Rb​), then Tb+1T_{b+1}Tb+1​ has carrier {none}⊔XbN\{\mathtt{none}\}\sqcup X_b^{\mathbb N}{none}⊔XbN​, the measurable structure obtained by identifying this carrier with the measurable disjoint sum of a singleton and the product space XbNX_b^{\mathbb N}XbN​, and the relation that relates two none\mathtt{none}none codes, never relates exactly one none\mathtt{none}none code, and relates two sequences precisely when each entry of either sequence is RbR_bRb​-related to some entry of the other sequence in the two separately quantified directions. At a nonzero limit bbb, its carrier is ∏n∈NXqb(n)\prod_{n\in\mathbb N}X_{q_b(n)}∏n∈N​Xqb​(n)​, its measurable structure is the product of the measurable structures at those coordinates, and its relation is coordinatewise Rqb(n)R_{q_b(n)}Rqb​(n)​, with every natural-number coordinate required. Here qbq_bqb​ is the chosen strictly increasing cofinal sequence below bbb when b<ω1b<\omega_1b<ω1​, and is the constant zero sequence when b≥ω1b\ge\omega_1b≥ω1​; the fact qb(n)<bq_b(n)<bqb​(n)<b, valid in both cases, supplies the earlier-stage argument required by the recursion. The function a↦Taa\mapsto T_aa↦Ta​ is defined on all ordinals in the stated universe, with no countability hypothesis on aaa. In particular, every uncountable nonzero limit stage is the countable product of copies of the zero-stage Boolean-sequence equality relation. Successor stages of uncountable ordinals still apply the same option/sequence jump to the preceding stage. The recursion uses concrete code spaces and their measurable structures throughout and does not form quotients.

fsTower_zero. The coded relation T0T_0T0​ defined by fsTower is equal to cantorEquality: its carrier is all Boolean sequences on the natural numbers, its measurable structure is the product structure of discrete Boolean spaces, and its relation is equality. The assertion is equality of the coded-relation bundles themselves, rather than only a comparison between their relations by reductions or isomorphisms.

fsTower_add_one. For every ordinal aaa, with no countability assumption, Ta+1T_{a+1}Ta+1​ is equal as a coded-relation bundle to the option/sequence jump of Ta=(Xa,Σa,Ra)T_a=(X_a,\Sigma_a,R_a)Ta​=(Xa​,Σa​,Ra​). Explicitly, the latter has carrier {none}⊔XaN\{\mathtt{none}\}\sqcup X_a^{\mathbb N}{none}⊔XaN​, the measurable structure transferred from the disjoint sum of a singleton and the product measurable space XaNX_a^{\mathbb N}XaN​, and the relation that is true on two none\mathtt{none}none codes, false on a mixed none\mathtt{none}none/sequence pair, and on sequences u,vu,vu,v is (∀i∈N  ∃j∈N  Ra(u(i),v(j)))∧(∀j∈N  ∃i∈N  Ra(u(i),v(j)))(\forall i\in\mathbb N\;\exists j\in\mathbb N\;R_a(u(i),v(j)))\land(\forall j\in\mathbb N\;\exists i\in\mathbb N\;R_a(u(i),v(j)))(∀i∈N∃j∈NRa​(u(i),v(j)))∧(∀j∈N∃i∈NRa​(u(i),v(j))). The stage a=0a=0a=0 is included, as are uncountable values of aaa.

fsTower_limit. For every ordinal aaa and every proof that aaa is a nonzero limit ordinal, TaT_aTa​ is equal as a coded-relation bundle to the countable product of Tqa(n)T_{q_a(n)}Tqa​(n)​ over all natural numbers nnn. If Tqa(n)=(Xqa(n),Σqa(n),Rqa(n))T_{q_a(n)}=(X_{q_a(n)},\Sigma_{q_a(n)},R_{q_a(n)})Tqa​(n)​=(Xqa​(n)​,Σqa​(n)​,Rqa​(n)​), this product has carrier ∏n∈NXqa(n)\prod_{n\in\mathbb N}X_{q_a(n)}∏n∈N​Xqa​(n)​, the corresponding product measurable structure, and relation ∀n∈N  Rqa(n)(x(n),y(n))\forall n\in\mathbb N\;R_{q_a(n)}(x(n),y(n))∀n∈NRqa​(n)​(x(n),y(n)). There is no hypothesis a<ω1a<\omega_1a<ω1​: for countable nonzero limits qaq_aqa​ is the selected strictly increasing cofinal sequence below aaa, whereas for uncountable nonzero limits qa(n)=0q_a(n)=0qa​(n)=0 for every natural number nnn, so the displayed product consists entirely of zero-stage factors. Zero and successor ordinals are excluded by the nonzero-limit hypothesis.

Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

  • Endorsed by username · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me