AFTD Auto-Formalizing Theoretical Domains

exists_strictly_ordered_intervals

theoremverified

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 LinearOrder is a TotalPreorder.
  • 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 than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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).

  1. 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.

    line 5

    uses Countable.of_equiv, toLex.symm

      have instCountable : Countable (Lex (A × Bool)) := Countable.of_equiv (A × Bool) toLex.symm
  2. The 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.

    lines 6–12

    uses Subtype.ext_iff.mp

      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)⟩⟩
  3. 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).

    lines 13–16

    uses Order.embedding_from_countable_to_dense

      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, ?_, ?_⟩
  4. 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).

    lines 17–24

    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⟩
  5. 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).

    lines 25–29

    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

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

/-- 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
See it in the graphDiscuss this resultChallenge it