The definition of a first-order language

Peter Susanszky

The definition of a first-order language

Let’s put together everything into some neater definitions.

Definition 6.5 (Formulas of $\mathcal{L}_1$ ). Let:

$\mathsf{CON}_{\mathcal{L}_1}=\{\neg, \wedge, \vee, \rightarrow\}$ , the connectives of $\mathcal{L}_1$ ;
$\mathsf{QUAN}_{\mathcal{L}_1}=\{\exists, \forall\}$ , the quantifiers of $\mathcal{L}_1$ ;
$\mathsf{CONS}_{\mathcal{L}_1}=\{\mathfrak{c}_{n} \mid n \in \mathbb{N}\}$ , the constants of $\mathcal{L}_1$ ;
$\mathsf{VAR}_{\mathcal{L}_1}=\{\mathbf{x}_{n} \mid n \in \mathbb{N}\}$ , the variables of $\mathcal{L}_1$ ;
$\mathsf{PRED}_{\mathcal{L}_1}=\{\mathfrak{P}^{n}_{k} \mid n, k \in \mathbb{N}\}$ , the predicates of $\mathcal{L}_1$ , and;
$\mathsf{S}_{\mathcal{L}_1}=\{\mathsf{,} , (, )\}$ .

Let $\mathsf{ALPH}_{\mathcal{L}_1}$ , the alphabet of $\mathcal{L}_1$ , be the smallest set such that $\mathsf{S}_{\mathcal{L}_1}$ , $\mathsf{QUAN}_{\mathcal{L}_1}$ , $\mathsf{CON}_{\mathcal{L}_1}$ , $\mathsf{CONS}_{\mathcal{L}_1}$ , $\mathsf{VAR}_{\mathcal{L}_1}$ , $\mathsf{PRED}_{\mathcal{L}_1} \subseteq \mathsf{ALPH}_{\mathcal{L}_1}$ . Let $\textsf{TERM}_{\mathcal{L}_1}=\{t \mid t \in \mathsf{CONS}_{\mathcal{L}_1}\text{ or } t\in\mathsf{VAR}_{\mathcal{L}_1}\}$ , the terms of $\mathcal{L}_1$ .

Let $\mathsf{ATOM}_{\mathcal{L}_1}$ , the atomic formulas of $\mathcal{L}_1$ , be the smallest set such that if $P$ is a predicate of arity $n$ in $\mathsf{PRED}_{\mathcal{L}_1}$ , and $t_1, …, t_n$ are (not necessarily distinct) terms in $\mathsf{TERM}_{\mathcal{L}_1}$ , then $P(t_1, …, t_n) \in \mathsf{ATOM}_{\mathcal{L}_1}$ .

The set of (well-formed) formulas of $\mathcal{L}_1$ is the smallest set $\mathsf{FORM}_{\mathcal{L}_1}$ such that:

$\mathsf{ATOM}_{\mathcal{L}_1} \subseteq \mathsf{FORM}_{\mathcal{L}_1}$ ;
if $X$ and $Y$ are in $\mathsf{FORM}_{\mathcal{L}_1}$ , and $x \in \mathsf{VAR}_{\mathcal{L}_1}$ , then:
1. $\neg X \in \mathsf{FORM}_{\mathcal{L}_1}$ ;
2. $(X \wedge Y) \in \mathsf{FORM}_{\mathcal{L}_1}$ ;
3. $(X \vee Y) \in \mathsf{FORM}_{\mathcal{L}_1}$ ;
4. $(X \rightarrow Y) \in \mathsf{FORM}_{\mathcal{L}_1}$ ;
5. $\exists x Y \in \mathsf{FORM}_{\mathcal{L}_1}$ , and;
6. $\forall x Y \in \mathsf{FORM}_{\mathcal{L}_1}$ .

Definition 6.6 (Sentences of $\mathcal{L}_1$ ). Let $\mathcal{F}: \mathsf{FORM}_{\mathcal{L}_1} \to \mathsf{VAR}_{\mathcal{L}_1}$ be the function defined for each $X \in \mathsf{FORM}_{\mathcal{L}_1}$ such that:

