AFTD Auto-Formalizing Theoretical Domains

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.
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

Lean source view module on GitHub

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