is_binary_linear_graph_code_bot
The singleton set containing only the empty graph on Fin n is a binary linear graph-code.
Statement
theorem is_binary_linear_graph_code_bot (n : ℕ) : is_binary_linear_graph_code n {⊥}- Source
- arXiv:2610.35136, Section 1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_binary_linear_graph_codeA family C of simple graphs on vertex set [n] is a binary linear graph-code if it contains the empty graph and is closed under symmetric…
Read back from the Lean
For every natural number $n$, the singleton set $\{\bot\}$ containing only the empty simple graph on vertex set $\mathrm{Fin}(n)$ is a binary linear graph code of order $n$.
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
To show that {⊥} is a binary linear graph-code, we verify the two defining properties: containing the empty graph ⊥ and closure under symmetric difference. The empty graph belongs to {⊥} trivially. For closure, any two graphs in {⊥} must equal ⊥, and the symmetric difference of ⊥ with itself is ⊥ by symmDiff_self.
The empty graph belongs to the code {⊥}, satisfying the first condition of a binary linear graph-code.
By definition, a binary linear graph-code must contain the empty graph ⊥ and be closed under symmetric difference. Splitting the conjunction yields two goals; the first, ⊥ ∈ {⊥}, holds immediately by simplification of singleton membership.
constructor · simp
Any elements G and G' in {⊥} must equal ⊥, reducing closure under symmetric difference to showing symmDiff ⊥ ⊥ ∈ {⊥}.
To establish closure under symmetric difference, we assume G, G' ∈ {⊥}. Applying Set.mem_singleton_iff simplifies these assumptions to G = ⊥ and G' = ⊥. Substituting ⊥ for both G and G' leaves the goal symmDiff ⊥ ⊥ ∈ {⊥}.
uses
Set.mem_singleton_iff· intro G G' hG hG' simp only [Set.mem_singleton_iff] at hG hG' subst hG hG'
The symmetric difference symmDiff ⊥ ⊥ is ⊥, which belongs to {⊥}.
By symmDiff_self, the symmetric difference of any element with itself is ⊥, so symmDiff ⊥ ⊥ simplifies to ⊥. Since ⊥ ∈ {⊥}, this closes the final goal.
uses
symmDiff_selfsimp [symmDiff_self]
Set.mem_singleton_iff- An element a is in the singleton set {b} if and only if a = b.
symmDiff_self- The symmetric difference of any element with itself is the bottom element ⊥.
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.
/-- The singleton set containing only the empty graph is a binary linear graph-code. -/theorem is_binary_linear_graph_code_bot (n : ℕ) : is_binary_linear_graph_code n {⊥} := by constructor · simp · intro G G' hG hG' simp only [Set.mem_singleton_iff] at hG hG' subst hG hG' simp [symmDiff_self]