if $X$ is of form $P(t_1, …, t_n)$ , then $\mathcal{F}(X)=\{x \mid x \in \mathsf{VAR}_{\mathcal{L}_1}\text{ and } x=t_k, 1 \leq k \leq n\}$ ;
if $X$ is of form $\neg Y$ , then $\mathcal{F}(X)=\{x \mid x \in \mathcal{F}(Y)\}$ ;
if $X$ is of form $(Y \wedge Z)$ , $(Y \vee Z)$ , $(Y \rightarrow Z)$ , then $\mathcal{F}(X)=\{x \mid x \in \mathcal{F}(Y) \text{ or } x \in \mathcal{F}(Z)\}$ ;
if $y \in \mathsf{VAR}_{\mathcal{L}_1}$ and $X$ is of form $\forall y Z$ , $\mathcal{F}(X)=\{x \mid x\in \mathcal{F}(Z) \text{ and } x\neq y\}$ .

Let $\mathsf{SEN}_{\mathcal{L}_1}=\{X \mid \mathcal{F}(X)=\emptyset\}$ , the set of closed formulas or sentences of $\mathcal{L}_1$ . If $\mathcal{F}(X)\neq \emptyset$ , we say $X$ is an open formula, and $\mathcal{F}(X)$ is the set of variables which have at least one free occurrence in $X$ .

Exercise 6.3. Read the above two definitions carefully, and try to understand every part. Then, explain in your own terms what the main aim of $\mathcal{F}$ is, and how it achieves it with this specific definition.

Definition 6.7. Provide a proof for the following claim:

Every atomic formula with at least one occurrence of a variable is open.

Yet another convention

Finally, here is yet another convention we shall make use of. Sometimes, we want to state exactly which variables of a complex formula $Y$ have at least one free occurrence in $Y$ . In such cases, we may write $Y(x_1, …, x_n)$ , with the list of free variables of $Y$ occurring between the parentheses. This is useful, for example, if we write $Y(x)$ , meaning that $Y$ only has $x$ occurring free somewhere, and then writing $\forall x Y(x)$ , which immediately shows that the latter formula is now closed.

Now $Y(x)$ looks suspiciously like an open atomic formula of $\mathcal{L}_1$ , and there are some clear parallels between the two, but it is still important to note that $X$ , $Y$ , …, here are not predicates but entire complex formulas. For example, $Y(x)$ may just be something like the open formula $\forall y(P(y, x) \vee Q(y))$ , and thus, $\forall x Y(x)$ would be the formula $\forall x\forall y(P(y, x) \vee Q(y))$ . As expected, this latter formula is closed.

Exercise 6.4. Determine for each of the following formulas whether they are open or closed. In each case, explain your reasoning.

$\forall x_1, \forall x_2 … \forall x_{10} X(x_1, x_2, …, x_{10})$
$\forall x \exists y X(y)$
$\exists y X(z)$
$\exists x \exists y \exists z X(x, y, z)$

In connection, and this will be crucial when we introduce our first-order tableau system, we will also work with substitutions. Most importantly, sometimes we may want to consider formulas where the variables have been substituted for names. In fact, this is one way to turn an open formula into a closed one.

For example, take the closed formula $\forall x (P(x) \wedge Q(x))$ . In the notation above, this may be represented as $\forall x Y(x)$ , while the open formula $P(x) \wedge Q(x)$ may be represented as $Y(x)$ . Now substituting the name $a$ for the variable $x$ in $Y$ , we get $P(a) \wedge Q(a)$ . You simply take each unbound occurrence of $x$ , and replace it with the name $a$ . We use the notation $Y(a/x)$ to denote substituting $a$ for $x$ . In full generality, we can say that for any formula $Y(x)$ , we denote by $Y(a/x)$ the result of substituting $a$ for each unbound occurrence of the variable $x$ in $Y$ .

Exercise 6.5. For each of the following, write the down the formula that is more concisely represented by our conventions.

$(P(x) \vee Q(y))(a/x)$
$Y(b/z)$ where $Y=\exists y (R(y, z) \wedge R(b, z))$
$(Q(x) \wedge \forall x R(x, a))(a/x)$
$((R(x, y) \vee R(y, x)) \rightarrow P(x))(a/x)(b/y)$

License

Icon for the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Yet another convention

License

Share This Book