Quantifiers

Quantifiers

The quantifiers for all, for some, and there exists

Understand and use the terms for all, for some (meaning for at least one), and there exists.

Earlier, we mentioned that when we have statements with an $x$ [or an $a$ or $b$ etc], then we clarify what we mean by the $x$ that we have written. We say that we need to set out exactly the scope of the $x$ in some way; and when we set out exactly what $x$ values we are talking about, we say that we "quantify" the $x$ value. In this section, we explore this notion of quantification by looking at the two different ways of quantifying an $x$ in a statement. [In more advanced treatments on the foundations of logic, it is common to use only one quantifier and derive any others from it; we do not take this approach in the TMUA.]

Here is an example from earlier where we added some information to a statement to tell us exactly what values we were considering. Instead of

$\text{if } 0 < a < b \text{ then } a^2 < b^2$

we wrote:

$\text{for all real values of } a \text{ and } b, \text{ if } 0 < a < b \text{ then } a^2 < b^2$

In this section we explore phrases that quantify $x$ [or $a$ or $b$ etc] such as for all, for some and there exists in more detail. We will start this exploration by looking at a number of statements and discussing them a little.

Consider the following statement:

$\text{for all real } x, x^2 \geq 0$

This is clearly a true statement but what is important to notice for this section is the phrase "for all". This phrase tells us what our statement applies to – in this case it tells us that the statement, $x^2 \geq 0$, applies to all real numbers. But why do we need to specify what a statement refers to? The reason is that if we don't there might be scope for confusion or ambiguity and mathematics doesn't like confusion or ambiguity. Here is another example. Consider the statement

$x^2 \text{ is an integer}$

Now this is sometimes true and sometimes false, for instance it is true when $x = 7$ and it is false when $x = 0.5$. However, if we write:

for all integers $x, x^2$ is an integer

it is true, but if we write

for all real $x, x^2$ is an integer

it is not true because there are some real $x$ values for which $x^2$ is not an integer, for instance $x = 0.5$.

Two things are important to note here:

1. Mathematicians like to say what their statements apply to and sometimes they do this using phrases like "for all".
2. Often a statement can be true only in certain situations and mathematicians can use phrases like "for all..." to make it clear what circumstances they are considering.

Sometimes, in place of "for all" we can write "for every" or "for each" so we can take a statement such as

for all integers $x, x^2$ is an integer

and rewrite it as:

for every integer $x, x^2$ is an integer

or

for each integer $x, x^2$ is an integer

Mathematicians also like to assert that something [some mathematical thing, like a number or a function etc.] can be found to make something true, in these cases they tend to use the term "there exists" [usually along with the phrase 'such that']. For instance:

there exists a real $x$ such that $x^2 = 4$

there exists an $x$ such that $x^2$ is an integer

there exists a real $x$ for which $x^2 = 4$

Sometimes we might find that a "there exists" statement is actually false; for instance:

there exists a real integer $x$ such that $x^2 = -4$

Sometimes, in place of there exists we can write for some or for at least one so we can take a statement such as:

$\text{there exists a real } x \text{ such that } x^2 = 4$

and write it as:

$\text{for some real } x, x^2 = 4$

or

$\text{for at least one real } x, x^2 = 4$

Thinking informally about for all and there exists.

When you see the phrase for all $x$ ... you can think of it as telling you that you can pick ANY $x$ you want from the given set of $x$'s and then the corresponding statement will be true. The phrase is telling you that every value of $x$ makes the statement true.

And when you see the phrase there exists an $x$ such that... you can think of it as issuing a challenge: you are challenged to FIND an $x$ that makes the statement that the phrase is applied to true. The phrase is telling you that there is at least one $x$ that makes the statement true.

Be aware that there exists does not mean that there must also be values for which the corresponding statement is false. For example, the statement

$\text{there exists a real } x \text{ for which } x^2 > -2$

