Skip to content

Terms, First-Order Formulas

First-Order Signature

A first-order signature is a 4-tuple \((Co, Fu, Re, r)\) where:

  1. \(Co\) is a set (possibly empty) of symbols called the constant symbols;
  2. \(Fu\) is a set (possibly empty) of symbols called the function symbols;
  3. \(Re\) is a set (possibly empty) of symbols called the relation symbols;
  4. \(Co\), \(Fu\), \(Re\) are pairwise disjoint;
  5. \(r\) is a function taking each symbol \(s\) in \(Fu \cup Re\) to a positive integer \(r(s)\) called the rank (or arity) of \(s\). We say a symbol is \(n\)-ary if it has arity \(n\); binary means 2-ary.

Variables

The variables of \(LR(\sigma)\) are the infinitely many symbols

\[ x_0, x_1, x_2, \ldots \]

which we assume are not in \(\sigma\).

Terms

Let \(\sigma = (Co, Fu, Re, r)\) be a first-order signature. A term of \(LR(\sigma)\) is defined as follows:

  1. Every constant symbol of \(\sigma\) is a term of \(LR(\sigma)\).
  2. Every variable is a term of \(LR(\sigma)\).
  3. For every function symbol \(F\) of \(\sigma\), if \(F\) has arity \(n\) and \(t_1, \ldots, t_n\) are terms of \(LR(\sigma)\), then \(F(t_1, \ldots, t_n)\) is a term of \(LR(\sigma)\).
  4. Nothing is a term of \(LR(\sigma)\) except as implied by (1), (2), (3).

Formula

Let \(\sigma = (Co, Fu, Re, r)\) be a first-order signature. A formula of \(LR(\sigma)\) is defined as follows:

  1. If \(s\) and \(t\) are terms of \(LR(\sigma)\), then the expression \((s=t)\) is a formula of \(LR(\sigma)\).
  2. If \(R\) is a relation symbol of arity \(n\) in \(\sigma\) and \(t_1, \ldots, t_n\) are terms of \(LR(\sigma)\), then the expression \(R(t_1, \ldots, t_n)\) is a formula of \(LR(\sigma)\)
  3. \(\bot\) is a formula of \(LR(\sigma)\).
  4. If \(\varphi\) and \(\psi\) are formulas of \(LR(\sigma)\), then so are the following expressions: \((\neg\varphi)\), \((\varphi\wedge\psi)\), \((\varphi\vee\psi)\), \((\varphi\rightarrow\psi)\), and \((\varphi\leftrightarrow\psi)\),
  5. If \(\varphi\) is a formula of \(LR(\sigma)\) and \(v\) is a variable, then the expressions \(\forall v\varphi\) and \(\exists v\varphi\) are formulas of \(LR(\sigma)\).
  6. Nothing is a formula of \(LR(\sigma)\) except as implied by (1)–(5).

The atomic formulas are the formulas constructed using clauses 1, 2 and 3.

A formula is quantifier-free if \(\forall\) and \(\exists\) does not occur anywhere in the formula.

Examples

Example 1

Let \(\sigma = (\{c,d\}, \{f, g\}, \{P, Q\}, r)\) where \(r(f)=2\), \(r(g)=1\), \(r(P)=1\) and \(r(Q)=3\).

The following are examples of terms of \(LR(\sigma)\) (you should draw the parse tree for each of the terms):

  1. \(x_0\)
  2. \(c\)
  3. \(f(c,x_0)\)
  4. \(f(f(f(d,x_0),c),g(c))\)
  5. \(g(f(g(c),c))\)

Examples of quantifier-free formulas of \(LR(\sigma)\) include: (you should draw the parse tree for each of these formulas)

  1. \(x_0 = x_1\)
  2. \(c=d\)
  3. \(f(c,d)=x_1 \wedge g(x_0)=c\)
  4. \((\neg (P(d) \rightarrow Q(g(x_0), d, x_0)))\)
  5. \((x_0=c)\wedge \neg P(g(x_0))\)

