Finite satisfiability of first-order sentences

Lax624099.FiniteSatisfiability · concepts/Lax624099/FiniteSatisfiability.lean · lax-624099

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    7 concepts; 19 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.ModelTheory.Semantics
    2import Mathlib.ModelTheory.Complexity
    3import Mathlib.Tactic.FinCases
    4import Lax904597.Classes
    5import Lax624099.Problems
    6
    7/-!
    8---
    9title: Finite satisfiability of first-order sentences
    10type: definition
    11---
    12An instance of finite satisfiability is a first-order sentence in negation
    13normal form, presented as a finite structure: its elements are the nodes of
    14the sentence's parse DAG, its variables, its relation symbols and their
    15argument positions, with relations marking the conjunction, disjunction and
    16quantifier nodes, the child relation, the variable a quantifier binds, the
    17equality and atomic literals with their arguments and the signature of each
    18symbol, the root, and a linear order on the syntax along which children
    19precede their parents. A model of such an instance is a finite nonempty type
    20with a local interpretation of the symbols, local meaning that the value of
    21a symbol depends only on the positions of its signature; the truth of a node
    22under an environment is the least fixed point of the Tarski clauses, one per
    23node kind. The instance is satisfiable when it is well-formed and the
    24universal closure of its root has a finite model, the problem of Trakhtenbrot
    25(1950); see Libkin (2004), chapter 9. FINSAT is the decision
    26problem of the structures isomorphic to a satisfiable instance.
    27-/
    28
    29namespace Lax624099.FiniteSatisfiability
    30
    31open FirstOrder
    32
    33open FirstOrder.Language
    34
    35/-- Relation symbols of the language of encoded first-order sentences in
    36negation normal form. -/
    37inductive 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
    72negation normal form, ordered by the order of its own syntax. -/
    73def finsat : Language :=
    74 ⟨fun _ => Empty, finsatRel⟩
    75
    76instance instIsRelationalFinsat : IsRelational finsat :=
    77 fun _ => ⟨fun f => Empty.elim f⟩
    78
    79/-- The order symbol of the syntax. -/
    80abbrev finsatLeSym : finsat.Relations 2 := .le
    81
    82/-- The symbol marking conjunction nodes. -/
    83abbrev finsatAndSym : finsat.Relations 1 := .andN
    84
    85/-- The symbol marking disjunction nodes. -/
    86abbrev finsatOrSym : finsat.Relations 1 := .orN
    87
    88/-- The symbol marking universal quantifier nodes. -/
    89abbrev finsatAllSym : finsat.Relations 1 := .allN
    90
    91/-- The symbol marking existential quantifier nodes. -/
    92abbrev finsatExSym : finsat.Relations 1 := .exN
    93
    94/-- The symbol of the child relation of the parse DAG. -/
    95abbrev finsatChildSym : finsat.Relations 2 := .child
    96
    97/-- The symbol binding a variable to a quantifier node. -/
    98abbrev finsatBindSym : finsat.Relations 2 := .bind
    99
    100/-- The symbol of positive equality literals. -/
    101abbrev finsatEqSym : finsat.Relations 3 := .eqL
    102
    103/-- The symbol of negated equality literals. -/
    104abbrev finsatNeqSym : finsat.Relations 3 := .neqL
    105
    106/-- The symbol of positive atoms. -/
    107abbrev finsatPosSym : finsat.Relations 2 := .posL
    108
    109/-- The symbol of negated atoms. -/
    110abbrev finsatNegSym : finsat.Relations 2 := .negL
    111
    112/-- The symbol giving the arguments of an atom. -/
    113abbrev finsatArgSym : finsat.Relations 3 := .arg
    114
    115/-- The symbol giving the signature of a relation symbol. -/
    116abbrev finsatSigSym : finsat.Relations 2 := .sig
    117
    118/-- The symbol marking the root node. -/
    119abbrev finsatRootSym : finsat.Relations 1 := .root
    120
    121open FirstOrder
    122
    123open Language Structure
    124
    125namespace FinSat
    126
    127section Reading
    128
    129variable {A : Type} [finsat.Structure A]
    130
    131/-- `x` precedes `y` in the order of the syntax. -/
    132def Ord (x y : A) : Prop := RelMap finsatLeSym ![x, y]
    133
    134/-- `x` strictly precedes `y` in the order of the syntax. -/
    135def OrdLt (x y : A) : Prop := Ord x y ∧ x ≠ y
    136
    137/-- The node `g` is a conjunction. -/
    138def AndG (g : A) : Prop := RelMap finsatAndSym ![g]
    139
    140/-- The node `g` is a disjunction. -/
    141def OrG (g : A) : Prop := RelMap finsatOrSym ![g]
    142
    143/-- The node `g` is a universal quantifier. -/
    144def AllG (g : A) : Prop := RelMap finsatAllSym ![g]
    145
    146/-- The node `g` is an existential quantifier. -/
    147def ExG (g : A) : Prop := RelMap finsatExSym ![g]
    148
    149/-- The node `c` is a child of the node `g`. -/
    150def ChildG (g c : A) : Prop := RelMap finsatChildSym ![g, c]
    151
    152/-- The quantifier node `g` binds the variable `x`. -/
    153def BindG (g x : A) : Prop := RelMap finsatBindSym ![g, x]
    154
    155/-- The node `g` is the literal `x = y`. -/
    156def EqG (g x y : A) : Prop := RelMap finsatEqSym ![g, x, y]
    157
    158/-- The node `g` is the literal `x ≠ y`. -/
    159def NeqG (g x y : A) : Prop := RelMap finsatNeqSym ![g, x, y]
    160
    161/-- The node `g` is a positive atom of the symbol `s`. -/
    162def PosG (g s : A) : Prop := RelMap finsatPosSym ![g, s]
    163
    164/-- The node `g` is a negated atom of the symbol `s`. -/
    165def NegG (g s : A) : Prop := RelMap finsatNegSym ![g, s]
    166
    167/-- The argument of the atom `g` at position `p` is the variable `x`. -/
    168def ArgG (g p x : A) : Prop := RelMap finsatArgSym ![g, p, x]
    169
    170/-- The symbol `s` has an argument position `p`. -/
    171def SigG (s p : A) : Prop := RelMap finsatSigSym ![s, p]
    172
    173/-- The node `g` is the root of the encoded sentence. -/
    174def RootG (g : A) : Prop := RelMap finsatRootSym ![g]
    175
    176end Reading
    177
    178/-- **Well-formedness of an encoded sentence**: the order symbol is a linear
    179order and the parse DAG descends along it. -/
    180structure 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
    200open Classical in
    201/-- Updating an environment at one variable. (Classical: the instance is a
    202bare type, with no decidable equality.) -/
    203noncomputable 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
    206section Semantics
    207
    208variable {A M : Type} [finsat.Structure A]
    209
    210/-- **One unfolding of the truth definition**: the value of the node `g` under
    211the environment `v`, given the values `rec` of the nodes below it. A
    212conjunction node holds when all its children do, a disjunction node when one
    213of them does, a quantifier node when all (respectively one) of the values of
    214its bound variable make all (one of) its children hold; a literal reads the
    215environment, an atom the interpretation `I`, on an assignment `w` of the
    216argument positions matching the environment on the arguments of the atom. -/
    217noncomputable 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
    229the truth of the node `g` under the environment `v`. -/
    230noncomputable 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
    235the truth definition, reached because a finite parse DAG has finite depth. -/
    236def 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
    240the arguments its signature declares. -/
    241def 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
    244end Semantics
    245
    246/-- **The encoded sentence has a finite model**: the instance is well-formed
    247and there is a finite nonempty universe with a local interpretation of the
    248relation symbols under which every environment satisfies the root – that is, a
    249finite model of the universal closure of the encoded formula. -/
    250def 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
    254end FinSat
    255
    256open Lax904597.Problems Lax624099.Problems
    257
    258/-- FINSAT: does the encoded first-order sentence have a finite model? -/
    259def FINSAT : DecisionProblem finsat :=
    260 DecisionProblem.ofPred FinSat.FinSatOn
    261
    262end Lax624099.FiniteSatisfiability
    263

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…