op1525_even_deletion_switch_counterexample
For the cyclic action on six points, the subsets {0,1} and {0,2} have matching ordinary deletion decks, but the card formed by flipping point 4 in the second subset has no match in the first subset’s weak switching deck, even allowing global complementation. Thus odd subset size cannot be removed from the proposed unequal-deck equivalence.
Statement
theorem op1525_even_deletion_switch_counterexample : let a : Fin 6 → Bool := fun x => decide (x = 0 ∨ x = 1) let b : Fin 6 → Bool := fun x => decide (x = 0 ∨ x = 2) let erase : (Fin 6 → Bool) → Fin 6 → Fin 6 → Bool := fun f v x => f x && !(decide (x = v)) let flip : (Fin 6 → Bool) → Fin 6 → Fin 6 → Bool := fun f v x => xor (f x) (decide (x = v)) let rotateEquiv : (Fin 6 → Bool) → (Fin 6 → Bool) → Prop := fun f g => ∃ k : Fin 6, ∀ x, f (x + k) = g x let weakEquiv : (Fin 6 → Bool) → (Fin 6 → Bool) → Prop := fun f g => ∃ (k : Fin 6) (d : Bool), ∀ x, f (x + k) = xor (g x) d (∃ π : Equiv.Perm (Fin 6), ∀ v, a v = true → rotateEquiv (erase a v) (erase b (π v))) ∧ ∀ w : Fin 6, ¬ weakEquiv (flip b 4) (flip a w)
- Source
- A finite parity-boundary example for OP-1525, found by recorded computation 25013.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof establishes the counterexample by providing an explicit permutation between the deletion decks and verifying the required equivalences by finite exhaustion. We choose the permutation π on ℤ₆ to be the transposition (1 2), which maps 0 ↦ 0 and 1 ↦ 2. The first conjunct—that deleting v ∈ {0, 1} matches deleting π(v) from {0, 2} up to rotation—holds because the resulting singletons are cyclic shifts of each other. The second conjunct—that flipping 4 in {0, 2} produces {0, 2, 4}, which is not weakly equivalent to any card flipped from {0, 1}—holds because the weak orbit of {0, 2, 4} contains no adjacent points, whereas every size-3 card flipped from {0, 1} contains the adjacent pair {0, 1}. Both finite checks are settled by Lean's decide tactic.
To prove the theorem, it suffices to show that the transposition (1 2) matches the deletion decks of A and B, and that flipping point 4 in B produces a card with no weak match in the switching deck of A.
We unfold the definitions of the subsets A = {0, 1} and B = {0, 2}, the point deletion and flipping operations, and rotational and weak equivalence. To satisfy the existential quantifier for the permutation π between the deletion decks, we supply the transposition Equiv.swap 1 2, which swaps 1 and 2 while fixing 0. This splits the goal into two independent obligations: verifying deletion deck equivalence under π, and verifying the non-existence of a weak switching match.
uses
Equiv.swapdsimp only refine ⟨⟨Equiv.swap 1 2, ?_⟩, ?_⟩
The deletion deck of A matches the deletion deck of B under the permutation π = (1 2).
For each element v ∈ A = {0, 1}, deleting v from A must be rotationally equivalent to deleting π(v) from B = {0, 2}. For v = 0, deleting 0 leaves {1} in A and {2} in B (since π(0) = 0), which are related by a cyclic shift of 5 in ℤ₆ (since 2 + 5 ≡ 1 mod 6). For v = 1, deleting 1 leaves {0} in A while deleting π(1) = 2 leaves {0} in B, which are identical (shift 0). Because all quantifiers range over the finite type Fin 6, this is verified by exhaustive finite evaluation.
· decideThe switched card B Δ {4} is not weakly equivalent to any card obtained by flipping a single point in A.
Flipping point 4 in B = {0, 2} yields the three-element set {0, 2, 4}. Under cyclic shifts and global complementation, the only sets that can arise from {0, 2, 4} in ℤ₆ are {0, 2, 4} itself and its complement {1, 3, 5}, neither of which contains any pair of adjacent elements. In contrast, any card formed by flipping a point w in A = {0, 1} either has size 1 (if w ∈ {0, 1}, whose complement has size 5) or size 3 of the form {0, 1, w} (if w ∉ {0, 1}), which always contains the adjacent pair {0, 1}. Consequently, no shift and no complementation can ever equate B Δ {4} with any card flipped from A. The tactic closes the goal by exhaustively checking all w, k ∈ Fin 6 and d ∈ Bool.
· decide
Equiv.swap- the permutation that transposes two given elements and fixes all other elements
- Both subgoals are closed by Lean's `decide` tactic, which verifies the statements by brute-force evaluation over the finite domain Fin 6 rather than by structural reasoning about distances in ℤ₆.
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.
theorem op1525_even_deletion_switch_counterexample : let a : Fin 6 → Bool := fun x => decide (x = 0 ∨ x = 1) let b : Fin 6 → Bool := fun x => decide (x = 0 ∨ x = 2) let erase : (Fin 6 → Bool) → Fin 6 → Fin 6 → Bool := fun f v x => f x && !(decide (x = v)) let flip : (Fin 6 → Bool) → Fin 6 → Fin 6 → Bool := fun f v x => xor (f x) (decide (x = v)) let rotateEquiv : (Fin 6 → Bool) → (Fin 6 → Bool) → Prop := fun f g => ∃ k : Fin 6, ∀ x, f (x + k) = g x let weakEquiv : (Fin 6 → Bool) → (Fin 6 → Bool) → Prop := fun f g => ∃ (k : Fin 6) (d : Bool), ∀ x, f (x + k) = xor (g x) d (∃ π : Equiv.Perm (Fin 6), ∀ v, a v = true → rotateEquiv (erase a v) (erase b (π v))) ∧ ∀ w : Fin 6, ¬ weakEquiv (flip b 4) (flip a w) := by dsimp only refine ⟨⟨Equiv.swap 1 2, ?_⟩, ?_⟩ · decide · decide