exists_strictly_ordered_intervals
For every countable linearly ordered type A, there exists a family of strictly separated intervals [l(a), r(a)] in (0, 1/2] such that a < b implies r(a) < l(b).
Statement
theorem exists_strictly_ordered_intervals (A : Type) [LinearOrder A] [Countable A] : ∃ (l r : A → ℝ), (∀ a, 0 < l a ∧ l a < r a ∧ r a ≤ (1 / 2 : ℝ)) ∧ (∀ a b, a < b → r a < l b)
- Source
- step towards countable_lex_stream_order_embedding_exists
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- countable_lex_stream_order_embedding_existsEvery lexicographic stream space over a countable linearly ordered alphabet admits an order embedding into the real line.
The proof, explained
The strategy is to represent each element a of the countable linear order A by a pair of ordered points (a, false) < (a, true) in the lexicographical product A × Bool, and embed this into the dense open interval (0, 1/2) ⊂ ℝ. By Cantor's embedding theorem (Order.embedding_from_countable_to_dense), there exists an order embedding from Lex (A × Bool) into (0, 1/2). Defining the endpoints as l(a) = e(a, false) and r(a) = e(a, true), the strict lexicographical ordering guarantees that 0 < l(a) < r(a) ≤ 1/2 and that a < b implies r(a) < l(b).
The lexicographically ordered type Lex (A × Bool) is countable.
Since A is countable and Bool is a two-element type, their Cartesian product A × Bool is countable. The equivalence toLex.symm transfers countability to the lexicographical type synonym Lex (A × Bool) via Countable.of_equiv.
uses
Countable.of_equiv,toLex.symmhave instCountable : Countable (Lex (A × Bool)) := Countable.of_equiv (A × Bool) toLex.symmThe open interval (0, 1/2) in ℝ is nontrivial (contains at least two distinct elements).
The values 1/4 and 3/8 both lie strictly between 0 and 1/2, and they are distinct (verified by numerical calculation). By Subtype.ext_iff.mp, if their subtype elements were equal, their underlying values would coincide, which is false; thus the interval contains at least two distinct points.
uses
Subtype.ext_iff.mphave instNontrivial : Nontrivial (Set.Ioo (0 : ℝ) (1 / 2 : ℝ)) := by have h1 : (0 : ℝ) < 1 / 4 := by norm_num have h2 : (1 / 4 : ℝ) < 1 / 2 := by norm_num have h3 : (0 : ℝ) < 3 / 8 := by norm_num have h4 : (3 / 8 : ℝ) < 1 / 2 := by norm_num have hne : (1 / 4 : ℝ) ≠ 3 / 8 := by norm_num exact ⟨⟨⟨1 / 4, h1, h2⟩, ⟨3 / 8, h3, h4⟩, fun h ↦ hne (Subtype.ext_iff.mp h)⟩⟩
Candidate interval endpoints l(a) and r(a) in (0, 1/2) are defined using an order embedding.
By Cantor's embedding theorem (Order.embedding_from_countable_to_dense), any countable linear order embeds into any nontrivial, densely ordered linear order. Applying this gives an order embedding e from Lex (A × Bool) into (0, 1/2). For each a ∈ A, the left endpoint l(a) is defined as the value of e(a, false) and the right endpoint r(a) as the value of e(a, true).
uses
Order.embedding_from_countable_to_denseobtain ⟨e⟩ := Order.embedding_from_countable_to_dense (Lex (A × Bool)) (Set.Ioo (0 : ℝ) (1 / 2 : ℝ)) let l : A → ℝ := fun a ↦ (e (toLex (a, false))).val let r : A → ℝ := fun a ↦ (e (toLex (a, true))).val refine ⟨l, r, ?_, ?_⟩
For every a ∈ A, the interval endpoints satisfy 0 < l(a) < r(a) ≤ 1/2.
Because e maps into (0, 1/2), we have 0 < l(a) and r(a) < 1/2, from which r(a) ≤ 1/2 follows by le_of_lt. In the lexicographical order, (a, false) < (a, true) holds by Prod.Lex.right because the first components are equal and false < true. Since e is an order embedding, preserving strict inequality, l(a) < r(a).
uses
Prod.Lex.right,le_of_lt· intro a have hmem_l := (e (toLex (a, false))).prop have hmem_r := (e (toLex (a, true))).prop have hlt : toLex (a, false) < toLex (a, true) := by change Prod.Lex (· < ·) (· < ·) (a, false) (a, true) exact Prod.Lex.right a (by decide) have he_lt : (e (toLex (a, false))).val < (e (toLex (a, true))).val := e.lt_iff_lt.mpr hlt exact ⟨hmem_l.1, he_lt, le_of_lt hmem_r.2⟩
For all a < b in A, the intervals are strictly separated: r(a) < l(b).
When a < b, the inequality (a, true) < (b, false) holds in the lexicographical order by Prod.Lex.left because their first components satisfy a < b. Since e preserves strict inequalities, this implies r(a) = e(a, true) < e(b, false) = l(b).
uses
Prod.Lex.left· intro a b hab have hlt : toLex (a, true) < toLex (b, false) := by change Prod.Lex (· < ·) (· < ·) (a, true) (b, false) exact Prod.Lex.left true false hab exact e.lt_iff_lt.mpr hlt
Countable.of_equiv- if α is countable and α is equivalent to β, then β is countable
toLex.symm- the canonical equivalence between a lexicographically ordered product type and its underlying product type
Subtype.ext_iff.mp- if two subtype elements are equal, then their underlying values are equal
Order.embedding_from_countable_to_dense- every countable linear order can be order-embedded into any nontrivial, densely ordered linear order
Prod.Lex.right- in a lexicographical product, if the first components are equal and the second components satisfy b₁ < b₂, then (a, b₁) < (a, b₂)
le_of_lt- strict inequality implies non-strict inequality (a < b implies a ≤ b)
Prod.Lex.left- in a lexicographical product, if the first components satisfy a₁ < a₂, then (a₁, b₁) < (a₂, b₂) regardless of the second components
- The fact that the open interval (0, 1/2) is densely ordered and linearly ordered is inferred automatically by typeclass synthesis for the subtype of ℝ.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every countable linearly ordered type embeds into strictly separated intervals in (0, 1/2]. -/theorem exists_strictly_ordered_intervals (A : Type) [LinearOrder A] [Countable A] : ∃ (l r : A → ℝ), (∀ a, 0 < l a ∧ l a < r a ∧ r a ≤ (1 / 2 : ℝ)) ∧ (∀ a b, a < b → r a < l b) := by have instCountable : Countable (Lex (A × Bool)) := Countable.of_equiv (A × Bool) toLex.symm have instNontrivial : Nontrivial (Set.Ioo (0 : ℝ) (1 / 2 : ℝ)) := by have h1 : (0 : ℝ) < 1 / 4 := by norm_num have h2 : (1 / 4 : ℝ) < 1 / 2 := by norm_num have h3 : (0 : ℝ) < 3 / 8 := by norm_num have h4 : (3 / 8 : ℝ) < 1 / 2 := by norm_num have hne : (1 / 4 : ℝ) ≠ 3 / 8 := by norm_num exact ⟨⟨⟨1 / 4, h1, h2⟩, ⟨3 / 8, h3, h4⟩, fun h ↦ hne (Subtype.ext_iff.mp h)⟩⟩ obtain ⟨e⟩ := Order.embedding_from_countable_to_dense (Lex (A × Bool)) (Set.Ioo (0 : ℝ) (1 / 2 : ℝ)) let l : A → ℝ := fun a ↦ (e (toLex (a, false))).val let r : A → ℝ := fun a ↦ (e (toLex (a, true))).val refine ⟨l, r, ?_, ?_⟩ · intro a have hmem_l := (e (toLex (a, false))).prop have hmem_r := (e (toLex (a, true))).prop have hlt : toLex (a, false) < toLex (a, true) := by change Prod.Lex (· < ·) (· < ·) (a, false) (a, true) exact Prod.Lex.right a (by decide) have he_lt : (e (toLex (a, false))).val < (e (toLex (a, true))).val := e.lt_iff_lt.mpr hlt exact ⟨hmem_l.1, he_lt, le_of_lt hmem_r.2⟩ · intro a b hab have hlt : toLex (a, true) < toLex (b, false) := by change Prod.Lex (· < ·) (· < ·) (a, true) (b, false) exact Prod.Lex.left true false hab exact e.lt_iff_lt.mpr hlt