AFTD Auto-Formalizing Theoretical Domains

not_is_perm_cover_empty

theoremverified

For any natural number k, the empty set does not satisfy is_perm_cover k ∅.

Statement

theorem not_is_perm_cover_empty (k : ℕ) : ¬ is_perm_cover k ∅
Source
folklore, sanity lemma for is_perm_cover
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_perm_coverFor a natural number k and a finite set C of natural numbers, is_perm_cover k C holds if every d in C is strictly positive (0 < d), and…

Read back from the Lean

For every natural number $k$, the empty set is not a permutation cover for $k$ (¬ is_perm_cover k ∅).

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

The proof proceeds by contradiction. If the empty set were a permutation cover for the symmetric group on $k$ elements, then by definition the order of every permutation—including the identity permutation—would divide some element $d \in \emptyset$. However, the empty set contains no elements, immediately producing a contradiction.

  1. Assuming the empty set is a permutation cover, it must contain some element $d$.

    Assume for contradiction that $\emptyset$ is a permutation cover for the symmetric group on $k$ elements. By definition of `is_perm_cover`, every permutation $\sigma$ must have its order divide some element of the cover. Evaluating this property at the identity permutation $\sigma = 1$ yields an element $d \in \emptyset$ (whose order divides $d$).

    lines 3–4

      intro h
      obtain ⟨d, hd, -⟩ := h.2 1
  2. Contradiction.

    By `Finset.notMem_empty`, the empty set contains no elements, contradicting $d \in \emptyset$.

    line 5

    uses Finset.notMem_empty

      exact Finset.notMem_empty d hd
Finset.notMem_empty
No element is a member of the empty finite set: $a \notin \emptyset$ for all $a$.

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 empty set is never a cover for the symmetric group on k elements. -/theorem not_is_perm_cover_empty (k : ℕ) : ¬ is_perm_cover k ∅ := by  intro h  obtain ⟨d, hd, -⟩ := h.2 1  exact Finset.notMem_empty d hd
See it in the graphDiscuss this resultChallenge it