forward_biased_selector_output_unique
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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
- forward_biased_selector_dominating_and_computableOn every Markov paging instance with n pages, cache C, fault on page s, and hitting probabilities α, assuming the dominating distribution…
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.
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₂`).
obtain ⟨hopt₁, hmin₁⟩ := h₁ obtain ⟨hopt₂, hmin₂⟩ := h₂
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 μ₁.
rcases hmin₁ μ₂ hopt₂ with h | h · exact h.symm
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 μ₂.
rcases hmin₂ μ₁ hopt₁ with h' | h' · exact h'
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`).
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)
- Lean uses the type synonym wrapper `toLex` to equip the function type `Fin n → ℝ` with the lexicographic preorder (`Pi.Lex`), allowing the strict relation to be written using `<` and enabling standard preorder lemmas like `lt_irrefl`.
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.
/-- 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)