Atoms in second-order relation variables

Lax485149.SecondOrderAtoms · concepts/Lax485149/SecondOrderAtoms.lean · lax-485149

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

    Given a block of second-order relation variables R1,…,RmR_1, \dots, R_m and kk first-order variables x1,…,xkx_1, \dots, x_k, an atom is an expression Ri(xj1,…,xjr)R_i(x_{j_1}, \dots, x_{j_r}), with rr the arity of RiR_i. It holds under an assignment of relations to the block and a valuation vv of the variables when the tuple (v(xj1),…,v(xjr))(v(x_{j_1}), \dots, v(x_{j_r})) belongs to the relation assigned to RiR_i. The clausal fragments of existential second-order logic, Krom and Horn, are built from these atoms.

    Concept map
    3 concepts; 23 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax904597.SecondOrder
    2
    3/-!
    4---
    5title: Atoms in second-order relation variables
    6type: definition
    7---
    8Given a block of second-order relation variables R1,…,RmR_1, \dots, R_m and kk
    9first-order variables x1,…,xkx_1, \dots, x_k, an atom is an expression
    10Ri(xj1,…,xjr)R_i(x_{j_1}, \dots, x_{j_r}), with rr the arity of RiR_i. It holds under an
    11assignment of relations to the block and a valuation vv of the variables when
    12the tuple (v(xj1),…,v(xjr))(v(x_{j_1}), \dots, v(x_{j_r})) belongs to the relation assigned
    13to RiR_i. The clausal fragments of existential second-order logic, Krom and
    14Horn, are built from these atoms.
    15-/
    16
    17namespace Lax485149.SecondOrderAtoms
    18
    19open Lax904597.SecondOrder
    20
    21open FirstOrder
    22
    23open Language Structure
    24
    25/-- An atom `R i (x_{f 0}, …)` in the relation variables of a block, with
    26arguments read from `k` universally quantified first-order variables. -/
    27structure 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
    34variable {B : SOBlock} {k : ℕ}
    35
    36/-- The truth value of a second-order atom under an assignment of the block
    37and a valuation of the universally quantified variables. -/
    38def 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
    41end Lax485149.SecondOrderAtoms
    42

    Discussion

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

    Loading discussion…