The concrete product-limit Friedman--Stanley hierarchy
DefinitionFSCofinalityHierarchy20261102The 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.
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
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 , a specified measurable-space structure on , and an arbitrary binary relation . It does not require to be nonempty, countable, standard Borel, or Polish, and it does not require 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 , the first uncountable ordinal, occur only where explicitly stated.
CountableSetJumpRelation. For every small type , every relation , and every two codes , the defined proposition is true when both codes are ; when and , it is exactly ; and when exactly one code is , 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 supplies a separate empty code, including when is empty and no sequence into exists. No measurable structure, countability assumption on , or equivalence-relation hypothesis on occurs. Thus the formula literally describes two-sided coverage by ; interpreting it as equality of represented sets requires properties of that this declaration does not assume.
setJump. For every coded relation , this definition produces a coded relation with carrier . Its measurable structure is the pullback, under the map sending to the left-hand singleton and to the right-hand , of the standard measurable disjoint sum ; carries the product measurable structure induced by and the singleton carries its usual measurable structure. Its relation is true on two codes, false when exactly one code is , and on two sequences is . 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 of coded relations indexed by all natural numbers , this definition produces a coded relation whose carrier is the dependent product , whose measurable structure is the product measurable structure of the , and whose relation on any two product elements is exactly . 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 , 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 , for every hypothesis that is a nonzero limit ordinal, and for every hypothesis , there exists a function satisfying all three conditions: for every natural number ; for all natural numbers with ; and for every ordinal , there exists a natural number such that . The final inequality is non-strict and does not require . The hypotheses exclude zero, every successor ordinal, and every uncountable ordinal. Neither a prescribed value of nor uniqueness of is asserted.
fundamentalSequence. For every ordinal supplied with a proof that it is a nonzero limit ordinal, this definition returns a function . If , it selects, by classical choice, one function whose values all lie below , which is strictly increasing, and for which every ordinal satisfies for some natural number . If , it instead returns the constant zero function for every natural number . 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 , every proof that is a nonzero limit ordinal, and every natural number , the value of the function just defined satisfies . No hypothesis 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 , supplied by the nonzero-limit hypothesis.
fundamentalSequence_strictMono. For every ordinal , every proof that is a nonzero limit ordinal, and every hypothesis , the function selected by fundamentalSequence is strictly increasing: for all natural numbers , if , then . 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 , every proof that is a nonzero limit ordinal, every hypothesis , every ordinal , and every hypothesis , there exists a natural number such that , where is the classically selected function in fundamentalSequence. The witness may depend on ; neither equality nor the strict inequality is stated. This assertion requires the countability bound on .
fsTower. For every ordinal , this definition gives a coded relation by ordinal recursion. At zero, its carrier is , its measurable structure is the product structure of the discrete Boolean factors, and its relation is equality. At a successor , if , then has carrier , the measurable structure obtained by identifying this carrier with the measurable disjoint sum of a singleton and the product space , and the relation that relates two codes, never relates exactly one code, and relates two sequences precisely when each entry of either sequence is -related to some entry of the other sequence in the two separately quantified directions. At a nonzero limit , its carrier is , its measurable structure is the product of the measurable structures at those coordinates, and its relation is coordinatewise , with every natural-number coordinate required. Here is the chosen strictly increasing cofinal sequence below when , and is the constant zero sequence when ; the fact , valid in both cases, supplies the earlier-stage argument required by the recursion. The function is defined on all ordinals in the stated universe, with no countability hypothesis on . 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 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 , with no countability assumption, is equal as a coded-relation bundle to the option/sequence jump of . Explicitly, the latter has carrier , the measurable structure transferred from the disjoint sum of a singleton and the product measurable space , and the relation that is true on two codes, false on a mixed /sequence pair, and on sequences is . The stage is included, as are uncountable values of .
fsTower_limit. For every ordinal and every proof that is a nonzero limit ordinal, is equal as a coded-relation bundle to the countable product of over all natural numbers . If , this product has carrier , the corresponding product measurable structure, and relation . There is no hypothesis : for countable nonzero limits is the selected strictly increasing cofinal sequence below , whereas for uncountable nonzero limits for every natural number , so the displayed product consists entirely of zero-stage factors. Zero and successor ordinals are excluded by the nonzero-limit hypothesis.
Confirmed by the mission captain (proposal self-audit).