AFTD Auto-Formalizing Theoretical Domains

countable_lex_stream_order_embedding_exists

theoremverified

Every lexicographic stream space over a countable linearly ordered alphabet admits an order embedding into the real line.

Statement

theorem countable_lex_stream_order_embedding_exists
    (A : Type) [LinearOrder A] [Countable A] :
    ∃ Φ : Lex (ℕ → A) → ℝ, ∀ u v : Lex (ℕ → A), u ≤ v ↔ Φ u ≤ Φ v
Source
step towards swf_anonymous_stationary_monotone_upper_lower_dominance_exists
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • exists_strictly_ordered_intervalsFor 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 <…
  • lex_stream_order_embedding_of_intervalsGiven a family of strictly separated intervals [l(a), r(a)] in (0, 1/2], the Cantor-type series Φ(u) = ∑_{k=0}^∞ (∏_{j<k} (r(u(j)) -…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The proof combines two intermediate results. First, countability of the linearly ordered alphabet $A$ is used to assign each element $a \in A$ a disjoint subinterval $(l(a), r(a)) \subseteq (0, 1/2]$ that strictly preserves the order ($a < b \implies r(a) < l(b)$). Second, this strictly ordered collection of intervals is passed to a general construction that embeds the lexicographically ordered stream space $\mathrm{Lex}(\mathbb{N} \to A)$ into $\mathbb{R}$.

  1. There exist interval endpoints $l, r : A \to \mathbb{R}$ assigning to each $a \in A$ a subinterval $(l(a), r(a)) \subseteq (0, 1/2]$ such that $a < b$ implies $r(a) < l(b)$.

    Since the linearly ordered alphabet $A$ is countable, the lemma `exists_strictly_ordered_intervals` produces functions $l, r : A \to \mathbb{R}$ satisfying $0 < l(a) < r(a) \le 1/2$ for all $a \in A$, with $r(a) < l(b)$ whenever $a < b$.

    line 5

    uses exists_strictly_ordered_intervals

      obtain ⟨l, r, ⟨h1, h2⟩⟩ := exists_strictly_ordered_intervals (A := A)
  2. There exists an order embedding $\Phi : \mathrm{Lex}(\mathbb{N} \to A) \to \mathbb{R}$.

    Applying `lex_stream_order_embedding_of_intervals` with the interval bounds $l$ and $r$ and their verified separation and positivity properties directly yields the desired order embedding $\Phi$ into $\mathbb{R}$.

    lines 6–7

    uses lex_stream_order_embedding_of_intervals

      exact lex_stream_order_embedding_of_intervals l r (fun a => (h1 a).1) (fun a => (h1 a).2.1)
        (fun a => (h1 a).2.2) h2
exists_strictly_ordered_intervals
Every countable linearly ordered set can be assigned strictly ordered subintervals $(l(a), r(a)) \subseteq (0, 1/2]$ such that $a < b$ implies $r(a) < l(b)$.
lex_stream_order_embedding_of_intervals
Given an alphabet with strictly ordered subintervals $(l(a), r(a)) \subseteq (0, 1/2]$ separated according to the linear order, there exists an order embedding from the lexicographical stream space into the real line.

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 lexicographic stream space over a countable linearly ordered alphabet admits an order embedding into the real line (Dubey et al. 2026, Lemma 1). -/theorem countable_lex_stream_order_embedding_exists    (A : Type) [LinearOrder A] [Countable A] :    ∃ Φ : Lex (ℕ → A) → ℝ, ∀ u v : Lex (ℕ → A), u ≤ v ↔ Φ u ≤ Φ v := by  obtain ⟨l, r, ⟨h1, h2⟩⟩ := exists_strictly_ordered_intervals (A := A)  exact lex_stream_order_embedding_of_intervals l r (fun a => (h1 a).1) (fun a => (h1 a).2.1)    (fun a => (h1 a).2.2) h2
See it in the graphDiscuss this resultChallenge it