is true, because $x^2 > -2$ when $x = 0$. It does not matter that $x^2 > -2$ for every real $x$.

Exercise M

1. Which of the following are true and which are false?
   • i. for every real $x, x^2$ is rational
   • ii. there exists a real $x$ such that $x^2$ is rational
   • iii. for every real $x, x^2 > x$
   • iv. there exists a real $x$ such that $x^2 > x$
   • v. for every real $x, x^3 > 0$
   • vi. there exists a real $x$ such that $x^3 > 0$
   • vii. for every real $x$ and $y, x^2 + y^2 > 2xy$
   • viii. there exists real $x$ and $y$ such that $x^2 + y^2 > 2xy$

Combining the two phrases together

Understand and use the terms for all, for some (meaning for at least one), and there exists.

You will often encounter statements in university mathematics that include both the phrase for all and the phrase there exists. When this happens the order in which they appear is very important. Here are a couple of statements to illustrate how important the order is:

S1: for all positive real $x$ there exists a real $y$ such that $y^2 = x$

S2: there exists a real $y$ such that for all positive real $x$, $y^2 = x$

A little thought will show you that S1 is true but S2 is false. Let us explore why:

S1 is telling us that if we pick any positive $x$ value then we can always find a $y$ value for that $x$ value that obeys the equation $y^2 = x$. In other words, we pick any positive $x$ value first and then look about to see if we can find a $y$ value to go with our chosen $x$ value – and we always can find such a $y$ value so S1 is true. It is useful to note that different choices of $x$ value have different $y$ values associated with them and this is allowed by S1.

S2 is telling us that we can find one value of $y$ such that $y^2 = x$ no matter what $x$ value we choose from the positive reals. This is clearly not true. Here the difference is that we are challenged to pick a $y$ value so that our chosen $y$ value then satisfies the test set by the second bit of the statement – we need to test that for our chosen $y$ value it is true that $y^2 = x$ for all positive $x$ values. In other words, to make the statement true we need to find at least one $y$ value such that this one $y$ value obeys all the following [and many more!]: $y^2 = 1$, $y^2 = 2$, $y^2 = 3$, $y^2 = \pi$, ...

What we take from these two examples is that the order of the phrases for all and there exists is important when they occur together and we have to respect the order in which they appear. [There are alternative logics, which do NOT appear in the TMUA, where the ordering of the quantifiers is dealt with differently; look up "independence friendly logic".] Only once we have dealt with the first phrase can we then deal with the second phrase in light of what the first phrase has told us.

And a final note: sometimes mathematicians write the phrase "for all real $x$" (or similar) at the end of a statement instead of at the start, to emphasise the embedded statement, for example:

$x^2 \geq 0 \text{ for all real } x$

This is fine for one occurrence of for all, but if it is mixed with for some or there exists in the same statement, then confusion will result, so it is very unwise to do this.

Exercise N

1. Which of the following are true and which are false:
   • i. for all real x there exists a real y such that: $x > y$
   • ii. for all real x there exists a real y such that: $y > x$
   • iii. for all real y there exists a real x such that: $x > y$
   • iv. for all real y there exists a real x such that: $y > x$
   • v. there exists a real x such that for all real y: $x > y$
   • vi. there exists a real x such that for all real y: $y > x$
   • vii. there exists a real y such that for all real x: $x > y$
   • viii. there exists a real y such that for all real x: $y > x$

Negating for all and there exists

Understand and use the terms for all, for some (meaning for at least one), and there exists.

Earlier we saw what happens when we negated [that is, put not in front of] statements such as A and B, A or B and so on. A natural question to ask is what happens when we use not together with for all and there exists. In this section we shall explore this. Before we begin we should mention again that we tend not just to write "not" in front of statements but translate them into more palatable English: here we shall say "it is not the case that..." in place of not by itself.

Let's start by looking at a few examples:

S1: for all real $x$, $x^2 > 6$

N1: it is not the case that for all real $x$, $x^2 > 6$

