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 number22 2 A natural number is a non-negative whole number. $n$ there exists a prime number $p$ with $p>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 $e^{x}$ is greater than $m$.

These kinds of statement are 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.

In propositional calculus we had WFFs. The corresponding thing in first order logic is called a first order formula. We will treat these very informally — if you want to learn about these in detail, 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.

Here is a simple example of a first order formula:

 $\forall x\in X\;\exists y\in Y\;:R(x,y)$

The meaning of this is “for all $x$ in the set $X$, there exists a $y$ in the set $Y$ such that the property $R(x,y)$ is true for $x$ and $y$.” The new things here are the symbol $\in$ which means “in,” the quantifiers $\forall$ and $\exists$, and the predicate $R(x,y)$. In the next two subsections we’ll explain what these last two are.

1.9.1 Predicates

A predicate $P(x)$ on a set $X$ is a statement that becomes true or false when an element of $X$ is substituted for the variable $x$. For example, “$x$ is even” is a predicate on the integers, since for every integer $n$ the statement “$n$ is even” is either true or false.

We need predicates like $P(x,y)$ that require more than one variable. For example, $P(x,y)$ could be the statement “$|x-y|<1$” which is a true or false statement about any two real numbers $x$ and $y$.

1.9.2 Quantifiers

Lots of statements in mathematics involve the idea of a predicate being true for some, or for all, values of a particular variable. For example:

• There exists some rational number $q$ such that $q^{2}=2$.

• For all real numbers $x$, we have $x^{2}\geqslant 0$.

• For all natural numbers $n$, there exists a prime number $p$ such that $p>n$.

To write these formally we use quantifiers. There are two types of quantifier: $\forall$, the universal quantifier, and $\exists$, the existential quantifier.

The universal quantifier $\forall$ is used to say that something is true for every element of a particular set, called the domain of the quantifier. If $P(x)$ is a predicate,

 $\forall x\in X:P(x)$

is read as “for all $x$ belonging to $X$, the statement $P(x)$ is true.” So

 $\forall x\in\mathbb{R}:x^{2}>0$

is false, because not every real number $x$ satisfies $x^{2}>0$, but

 $\forall x\in\mathbb{R}:x^{2}\geqslant 0$

is true, since every real number $x$ satisfies $x^{2}\geqslant 0$.

The existential quantifier $\exists$ is used to say that something is true for at least one element of a particular set, again called the domain. If $P(x)$ is a predicate

 $\exists x\in X:P(x)$

says “there exists $x$ in $X$ such that $P(x)$ is true.” Such a statement is true when there is at least one $x$ belonging to the set $X$ making $P(x)$ true. For example,

 $\exists x\in\mathbb{R}:x^{2}>0$

is true, because there is at least one real number $x$ whose square is positive (in fact, there’s infinitely many!), but

 $\exists x\in\mathbb{R}:x^{2}<0$

is false since there is no real number $x$ whose square is negative.

Let’s write the three examples at the start of this subsection using quantifier notation. We use $\mathbb{Q}$ to represent the set of rational numbers, $\mathbb{R}$ for the set of real numbers, $\mathbb{N}$ for the set of natural numbers, and $\mathbb{P}$ for the set of prime numbers. The statement are then:

• $\exists q\in\mathbb{Q}:q^{2}=2$

• $\forall x\in\mathbb{R}:x^{2}>0$

• $\forall n\in\mathbb{N}\;\exists p\in\mathbb{P}:p>n.$

1.9.3 Note on how domains for quantifiers are specified

In all the examples above, we specified the domain of the quantifier explicitly. Sometimes, especially in analysis, the domain is specified using a condition. Analysts will write

 $\forall\epsilon>0\;\exists\delta>0\;:\ldots$

to mean “for all positive real numbers $\epsilon$, there exists a positive real number $\delta$, …”. You can think of this as meaning

 $\forall\epsilon\in(0,\infty)\;\exists\delta\in(0,\infty):\ldots$

where $(0,\infty)$ means the set of all positive real numbers.

There are even times when the domain of one variable seems to depend on another — you might see an expression like

 $\forall n\in\mathbb{N}\;\exists p\geqslant n:P(p,n)$

If $p$ is intended to be a natural number, for example, we could rewrite this as

 $\forall n\in\mathbb{N}\;\exists p\in\mathbb{N}:(p\geqslant n)\wedge P(p,n).$

1.9.4 Multiple quantifiers

We need more than one quantifier to express statements whose truth depends on more than one variable. For example, in analysis, the definition of a function $f$ being bounded is that

 $\exists M\in\mathbb{R}\;\forall x\in\mathbb{R}:|f(x)|\leqslant M,$

that is, there exists a real number $M$ such that for all real numbers $x$ we have $|f(x)|\leqslant M$. The definition of a function being continuous at a point is even more complicated, requiring three quantifiers.

When we have more than one quantifier, it’s important to get the quantifiers in the correct order because if you change the order of the quantifiers you may change whether or not the statement is true.

Example 1.9.2.
 $\forall x\in\mathbb{R}\;\exists y\in\mathbb{R}:x+y=0$

is true, because no matter what real number $x$ you give me, I can find a real number $y$ (equal to $-x$) such that $x+y=0$. On the other hand

 $\exists y\in\mathbb{R}\;\forall x\in\mathbb{R}:x+y=0$

