list_lex_map_iff_of_strictMono
lemmaverified
A strictly monotone map from naturals to reals preserves and reflects the strict lexicographic order on lists.
Statement
lemma list_lex_map_iff_of_strictMono {f : ℕ → ℝ} (hf : StrictMono f) :
∀ l₁ l₂ : List ℕ, List.Lex (· < ·) (l₁.map f) (l₂.map f) ↔ List.Lex (· < ·) l₁ l₂- Source
- step towards leximin_ef1_not_pareto_optimal (conjecture of The Unreasonable Fairness of Maximum Nash Welfare, ACM TEAC 7(3), 2019, App. B)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- lxv_leximin_lt_iffIn the instance, the real leximin comparison is equivalent to the lexicographic comparison of integer profiles.
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.
/-- Lexicographic order is preserved and reflected by a strictly monotone map. -/lemma list_lex_map_iff_of_strictMono {f : ℕ → ℝ} (hf : StrictMono f) : ∀ l₁ l₂ : List ℕ, List.Lex (· < ·) (l₁.map f) (l₂.map f) ↔ List.Lex (· < ·) l₁ l₂ := by intro l₁ induction l₁ with | nil => intro l₂; cases l₂ <;> simp | cons a l₁ ih => intro l₂ cases l₂ with | nil => simp | cons b l₂ => simp only [List.map_cons, List.cons_lex_cons_iff, hf.lt_iff_lt, hf.injective.eq_iff, ih l₂]