Definition:Structure for Predicate Logic
This page is about Structure in the context of Predicate Logic. For other uses, see Structure.
Definition
Let $\LL_1$ be the language of predicate logic.
A structure $\AA$ for $\LL_1$ comprises:
- $(1): \quad$ A non-empty set $A$;
- $(2): \quad$ For each function symbol $f$ of arity $n$, a mapping $f_\AA: A^n \to A$;
- $(3): \quad$ For each predicate symbol $p$ of arity $n$, a mapping $p_\AA: A^n \to \Bbb B$
where $\Bbb B$ denotes the set of truth values.
$A$ is called the underlying set of $\AA$.
$f_\AA$ and $p_\AA$ are called the interpretations of $f$ and $p$ in $\AA$, respectively.
We remark that function symbols of arity $0$ are interpreted as constants in $A$.
To avoid pathological situations with the interpretation of arity-$0$ function symbols, it is essential that $A$ be non-empty.
Also, the predicate symbols may be interpreted as relations via their characteristic functions.
Formal Semantics
Formal Semantics for Sentences
The structures for $\LL_1$ can be interpreted as a formal semantics for $\LL_1$, which we denote by $\mathrm{PL}$.
For the purpose of this formal semantics, we consider only sentences instead of all WFFs.
The structures of $\mathrm{PL}$ are said structures for $\LL_1$.
A sentence $\mathbf A$ is declared ($\mathrm{PL}$-)valid in a structure $\AA$ if and only if:
- $\map {\operatorname{val}_\AA} {\mathbf A} = \T$
where $\map {\operatorname{val}_\AA} {\mathbf A}$ is the value of $\mathbf A$ in $\AA$.
Symbolically, this can be expressed as:
- $\AA \models_{\mathrm{PL} } \mathbf A$
Formal Semantics for WFFs
The structures for $\LL_1$ can be interpreted as a formal semantics for $\LL_1$, which we denote by $\mathrm{PL_A}$.
The structures of $\mathrm{PL_A}$ are pairs $\struct {\AA, \sigma}$, where:
- $\AA$ is a structure for $\LL_1$
- $\sigma$ is an assignment for $\AA$
A WFF $\mathbf A$ is declared ($\mathrm{PL_A}$-)valid in a structure $\AA$ if and only if:
- $\sigma$ is an assignment for $\mathbf A$
- $\map {\operatorname{val}_\AA} {\mathbf A} \sqbrk \sigma = \T$
where $\map {\operatorname{val}_\AA} {\mathbf A} \sqbrk \sigma$ is the value of $\mathbf A$ under $\sigma$.
Symbolically, this can be expressed as one of the following:
- $\AA, \sigma \models_{\mathrm{PL_A} } \mathbf A$
- $\AA \models_{\mathrm{PL_A} } \mathbf A \sqbrk \sigma$
Also known as
A structure for $\LL_1$ is also often called a structure for predicate logic or first-order structure.
The latter formulation is particularly used when the precise vocabulary used for $\LL_1$ is not important.
Also see
Sources
- 2009: Kenneth Kunen: The Foundations of Mathematics ... (previous) ... (next): $\text {II}.7$ First-Order Logic Semantics: Definition $\text {II}.7.1$