Proof of `The edges of a definable flip are quantifier-free definable`

groundedproofs/Lax185574Proofs/DefinableFlipFormula.lean · lax-185574

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 20 of this submission's paper

Description

Two distinct vertices are adjacent in G⊕(pˉ,R)G ⊕ (p̄, R) exactly when either they are adjacent and the pair of their atomic types over pˉp̄ is not in RR, or they are non-adjacent and the pair is in RR. Membership of the pair of atomic types in RR is a finite disjunction, over the pairs in RR, of conjunctions of the atomic formulas x=pix = pᵢ, x≠pi∧E(x,pi)x ≠ pᵢ ∧ E(x, pᵢ) and x≠pi∧¬E(x,pi)x ≠ pᵢ ∧ ¬E(x, pᵢ).