AFTD Auto-Formalizing Theoretical Domains

finset_one_inclusion_graph_not_adj_empty_pair

theoremverified

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

Statement

theorem finset_one_inclusion_graph_not_adj_empty_pair {α : Type*} [DecidableEq α] (a b : α)
    (hab : a ≠ b) :
    ¬ (finset_one_inclusion_graph ({∅, {a, b}} : Finset (Finset α))).Adj
      ⟨∅, by simp⟩ ⟨{a, b}, 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 2

The proof, explained

In the one-inclusion graph of a family of finite sets, two vertices are adjacent if and only if their symmetric difference has cardinality 1. For the vertices ∅ and {a, b}, their symmetric difference is simply {a, b}. Since a ≠ b, this pair has cardinality 2 rather than 1, which rules out adjacency.

  1. Non-adjacency of ∅ and {a, b} reduces to showing |∅ △ {a, b}| ≠ 1.

    The sets ∅ and {a, b} are verified to be members of {∅, {a, b}} inline by `simp`. By definition of `finset_one_inclusion_graph`, two vertices are adjacent if and only if the cardinality of their symmetric difference is 1. The `show` statement unfolds this definition, so the negated adjacency goal becomes ¬ (|∅ △ {a, b}| = 1).

    lines 4–5

          ⟨∅, by simp⟩ ⟨{a, b}, by simp⟩ := by
      show ¬ (symmDiff (∅ : Finset α) {a, b}).card = 1
  2. ∅ △ {a, b} = {a, b}

    By extensionality (`ext x`), it suffices to show that an arbitrary element x is in ∅ △ {a, b} if and only if x ∈ {a, b}. Using `Finset.mem_symmDiff`, x belongs to the symmetric difference if and only if it is in exactly one of the sets. Since ∅ is empty, this condition simplifies to x ∈ {a, b}.

    lines 6–7

    uses Finset.mem_symmDiff

      have h : symmDiff (∅ : Finset α) {a, b} = {a, b} := by
        ext x; simp [Finset.mem_symmDiff]
  3. The cardinality of the symmetric difference is 2, which is not 1.

    Rewriting with the identity h replaces ∅ △ {a, b} with {a, b}. Because a ≠ b by hypothesis `hab`, `Finset.card_pair` evaluates |{a, b}| to 2. This reduces the goal to ¬ (2 = 1), which is closed by computational decision (`decide`).

    lines 8–9

    uses Finset.card_pair

      rw [h, Finset.card_pair hab]
      decide
Finset.mem_symmDiff
An element belongs to the symmetric difference of two finite sets if and only if it belongs to one of the sets and not the other.
Finset.card_pair
A pair {a, b} of distinct elements (a ≠ b) has cardinality 2.

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_not_adj_empty_pair {α : Type*} [DecidableEq α] (a b : α)    (hab : a ≠ b) :    ¬ (finset_one_inclusion_graph ({∅, {a, b}} : Finset (Finset α))).Adj      ⟨∅, by simp⟩ ⟨{a, b}, by simp⟩ := by  show ¬ (symmDiff (∅ : Finset α) {a, b}).card = 1  have h : symmDiff (∅ : Finset α) {a, b} = {a, b} := by    ext x; simp [Finset.mem_symmDiff]  rw [h, Finset.card_pair hab]  decide
See it in the graphDiscuss this resultChallenge it