AFTD Auto-Formalizing Theoretical Domains

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

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]
See it in the graphDiscuss this resultChallenge it