AFTD Auto-Formalizing Theoretical Domains

forward_biased_selector_output_unique

theoremverified

For any cache C, hitting probabilities α, and target page e, if μ₁ and μ₂ both satisfy is_forward_biased_selector_output C α e, then μ₁ = μ₂.

Statement

theorem forward_biased_selector_output_unique {n : ℕ} {C : Finset (Fin n)}
    {α : Fin n → Fin n → ℝ} {e : Fin n} {μ₁ μ₂ : Fin n → ℝ}
    (h₁ : is_forward_biased_selector_output C α e μ₁)
    (h₂ : is_forward_biased_selector_output C α e μ₂) :
    μ₁ = μ₂
Source
arXiv:2610.40824 Proposition 7
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_forward_biased_selector_outputA distribution μ is the forward-biased selector output for cache C, hitting probabilities α, and target page e if μ is an optimal solution…
  • 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…
  • is_forward_biased_optimalA distribution μ is an optimal solution to the forward-biased linear program if μ is a dominating distribution supported on cache C and…
Used by 1

Read back from the Lean

For any natural number $n$, any subset $C \subseteq \mathrm{Fin}(n)$, any function $\alpha : \mathrm{Fin}(n) \to \mathrm{Fin}(n) \to \mathbb{R}$, any element $e \in \mathrm{Fin}(n)$, and any functions $\mu_1, \mu_2 : \mathrm{Fin}(n) \to \mathbb{R}$: if both $\mu_1$ and $\mu_2$ are forward-biased selector outputs for $(C, \alpha, e)$, then $\mu_1 = \mu_2$. That is, the forward-biased selector output associated with $(C, \alpha, e)$ is unique.

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

The proof establishes uniqueness by the antisymmetry of the strict lexicographic order. A forward-biased selector output is an optimal distribution such that any other optimal distribution is either equal to it or strictly lexicographically smaller. Applying this property mutually to μ₁ and μ₂ implies that either they are equal, or each is strictly lexicographically smaller than the other, which contradicts the irreflexivity of strict inequality.

  1. Both μ₁ and μ₂ are optimal distributions, and any optimal distribution ν is either equal to μ₁ (resp. μ₂) or strictly lexicographically smaller than μ₁ (resp. μ₂).

    Unpack the definition of `is_forward_biased_selector_output` for both μ₁ (giving optimality `hopt₁` and maximality `hmin₁`) and μ₂ (giving optimality `hopt₂` and maximality `hmin₂`).

    lines 7–8

      obtain ⟨hopt₁, hmin₁⟩ := h₁
      obtain ⟨hopt₂, hmin₂⟩ := h₂
  2. Either μ₁ = μ₂, or μ₂ is strictly lexicographically smaller than μ₁.

    Because μ₂ is an optimal distribution (`hopt₂`), instantiate the condition `hmin₁` with ν = μ₂. In the first case, μ₂ = μ₁, which immediately yields μ₁ = μ₂ by symmetry. In the second case, μ₂ is strictly lexicographically smaller than μ₁.

    lines 9–10

      rcases hmin₁ μ₂ hopt₂ with h | h
      · exact h.symm
  3. Assuming μ₂ is strictly lexicographically smaller than μ₁, either μ₁ = μ₂ (closing the goal) or μ₁ is strictly lexicographically smaller than μ₂.

    Because μ₁ is optimal (`hopt₁`), instantiate the condition `hmin₂` with ν = μ₁. This gives either μ₁ = μ₂, which settles the claim directly, or that μ₁ is strictly lexicographically smaller than μ₂.

    lines 11–12

      rcases hmin₂ μ₁ hopt₁ with h' | h'
      · exact h'
  4. The remaining case, where both μ₂ <_lex μ₁ and μ₁ <_lex μ₂ hold simultaneously, is impossible.

    Cast both lexicographic inequalities to strict inequalities on `toLex`. By transitivity, `toLex μ₁ < toLex μ₁`, which contradicts the irreflexivity of strict inequality (`lt_irrefl`).

    lines 13–16

    uses toLex, lt_irrefl

      · exfalso
        have hlt1 : toLex μ₁ < toLex μ₂ := h'
        have hlt2 : toLex μ₂ < toLex μ₁ := h
        exact lt_irrefl _ (hlt1.trans hlt2)
toLex
the canonical equivalence between a type and its lexicographically ordered synonym `Lex α`
lt_irrefl
strict inequality is irreflexive: no element is strictly less than itself (¬a < a)

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

/-- Uniqueness of the forward-biased selector output. -/theorem forward_biased_selector_output_unique {n : ℕ} {C : Finset (Fin n)}    {α : Fin n → Fin n → ℝ} {e : Fin n} {μ₁ μ₂ : Fin n → ℝ}    (h₁ : is_forward_biased_selector_output C α e μ₁)    (h₂ : is_forward_biased_selector_output C α e μ₂) :    μ₁ = μ₂ := by  obtain ⟨hopt₁, hmin₁⟩ := h₁  obtain ⟨hopt₂, hmin₂⟩ := h₂  rcases hmin₁ μ₂ hopt₂ with h | h  · exact h.symm  rcases hmin₂ μ₁ hopt₁ with h' | h'  · exact h'  · exfalso    have hlt1 : toLex μ₁ < toLex μ₂ := h'    have hlt2 : toLex μ₂ < toLex μ₁ := h    exact lt_irrefl _ (hlt1.trans hlt2)
See it in the graphDiscuss this resultChallenge it