perm_card_val_lt
theoremverified
For a permutation s of {0, ..., n-1} and c in {0, ..., n-1}, exactly c elements x have s(x) < c.
Statement
theorem perm_card_val_lt {n : ℕ} (σ : Equiv.Perm (Fin n)) (c : Fin n) : (Finset.univ.filter fun x : Fin n => (σ x : ℕ) < c).card = c
- Source
- step towards hollow_shell_blocking_pairs_ncard_le (Shield-Core upper bound, A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem (2026), arXiv:2609.17418, Sec. 7.1)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- perm_inv_left_addFor a permutation s of {0, ..., n-1} and a position g, the number of x < g with s(x) > s(g), plus s(g), equals the number of x > g with…
- perm_card_left_gt_leFor a permutation s of {0, ..., n-1} and a position x with x <= s(x), the number of i < x with s(i) > s(x) is at most the number of j > x…
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.
theorem perm_card_val_lt {n : ℕ} (σ : Equiv.Perm (Fin n)) (c : Fin n) : (Finset.univ.filter fun x : Fin n => (σ x : ℕ) < c).card = c := by have h1 : (Finset.univ.filter fun x : Fin n => (σ x : ℕ) < c) = (Finset.Iio c).map σ.symm.toEmbedding := by ext x simp [Finset.mem_map_equiv] rw [h1, Finset.card_map, Fin.card_Iio]