which is the same statement except that the quantifiers are the other way round, is false because there is no real number $y$ such that for all real numbers $x$ we have $x+y=0$.

However, quantifiers of the same type can be swapped without changing the truth or falsity of the statement, for example both

 $\forall x\in X\;\forall y\in Y:P(x,y)$

and

 $\forall y\in Y\;\forall x\in X:P(x,y)$

are true if and only if $P(x,y)$ is true for every $x$ in $X$ and every $y$ in $Y$.

1.9.5 Negation

It’s often useful to ask what it would mean for a quantified statement not to be true. For example, you might want to prove that a certain sequence $(a_{n})$ does not tend to 0. The definition of a sequence tending to 0 is that

 $\forall\epsilon\in(0,\infty)\;\exists N\in\mathbb{N}\;\forall n\in\mathbb{N}:n% \geqslant N\implies|a_{n}|<\epsilon.$

We could negate this just by adding a $\neg$ to the front: to say that a sequence does not tend to 0 is to say that

 $\neg\forall\epsilon\in(0,\infty)\;\exists N\in\mathbb{N}\;\forall n\in\mathbb{% N}:n\geqslant N\implies|a_{n}|<\epsilon$

but it would be helpful if we could simplify this in some way, to make it easier to prove. We can do this with the following quantifier rules.

Theorem 1.9.1.

For any predicate $P(x)$ on a set $X$,

1. 1.

$\neg(\forall x\in X:P(x))$ is true if and only if $\exists x\in X:\neg P(x)$ is true, and

2. 2.

$\neg(\exists x\in X:P(x))$ is true if and only if $\forall x\in X:\neg P(x)$ is true.

The first of these holds because to say $\forall x\in X:P(x)$ is false means that not every $P(x)$ for $x\in X$ is true, that is, there exists $x\in X$ such that $P(x)$ is false. The second can be seen similarly.

By using these rules repeatedly, we can find equivalent forms of negated quantified statements even when they contain multiple quantifiers. Returning to our example of a sequence not tending to zero,

 $\displaystyle\neg\forall\epsilon\in(0,\infty)\;\exists N\in\mathbb{N}\;\forall n% \in\mathbb{N}:n\geqslant N\implies|a_{n}|<\epsilon$ is true if and only if $\displaystyle\exists\epsilon\in(0,\infty)\;\neg\exists N\in\mathbb{N}\;\forall n% \in\mathbb{N}:n\geqslant N\implies|a_{n}|<\epsilon$ is true, if and only if $\displaystyle\exists\epsilon\in(0,\infty)\;\forall N\in\mathbb{N}\;\neg\forall n% \in\mathbb{N}:n\geqslant N\implies|a_{n}|<\epsilon$ is true, if and only if $\displaystyle\exists\epsilon\in(0,\infty)\;\forall N\in\mathbb{N}\;\exists n% \in\mathbb{N}:\neg(n\geqslant N\implies|a_{n}|<\epsilon).$

At this point we can use what we know about logical equivalences for WFFs to simplify further: this is equivalent to

 $\exists\epsilon\in(0,\infty)\;\forall N\in\mathbb{N}\;\exists n\in\mathbb{N}:(% n\geqslant N)\wedge(|a_{n}|\geqslant\epsilon).$

We now know what we need to do to prove $(a_{n})$ doesn’t tend to 0: we have to find some $\epsilon>0$ such that for every $N$, there is an $n\geqslant N$ such that $|a_{n}|\geqslant\epsilon$.

We will now look at some more examples of producing useful equivalent forms for negations of quantified statements. We’re going to use real-life examples from bits of mathematics you may not have met yet, but this won’t be a problem as our negation procedure doesn’t require understanding anything about the meaning of the statement!

Example 1.9.3.

The statement “every value the function $f:\mathbb{R}\to\mathbb{R}$ takes is less than 10” can be written

 $\forall x\in\mathbb{R}:f(x)<10.$

What does it mean for this to be false? Let’s negate it, using the negation of quantifiers theorem 1.9.1. That tells us

 $\neg\forall x\in\mathbb{R}:P(x)$

is equivalent to

 $\exists x\in\mathbb{R}:\neg P(x)$

which in our case says $\exists x\in\mathbb{R}:\neg(f(x)<10)$, or $\exists x\in\mathbb{R}:f(x)\geqslant 10$.

Example 1.9.4.

Consider the statement “the function $f:\mathbb{R}\to\mathbb{R}$ is bounded”, which we could write as

 $\exists M\in\mathbb{R}\;\forall x\in\mathbb{R}\;|f(x)|\leqslant M.$

Let’s negate it. To keep things short, we’ll write $P(x,M)$ for the predicate $|f(x)|\leqslant M$. We know that

 $\displaystyle\neg\exists M\in\mathbb{R}\forall x\in\mathbb{R}:P(x,M)$ is true if and only if $\displaystyle\forall M\in\mathbb{R}\;\neg\forall x\in\mathbb{R}:P(x,M)$ is true, if and only if $\displaystyle\forall M\in\mathbb{R}\;\exists x\in\mathbb{R}:\neg P(x,M).$

so “the function $f$ is not bounded” can be written as $\forall M\in\mathbb{R}\;\exists x\in\mathbb{R}:\neg(|f(x)|\leqslant M)$, or equivalently, $\forall M\in\mathbb{R}\;\exists x\in\mathbb{R}:|f(x)|>M$.