We were unable to assign a truth value to this statement because we had no information about \(x\text{.}\) It is clear that this sentence is true for some values of \(x\) and false for others:
If \(x=0\) the sentence makes sense but is false.
If \(x=1\) the sentence makes sense and is true.
If \(x\) is the colour blue, then it doesn’t even make sense.
Now we can express things in a more compact (and a little more abstract) way: \(P(0)\) is false, while \(P(4)\) is true.
Just as Result 3.2.7 was a statement about integers, we might choose to study the open sentence over, say, the set \(S = \{0,1,2,3,4\}\text{.}\) In this case we would analyse the truth-values of \(P(x)\) over the domain 48 \(S\text{.}\) Checking carefully we find that
\(P(1), P(4)\) are true and \(P(0),P(2),P(3)\) are false.
Such lists are going to become very cumbersome over big domains, let alone infinite 49 domains. However, we could summarise that list by saying that the statement is true sometimes, but not true always. To be a little more precise:
\(P(x)\) is true for some \(x \in S\text{,}\) and
\(P(x)\) is not true for all \(x \in S\text{.}\)
Notice that the extra bits of text “for some \(x \in S\)” and “for all \(x \in S\)” place restrictions which values of \(x\) we take, and so turn the open sentences into statements. With that extra text we can now assign truth values.
To be even more careful, we can write the above as
There exists \(x\in S\) so that \(x^2-5x+4=0\text{,}\) and
For all \(x \in S\text{,}\)\(x^2+5x-4=0\)
where the first is now a true statement, and the second is a false statement. The extra bits “For all” and “There exists” are called quantifiers.
Definition6.1.1.
We typically work with two quantifiers in mathematics — the universal quantifier and the existential quantifier.
The universal quantifier is denoted \(\forall\) and is read as “for all” or “for every”. The statement
\begin{equation*}
\forall x\in A, P(x)
\end{equation*}
is true provided \(P(x)\) is true for every single value of \(x\in A\) and otherwise the statement is false.
The existential quantifier is denoted \(\exists\) and is read as “there exists”. The statement
\begin{equation*}
\exists x\in A \text{ so that } P(x)
\end{equation*}
is true provided there is at least one value of \(x\in A\) so that \(P(x)\) is true, and otherwise the statement is false.
Back to our two statements above. We can now write them as
“\(\exists x \in S\) such that \(x^2 - 5x+4 = 0\)” or “\(\exists x\in S \st x^2 - 5x+4 = 0 \)”.
“For every \(x \in S, x^2 - 5x+4 = 0\)” or “\(\forall x\in S, x^2 - 5x+4 = 0 \)”
Remark6.1.2.Punctuation please.
Be careful to punctuate these statements nicely — make sure that it is clear to the reader where the quantifier stops and the open sentence begins. In the case of for-all statements we usually just place a comma:
For there-exists statements we write in “so that” or “such that”, since that is how the statements are typically read. Your busy hard-working mathematician will contract the “so that” to “s.t.”:
It is also generally considered bad style to use \(\exists\) and \(\forall\) in sentences in place of “there exists” and “for all”. Mind you, that doesn’t stop people doing it, but in general, it is okay to do in a mathematical statement or equation, but you should avoid writing them in the middle of paragraphs (except in scratch work).
Quantifiers are often a point of confusion for students. This can be exacerbated by the number of different ways they can be expressed in written or spoken languauge. For example, the statement “\(\exists x\in A \st P(x)\)” can be read as
There exists \(x\) in \(A\) so that \(P(x)\) is true.
There is \(x\) in \(A\) so that \(P(x)\) is true.
There is at least one \(x\) in \(A\) so that \(P(x)\) is true.
\(P(x)\) is true for at least one value of \(x\) from \(A\)
We can find an \(x\) in \(A\) so that \(P(x)\) is true.
We can always find an \(x\) in \(A\) that makes \(P(x)\) is true.
At least one \(x\) in \(A\) exists so that \(P(x)\) is true.
…
The above is just what the author thought of in a couple of minutes.
Similarly, the statement “\(\forall x\in A, P(x)\)” can be read in many ways:
For all \(x\) in \(A\text{,}\)\(P(x)\) is true.
For every \(x\) in \(A\text{,}\)\(P(x)\) is true.
No matter which \(x\) we choose from \(A\text{,}\)\(P(x)\) is true.
Every single \(x\) in \(A\) makes \(P(x)\) true.
\(P(x)\) is true for every \(x\) in \(A\text{.}\)
Every choice of \(x\) from \(A\) makes \(P(x)\) true.
All the \(x\) in \(A\) makes \(P(x)\) true.
…
Oof!
We need to add one more to the list of ways to read \(\forall x \in A, P(x)\text{:}\)
If \(x\) is in \(A\) then \(P(x)\) is true.
This is critically important, because it shows us a link between the universal quantifier and the implication. It shows us that:
\begin{equation*}
( \forall x \in A, P(x) ) \equiv (x \in A \implies P(x) )
\end{equation*}
Thankfully it is not too hard to see why — think about their truth values.
\(\forall x \in A, P(x)\) is true provided \(P(x)\) is true for every single \(x\) from \(A\text{.}\) It is false if we can find at least one value of \(x\) from \(A\) so that \(P(x)\) is false.
On the other hand, the implication \(x\in A \implies P(x)\text{,}\) is false when the hypothesis is true, but the conclusion is false. That is, we can find a value of \(x\in A\) so that \(P(x)\) is false. Otherwise the implication is true.
More generally when we have a statement like
If \(n\) is even then \(n^2\) is true.
there is an implicit assumption that we actually mean
For all \(n\text{,}\) if \(n\) is even then \(n^2\) is even.
Of course, we don’t really mean for every single possible value of the variable \(x\) taken from the set of all possible things in this and every other universe. We actually mean
\begin{align*}
\forall x \in A, P(x) &\implies Q(x)
\end{align*}
where the set \(A\) is often inferred by context. So when we are talking about even and odd numbers (as above), we really mean
For all integers \(n\text{,}\) if \(n\) is even then \(n^2\) is true.
Typically the context is clear, and so it is is just cumbersome 50 to write “\(\forall x \in A,\dots\)” before our statements. When it is us doing the writing, we can look after our reader and try to make sure the context is clear. To this end, a good general rule is:
If you are worried that the reader might not understand the context or that your statements might be open to misinterpretation, then put in more words and more details.
or, to be a little more to the point:
If in doubt, put in more details.
Time for a simple example (we’ll do more complicated ones in the next section).
Example6.1.3.
Let \(P(n)\) be the open sentence “\((7n-6)/3 \) is an integer.” over the domain \(\mathbb{Z}\text{.}\) Explain whether the following statements are true
\begin{align*}
\exists n \in \mathbb{Z} \st\amp P(n) \\
\forall n \in \mathbb{Z}, \amp P(n)
\end{align*}
In order for this to be true we need to find at least one integer \(n\) that makes \(P(n)\) to be true. For example, setting \(n=0\) gives
\begin{equation*}
P(0): -2 \text{ is an integer}
\end{equation*}
which is true.
Since we have found at least one value of \(n\) to make the open sentence true, the statement is true.
In order for the second statement to be true, no matter which integer \(n\) we choose, the statement \(P(n)\) is true. However, if we pick \(n=1\) then
\begin{equation*}
P(1): \frac{1}{3} \text{ is an integer}
\end{equation*}
which is clearly false.
Since we cannot pick whatever integer \(n\) we want, and still have \(P(n)\) true, it follows that the statement is false. To be more precise, it is false because there is some \(n\) so that \(P(n)\) is false. In symbols this is:
\begin{equation*}
\exists n \in\mathbb{Z} \st \neg P(n).
\end{equation*}
Notice that in the case of the second statement in the above exercise, we have shown the statement to be false, by demonstrating that its negation is true. This brings us to negating quantifiers.
Again, this terminology is reminiscent of functions.
Actually we cannot even construct such lists over some types of infinite domains — see Chapter 12.
And tedious for the hard-working time-pressed mathematician.
