Consider the statements below. Decide whether any are equivalent to each other, or whether any imply any others.
You can fool some people all of the time.
You can fool everyone some of the time.
You can always fool some people.
Sometimes you can fool everyone.
Checkpoint1.3.1.
After thinking about the Investigate! problem above, share your initial thoughts below.
We have been a little sloppy when describing statements. Consider, “if a number is a multiple of 4, then it is even.” This is a fantastic example of a true implication with a false converse (just because a number is even, doesn’t mean it is a multiple of 4). However, the example isn’t really a “statement” in the sense we have been using, since “a number” is some sort of variable.
Let’s be a little more careful. To make the variable explicit, write the sentence this way:
If \(x\) is a multiple of 4, then \(x\) is even.
While the sentence is not a statement, it becomes a statement as soon as we substitute a number in for \(x\text{.}\) Examples:
If 8 is a multiple of 4, then 8 is even.
If 14 is a multiple of 4, then 14 is even.
Both of these are statements, and both of them are true (the first because it is true implies true, the second because it is false implies true). In fact, any number (integer) we substitute for \(x\) will resolve to a true statement!
Let’s just consider the first five natural numbers: 0, 1, 2, 3, 4. Each statement we get is an implication, and we can call the five “if” parts \(P, Q, R, S, U\) and the five “then” parts \(A, B, C, D, E\) (luckily we are only talking about five statements). We then claim that all these implications are true, so we claim that this is true:
\begin{equation*}
(P \imp A) \wedge (Q \imp B) \wedge (R \imp C) \wedge (S\imp D) \wedge (U \imp E)\text{.}
\end{equation*}
We can even make a truth table (with \(2^{10} = 1024\) rows) to help us understand the statement.
Let’s go wild and consider the first 25 natural numbers. With only twenty-six capital letters, we need another way to refer to the atomic statements. We will use subscripts: \(P_0, P_1, \ldots, P_{24}\) for the “if” parts and \(Q_0, Q_1, \ldots, Q_{24}\) for the “then” parts. Now to claim that all these are true is to claim that the following is a true statement:
Of course, the dot-dot-dots here are not really part of logic, that is just short hand to say that I didn’t want to type out all 25 implications.
What we really want, though, is to take the conjunction (“and”) of the infinitely many statements \(P_n \imp Q_n\) where we replace \(n\) with each of the infinitely many integers. Not only is this impractical, it is also “illegal”: a molecular statement must be made up of a finite number of atoms in our construction of symbolic logic.
There must be a better way! What we want is to claim that “for all numbers \(n\text{,}\) the implication \(P_n \imp Q_n\) is true.” So let’s say this. We even introduce a new symbol to deal with the quantifier, “for all”.
Definition1.3.2.
The universal quantifier is written \(\forall\) and read, “for all.”
Our statement above can then be written as,
\begin{equation*}
\forall n (P_n \imp Q_n)\text{.}
\end{equation*}
That seems much nicer than writing out infinitely many implications.
While we are at it, let’s consider a way to work with arbitrarily many disjunctions (“or” statements). Remember that a disjunction is true precisely when at least one of the parts are true. For example, we might claim that the statement, “\(n\) is prime and \(n\) is even,” is true for at least one value of \(n\text{.}\) Maybe use \(P_n\) for “\(n\) is prime” and \(E_n\) for “\(n\) is odd” Instead of writing,
(which is not allowed, because statements must be finite), we should write,
\begin{equation*}
\exists n (P_n \wedge E_n)\text{.}
\end{equation*}
Definition1.3.3.
The existential quantifier is written \(\exists\) and is read, “there exists.”
Our goal in this section is to understand statements that involve these two quantifiers and learn how they interact with the logical connectives from propositional logic studied in Section 1.2.
Objectives
After completing this section, you should be able to do the following.
Identify the logical form of statements involving quantifiers and write them out in symbols.
Simplify statements involving quantifiers and logical connectives, including negation.
Justify why a statement involving quantifiers is true or false by considering the domain of discourse.
ExercisesPreview Activity
Before reading on to the main content of the section, complete this preview activity to start thinking about the types of questions this section will address.
1.
Let \(P(x,y)\) be the predicate, “person \(x\) can be fooled at time \(y\text{.}\)”
Match each statement with it’s representation in symbols.
Some people can be fooled all of the time.
\(\exists x \forall y P(x,y)\)
Everyone can be fooled sometimes.
\(\forall x \exists y P(x,y)\)
It is always true that some people can be fooled.
\(\forall y \exists x P(x,y)\)
Sometimes everyone can be fooled.
\(\exists y \forall x P(x,y)\)
2.
Your friend believes that in fact you cannot fool everyone at the same time. What is another way of saying this, and how would you write that in symbols (using \(P(x,y)\) to say you can fool \(x\) at time \(y\)).
Someone is never fooled. \(\exists x \forall y\neg P(x,y)\)
Everyone is never fooled. \(\forall x \forall y \neg P(x,y)\)
Someone is not fooled sometimes. \(\exists x \exists y \neg P(x,y)\)
Everyone is not fooled sometimes. \(\forall x \exists y \neg P(x,y)\)
3.
Regardless of your beliefs of how many people can be fooled at various times, what could you conclude if we reinterpret \(P(x,y)\) to mean \(x \lt y\) and only quantify over the natural numbers (so \(\forall x\) means “for all natural numbers” and \(\exists x\) means “there exists a natural number”)? Select all of the following that apply.
\(\forall x \exists y P(x,y)\) is true.
\(\exists x \forall y P(x,y)\) is true.
Careful, \(P(x,y)\) means \(x\) is less than \(y\text{,}\) not \(x\) is less than or equal to \(y\text{.}\)
\(\forall y \exists x P(x,y)\) is true.
\(\exists y \forall x P(x,y)\) is true.
No matter what \(P(x,y)\) means, we can conclude that \(\forall x \exists y P(x,y)\) and \(\exists y \forall x\) are NOT logically equivalent
SubsectionStatements with variables
Suppose we wanted to claim that if \(n\) is prime, then \(n+7\) is not prime. This looks like an implication. I would like to write something like
where \(P(n)\) means “\(n\) is prime.” We could have also written \(P_n\text{,}\) but using parentheses is a little more common, and suggests that we can substitute values for \(n\text{,}\) just like we substitute values in functions. The variable in a sentence like this is called a free variable. It is a variable that we have not specified anything about. A sentence that contains variables is called a predicate.
As we have seen, when we substitute a value for \(n\text{,}\) we get a statement. \(P(11)\) is a statement, and therefore
is a statement, which happens to be true. In fact, it turns out that no matter what value we plug in for \(n\text{,}\) we get a true implication in this case. Thus we claim that the following is a true statement.
\begin{equation*}
\forall n (P(n) \imp P(n+7))\text{.}
\end{equation*}
By the way, once we quantify the \(n\text{,}\) we say that the variable is no longer free, but rather is a bound variable (it is bound by the quantifier). Since there are no free variables any more, the sentence really is a statement.
Although there are many types of quantifiers in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal. Here is a summary of these two together.
Universal and Existential Quantifiers.
The existential quantifier is \(\exists\) and is read “there exists” or “there is.”
For example,
\begin{equation*}
\exists x (x \lt 0)
\end{equation*}
asserts that there is a number less than 0.
The universal quantifier is \(\forall\) and is read “for all” or “every.”
For example,
\begin{equation*}
\forall x (x \ge 0)
\end{equation*}
asserts that every number is greater than or equal to 0.
As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement
\begin{equation*}
\forall x \exists y (y \lt x)\text{.}
\end{equation*}
You would read this, “for every \(x\) there is some \(y\) such that \(y\) is less than \(x\text{.}\)” Is this true? The answer depends on what our domain of discourse is: when we say “for all” \(x\text{,}\) do we mean all positive integers or all real numbers or all elements of some other set? Usually this information is implied. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2, …, so let’s take that for our domain of discourse here.
For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let \(y\) be \(x-1\text{?}\) But here is the problem: what if \(x = 0\text{?}\) Then \(y = -1\) and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,
\begin{equation*}
\exists x \forall y (y \ge x)\text{.}
\end{equation*}
To show that the original statement is false, we proved that the negation was true. Notice how the negation and original statement compare. This is typical.
Quantifiers and Negation.
\(\neg \forall x P(x)\) is equivalent to \(\exists x \neg P(x)\text{.}\)
\(\neg \exists x P(x)\) is equivalent to \(\forall x \neg P(x)
\text{.}\)
Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type. This should not be surprising: if not everything has a property, then something doesn’t have that property. And if there is not something with a property, then everything doesn’t have that property.
Another way to see why this makes sense: universal quantifiers are like (possibly infinite) conjunctions, and existential quantifiers are like (possibly infinite) disjunctions. De Morgan’s laws tells us that when we negate a conjunction, we get a disjunction, and when we negate a disjunction, we get a conjunction. Isn’t it great when everything works out as it should?
Example1.3.4.
Suppose we claim that there is no smallest number. We can translate this into symbols as
\begin{equation*}
\neg \exists x \forall y (x \le y)
\end{equation*}
(literally, “it is not true that there is a number \(x\) such that for all numbers \(y\text{,}\)\(x\) is less than or equal to \(y\)”).
However, we know how negation interacts with quantifiers: we can pass a negation over a quantifier by switching the quantifier type (between universal and existential). So the statement above should be logically equivalent to
\begin{equation*}
\forall x \exists y (y \lt x)\text{.}
\end{equation*}
Notice that \(y \lt x\) is the negation of \(x \le y\text{.}\) This literally says, “for every number \(x\) there is a number \(y\) which is smaller than \(x\text{.}\)” We see that this is another way to make our original claim.
It is important to stress that predicate logic extends propositional logic (much in the way quantum mechanics extends classical mechanics). Everything that we learned about logical equivalence and deductions still applies. However, predicate logic allows us to analyze statements at a higher resolution, digging down into the individual propositions \(P\text{,}\)\(Q\text{,}\) etc.
To do this, we need to understand how quantifiers and connectives interact. We have already seen something about negations and quantifiers. What about the other connectives? Let’s look at an example exploring how the universal quantifier and disjunctions can (or cannot) work together.
Example1.3.5.
Consider the two statements,
\begin{equation*}
\forall x (P(x) \vee Q(x)) \qquad \qquad \forall x P(x) \vee \forall x Q(x)\text{.}
\end{equation*}
Are these logically equivalent?
Solution.
These statements are NOT logically equivalent. Intuitively, the statement on the left is claiming that everything is either a \(P\)-thing or a \(Q\)-thing. The statement on the right is claiming either everything is a \(P\)-thing or that everything is a \(Q\)-thing. These feel different.
To be sure, we would like to think of predicates \(P(x)\) and \(Q(x)\) and some domain of discourse such that one of the statements is true and the other is false. How about we let \(P(x)\) be, “\(x\) is even” and \(Q(x)\) be “\(x\) is odd.” Our domain of discourse will be all integers (as that is the set of numbers for which even and odd make sense).
The statement on the left is true! Every number is either even or odd. But is every number even? No. Is every number odd? No. So the statement on the right is false (it is a false or false).
Interestingly, the statement on the right implies the statement on the left. That is,
\begin{equation*}
(\forall x P(x) \vee \forall x E(x)) \imp \forall x (P(x) \vee Q(x))
\end{equation*}
is always true.
This is sort of like a tautology, although we reserve that term for necessary truths in propositional logic. A statement in predicate logic that is necessarily true gets the more prestigious designation of a law of logic (or sometimes logically valid, but that is less fun).
We can also consider how quantifiers interact with each other.
Example1.3.6.
Can you switch the order of quantifiers? For example, consider the two statements:
\begin{equation*}
\forall x \exists y P(x,y) \qquad \text{ and } \qquad \exists y \forall x P(x,y)\text{.}
\end{equation*}
Are these logically equivalent?
Solution.
These statements are NOT logically equivalent. To see this, we should provide an interpretation of the predicate \(P(x,y)\) which makes one of the statements true and the other false.
Let \(P(x,y)\) be the predicate \(x \lt y\text{.}\) It is true, in the natural numbers, that for all \(x\) there is some \(y\) greater than that \(x\) (since there are infinitely many numbers). However, there is not a natural number \(y\) which is greater than every number \(x\text{.}\) Thus it is possible for \(\forall x \exists y P(x,y)\) to be true while \(\exists y \forall x P(x,y)\) is false.
We cannot do the reverse of this though. If there is some \(y\) for which every \(x\) satisfies \(P(x,y)\text{,}\) then certainly for every \(x\) there is some \(y\) which satisfies \(P(x,y)\text{.}\) The first is saying we can find one \(y\) that works for every \(x\text{.}\) The second allows different \(y\)’s to work for different \(x\)’s, but there is nothing preventing us from using the same \(y\) that work for every \(x\text{.}\) In other words, while we don’t have logical equivalence between the two statements, we do have a valid deduction rule:
\(\exists y \forall x P(x,y)\)
\(\therefore\)
\(\forall x \exists y P(x,y)\)
Put yet another way, this says that the single statement
\begin{equation*}
\exists y \forall x P(x,y) \imp \forall x \exists y P(x,y)
\end{equation*}
is always true; it is a law of logic.
A full treatment of predicate logic is beyond the scope of this text. One reason is that there is no systematic procedure for deciding whether two statements in predicate logic are logically equivalent (i.e., there is no analogue to truth tables here).
Implicit Quantifiers.
It is always a good idea to be precise in mathematics. Sometimes though, we can relax a little bit, as long as we all agree on a convention. An example of such a convention is to assume that sentences containing predicates with free variables are intended as statements, where the variables are universally quantified.
For example, do you believe that if a shape is a square, then it is a rectangle? But how can that be true if it is not a statement? To be a little more precise, we have two predicates: \(S(x)\) standing for “\(x\) is a square” and \(R(x)\) standing for “\(x\) is a rectangle”. The sentence we are looking at is,
This is neither true nor false, as it is not a statement. But come on! We all know that we meant to consider the statement,
\begin{equation*}
\forall x (S(x) \imp R(x))\text{,}
\end{equation*}
and this is what our convention tells us to consider. When we add enough universal quantifiers to the beginning of a sentence so that all free variables become bound, we call the resulting statement the universal generalization of the original sentence.
Similarly, we will often be a bit sloppy about the distinction between a predicate and a statement. For example, we might write, let \(P(n)\) be the statement, “\(n\) is prime,” which is technically incorrect. It is implicit that we mean that we are defining \(P(n)\) to be a predicate, which for each \(n\) becomes the statement, \(n\) is prime.
Reading QuestionsReading Questions
1.
Consider the sentence, \(\exists x P(x,y) \imp \forall x P(x,y)\text{.}\) What can we say about this sentence? Select all that apply.
The sentence is a statement because it contains quantifiers.
The sentence is not a statement because \(x\) and \(z\) are free variables.
The sentence is not a statement because \(y\) is a free variable.
The universal generalization of the sentence is a statement.
2.
Which of the following statements is a law of logic?
\(\forall x (P(x) \vee \neg P(x))\text{.}\)
\(\exists x P(x) \imp \forall x P(x)\text{.}\)
\(\neg\forall x P(x) \imp \exists x P(x)\text{.}\)
\(\forall x \exists y P(x,y) \iff \exists y \forall x P(x,y)\text{.}\)
3.
What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
ExercisesPractice Problems
1.
Let \(P(x)\) be the predicate, “\(17x+1\) is even.”
Is \(P(15)\) true or false?
True
False
Neither (not a statement)
What, if anything, can you conclude about \(\exists x P(x)\) from the truth value of \(P(15)\text{?}\)
\(\exists x P(x)\) must be true.
\(\exists x P(x)\) must be false.
\(\exists x P(x)\) could be true or could be false.
What, if anything, can you conclude about \(\forall x P(x)\) from the truth value of \(P(15)\text{?}\)
\(\forall x P(x)\) must be true.
\(\forall x P(x)\) must be false.
\(\forall x P(x)\) could be true or could be false.
2.
Let \(P(x)\) be the predicate, “\(18x+1\) is even.”
Is \(P(15)\) true or false?
True
False
Neither (not a statement)
What, if anything, can you conclude about \(\exists x P(x)\) from the truth value of \(P(15)\text{?}\)
\(\exists x P(x)\) must be true.
\(\exists x P(x)\) must be false.
\(\exists x P(x)\) could be true or could be false.
What, if anything, can you conclude about \(\forall x P(x)\) from the truth value of \(P(15)\text{?}\)
\(\forall x P(x)\) must be true.
\(\forall x P(x)\) must be false.
\(\forall x P(x)\) could be true or could be false.
3.
Suppose \(P(x,y)\) is some binary predicate defined on a very small domain of discourse: just the integers 1, 2, 3, and 4. For each of the 16 pairs of these numbers, \(P(x,y)\) is either true or false, according to the following table (\(x\) values are rows, \(y\) values are columns).
1
2
3
4
1
T
F
F
F
2
F
T
T
F
3
T
T
T
T
4
F
F
F
F
For example, \(P(1,3)\) is false, as indicated by the F in the first row, third column.
Use the table to decide whether the following statements are true or false.
\(\displaystyle \exists y \forall x P(x,y)\text{.}\)
\(\displaystyle \forall y \exists x P(x,y)\text{.}\)
\(\displaystyle \forall x \exists y P(x,y)\text{.}\)
\(\displaystyle \exists x \forall y P(x,y)\text{.}\)
ExercisesAdditional Exercises
1.
For a given predicate \(P(x)\text{,}\) you might believe that the statements \(\forall x P(x)\) or \(\exists x P(x)\) are either true or false. How would you decide if you were correct in each case? You have four choices: you could give an example of an element \(n\) in the domain for which \(P(n)\) is true or for which \(P(n)\) if false, or you could argue that no matter what \(n\) is, \(P(n)\) is true or is false.
What would you need to do to prove \(\forall x P(x)\) is true?
What would you need to do to prove \(\forall x P(x)\) is false?
What would you need to do to prove \(\exists x P(x)\) is true?
What would you need to do to prove \(\exists x P(x)\) is false?
2.
Translate into symbols. Use \(E(x)\) for “\(x\) is even” and \(O(x)\) for “\(x\) is odd.”
No number is both even and odd.
One more than any even number is an odd number.
There is prime number that is even.
Between any two numbers there is a third number.
There is no number between a number and one more than that number.
3.
Translate into English:
\(\forall x (E(x) \imp E(x +2))\text{.}\)
\(\forall x \exists y (\sin(x) = y)\text{.}\)
\(\forall y \exists x (\sin(x) = y)\text{.}\)
\(\forall x \forall y (x^3 = y^3 \imp x = y)\text{.}\)
4.
Suppose \(P(x)\) is some predicate for which the statement \(\forall x P(x)\) is true. Is it also the case that \(\exists x P(x)\) is true? In other words, is the statement \(\forall x P(x) \imp \exists x P(x)\) always true? Is the converse always true? Assume the domain of discourse is non-empty.
Hint.
Try an example. What if \(P(x)\) was the predicate, “\(x\) is prime”? What if it was “if \(x\) is divisible by 4, then it is even”? Of course examples are not enough to prove something in general, but that is entirely the point of this question.
5.
For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false.
\(\forall x \exists y (y^2 = x)\text{.}\)
\(\forall x \forall y (x \lt y \imp \exists z (x \lt z \lt y))\text{.}\)
\(\exists x \forall y \forall z (y \lt z \imp y \le x \le z)\text{.}\)
Hint.
First figure out what each statement is saying. For part (c), you don’t need to assume the domain is an infinite set.
6.
Simplifying negations will be especially useful when we try to prove a statement by considering what would happen if it were false. For each statement below, write the negation of the statement as simply as possible. Don’t just say, “it is false that …”
Every number is either even or odd.
There is a sequence that is both arithmetic and geometric.
For all numbers \(n\text{,}\) if \(n\) is prime, then \(n+3\) is not prime.
Hint.
It might help to translate the statements into symbols and then use the formulaic rules to simplify negations (i.e., rules for quantifiers and De Morgan’s laws). After simplifying, you should get \(\forall x(\neg E(x) \wedge \neg O(x))\text{,}\) for the first one, for example. Then translate this back into English.
7.
We can simplify statements in predicate logic using our rules for passing negations over quantifiers, and then applying propositional logical equivalence to the “inside” propositional part. Simplify the statements below (so negation appears only directly next to predicates).
\(\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}\)
\(\neg \forall x \neg
\forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}\)
There is a number \(n\) for which no other number is either less \(n\) than or equal to \(n\text{.}\)
It is false that for every number \(n\) there are two other numbers which \(n\) is between.
8.
Simplify the statements below to the point that negation symbols occur only directly next to predicates.
\(\neg \forall x \forall y (x \lt y \vee y \lt x)\text{.}\)
\(\neg(\exists
x P(x) \imp \forall y P(y))\text{.}\)
9.
Consider the statement, “For all natural numbers \(n\text{,}\) if \(n\) is prime, then \(n\) is solitary.” You do not need to know what solitary means for this problem, just that it is a property that some numbers have and others do not.
Write the converse and the contrapositive of the statement, saying which is which. Note: the original statement claims that an implication is true for all \(n\text{,}\) and it is that implication that we are taking the converse and contrapositive of.
Write the negation of the original statement. What would you need to show to prove that the statement is false?
Even though you don’t know whether 10 is solitary (in fact, nobody knows this), is the statement “if 10 is prime, then 10 is solitary” true or false? Explain.
It turns out that 8 is solitary. Does this tell you anything about the truth or falsity of the original statement, its converse or its contrapositive? Explain.
Assuming that the original statement is true, what can you say about the relationship between the set\(P\) of prime numbers and the set\(S\) of solitary numbers. Explain.