S2: there exists a real $x$ such that $x^2 < 0$

N2: it is not the case that there exists a real $x$ such that $x^2 < 0$

What about the truth of these statements? S1 is false, so N1 is true; S2 is false so N2 is true.

What we want to do is see if we can translate N1 and N2 in some way into a simpler statement. We start with N1: what does N1 say? It says that it's not true that $x^2 > 6$ for all real $x$ values; in other words, it is telling is that there must be some $x$ value for which it is not true that $x^2 > 6$. And in this case, we can easily find such an $x$, for instance $x = 2$. So we now have two equivalent ways of writing out N1:

N1old: It is not the case that for all real $x$, $x^2 > 6$

N1new: there exists a real $x$ such that $x^2 > 6$ is not the case

Let's look more carefully at these two versions of N1 to see if we can understand their general structure:

• N1old has the structure: not-(for all) statement
• N1new has the structure: (there exists) not-statement

We can actually go further with N1new, by translating "$x^2 > 6$ is not the case" into a simpler statement. If $x^2 > 6$ is not the case, then we must have $x^2 \leq 6$, so N1 finally becomes

N1newest: there exists a real x such that $x^2 \leq 6$

Now let's look at N2: What does N2 say? It says that no matter how hard we look we will never find a real $x$ value that makes $x^2 < 0$ true. In other words, for every real $x$ value the statement $x^2 < 0$ must be false; or, we could say that for every real $x$ value it is not the case that $x^2 < 0$. So, we now have two equivalent ways of writing out N2:

N2old: it is not the case that there exists a real $x$ such that $x^2 < 0$

N2new: for all real x it is not the case that $x^2 < 0$

Let's look more carefully at these two versions of N2 to see if we can understand their general structure:

• N2old has the structure: not-(there exists) statement
• N2new has the structure: (for all) not-statement

Again, we can simplify our N2new statement one further step to get

N2newest: for all real x, $x^2 \geq 0$

In summary, we have the following:

• not-(for all statement) is equivalent to (there exists) not-statement
• not-(there exists statement) is equivalent to (for all) not-statement

Symbols

Not in the specification and not required for the test.

Whilst you are not expected to know, and won't be tested on, the symbols used for the phrases for all and there exists, it is useful to know what they are and see how the above examples can be translated using these symbols. In this section we shall look, briefly, at the symbolism. In addition, it is worth noting that mathematicians call the phrases for all and there exists quantifiers: for all is known as the universal quantifier (because it sets the universe of things that you are allowed to consider), and there exists is known as the existential quantifier for obvious reasons.

Now some symbolism:

• for all is written as an upside-down A: ∀
• there exists is written as a backwards E: ∃

These symbols are often combined with set theory and other notation:

• ∈ to mean "belongs to"
• : [a colon] to mean "such that"
• ¬ to mean not

We can now translate some of the statements we looked at in previous sections using this notation:

• N1old: it is not the case that for all real x, $x^2 > 6$ N1old translated: ¬(∀x ∈ ℝ, $x^2 > 6$)
• N1new: there exists a real x such that $x^2 > 6$ is not the case N1new translated: ∃x ∈ ℝ: ¬(x² > 6)
• N2old: it is not the case that there exists a real x such that $x^2 < 0$ N2old translated: ¬(∃x ∈ ℝ: ($x^2 < 0$))
• N2new: for all real x it is not the case that $x^2 < 0$ N2new translated: ∀x ∈ ℝ, ¬(x² < 0)

Looking at these we can see that in general we have:

¬∀ is the same as ∃¬; and ¬∃ is the same as ∀¬

And it is always worth recalling from the discussions we had above that ∀ ... ∃ is not generally the same as ∃ ... ∀

And a final note: If a mathematician writes, as mentioned above, something like "$x^2 \ge 0$ for all real x", it would still usually be translated into symbols as ∀x ∈ ℝ, $x^2 \ge 0$ with the ∀ at the beginning.