Finite satisfiability of first-order sentences
Lax624099.FiniteSatisfiability · concepts/Lax624099/FiniteSatisfiability.lean · lax-624099
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An instance of finite satisfiability is a first-order sentence in negation normal form, presented as a finite structure: its elements are the nodes of the sentence's parse DAG, its variables, its relation symbols and their argument positions, with relations marking the conjunction, disjunction and quantifier nodes, the child relation, the variable a quantifier binds, the equality and atomic literals with their arguments and the signature of each symbol, the root, and a linear order on the syntax along which children precede their parents. A model of such an instance is a finite nonempty type with a local interpretation of the symbols, local meaning that the value of a symbol depends only on the positions of its signature; the truth of a node under an environment is the least fixed point of the Tarski clauses, one per node kind. The instance is satisfiable when it is well-formed and the universal closure of its root has a finite model, the problem of Trakhtenbrot (1950); see Libkin (2004), chapter 9. FINSAT is the decision problem of the structures isomorphic to a satisfiable instance.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | import Mathlib.ModelTheory.Complexity |
| 3 | import Mathlib.Tactic.FinCases |
| 4 | import Lax904597.Classes |
| 5 | import Lax624099.Problems |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Finite satisfiability of first-order sentences |
| 10 | type: definition |
| 11 | --- |
| 12 | An instance of finite satisfiability is a first-order sentence in negation |
| 13 | normal form, presented as a finite structure: its elements are the nodes of |
| 14 | the sentence's parse DAG, its variables, its relation symbols and their |
| 15 | argument positions, with relations marking the conjunction, disjunction and |
| 16 | quantifier nodes, the child relation, the variable a quantifier binds, the |
| 17 | equality and atomic literals with their arguments and the signature of each |
| 18 | symbol, the root, and a linear order on the syntax along which children |
| 19 | precede their parents. A model of such an instance is a finite nonempty type |
| 20 | with a local interpretation of the symbols, local meaning that the value of |
| 21 | a symbol depends only on the positions of its signature; the truth of a node |
| 22 | under an environment is the least fixed point of the Tarski clauses, one per |
| 23 | node kind. The instance is satisfiable when it is well-formed and the |
| 24 | universal closure of its root has a finite model, the problem of Trakhtenbrot |
| 25 | (1950); see Libkin (2004), chapter 9. FINSAT is the decision |
| 26 | problem of the structures isomorphic to a satisfiable instance. |
| 27 | -/ |
| 28 | |
| 29 | namespace Lax624099.FiniteSatisfiability |
| 30 | |
| 31 | open FirstOrder |
| 32 | |
| 33 | open FirstOrder.Language |
| 34 | |
| 35 | /-- Relation symbols of the language of encoded first-order sentences in |
| 36 | negation normal form. -/ |
| 37 | inductive finsatRel : ℕ → Type |
| 38 | /-- `le x y`: the order of the syntax. -/ |
| 39 | | le : finsatRel 2 |
| 40 | /-- `andN g`: the node `g` is the conjunction of its children. -/ |
| 41 | | andN : finsatRel 1 |
| 42 | /-- `orN g`: the node `g` is the disjunction of its children. -/ |
| 43 | | orN : finsatRel 1 |
| 44 | /-- `allN g`: the node `g` universally quantifies its bound variable. -/ |
| 45 | | allN : finsatRel 1 |
| 46 | /-- `exN g`: the node `g` existentially quantifies its bound variable. -/ |
| 47 | | exN : finsatRel 1 |
| 48 | /-- `child g c`: the node `c` is one of the children of the node `g`. -/ |
| 49 | | child : finsatRel 2 |
| 50 | /-- `bind g x`: the quantifier node `g` binds the variable `x`. -/ |
| 51 | | bind : finsatRel 2 |
| 52 | /-- `eqL g x y`: the node `g` is the literal `x = y`. -/ |
| 53 | | eqL : finsatRel 3 |
| 54 | /-- `neqL g x y`: the node `g` is the literal `x ≠ y`. -/ |
| 55 | | neqL : finsatRel 3 |
| 56 | /-- `posL g s`: the node `g` is a positive atom of the relation symbol |
| 57 | `s`. -/ |
| 58 | | posL : finsatRel 2 |
| 59 | /-- `negL g s`: the node `g` is a negated atom of the relation symbol |
| 60 | `s`. -/ |
| 61 | | negL : finsatRel 2 |
| 62 | /-- `arg g p x`: the argument of the atom `g` at position `p` is the |
| 63 | variable `x`. -/ |
| 64 | | arg : finsatRel 3 |
| 65 | /-- `sig s p`: the relation symbol `s` has an argument position `p`. -/ |
| 66 | | sig : finsatRel 2 |
| 67 | /-- `root g`: the node `g` is the root of the encoded sentence. -/ |
| 68 | | root : finsatRel 1 |
| 69 | deriving DecidableEq |
| 70 | |
| 71 | /-- The relational vocabulary of encoded first-order sentences: a parse DAG in |
| 72 | negation normal form, ordered by the order of its own syntax. -/ |
| 73 | def finsat : Language := |
| 74 | ⟨fun _ => Empty, finsatRel⟩ |
| 75 | |
| 76 | instance instIsRelationalFinsat : IsRelational finsat := |
| 77 | fun _ => ⟨fun f => Empty.elim f⟩ |
| 78 | |
| 79 | /-- The order symbol of the syntax. -/ |
| 80 | abbrev finsatLeSym : finsat.Relations 2 := .le |
| 81 | |
| 82 | /-- The symbol marking conjunction nodes. -/ |
| 83 | abbrev finsatAndSym : finsat.Relations 1 := .andN |
| 84 | |
| 85 | /-- The symbol marking disjunction nodes. -/ |
| 86 | abbrev finsatOrSym : finsat.Relations 1 := .orN |
| 87 | |
| 88 | /-- The symbol marking universal quantifier nodes. -/ |
| 89 | abbrev finsatAllSym : finsat.Relations 1 := .allN |
| 90 | |
| 91 | /-- The symbol marking existential quantifier nodes. -/ |
| 92 | abbrev finsatExSym : finsat.Relations 1 := .exN |
| 93 | |
| 94 | /-- The symbol of the child relation of the parse DAG. -/ |
| 95 | abbrev finsatChildSym : finsat.Relations 2 := .child |
| 96 | |
| 97 | /-- The symbol binding a variable to a quantifier node. -/ |
| 98 | abbrev finsatBindSym : finsat.Relations 2 := .bind |
| 99 | |
| 100 | /-- The symbol of positive equality literals. -/ |
| 101 | abbrev finsatEqSym : finsat.Relations 3 := .eqL |
| 102 | |
| 103 | /-- The symbol of negated equality literals. -/ |
| 104 | abbrev finsatNeqSym : finsat.Relations 3 := .neqL |
| 105 | |
| 106 | /-- The symbol of positive atoms. -/ |
| 107 | abbrev finsatPosSym : finsat.Relations 2 := .posL |
| 108 | |
| 109 | /-- The symbol of negated atoms. -/ |
| 110 | abbrev finsatNegSym : finsat.Relations 2 := .negL |
| 111 | |
| 112 | /-- The symbol giving the arguments of an atom. -/ |
| 113 | abbrev finsatArgSym : finsat.Relations 3 := .arg |
| 114 | |
| 115 | /-- The symbol giving the signature of a relation symbol. -/ |
| 116 | abbrev finsatSigSym : finsat.Relations 2 := .sig |
| 117 | |
| 118 | /-- The symbol marking the root node. -/ |
| 119 | abbrev finsatRootSym : finsat.Relations 1 := .root |
| 120 | |
| 121 | open FirstOrder |
| 122 | |
| 123 | open Language Structure |
| 124 | |
| 125 | namespace FinSat |
| 126 | |
| 127 | section Reading |
| 128 | |
| 129 | variable {A : Type} [finsat.Structure A] |
| 130 | |
| 131 | /-- `x` precedes `y` in the order of the syntax. -/ |
| 132 | def Ord (x y : A) : Prop := RelMap finsatLeSym ![x, y] |
| 133 | |
| 134 | /-- `x` strictly precedes `y` in the order of the syntax. -/ |
| 135 | def OrdLt (x y : A) : Prop := Ord x y ∧ x ≠ y |
| 136 | |
| 137 | /-- The node `g` is a conjunction. -/ |
| 138 | def AndG (g : A) : Prop := RelMap finsatAndSym ![g] |
| 139 | |
| 140 | /-- The node `g` is a disjunction. -/ |
| 141 | def OrG (g : A) : Prop := RelMap finsatOrSym ![g] |
| 142 | |
| 143 | /-- The node `g` is a universal quantifier. -/ |
| 144 | def AllG (g : A) : Prop := RelMap finsatAllSym ![g] |
| 145 | |
| 146 | /-- The node `g` is an existential quantifier. -/ |
| 147 | def ExG (g : A) : Prop := RelMap finsatExSym ![g] |
| 148 | |
| 149 | /-- The node `c` is a child of the node `g`. -/ |
| 150 | def ChildG (g c : A) : Prop := RelMap finsatChildSym ![g, c] |
| 151 | |
| 152 | /-- The quantifier node `g` binds the variable `x`. -/ |
| 153 | def BindG (g x : A) : Prop := RelMap finsatBindSym ![g, x] |
| 154 | |
| 155 | /-- The node `g` is the literal `x = y`. -/ |
| 156 | def EqG (g x y : A) : Prop := RelMap finsatEqSym ![g, x, y] |
| 157 | |
| 158 | /-- The node `g` is the literal `x ≠ y`. -/ |
| 159 | def NeqG (g x y : A) : Prop := RelMap finsatNeqSym ![g, x, y] |
| 160 | |
| 161 | /-- The node `g` is a positive atom of the symbol `s`. -/ |
| 162 | def PosG (g s : A) : Prop := RelMap finsatPosSym ![g, s] |
| 163 | |
| 164 | /-- The node `g` is a negated atom of the symbol `s`. -/ |
| 165 | def NegG (g s : A) : Prop := RelMap finsatNegSym ![g, s] |
| 166 | |
| 167 | /-- The argument of the atom `g` at position `p` is the variable `x`. -/ |
| 168 | def ArgG (g p x : A) : Prop := RelMap finsatArgSym ![g, p, x] |
| 169 | |
| 170 | /-- The symbol `s` has an argument position `p`. -/ |
| 171 | def SigG (s p : A) : Prop := RelMap finsatSigSym ![s, p] |
| 172 | |
| 173 | /-- The node `g` is the root of the encoded sentence. -/ |
| 174 | def RootG (g : A) : Prop := RelMap finsatRootSym ![g] |
| 175 | |
| 176 | end Reading |
| 177 | |
| 178 | /-- **Well-formedness of an encoded sentence**: the order symbol is a linear |
| 179 | order and the parse DAG descends along it. -/ |
| 180 | structure IsWF (A : Type) [finsat.Structure A] : Prop where |
| 181 | /-- The order of the syntax is reflexive. -/ |
| 182 | ord_refl : ∀ x : A, Ord x x |
| 183 | /-- The order of the syntax is transitive. -/ |
| 184 | ord_trans : ∀ x y z : A, Ord x y → Ord y z → Ord x z |
| 185 | /-- The order of the syntax is antisymmetric. -/ |
| 186 | ord_antisymm : ∀ x y : A, Ord x y → Ord y x → x = y |
| 187 | /-- The order of the syntax is total. -/ |
| 188 | ord_total : ∀ x y : A, Ord x y ∨ Ord y x |
| 189 | /-- Children come strictly earlier: the parse DAG is acyclic. -/ |
| 190 | child_lt : ∀ g c : A, ChildG g c → OrdLt c g |
| 191 | /-- An atom has at most one argument at each position. -/ |
| 192 | arg_fun : ∀ g p x x' : A, ArgG g p x → ArgG g p x' → x = x' |
| 193 | /-- An atom has at most one relation symbol. -/ |
| 194 | atom_sym : ∀ g s s' : A, (PosG g s ∨ NegG g s) → (PosG g s' ∨ NegG g s') → s = s' |
| 195 | /-- An atom only has arguments at the positions of its symbol's signature. -/ |
| 196 | arg_sig : ∀ g s p x : A, (PosG g s ∨ NegG g s) → ArgG g p x → SigG s p |
| 197 | /-- An atom has an argument at every position of its symbol's signature. -/ |
| 198 | arg_tot : ∀ g s p : A, (PosG g s ∨ NegG g s) → SigG s p → ∃ x, ArgG g p x |
| 199 | |
| 200 | open Classical in |
| 201 | /-- Updating an environment at one variable. (Classical: the instance is a |
| 202 | bare type, with no decidable equality.) -/ |
| 203 | noncomputable def upd {A M : Type} (v : A → M) (x : A) (d : M) : A → M := |
| 204 | fun z => if z = x then d else v z |
| 205 | |
| 206 | section Semantics |
| 207 | |
| 208 | variable {A M : Type} [finsat.Structure A] |
| 209 | |
| 210 | /-- **One unfolding of the truth definition**: the value of the node `g` under |
| 211 | the environment `v`, given the values `rec` of the nodes below it. A |
| 212 | conjunction node holds when all its children do, a disjunction node when one |
| 213 | of them does, a quantifier node when all (respectively one) of the values of |
| 214 | its bound variable make all (one of) its children hold; a literal reads the |
| 215 | environment, an atom the interpretation `I`, on an assignment `w` of the |
| 216 | argument positions matching the environment on the arguments of the atom. -/ |
| 217 | noncomputable def gstep (I : A → (A → M) → Prop) (rec : (A → M) → A → Prop) |
| 218 | (v : A → M) (g : A) : Prop := |
| 219 | (AndG g ∧ ∀ c, ChildG g c → rec v c) ∨ |
| 220 | (OrG g ∧ ∃ c, ChildG g c ∧ rec v c) ∨ |
| 221 | (AllG g ∧ ∀ x, BindG g x → ∀ d : M, ∀ c, ChildG g c → rec (upd v x d) c) ∨ |
| 222 | (ExG g ∧ ∃ x, BindG g x ∧ ∃ d : M, ∃ c, ChildG g c ∧ rec (upd v x d) c) ∨ |
| 223 | (∃ x y, EqG g x y ∧ v x = v y) ∨ |
| 224 | (∃ x y, NeqG g x y ∧ v x ≠ v y) ∨ |
| 225 | (∃ s, PosG g s ∧ ∃ w : A → M, (∀ p x, ArgG g p x → w p = v x) ∧ I s w) ∨ |
| 226 | (∃ s, NegG g s ∧ ∃ w : A → M, (∀ p x, ArgG g p x → w p = v x) ∧ ¬I s w) |
| 227 | |
| 228 | /-- **Satisfaction, by iteration**: `gval I k v g` is the `k`-th approximant of |
| 229 | the truth of the node `g` under the environment `v`. -/ |
| 230 | noncomputable def gval (I : A → (A → M) → Prop) : ℕ → (A → M) → A → Prop |
| 231 | | 0 => fun _ _ => False |
| 232 | | k + 1 => gstep I (gval I k) |
| 233 | |
| 234 | /-- **The node `g` holds under the environment `v`**: the least fixed point of |
| 235 | the truth definition, reached because a finite parse DAG has finite depth. -/ |
| 236 | def Gval (I : A → (A → M) → Prop) (v : A → M) (g : A) : Prop := |
| 237 | ∃ k, gval I k v g |
| 238 | |
| 239 | /-- An interpretation is **local** when the value of a symbol depends only on |
| 240 | the arguments its signature declares. -/ |
| 241 | def Local (I : A → (A → M) → Prop) : Prop := |
| 242 | ∀ (s : A) (w w' : A → M), (∀ p, SigG s p → w p = w' p) → (I s w ↔ I s w') |
| 243 | |
| 244 | end Semantics |
| 245 | |
| 246 | /-- **The encoded sentence has a finite model**: the instance is well-formed |
| 247 | and there is a finite nonempty universe with a local interpretation of the |
| 248 | relation symbols under which every environment satisfies the root – that is, a |
| 249 | finite model of the universal closure of the encoded formula. -/ |
| 250 | def FinSatOn (A : Type) [finsat.Structure A] : Prop := |
| 251 | IsWF A ∧ ∃ (M : Type) (_ : Finite M) (_ : Nonempty M) (I : A → (A → M) → Prop), |
| 252 | Local I ∧ ∀ (v : A → M) (g : A), RootG g → Gval I v g |
| 253 | |
| 254 | end FinSat |
| 255 | |
| 256 | open Lax904597.Problems Lax624099.Problems |
| 257 | |
| 258 | /-- FINSAT: does the encoded first-order sentence have a finite model? -/ |
| 259 | def FINSAT : DecisionProblem finsat := |
| 260 | DecisionProblem.ofPred FinSat.FinSatOn |
| 261 | |
| 262 | end Lax624099.FiniteSatisfiability |
| 263 |
Builds on
Used by
Lax624099.CodeHaltingInvarianceLax624099.CodehaltRECompleteLax624099.ConcreteInstancesLax624099.FiniteSatisfiabilityInvarianceLax624099.FinsatRECompleteLax624099.HaltingInvarianceLax624099.HaltingUndecidableLax624099.HaltRECompleteLax624099.NPSubsetRELax624099.PcpRECompleteLax624099.PcpUndecidableLax624099.PostCorrespondenceInvarianceLax624099.REClosureLax624099.ReductionsComputableLax624099.REFiniteLax624099.REHardUndecidableLax624099.REIsRecursivelyEnumerableLax624099.RENeCoRELax624099.Trakhtenbrot
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments