Atoms in second-order relation variables
Lax485149.SecondOrderAtoms · concepts/Lax485149/SecondOrderAtoms.lean · lax-485149
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Given a block of second-order relation variables and first-order variables , an atom is an expression , with the arity of . It holds under an assignment of relations to the block and a valuation of the variables when the tuple belongs to the relation assigned to . The clausal fragments of existential second-order logic, Krom and Horn, are built from these atoms.
Concept map
Lean source view on GitHub
| 1 | import Lax904597.SecondOrder |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Atoms in second-order relation variables |
| 6 | type: definition |
| 7 | --- |
| 8 | Given a block of second-order relation variables and |
| 9 | first-order variables , an atom is an expression |
| 10 | , with the arity of . It holds under an |
| 11 | assignment of relations to the block and a valuation of the variables when |
| 12 | the tuple belongs to the relation assigned |
| 13 | to . The clausal fragments of existential second-order logic, Krom and |
| 14 | Horn, are built from these atoms. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax485149.SecondOrderAtoms |
| 18 | |
| 19 | open Lax904597.SecondOrder |
| 20 | |
| 21 | open FirstOrder |
| 22 | |
| 23 | open Language Structure |
| 24 | |
| 25 | /-- An atom `R i (x_{f 0}, …)` in the relation variables of a block, with |
| 26 | arguments read from `k` universally quantified first-order variables. -/ |
| 27 | structure SOAtom (B : SOBlock) (k : ℕ) where |
| 28 | /-- The relation variable of the block the atom is about. -/ |
| 29 | idx : B.ι |
| 30 | /-- The arguments, as indices among the `k` universally quantified |
| 31 | variables. -/ |
| 32 | args : Fin (B.arity idx) → Fin k |
| 33 | |
| 34 | variable {B : SOBlock} {k : ℕ} |
| 35 | |
| 36 | /-- The truth value of a second-order atom under an assignment of the block |
| 37 | and a valuation of the universally quantified variables. -/ |
| 38 | def SOAtom.Holds {A : Type} (a : SOAtom B k) (ρ : B.Assignment A) (v : Fin k → A) : Prop := |
| 39 | ρ a.idx fun j => v (a.args j) |
| 40 | |
| 41 | end Lax485149.SecondOrderAtoms |
| 42 |
Builds on
Used by
Lax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.KromFragmentLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureClosureLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLComplete
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments