finset_one_inclusion_graph_adj_empty_singleton
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
- finset_one_inclusion_graph_not_adj_empty_pairIn the one-inclusion graph of {∅, {a, b}} with a ≠ b, ∅ and {a, b} are not adjacent.
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.
∅ 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.
⟨∅, by simp⟩ ⟨{a}, by simp⟩ := by
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.
show (symmDiff (∅ : Finset α) {a}).card = 1∅ △ {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}.
uses
Finset.mem_symmDiffhave h : symmDiff (∅ : Finset α) {a} = {a} := by ext x; simp [Finset.mem_symmDiff]
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.
uses
Finset.card_singletonrw [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
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.
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]