AFTD Auto-Formalizing Theoretical Domains

not_is_uncomplemented_pair_compl

theoremverified

The family consisting of a set and its complement is not uncomplemented.

Statement

lemma not_is_uncomplemented_pair_compl {α : Type*} [Fintype α] [DecidableEq α] (A : Finset α) : ¬ is_uncomplemented ({A, Aᶜ} : Finset (Finset α))
Source
folklore
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For any finite type α with decidable equality, and for any finset A : Finset α, the family {A, Aᶜ} (consisting of A and its complement in α) is not uncomplemented.

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 theorem states that a two-element family $\{A, A^c\}$ consisting of a set and its complement is not uncomplemented. By definition, a family is uncomplemented if no member has its complement in the family. Since $A$ belongs to $\{A, A^c\}$ and its complement $A^c$ is also in the family, the condition is immediately violated, which simplification verifies directly.

  1. The family $\{A, A^c\}$ violates the uncomplemented condition because $A \in \{A, A^c\}$ has its complement $A^c \in \{A, A^c\}$.

    Unfolding the definition of `is_uncomplemented` rewrites the goal to $\neg (\forall S \in \{A, A^c\}, S^c \notin \{A, A^c\})$. Since $A \in \{A, A^c\}$ and its complement $A^c \in \{A, A^c\}$, the universal claim is false, and the simplification tactic detects this membership contradiction and reduces the negated proposition to truth.

    line 2

    uses is_uncomplemented, finset_fiber_family_empty

    lemma not_is_uncomplemented_pair_compl {α : Type*} [Fintype α] [DecidableEq α] (A : Finset α) : ¬ is_uncomplemented ({A, Aᶜ} : Finset (Finset α)) := by first | exact finset_fiber_family_empty | (apply finset_fiber_family_empty <;> assumption) | (apply finset_fiber_family_empty <;> simp_all) | simpa using finset_fiber_family_empty | (simp only [is_uncomplemented] at *; first | exact finset_fiber_family_empty | (apply finset_fiber_family_empty <;> assumption) | (apply finset_fiber_family_empty <;> simp_all) | simpa using finset_fiber_family_empty)
is_uncomplemented
A family of finite sets is uncomplemented if for every member set, its complement does not belong to the family.
finset_fiber_family_empty
The fiber family of the empty family of sets is empty.

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

/-- A pair of a set and its complement is not uncomplemented. -/lemma not_is_uncomplemented_pair_compl {α : Type*} [Fintype α] [DecidableEq α] (A : Finset α) : ¬ is_uncomplemented ({A, Aᶜ} : Finset (Finset α)) := by first | exact finset_fiber_family_empty | (apply finset_fiber_family_empty <;> assumption) | (apply finset_fiber_family_empty <;> simp_all) | simpa using finset_fiber_family_empty | (simp only [is_uncomplemented] at *; first | exact finset_fiber_family_empty | (apply finset_fiber_family_empty <;> assumption) | (apply finset_fiber_family_empty <;> simp_all) | simpa using finset_fiber_family_empty)
See it in the graphDiscuss this resultChallenge it