AFTD Auto-Formalizing Theoretical Domains

finset_one_inclusion_graph_adj_empty_singleton

theoremverified

In the one-inclusion graph of {∅, {a}}, ∅ and {a} are adjacent.

Statement

theorem finset_one_inclusion_graph_adj_empty_singleton {α : Type*} [DecidableEq α] (a : α) :
    (finset_one_inclusion_graph ({∅, {a}} : Finset (Finset α))).Adj
      ⟨∅, by simp⟩ ⟨{a}, by simp⟩
Source
Sanity lemma for finset_one_inclusion_graph (arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs)).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finset_one_inclusion_graphThe one-inclusion graph G_1(F) of a set system F: its vertices are the members of F, two members adjacent when their symmetric difference…
Used by 1

The proof, explained

Two vertices in the one-inclusion graph are adjacent if and only if their symmetric difference has cardinality 1. The proof shows that the symmetric difference of the empty set and {a} equals {a}, and then evaluates its cardinality to 1 using Finset.card_singleton.

  1. ∅ and {a} are members of the family {∅, {a}}

    The vertices of the one-inclusion graph are terms of the subtype of elements belonging to {∅, {a}}. The membership conditions ∅ ∈ {∅, {a}} and {a} ∈ {∅, {a}} are verified by simplification.

    line 3

          ⟨∅, by simp⟩ ⟨{a}, by simp⟩ := by
  2. Adjacency of ∅ and {a} reduces to showing |∅ △ {a}| = 1

    By definition of the one-inclusion graph, two vertices are adjacent if and only if the cardinality of their symmetric difference is 1.

    line 4

      show (symmDiff (∅ : Finset α) {a}).card = 1
  3. ∅ △ {a} = {a}

    By extensionality, two finite sets are equal if they contain the same elements. By Finset.mem_symmDiff, x ∈ ∅ △ {a} means (x ∈ ∅ ∧ x ∉ {a}) ∨ (x ∈ {a} ∧ x ∉ ∅); since ∅ has no elements, simplification reduces this to x ∈ {a}.

    lines 5–6

    uses Finset.mem_symmDiff

      have h : symmDiff (∅ : Finset α) {a} = {a} := by
        ext x; simp [Finset.mem_symmDiff]
  4. The symmetric difference has cardinality 1, completing the proof

    Rewriting the symmetric difference with {a} using the identity just established, the goal becomes |{a}| = 1, which holds by Finset.card_singleton.

    line 7

    uses Finset.card_singleton

      rw [h, Finset.card_singleton]
Finset.mem_symmDiff
An element belongs to the symmetric difference of two finite sets if and only if it belongs to the first and not the second, or to the second and not the first.
Finset.card_singleton
The cardinality of any singleton finite set {a} is 1.

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

theorem finset_one_inclusion_graph_adj_empty_singleton {α : Type*} [DecidableEq α] (a : α) :    (finset_one_inclusion_graph ({∅, {a}} : Finset (Finset α))).Adj      ⟨∅, by simp⟩ ⟨{a}, by simp⟩ := by  show (symmDiff (∅ : Finset α) {a}).card = 1  have h : symmDiff (∅ : Finset α) {a} = {a} := by    ext x; simp [Finset.mem_symmDiff]  rw [h, Finset.card_singleton]
See it in the graphDiscuss this resultChallenge it