The definition of a first-order language
Let’s put together everything into some neater definitions.
Definition 6.5 (Formulas of ℒ1). Let:
-
𝖢𝖮𝖭ℒ1={¬,∧,∨,→}, the connectives of ℒ1;
-
𝖰𝖴𝖠𝖭ℒ1={∃,∀}, the quantifiers of ℒ1;
-
𝖢𝖮𝖭𝖲ℒ1={𝔠n∣n∈ℕ}, the constants of ℒ1;
-
𝖵𝖠𝖱ℒ1={𝐱n∣n∈ℕ}, the variables of ℒ1;
-
𝖯𝖱𝖤𝖣ℒ1={𝔓nk∣n,k∈ℕ}, the predicates of ℒ1, and;
-
𝖲ℒ1={,,(,)}.
Let 𝖠𝖫𝖯𝖧ℒ1, the alphabet of ℒ1, be the smallest set such that 𝖲ℒ1, 𝖰𝖴𝖠𝖭ℒ1, 𝖢𝖮𝖭ℒ1, 𝖢𝖮𝖭𝖲ℒ1, 𝖵𝖠𝖱ℒ1, 𝖯𝖱𝖤𝖣ℒ1⊆𝖠𝖫𝖯𝖧ℒ1. Let 𝖳𝖤𝖱𝖬ℒ1={t∣t∈𝖢𝖮𝖭𝖲ℒ1ort∈𝖵𝖠𝖱ℒ1}, the terms of ℒ1.
Let 𝖠𝖳𝖮𝖬ℒ1, the atomic formulas of ℒ1, be the smallest set such that if P is a predicate of arity n in 𝖯𝖱𝖤𝖣ℒ1, and t1,...,tn are (not necessarily distinct) terms in 𝖳𝖤𝖱𝖬ℒ1, then P(t1,...,tn)∈𝖠𝖳𝖮𝖬ℒ1.
The set of (well-formed) formulas of ℒ1 is the smallest set 𝖥𝖮𝖱𝖬ℒ1 such that:
-
𝖠𝖳𝖮𝖬ℒ1⊆𝖥𝖮𝖱𝖬ℒ1;
-
if X and Y are in 𝖥𝖮𝖱𝖬ℒ1, and x∈𝖵𝖠𝖱ℒ1, then:
-
¬X∈𝖥𝖮𝖱𝖬ℒ1;
-
(X∧Y)∈𝖥𝖮𝖱𝖬ℒ1;
-
(X∨Y)∈𝖥𝖮𝖱𝖬ℒ1;
-
(X→Y)∈𝖥𝖮𝖱𝖬ℒ1;
-
∃xY∈𝖥𝖮𝖱𝖬ℒ1, and;
-
∀xY∈𝖥𝖮𝖱𝖬ℒ1.
-
Definition 6.6 (Sentences of ℒ1). Let ℱ:𝖥𝖮𝖱𝖬ℒ1→𝖵𝖠𝖱ℒ1 be the function defined for each X∈𝖥𝖮𝖱𝖬ℒ1 such that:
-
if X is of form P(t1,...,tn), then ℱ(X)={x∣x∈𝖵𝖠𝖱ℒ1andx=tk,1≤k≤n};
-
if X is of form ¬Y, then ℱ(X)={x∣x∈ℱ(Y)};
-
if X is of form (Y∧Z), (Y∨Z), (Y→Z), then ℱ(X)={x∣x∈ℱ(Y)orx∈ℱ(Z)};
-
if y∈𝖵𝖠𝖱ℒ1 and X is of form ∀yZ, ℱ(X)={x∣x∈ℱ(Z)andx≠y}.
Let 𝖲𝖤𝖭ℒ1={X∣ℱ(X)=∅}, the set of closed formulas or sentences of ℒ1. If ℱ(X)≠∅, we say X is an open formula, and ℱ(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 ℱ 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(x1,...,xn), 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 ∀xY(x), which immediately shows that the latter formula is now closed.
Now Y(x) looks suspiciously like an open atomic formula of ℒ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 ∀y(P(y,x)∨Q(y)), and thus, ∀xY(x) would be the formula ∀x∀y(P(y,x)∨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.
-
∀x1,∀x2...∀x10X(x1,x2,...,x10)
-
∀x∃yX(y)
-
∃yX(z)
-
∃x∃y∃zX(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 ∀x(P(x)∧Q(x)). In the notation above, this may be represented as ∀xY(x), while the open formula P(x)∧Q(x) may be represented as Y(x). Now substituting the name a for the variable x in Y, we get P(a)∧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)∨Q(y))(a/x)
-
Y(b/z) where Y=∃y(R(y,z)∧R(b,z))
-
(Q(x)∧∀xR(x,a))(a/x)
-
((R(x,y)∨R(y,x))→P(x))(a/x)(b/y)