finset_one_inclusion_graph_not_adj_empty_pair
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
- 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…
- finset_one_inclusion_graph_adj_empty_singletonIn the one-inclusion graph of {∅, {a}}, ∅ and {a} are adjacent.
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.
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).
⟨∅, by simp⟩ ⟨{a, b}, by simp⟩ := by show ¬ (symmDiff (∅ : Finset α) {a, b}).card = 1
∅ △ {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}.
uses
Finset.mem_symmDiffhave h : symmDiff (∅ : Finset α) {a, b} = {a, b} := by ext x; simp [Finset.mem_symmDiff]
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`).
uses
Finset.card_pairrw [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.
- The subtype representations ⟨∅, ...⟩ and ⟨{a, b}, ...⟩ require explicit membership proofs that ∅ and {a, b} belong to {∅, {a, b}}; on line 4, these obligations are discharged inline by `simp`.
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_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