Examples of formulas of \(LR(\sigma)\) include the above 5 quantifier-free formulas plus all of the following: (you should draw the parse tree for each of these formulas)

  1. \(\exists x_0 (x_0 = x_1)\)
  2. \(\exists x_0 (x_0 = c)\)
  3. \((\forall x_1\exists x_0 (x_0 = x_1)\wedge \forall x_2 P(x_2))\)
  4. \((\forall x_0 P(c)\wedge \exists x_1 P(x_1))\)
  5. \(\forall x_0\exists x_1 Q(c, x_0, x_1)\)
  6. \((P(x_0)\wedge P(x_1))\)
  7. \(\forall x_0 P(x_0)\)
  8. \(\forall x_1 P(x_0)\)
  9. \(\forall x_0 (P(x_0)\rightarrow P(c))\)
  10. \(\forall x_0 (Q(x_0,c,x_1)\rightarrow (P(f(c))\wedge \exists x_2 P(g(x_2,d,f(c)))))\)

The Language of Arithmetic

Let \(\sigma_{arith}\) be the following signature:

  1. There is a single constant symbol \(\bar{0}\)
  2. There are three function symbols: \(\bar{S}\), \(\bar{+}\) and \(\bar{\times}\). The function symbol \(\bar{S}\) has arity 1 and \(\bar{+}\) and \(\bar{\times}\) have arity 2.
  3. There are no relation symbols.

The resulting language \(LR(\sigma_{arith})\) is the first-order language of arithmetic.

The following are examples of terms of \(LR(\sigma_{arith})\) (you should draw the parse tree for each of the terms):

  1. \(x_0\)
  2. \(\bar{0}\)
  3. \(\bar{S}(\bar{S}(\bar{0}))\)
    Informally, we typically write this as \(\bar{S}\bar{S}(\bar{0})\)
  4. \(\bar{+}(\bar{S}(\bar{S}(\bar{0})), x_0)\).
    Informally, we typically write this as \((\bar{S}\bar{S}(\bar{0}) \bar{+} x_0)\)
  5. \(\bar{+}(\bar{\times}(\bar{S}(\bar{S}(\bar{0})),x_0), \bar{S}(\bar{0}))\)
    Informally, we typically write this as \((\bar{S}\bar{S}(\bar{0}) \bar{\times} x_0) \bar{+} \bar{S}(\bar{0})\)

Examples of quantifier-free formulas of \(LR(\sigma_{arith})\) include: (you should draw the parse tree for each of these formulas)

  1. \(x_0 = x_1\)
  2. \(\bar{0}=\bar{S}(\bar{0})\)
  3. \((\neg(\bar{0}=\bar{S}(\bar{0})))\)
    Informally, we typically write this as \((\bar{0}\neq \bar{S}(\bar{0}))\)
  4. \(\bar{S}(\bar{0})\bar{+} \bar{S}\bar{S}(\bar{0}) = \bar{S}(\bar{S}(\bar{0})\bar{+} \bar{S}(\bar{0}))\)
  5. \(((x_1=\bar{0}) \wedge x_2\bar{\times} x_1 = \bar{S}(\bar{0}))\)

Examples of formulas of \(LR(\sigma_{arith})\) include the above 5 quantifier-free formulas plus all of the following: (you should draw the parse tree for each of these formulas)

  1. \(\exists x_0 (x_0 = \bar{S}\bar{S}\bar{S}(\bar{0}))\)
  2. \(\forall x_0 (x_0 \neq \bar{S}(x_0))\)
  3. \(\forall x_0 \exists x_1 (x_0 = \bar{S}(x_1))\)
  4. \(\forall x_0 (x_0 \bar{+} \bar{0} = x_0)\)
  5. \(\forall x_0 ( \bar{0} \bar{+} x_0 = x_0)\)
  6. \(\forall x_0 \forall x_1 ((x_0 \bar{+} \bar{S}(x_0)) = \bar{S}(x_0\bar{+} x_1))\)

Numeral

For each natural number \(n\in\mathbb{N}\), let \(\bar{n}\) be the term consisting of \(n\) applications of the function symbol \(\bar{S}\) to the constant \(\bar{0}\). That is,

\[ \bar{n} = \underbrace{\bar{S}\cdots \bar{S}}_{n-times}(\bar{0}) \]

Examples of numerals include:

