countable_lex_stream_order_embedding_exists
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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}$.
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$.
uses
exists_strictly_ordered_intervalsobtain ⟨l, r, ⟨h1, h2⟩⟩ := exists_strictly_ordered_intervals (A := A)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}$.
uses
lex_stream_order_embedding_of_intervalsexact 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
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 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