sages_row_other_than_ne
For S ≥ 2, the canonical other sage of x (seat 1 if x is at seat 0, else seat 0) is not x.
Statement
theorem sages_row_other_than_ne {S : ℕ} (hS : 2 ≤ S) (x : Fin S) :
sages_row_other_than hS x ≠ x- Source
- step towards sages_row_upper_bound_binomial
- Verified
- 31 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- sages_row_other_thanFor S ≥ 2 sages, a canonical sage other than a given sage x: seat 1 if x occupies seat 0, and seat 0 otherwise.
The proof, explained
The proof proceeds by contradiction. Assuming the canonical other sage of x is x itself, we project this equality to the underlying seat numbers, obtaining (if x = 0 then 1 else 0) = x. A case split on whether x = 0 yields 1 = 0 in the first case and 0 = x ≠ 0 in the second, both of which are impossible.
Assuming the canonical partner equals x, the underlying seat index satisfies (if x = 0 then 1 else 0) = x.
We argue by contradiction, assuming that `sages_row_other_than hS x = x`. Applying `congrArg` with `Fin.val` extracts the equality of the underlying natural numbers. Unfolding the definition of `sages_row_other_than` simplifies this equality to `(if x = 0 then 1 else 0) = x`.
uses
congrArg,Fin.valintro h have hv := congrArg Fin.val h simp only [sages_row_other_than] at hv
Both branches of the case analysis contradict the assumption, completing the proof.
We split into cases based on whether the seat index of x is 0 (`split_ifs`). If x = 0, the equation reduces to 1 = 0, an immediate contradiction. If x ≠ 0, the equation reduces to 0 = x, which contradicts x ≠ 0. In each branch, linear integer arithmetic (`omega`) detects the contradiction.
split_ifs at hv with h0 <;> omega
congrArg- Equal inputs produce equal outputs under any function: if a₁ = a₂, then f a₁ = f a₂.
Fin.val- The underlying natural number represented by an element of Fin n.
- In Lean, elements of `Fin S` bundle a natural number with a proof that it is strictly less than `S`; line 5 explicitly projects equality in `Fin S` to equality in `ℕ` via `congrArg Fin.val`, a step that is implicit on paper.
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.
/-- The canonical partner `sages_row_other_than hS x` really is a different sage from `x`. -/theorem sages_row_other_than_ne {S : ℕ} (hS : 2 ≤ S) (x : Fin S) : sages_row_other_than hS x ≠ x := by intro h have hv := congrArg Fin.val h simp only [sages_row_other_than] at hv split_ifs at hv with h0 <;> omega