\(\bar{1}=\bar{S}(\bar{0})\)
\(\bar{2}=\bar{S}\bar{S}(\bar{0})\)
\(\bar{3}=\bar{S}\bar{S}\bar{S}(\bar{0})\)
\(\bar{7}=\bar{S}\bar{S}\bar{S}\bar{S}\bar{S}\bar{S}\bar{S}(\bar{0})\)

Important Point

It is very important to understand the difference betweent the following two statements:

  1. \(\forall x(x \bar{+} \bar{0} = x)\)
  2. For all \(n\in\mathbb{N}\), \(\bar{n} \bar{+} \bar{0}=\bar{n}\)

Statement 1 is a formula of first-order arithmetic. Statement 2 is not a formula of first-order arithmetic. It is a formula schema: a shorthand for expressing infinitely many atomic formulas of first-order arithmetic. That is, statement 2 is short hand for the following list of formulas:

  1. \(\bar{0} \bar{+} \bar{0}=\bar{0}\)
  2. \(\bar{1} \bar{+} \bar{0}=\bar{1}\)
  3. \(\bar{2} \bar{+} \bar{0}=\bar{2}\)
  4. \(\cdots\)

The Language of Linear Orders

Let \(\sigma_{lin}\) be the following signature:

  1. There are no constant symbols.
  2. There are no function symbols.
  3. There is a single binary relation symbol \(<\).

The only terms of \(LR(\sigma_{lin})\) are the variables \(x_0, x_1, \ldots\).

Examples of formulas of \(LR(sigma_{arith})\) include:

  1. \(x_0 < x_1\)
  2. \(\forall x_0 \exists x_1 (x_0 < x_1)\)
  3. \(\forall x_0\forall x_1\forall x_2(((x_0 < x_1) \wedge (x_1 < x_2)) \rightarrow (x_0 < x_2))\)
  4. \(\forall x_0(\neg (x_0 < x_0))\)
  5. \(\forall x_0\exists x_1(x_1 < x_0)\)

Free/Bound Variables

(Definition 5.1.1) An occurrence of a variable in a piece of mathematical text is said to be free if the text allows us to read the variable as a name. If not free, the occurrence is bound. When an occurrence of a variable in the text is bound, there must always be something in the text that prevents us taking the occurrence as a name.

If \(t\) is a term, then \(x\) is free in \(t\) if \(x\) occurs in \(t\).

Free Occurrence of a Variable

Suppose that \(x\) is a variable. Then, \(x\) occurs free in \(\varphi\) is defined as follows:

  1. If \(\varphi\) is an atomic formula, then \(x\) occurs free in \(\varphi\) provided \(x\) occurs in \(\phi\) (i.e., is a symbol in \(\varphi\)).
  2. \(x\) occurs free in \(\neg\psi\) iff \(x\) occurs free in \(\psi\)
  3. \(x\) occurs free in \(\psi_1\wedge\psi_2\) iff \(x\) occurs free in \(\psi_1\) or \(x\) occurs free in \(\psi_2\) (similarly for the other Boolean connectives \(\vee\), \(\rightarrow\), \(\leftrightarrow\))
  4. \(x\) occurs free in \((\forall y)\psi\) iff \(x\) occurs free in \(\psi\) and \(x\ne y\)
  5. \(x\) occurs free in \((\exists y)\psi\) iff \(x\) occurs free in \(\psi\) and \(x\ne y\)

A variable \(x\) that is not free is said to be bound.

Closed Term/Sentence

A term that does not contain any variables is said to be a closed term. Formulas that do not contain any free variables are called sentences.

Variable Occurrences

We sometimes need to talk about different occurrences of a variable in a formula. For example, in the formula:

\[ P(x)\wedge R(c,x) \]

There is one free variable \(x\). Note that \(x\) occurrs twice in this formula: Once in the left conjunct and once in the right conjunct. The variable \(x\) occurs three times in the following formula:

\[ P(x)\wedge R(x,x) \]

Note that same variable may occur both as a bound variable and a free variable in a formula:

\[ (\forall xP(x) \wedge R(c,x)) \]

In the above formula, \(x\) is free because it occurs free in the right conjunct \(R(c,x)\).