AFTD Auto-Formalizing Theoretical Domains

or_power

def

The n-th OR-power (co-normal power) of a simple graph G has vertex set Fin n → V, with an edge between x and y if and only if there exists some coordinate i such that x(i) is adjacent to y(i) in G.

Statement

def or_power {V : Type*} (G : SimpleGraph V) (n : ℕ) : SimpleGraph (Fin n → V)
Defined in
arXiv:2610.41977, Eq. (1.1)
Verified
02 Nov 2026
Axioms
none listed

Read back from the Lean

Given a type V, a simple graph G on V, and a natural number n, or_power G n defines a simple graph on the vertex type Fin n → V (tuples of length n with entries in V) in which two vertices x and y are adjacent if and only if there exists some index i : Fin n such that x i and y i are adjacent in 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 n-th OR-power (co-normal power) of a simple graph G: two words of length n are adjacent if and only if they are adjacent in at least one coordinate. -/
def or_power {V : Type*} (G : SimpleGraph V) (n : ℕ) : SimpleGraph (Fin n → V) := {
  Adj := fun x y => ∃ i : Fin n, G.Adj (x i) (y i)
  symm := ⟨fun _ _ ⟨i, hi⟩ => ⟨i, hi.symm⟩⟩
  loopless := ⟨fun _ ⟨_i, hi⟩ => G.loopless.irrefl _ hi⟩
}
See it in the graphDiscuss this resultChallenge it