1 Logic 1.8 Adequacy 1.10 Interpretations

1.9 First order logic

The WFFs we have studied so far only capture logical statements of a very simple form. Very commonly we want to work with more complex statements, especially those that depend on some kind of parameter or variable. Here are some examples.

Example 1.9.1.

•

There exists a rational number $x$ with $x^{2}=2$ .
•

For every natural number²² 2 A natural number is a non-negative whole number. $n$ there exists a natural number $m$ with $m>n$ .
•

For all real numbers $m$ there exists a real number $n$ such that for all real numbers $x$ greater than $n$ it holds that $f(x)$ is greater than $m$ .

This kind of statement is especially common in analysis, but they arise everywhere in mathematics. Propositional calculus doesn’t have a way of talking about statements that depend on a variable, and might be true for some values, or all values, or no values that variable could take. It also has no way to talk about functions or relations. The logical theory we’re going to learn about that can deal with statements like this is called first order logic or predicate calculus.

1.9.1 Informal introduction to first order formulas

In propositional calculus we had WFFs. The corresponding thing in first order calculus is called a first order formula.

When we studied propositional calculus, we were able to give a precise definition of a WFF. Doing something similar in first order logic is much more complicated, so we won’t do that (if you want to know how, read chapter 4 of the book by Goldrei mentioned in the further reading section at the end of this chapter, or take MATH0037 in year 3). Instead we are going to list the ingredients used to write first order formulas and give some examples.

Here is a simple example of a first order formula:

\forall x\exists y\;R(x,y)

The intended meaning of this is “for all $x$ , there exists a $y$ , such that $x$ and $y$ are related by the relation $R$ .” At the moment, this is like a WFF in that it isn’t true or false — we need more information (what sort of thing are the $x$ s and $y$ s? What is the relation $R$ ?) to decide that.

1.9.2 Quantifiers, variable symbols, relation symbols

First order formulas are made up of

•

quantifiers $\forall$ and $\exists$ ,
•

the logical connectives $\neg,\wedge,\vee,\implies$ and brackets,
•

variable symbols $x,y,z,\ldots$ , and
•

relation symbols $P,Q,R,\ldots$

The quantifiers $\forall$ and $\exists$ are known as the universal quantifier and the existential quantifier). Formulas that contain $\forall x\;\ldots$ are interpreted to mean “for all $x$ , …” and formulas that contain $\exists x\;\ldots$ are interpreted to mean “there exists an $x$ such that ….”

We write $R(x,y)$ to indicate that $x$ and $y$ are related by some relation $R$ . A two-variable relation is a property of two things that can be true or false, for example $\leqslant$ and $\neq$ and $=$ are relations on the real numbers: for every two real numbers $x$ and $y$ , the statements $x\leqslant y$ and $x\neq y$ and $x=y$ are either true or false.

We allow relations on any number of things. A one-variable relation $R(x)$ is just a true or false property of a single thing $x$ (for example, “ $x$ is even”), a three-variable relation $R(x,y,z)$ is a true or false property of three things (for example, “ $x+y$ equals $z$ ”), and so on.

The three statements in Example 1.9.1 correspond to first order formulas

•

$\exists x\;P(x)$ (“there exists a rational number $x$ with $x^{2}=2$ ”)
•

$\forall n\;\exists m\;Q(n,m)$ (“for every natural number $n$ there exists a natural number $m$ with $m>n$ ”)
•

$\forall m\;\exists n\;\forall x\;(P(x,n)\implies Q(x,m))$ (“for all $m$ there exists an $n$ such that for all $x$ greater than $n$ , $f(x)$ is greater than $m$ .”)

Turning the first order formula into the statement in brackets is called giving an interpretation for the formula.