involution_equal_blocks_internal_card
If an involution preserves the union of two disjoint finite blocks of equal cardinality, the number of vertices paired internally in the first block equals the corresponding number in the second block. It suffices that the involution identity hold on their union.
Statement
theorem involution_equal_blocks_internal_card {V : Type*} [DecidableEq V] (p : V → V) (A B : Finset V) (hdis : Disjoint A B) (hcard : A.card = B.card) (hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B) (hinv : ∀ v ∈ A ∪ B, p (p v) = v) : (A.filter fun v => p v ∈ A).card = (B.filter fun v => p v ∈ B).card
- Source
- IN-338 structural/repair helpers for OP-306, the prescribed-coloring conjecture in arXiv:2610.22142 Sections3.3.2 and6. Exact matching-involution balance and the method obstruction computed in experiment8464. These are certificate/method lemmas, not new wild-number bounds or research advances.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- wild_rainbow_equal_blocks_closed_matching_crossesIn a properly colored complete graph with one specified missing vertex for each color, let two disjoint equally sized blocks have no…
The proof, explained
The proof partitions each block into internally paired elements (mapped into the same block) and cross-paired elements (mapped into the other block). Because the involution p stabilizes A ∪ B and the blocks are disjoint, an element leaves its block if and only if it lands in the other. Applying p to the cross-paired elements yields a bijection between those in A and those in B, showing both cross-paired sets have equal cardinality. Subtracting these equal cross-counts from the equal total cardinalities |A| = |B| establishes that the internal counts are also equal.
The number of vertices in A mapped into B equals the number of vertices in B mapped into A.
The involution p acts as a bijection between {v ∈ A | p v ∈ B} and {v ∈ B | p v ∈ A} via card_nbij'. For v ∈ A with p(v) ∈ B, the involution property p(p(v)) = v implies p(v) is mapped back to A, so p maps the first set into the second. By symmetry, p maps the second set into the first. Since both sets are contained in A ∪ B, p(p(v)) = v holds on each, confirming that p is its own inverse on these subsets.
uses
card_nbij',mem_filter,mem_union_left,mem_union_righthave hcross : (A.filter fun v => p v ∈ B).card = (B.filter fun v => p v ∈ A).card := by refine card_nbij' p p ?_ ?_ ?_ ?_ · intro v hv obtain ⟨hvA, hpB⟩ := mem_filter.mp hv exact mem_filter.mpr ⟨hpB, by rw [hinv v (mem_union_left B hvA)]; exact hvA⟩ · intro v hv obtain ⟨hvB, hpA⟩ := mem_filter.mp hv exact mem_filter.mpr ⟨hpA, by rw [hinv v (mem_union_right A hvB)]; exact hvB⟩ · intro v hv exact hinv v (mem_union_left B (mem_filter.mp hv).1) · intro v hv exact hinv v (mem_union_right A (mem_filter.mp hv).1)
The elements of A not mapped into A are precisely those mapped into B.
By set extensionality, an element v ∈ A has p(v) ∉ A if and only if p(v) ∈ B. By stability of A ∪ B under p, p(v) must belong to A or B (mem_union). If p(v) ∉ A, it must belong to B. Conversely, because A and B are disjoint (disjoint_left), if p(v) ∈ B then p(v) ∉ A.
uses
mem_filter,mem_union,mem_union_left,disjoint_lefthave hApart : A.filter (fun v => p v ∉ A) = A.filter (fun v => p v ∈ B) := by ext v simp only [mem_filter] constructor · rintro ⟨hvA, hpA⟩ exact ⟨hvA, (mem_union.mp (hstable v (mem_union_left B hvA))).resolve_left hpA⟩ · rintro ⟨hvA, hpB⟩ exact ⟨hvA, fun hpA => disjoint_left.mp hdis hpA hpB⟩
The elements of B not mapped into B are precisely those mapped into A.
Symmetrically, by extensionality, an element v ∈ B has p(v) ∉ B if and only if p(v) ∈ A. Stability guarantees p(v) ∈ A ∪ B (mem_union), so p(v) ∉ B forces p(v) ∈ A. Conversely, disjointness of A and B (disjoint_left) ensures that p(v) ∈ A forces p(v) ∉ B.
uses
mem_filter,mem_union,mem_union_right,disjoint_lefthave hBpart : B.filter (fun v => p v ∉ B) = B.filter (fun v => p v ∈ A) := by ext v simp only [mem_filter] constructor · rintro ⟨hvB, hpB⟩ exact ⟨hvB, (mem_union.mp (hstable v (mem_union_right A hvB))).resolve_right hpB⟩ · rintro ⟨hvB, hpA⟩ exact ⟨hvB, fun hpB => disjoint_left.mp hdis hpA hpB⟩
|{v ∈ A | p v ∈ A}| + |{v ∈ A | p v ∈ B}| = |A| and |{v ∈ B | p v ∈ B}| + |{v ∈ B | p v ∈ A}| = |B|.
Partitioning A into elements mapped into A and elements not mapped into A decomposes |A| into the sum of these two counts (card_filter_add_card_filter_not). Rewriting with hApart replaces the non-internal elements with those mapped into B. The identical partitioning and rewrite with hBpart on B gives the corresponding sum decomposition for |B|.
uses
card_filter_add_card_filter_nothave hAcount := card_filter_add_card_filter_not (s := A) (fun v => p v ∈ A) have hBcount := card_filter_add_card_filter_not (s := B) (fun v => p v ∈ B) rw [hApart] at hAcount rw [hBpart] at hBcount
The number of internally paired vertices in A equals the number of internally paired vertices in B.
Linear arithmetic (omega) finishes the proof: |A| = |B| by hypothesis, the cross-paired counts |{v ∈ A | p v ∈ B}| and |{v ∈ B | p v ∈ A}| are equal by hcross, and subtracting these equal cross-counts from the equal block totals in hAcount and hBcount yields equal internal counts.
omega
card_nbij'- Two finite sets have equal cardinality if there are maps between them that are mutually inverse on the two sets.
mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
mem_union_left- If an element belongs to a finset s, it belongs to the union s ∪ t.
mem_union_right- If an element belongs to a finset t, it belongs to the union s ∪ t.
mem_union- An element belongs to the union s ∪ t if and only if it belongs to s or to t.
disjoint_left- Two finsets are disjoint if and only if no element of the first belongs to the second.
card_filter_add_card_filter_not- For any predicate on a finite set, the number of elements satisfying it plus the number of elements not satisfying it equals the cardinality of the set.
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.
open Finsetset_option maxHeartbeats 2500000theorem involution_equal_blocks_internal_card {V : Type*} [DecidableEq V] (p : V → V) (A B : Finset V) (hdis : Disjoint A B) (hcard : A.card = B.card) (hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B) (hinv : ∀ v ∈ A ∪ B, p (p v) = v) : (A.filter fun v => p v ∈ A).card = (B.filter fun v => p v ∈ B).card := by have hcross : (A.filter fun v => p v ∈ B).card = (B.filter fun v => p v ∈ A).card := by refine card_nbij' p p ?_ ?_ ?_ ?_ · intro v hv obtain ⟨hvA, hpB⟩ := mem_filter.mp hv exact mem_filter.mpr ⟨hpB, by rw [hinv v (mem_union_left B hvA)]; exact hvA⟩ · intro v hv obtain ⟨hvB, hpA⟩ := mem_filter.mp hv exact mem_filter.mpr ⟨hpA, by rw [hinv v (mem_union_right A hvB)]; exact hvB⟩ · intro v hv exact hinv v (mem_union_left B (mem_filter.mp hv).1) · intro v hv exact hinv v (mem_union_right A (mem_filter.mp hv).1) have hApart : A.filter (fun v => p v ∉ A) = A.filter (fun v => p v ∈ B) := by ext v simp only [mem_filter] constructor · rintro ⟨hvA, hpA⟩ exact ⟨hvA, (mem_union.mp (hstable v (mem_union_left B hvA))).resolve_left hpA⟩ · rintro ⟨hvA, hpB⟩ exact ⟨hvA, fun hpA => disjoint_left.mp hdis hpA hpB⟩ have hBpart : B.filter (fun v => p v ∉ B) = B.filter (fun v => p v ∈ A) := by ext v simp only [mem_filter] constructor · rintro ⟨hvB, hpB⟩ exact ⟨hvB, (mem_union.mp (hstable v (mem_union_right A hvB))).resolve_right hpB⟩ · rintro ⟨hvB, hpA⟩ exact ⟨hvB, fun hpB => disjoint_left.mp hdis hpA hpB⟩ have hAcount := card_filter_add_card_filter_not (s := A) (fun v => p v ∈ A) have hBcount := card_filter_add_card_filter_not (s := B) (fun v => p v ∈ B) rw [hApart] at hAcount rw [hBpart] at hBcount omega