AFTD Auto-Formalizing Theoretical Domains

binary_function_graph_adj_const

lemmaverified

In the binary function graph of any simple graph on a nonempty vertex set, the constant false and constant true functions are adjacent.

Statement

lemma binary_function_graph_adj_const {V : Type*} [Nonempty V] (G : SimpleGraph V) : (binary_function_graph G).Adj (fun _ => false) (fun _ => true)
Source
arXiv:2610.37920 Section 2
Verified
01 Nov 2026
Axioms
Quot.soundpropext
Built on 1
  • binary_function_graphThe binary function graph of a simple graph G is the graph with vertices V → Bool, where two distinct functions f and g are adjacent if…

Read back from the Lean

For every nonempty type $V$ and every simple graph $G$ on $V$, the constant false function fun _ => false and the constant true function fun _ => true (both of type $V \to \mathrm{Bool}$) are adjacent in binary_function_graph G.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The constant false and constant true functions are adjacent in the binary function graph. -/
lemma binary_function_graph_adj_const {V : Type*} [Nonempty V] (G : SimpleGraph V) : (binary_function_graph G).Adj (fun _ => false) (fun _ => true) := by
  constructor
  · intro h
    obtain ⟨v⟩ := ‹Nonempty V›
    exact Bool.false_ne_true (congr_fun h v)
  · intro b
    have : {v : V | (fun _ => false) v = b ∧ (fun _ => true) v = b} = ∅ := by
      ext v; simp
    rw [this]
    exact Set.pairwise_empty _
See it in the graphDiscuss this resultChallenge it