CodingTheory.Johnson.card_filter_add_two
theoremverifiedimported Lean
Removing an element and its negation costs at most two. Let $S$ be a finite subset of an additive group $V$, and let $u \in S$. Then \[ \abs{S} \le \abs{\{\, v \in S : v \neq u \text{ and } v \neq -u \,\}} + 2. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators RealInnerProductSpace in open Finset in open Classical in open scoped RealInnerProductSpace in open scoped InnerProductSpace in open Finset in open Classical in attribute [local instance] Classical.dec in lemma CodingTheory.Johnson.card_filter_add_two {V : Type*} [AddGroup V] (S : Finset V) (u : V) (_hu : u ∈ S) : S.card ≤ (S.filter (fun v => v ≠ u ∧ v ≠ -u)).card + 2
- Source
- TCSlib, `CodingTheory.Johnson.card_filter_add_two`
- Lean proof
- By Allan Li, Frederick Dehmel, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CodingTheory.Johnson.card_filter_add_two← CodingTheory.Johnson.card_filter_add_two (TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:342): adapted
What was changed in
CodingTheory.Johnson.card_filter_add_two--- TCSlib/ErrorCorrectingCodes/JohnsonBound.lean:342 (CodingTheory.Johnson.card_filter_add_two) +++ as compiled here @@ -1,2 +1,12 @@ -lemma card_filter_add_two {V : Type*} [AddGroup V] +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open scoped BigOperators RealInnerProductSpace in +open Finset in +open Classical in +open scoped RealInnerProductSpace in +open scoped InnerProductSpace in +open Finset in +open Classical in +attribute [local instance] Classical.dec in +lemma CodingTheory.Johnson.card_filter_add_two {V : Type*} [AddGroup V] (S : Finset V) (u : V) (_hu : u ∈ S) : @@ -5,3 +15,3 @@ suffices (S.filter (fun v => ¬(v ≠ u ∧ v ≠ -u))).card ≤ 2 by - have := Finset.filter_card_add_filter_neg_card_eq_card (s := S) (p := fun v => v ≠ u ∧ v ≠ -u) + have := Finset.card_filter_add_card_filter_not (s := S) (p := fun v => v ≠ u ∧ v ≠ -u) omega - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- CodingTheory.Johnson.rankin_bound_generalRankin bound in a finite-dimensional space. Let $V$ be a finite-dimensional real inner product space, and let $S$ be a finite set of…
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen scoped BigOperators RealInnerProductSpace inopen Finset inopen Classical inopen scoped RealInnerProductSpace inopen scoped InnerProductSpace inopen Finset inopen Classical inattribute [local instance] Classical.dec inlemma CodingTheory.Johnson.card_filter_add_two {V : Type*} [AddGroup V] (S : Finset V) (u : V) (_hu : u ∈ S) : S.card ≤ (S.filter (fun v => v ≠ u ∧ v ≠ -u)).card + 2 := by classical suffices (S.filter (fun v => ¬(v ≠ u ∧ v ≠ -u))).card ≤ 2 by have := Finset.card_filter_add_card_filter_not (s := S) (p := fun v => v ≠ u ∧ v ≠ -u) omega have hsub : S.filter (fun v => ¬(v ≠ u ∧ v ≠ -u)) ⊆ {u, -u} := by intro v hv simp only [Finset.mem_filter, not_and_or, not_ne_iff] at hv simp only [Finset.mem_insert, Finset.mem_singleton] tauto exact le_trans (Finset.card_le_card hsub) (le_trans (Finset.card_insert_le u {-u}) (by simp))