is_perfect_set_two
The singleton set containing the transposition swap 0 1 on Fin 2 is a perfect set of order 2.
Statement
theorem is_perfect_set_two :
is_perfect_set 2 {Equiv.swap (0 : Fin 2) (1 : Fin 2)}- Formalizes
- folklore
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_perfect_setA perfect set of order n is a finite set of n - 1 permutations of Fin n that are derangements and pairwise mutually deranged.
Read back from the Lean
The singleton set containing the transposition of $0$ and $1$ (in the permutation group of $\mathrm{Fin}\ 2$) is a "perfect set" of degree $2$ (satisfies is_perfect_set 2).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the singleton set $\{\operatorname{swap}(0, 1)\}$ is a perfect set of order $2$, we verify the three conditions in the definition of `is_perfect_set`. The cardinality condition $|\{\operatorname{swap}(0, 1)\}| = 2 - 1 = 1$ holds immediately. The derangement condition is verified by checking both elements of $\operatorname{Fin} 2$, confirming that the transposition $\operatorname{swap}(0, 1)$ leaves no point fixed. Finally, the requirement that distinct permutations disagree everywhere holds vacuously because a singleton contains no two distinct elements.
It suffices to verify the three defining conditions of a perfect set: cardinality $2 - 1$, derangement of each element, and pairwise disagreement of distinct elements.
The definition of `is_perfect_set 2 S` is the conjunction of three properties: $|S| = 2 - 1$, every permutation in $S$ is fixed-point-free, and distinct permutations in $S$ disagree on every input. Decomposing this conjunction yields three separate subgoals.
refine ⟨?_, ?_, ?_⟩The singleton set $\{\operatorname{swap}(0, 1)\}$ has cardinality $2 - 1$. automation
The cardinality of any singleton set is $1$, which equals $2 - 1$.
· simpEvery permutation in $\{\operatorname{swap}(0, 1)\}$ is a derangement on $\operatorname{Fin} 2$.
Since the set is a singleton, any element $\sigma$ in it must equal $\operatorname{swap}(0, 1)$. By definition, being a derangement means having no fixed points. Exhausting the two elements of $\operatorname{Fin} 2$, we compute $\operatorname{swap}(0, 1)(0) = 1 \neq 0$ and $\operatorname{swap}(0, 1)(1) = 0 \neq 1$, so the transposition fixes no elements.
uses
Finset.mem_singleton,derangements· intro σ hσ simp only [Finset.mem_singleton] at hσ subst hσ dsimp [derangements] intro x fin_cases x <;> decide
Any two distinct permutations in $\{\operatorname{swap}(0, 1)\}$ disagree at every point in $\operatorname{Fin} 2$.
Suppose $\sigma$ and $\tau$ are permutations in $\{\operatorname{swap}(0, 1)\}$ with $\sigma \neq \tau$. Because both belong to the singleton set, both equal $\operatorname{swap}(0, 1)$, implying $\sigma = \tau$. This contradicts the assumption $\sigma \neq \tau$, so the claim holds vacuously.
uses
Finset.mem_singleton· intro σ hσ τ hτ hne simp only [Finset.mem_singleton] at hσ hτ subst hσ hτ exact (hne rfl).elim
Finset.mem_singleton- An element $b$ belongs to the singleton set $\{a\}$ if and only if $b = a$.
derangements- The set of permutations of a type that leave no element fixed, that is, $\sigma(x) \neq x$ for all $x$.
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.
/-- The swap on Fin 2 forms a perfect set of order 2. -/theorem is_perfect_set_two : is_perfect_set 2 {Equiv.swap (0 : Fin 2) (1 : Fin 2)} := by refine ⟨?_, ?_, ?_⟩ · simp · intro σ hσ simp only [Finset.mem_singleton] at hσ subst hσ dsimp [derangements] intro x fin_cases x <;> decide · intro σ hσ τ hτ hne simp only [Finset.mem_singleton] at hσ hτ subst hσ hτ exact (hne rfl).elim