and syntax, semantics, free variables and size statistics
DefinitionCoRSuccGap_Supplement_FiniteVariableLogicFor a binary vocabulary and a fixed finite set of variable names, formulas are generated by relation atoms , equality atoms , negation, binary conjunction and disjunction, and existential and universal quantification. Quantifiers store a variable name, so names can be reused and rebound without restricting quantifier number or depth.
The definition supplies Tarskian assignment semantics, the free-variable set, syntax-tree node count, quantifier-occurrence count, and the binary assignment relations of and formulas with output coordinates . It also defines
and a constructive -to-CoR compiler interface carrying the output circuit, correctness on every nonempty structure, and a construction-cost witness.
Formalization Note The names are Fin 2 or Fin 3; 0,1,2 represent . The third assignment coordinate in a binary query is dummy when it is not free. Formula size counts every atom, connective and quantifier node; quantifier count is occurrence count, not depth.
import Mathlib
import Definitions.Def_CoRSuccGap_Circuit
set_option autoImplicit false
namespace CoRSuccGap
namespace Supplement
/-!
# Finite-variable first-order formulas and constructive CoR compilation
Uezato--Nakamura, *An Exponential Succinctness Gap between Three-Variable Logic and the
Calculus of Relations*, arXiv:2609.26778 (held version, sha256 5ad6337d…c9b6), Section 2.1,
pp.13--14 (PDF 15--16), and Theorem 5.1, p.28 (PDF 30).
The syntax has relation and equality atoms, unrestricted Boolean connectives, and existential and
universal quantifiers. A binder stores a variable name, so names may be reused and rebound. The
statistics count syntax-tree nodes and quantifier occurrences, not depth. `FO3Compiler` packages
the constructive upper-bound claim: an output circuit, semantic correctness on every nonempty
structure, and the number of construction steps.
-/
/-- First-order formulas over binary relation symbols `σ`, using names from `V`. -/
inductive FOFormula (σ : Type*) (V : Type*) where
| rel (R : σ) (u v : V)
| eq (u v : V)
| neg (p : FOFormula σ V)
| and (p q : FOFormula σ V)
| or (p q : FOFormula σ V)
| ex (u : V) (p : FOFormula σ V)
| all (u : V) (p : FOFormula σ V)
namespace FOFormula
variable {σ V : Type*}
/-- Tarskian semantics under an assignment of the available variable names. -/
def eval [DecidableEq V] {D : Type*} (M : σ → D → D → Prop) (s : V → D) :
FOFormula σ V → Prop
| rel R u v => M R (s u) (s v)
| eq u v => s u = s v
| neg p => ¬ p.eval M s
| and p q => p.eval M s ∧ q.eval M s
| or p q => p.eval M s ∨ q.eval M s
| ex u p => ∃ d, p.eval M (Function.update s u d)
| all u p => ∀ d, p.eval M (Function.update s u d)
/-- The set of free variable names. -/
def freeVars [DecidableEq V] : FOFormula σ V → Finset V
| rel _ u v => {u, v}
| eq u v => {u, v}
| neg p => p.freeVars
| and p q => p.freeVars ∪ q.freeVars
| or p q => p.freeVars ∪ q.freeVars
| ex u p => p.freeVars.erase u
| all u p => p.freeVars.erase u
/-- Syntax-tree node count; every atom, connective, and quantifier contributes one. -/
def numNodes : FOFormula σ V → ℕ
| rel _ _ _ => 1
| eq _ _ => 1
| neg p => p.numNodes + 1
| and p q => p.numNodes + q.numNodes + 1
| or p q => p.numNodes + q.numNodes + 1
| ex _ p => p.numNodes + 1
| all _ p => p.numNodes + 1
/-- Number of existential and universal quantifier occurrences. -/
def numQuantifiers : FOFormula σ V → ℕ
| rel _ _ _ => 0
| eq _ _ => 0
| neg p => p.numQuantifiers
| and p q => p.numQuantifiers + q.numQuantifiers
| or p q => p.numQuantifiers + q.numQuantifiers
| ex _ p => p.numQuantifiers + 1
| all _ p => p.numQuantifiers + 1
/-- The binary assignment relation of an FO² formula, with names `0=x`, `1=y`. -/
def query2 (p : FOFormula σ (Fin 2)) {D : Type*} (M : σ → D → D → Prop) :
D → D → Prop :=
fun x y => p.eval M (fun i => Fin.cases x (fun _ => y) i)
/-- The binary assignment relation of an FO³ formula whose only possible free names are
`0=x`, `1=y`; the third assignment coordinate is a dummy. -/
noncomputable def query3 (p : FOFormula σ (Fin 3)) {D : Type*} [Nonempty D]
(M : σ → D → D → Prop) : D → D → Prop :=
fun x y => p.eval M (fun i =>
if i = (0 : Fin 3) then x else if i = (1 : Fin 3) then y else Classical.choice inferInstance)
end FOFormula
/-- The paper's logarithm convention `log m = max(log₂ m, 1)`. -/
noncomputable def paperLog (m : ℕ) : ℝ := max (Real.logb 2 m) 1
/-- A constructive translation of all FO³ formulas over a fixed vocabulary into relational
circuits. Correctness is required for formulas with at most the two output variables free. -/
structure FO3Compiler (σ : Type*) where
circuit : FOFormula σ (Fin 3) → Circuit σ
constructionTime : FOFormula σ (Fin 3) → ℕ
correct : ∀ (p : FOFormula σ (Fin 3)),
p.freeVars ⊆ ({0, 1} : Finset (Fin 3)) →
∀ (D : Type) [Nonempty D] (M : σ → D → D → Prop),
(circuit p).eval M = p.query3 M
end Supplement
end CoRSuccGap