AFTD Auto-Formalizing Theoretical Domains

is_binary_linear_graph_code_bot

theoremverified

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.

  1. 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.

    lines 3–4

      constructor
      · simp
  2. 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 ⊥ ⊥ ∈ {⊥}.

    lines 5–7

    uses Set.mem_singleton_iff

      · intro G G' hG hG'
        simp only [Set.mem_singleton_iff] at hG hG'
        subst hG hG'
  3. 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.

    line 8

    uses symmDiff_self

        simp [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

/-- 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]
See it in the graphDiscuss this resultChallenge it