not_is_uncomplemented_pair_compl
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
- is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- finset_fiber_family_emptyThe fiber family of the empty family is empty.
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.
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.
uses
is_uncomplemented,finset_fiber_family_emptylemma 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.
- The proof script was generated by an automated search pattern (`first | ...`). Although `finset_fiber_family_empty` is passed to `simpa`, it is entirely unused: once `is_uncomplemented` is unfolded, `simp` closes the goal by directly evaluating the finite set memberships.
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.
/-- 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)