AFTD Auto-Formalizing Theoretical Domains

is_perfect_set_two

theoremverifiedformalization

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.

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

    line 4

      refine ⟨?_, ?_, ?_⟩
  2. The singleton set $\{\operatorname{swap}(0, 1)\}$ has cardinality $2 - 1$. automation

    The cardinality of any singleton set is $1$, which equals $2 - 1$.

    line 5

      · simp
  3. Every 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.

    lines 6–11

    uses Finset.mem_singleton, derangements

      · intro σ hσ
        simp only [Finset.mem_singleton] at hσ
        subst hσ
        dsimp [derangements]
        intro x
        fin_cases x <;> decide
  4. 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.

    lines 12–15

    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

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