AFTD Auto-Formalizing Theoretical Domains

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

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