1.9 First order logic

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 “” which is a true or false statement about any two real numbers $x$ and $y$.

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⩾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 ℝ:x^2>0$$

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

$$\forall x\in ℝ:x^2⩾0$$

is true, since every real number $x$ satisfies $x^2⩾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 ℝ: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

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, $ℝ$ 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 ℝ:x^2>0$

• •

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

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 ϵ>0\exists \delta >0:\mathrm{\dots }$$

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

$$\forall ϵ\in (0,\mathrm{\infty })\exists \delta \in (0,\mathrm{\infty }):\mathrm{\dots }$$

where $(0,\mathrm{\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⩾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⩾n)\wedge P(p,n).$$

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 ℝ\forall x\in ℝ:|f(x)|⩽M,$$

that is, there exists a real number $M$ such that for all real numbers $x$ we have $|f(x)|⩽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.

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$.

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

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

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.

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,

	is true if and only if
	is true, if and only if
	is true, if and only if

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

$$\exists ϵ\in (0,\mathrm{\infty })\forall N\in \mathbb{N}\exists n\in \mathbb{N}:(n⩾N)\wedge (|a_n|⩾ϵ).$$

We now know what we need to do to prove $(a_n)$ doesn’t tend to 0: we have to find some $ϵ>0$ such that for every $N$, there is an $n⩾N$ such that $|a_n|⩾ϵ$.

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!