AFTD Auto-Formalizing Theoretical Domains

lift_linear_order_min_eq

theoremverified

If the global minimum of a linear order on Fin n lies in the range of an embedding f from Fin k to Fin n with f(j) = m, then j is the unique minimum of the induced linear order on Fin k.

Statement

theorem lift_linear_order_min_eq {k n : ℕ} (hk : 0 < k) (hn : 0 < n)
    (L : LinearOrder (Fin n)) (f : Fin k ↪ Fin n) (j : Fin k)
    (hj : f j = linearOrderMin hn L) :
    linearOrderMin hk (LinearOrder.lift' f.toFun f.injective) = j
Source
arXiv:2610.34762 Lemma 6 proof (Step 5)
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • linearOrderMinThe minimum element of Fin n with respect to a linear order L, for n > 0.
Used by 1
  • subset_transfer_two_comparisonsSuppose an algorithm on k objects succeeds in minimum selection with probability at least p on every strict order and uses at most two…

Read back from the Lean

For any natural numbers $k$ and $n$ satisfying $0 < k$ and $0 < n$, any linear order $L$ on $\mathrm{Fin}(n)$, any embedding (injective function) $f : \mathrm{Fin}(k) \hookrightarrow \mathrm{Fin}(n)$, and any element $j \in \mathrm{Fin}(k)$: if $f(j)$ is the minimum element of $\mathrm{Fin}(n)$ with respect to $L$ (as given by linearOrderMin), then $j$ is the minimum element of $\mathrm{Fin}(k)$ with respect to the linear order on $\mathrm{Fin}(k)$ lifted from $L$ via $f$ (LinearOrder.lift').

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that j is the minimum of Fin k in the induced linear order, it suffices to show that j ≤ b for all b ∈ Fin k. By definition of the order lifted along the embedding f, this is equivalent to f(j) ≤ f(b) in the ambient linear order on Fin n. Since f(j) is given to be the global minimum of Fin n, it is less than or equal to f(b) for all b, completing the proof.

  1. To show that j is the minimum of Fin k in the induced linear order, it suffices to show that j ≤ b for all b ∈ Fin k.

    Unfolding the definition of linearOrderMin, the goal is to show that the minimum of the universal set of Fin k under the induced order is j. By Finset.min'_eq_iff, an element is the minimum of a finite set if and only if it belongs to the set and is less than or equal to every element in it. Since j belongs to Finset.univ by Finset.mem_univ, this reduces to showing that j ≤ b for all b.

    lines 6–8

    uses Finset.min'_eq_iff, Finset.mem_univ

      change @Finset.min' (Fin k) (LinearOrder.lift' f.toFun f.injective) Finset.univ _ = j
      rw [@Finset.min'_eq_iff (Fin k) (LinearOrder.lift' f.toFun f.injective) Finset.univ _ j]
      refine ⟨Finset.mem_univ _, ?_⟩
  2. For any b ∈ Fin k, the inequality j ≤ b in the induced linear order is equivalent to f(j) ≤ f(b) in the ambient order L.

    Fix an arbitrary b ∈ Fin k. By the definition of the induced linear order LinearOrder.lift', the relation j ≤ b on Fin k is defined directly as f(j) ≤ f(b) under the ambient linear order L on Fin n.

    lines 9–11

      intro b _
      show (LinearOrder.lift' f.toFun f.injective).le j b
      change L.le (f j) (f b)
  3. The inequality f(j) ≤ f(b) holds because f(j) is the global minimum of the order L.

    Rewriting with the hypothesis hj replaces f(j) with the global minimum linearOrderMin hn L. By Finset.min'_le, the minimum of the universal set Finset.univ under L is less than or equal to any element in Finset.univ, which includes f(b) by Finset.mem_univ.

    lines 12–13

    uses Finset.min'_le, Finset.mem_univ

      rw [hj]
      exact @Finset.min'_le (Fin n) L Finset.univ (f b) (Finset.mem_univ _)
Finset.min'_eq_iff
An element is the minimum of a nonempty finite set with respect to a linear order if and only if it belongs to the set and is less than or equal to every element in the set.
Finset.mem_univ
Every element of a finite type belongs to its universal set Finset.univ.
Finset.min'_le
The minimum of a nonempty finite set is less than or equal to any element of that set.

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

/-- The pre-image of the global minimum under an embedding is the minimum of the induced linear order. -/theorem lift_linear_order_min_eq {k n : ℕ} (hk : 0 < k) (hn : 0 < n)    (L : LinearOrder (Fin n)) (f : Fin k ↪ Fin n) (j : Fin k)    (hj : f j = linearOrderMin hn L) :    linearOrderMin hk (LinearOrder.lift' f.toFun f.injective) = j := by  change @Finset.min' (Fin k) (LinearOrder.lift' f.toFun f.injective) Finset.univ _ = j  rw [@Finset.min'_eq_iff (Fin k) (LinearOrder.lift' f.toFun f.injective) Finset.univ _ j]  refine ⟨Finset.mem_univ _, ?_⟩  intro b _  show (LinearOrder.lift' f.toFun f.injective).le j b  change L.le (f j) (f b)  rw [hj]  exact @Finset.min'_le (Fin n) L Finset.univ (f b) (Finset.mem_univ _)
See it in the graphDiscuss this resultChallenge it