Processing math: 100%

The definition of a first-order language

Let’s put together everything into some neater definitions.

Definition 6.5 (Formulas of 1). Let:

  1. 𝖢𝖮𝖭1={¬,,,}, the connectives of 1;

  2. 𝖰𝖴𝖠𝖭1={,}, the quantifiers of 1;

  3. 𝖢𝖮𝖭𝖲1={𝔠nn}, the constants of 1;

  4. 𝖵𝖠𝖱1={𝐱nn}, the variables of 1;

  5. 𝖯𝖱𝖤𝖣1={𝔓nkn,k}, the predicates of 1, and;

  6. 𝖲1={,,(,)}.

Let 𝖠𝖫𝖯𝖧1, the alphabet of 1, be the smallest set such that 𝖲1, 𝖰𝖴𝖠𝖭1, 𝖢𝖮𝖭1, 𝖢𝖮𝖭𝖲1, 𝖵𝖠𝖱1, 𝖯𝖱𝖤𝖣1𝖠𝖫𝖯𝖧1. Let 𝖳𝖤𝖱𝖬1={tt𝖢𝖮𝖭𝖲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𝖥𝖮𝖱𝖬1;

  2. if X and Y are in 𝖥𝖮𝖱𝖬1, and x𝖵𝖠𝖱1, then:

    1. ¬X𝖥𝖮𝖱𝖬1;

    2. (XY)𝖥𝖮𝖱𝖬1;

    3. (XY)𝖥𝖮𝖱𝖬1;

    4. (XY)𝖥𝖮𝖱𝖬1;

    5. xY𝖥𝖮𝖱𝖬1, and;

    6. xY𝖥𝖮𝖱𝖬1.

Definition 6.6 (Sentences of 1). Let :𝖥𝖮𝖱𝖬1𝖵𝖠𝖱1 be the function defined for each X𝖥𝖮𝖱𝖬1 such that:

  1. if X is of form P(t1,...,tn), then (X)={xx𝖵𝖠𝖱1andx=tk,1kn};

  2. if X is of form ¬Y, then (X)={xx(Y)};

  3. if X is of form (YZ), (YZ), (YZ), then (X)={xx(Y)orx(Z)};

  4. if y𝖵𝖠𝖱1 and X is of form yZ, (X)={xx(Z)andxy}.

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 xy(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.

  1. x1,x2...x10X(x1,x2,...,x10)

  2. xyX(y)

  3. yX(z)

  4. xyzX(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.

  1. (P(x)Q(y))(a/x)

  2. Y(b/z) where Y=y(R(y,z)R(b,z))

  3. (Q(x)xR(x,a))(a/x)

  4. ((R(x,y)R(y,x))P(x))(a/x)(b/y)

License

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

Learning Logic Backwards Copyright © by Peter Susanszky is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License, except where otherwise noted.

Share This Book