So far we have seen how statements can be combined with logical symbols. This is helpful when trying to understand a complicated mathematical statement since you can determine under which conditions the complicated statement is true. Additionally, we have been able to analyze the logical form of arguments to decide which arguments are valid and which are not. However, the types of statements we have been able to make so far has be sorely limited. For example, consider a classic argument:
All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
This is clearly a valid argument. It is an example of a syllogism. Historically, the study of logic began with Aristotle who worked out all possible forms of syllogisms and decided which were valid and which were not. We will not do that here. However, this is an important example because it highlights a limitation of the propositional logic we have studied so far. Can we use propositional logic to analyze the argument?
The trouble is that we don't have a way to translate “all men are mortal.” It looks like an implication: being a man implies you are mortal. So maybe it is \(P \imp Q\). But what is \(P\)? We could rephrase: “if Socrates is a man, then Socrates is mortal.” Now we have a valid argument form we have seen before. But it is not quite the same. (Suppose the argument was: all men are mortal, all mortals have hair, therefore all men have hair. This is also valid and Socrates has nothing to do with it.) Or perhaps we could go with, “for every thing there is, if the thing is a man, then the thing is mortal.” Looks promising, but we still can't let \(P\) be “the thing is a man” because that is not a statement (“thing” is a variable).
One way to sort this mess out is to introduce a new sort of logic called predicate logic. This is the logic of properties. Doing so will allow us to discuss how properties of various things are related. Above, if a thing has the property of being a man, then it has the property of being mortal. We can then quantify over what things we talk about. In the example above, all things.
Another way to accomplish much of the same goal is to use set theory. We can talk about collections of things, for example the collection of all men and the collection of all mortal things. We can then express “all men are mortal” by saying that the set of men is a subset of the set of mortals. Then we claim that Socrates is a member of the set of men, so therefore is also a member of the set of mortals.
One last example to highlight these two different approaches before delving into details. We all agree that all squares are rectangles. The set theory approach would be to consider the set of squares and the set of rectangles, and point out that one is a subset of the other (the squares are a subset of the rectangles). The predicate logic approach would be to consider the properties of “being a square” and of “being a rectangle” and assign these to predicates, say \(S\) and \(R\). We would then say \(\forall x (S(x) \imp R(x))\): for all things, if the thing is a square, then it is a rectangle. So having the property of being a square implies having the property of being a rectangle.
We can think of predicates as properties of objects. For example, consider the predicate \(E\) which we will use to mean “is even.” Being even is a property of some numbers, so \(E\) needs to be applied to something. We will adopt the notation \(E(x)\) to mean \(x\) is even. (Some books would write \(Ex\) instead.) Notice that if we put a number in for \(x\), then this becomes a statement, and as such, can be true or false. So \(E(2)\) is true, and \(E(3)\) is false. A predicate is like a function with codomain equal to the set of truth values \(\{T, F\}\). On the other hand, \(E(x)\) is not true or false, since we don't know what \(x\) is. If we have a variable floating around like that, we say the expression is merely a formula, and not a statement.
Since \(E(2)\) is a statement (a proposition), we can apply propositional logic to it. Consider
\begin{equation*}
E(2) \wedge \neg E(3)
\end{equation*}
which is a true statement, because it is both the case that 2 is even and that 3 is not even. What we have done here is capture the logical form (using connectives) of the statement “2 is even and 3 is not” as well as the mathematical content (using predicates).
Notice that we can only assert even-ness of a single number at a time. That is to say, \(E\) is a one-place predicate. There are also predicates which assert a property of two or more numbers (or other objects) at the same time. Consider the two-place predicate “is less than.” Perhaps we will use the variable \(L\). Now we can say \(L(2,3)\), which is true because 2 is less than 3. Of course we are already have a symbol for this: \(2 \lt 3\). However, what about “divides evenly into” as a predicate? We can say \(D(2,10)\) is true because 2 divides evenly into 10, while \(D(3, 10)\) is false since there is a remainder when you divide 10 by 3. Incidentally, there is a standard mathematical symbol for this: \(2 | 10\) is read “2 divides 10.”
Predicates can be as complicated and have as many places as we want or need. For example, we could let \(R(x,y,z,u,v,w)\) be the predicate asserting that \(x\), \(y\), \(z\) are distinct natural numbers whose only common factor is \(u\), the difference between \(x\) and \(y\) is \(v\) and the difference between \(y\) and \(z\) is \(w\). This is a silly and most likely useless example, but it is an example of a predicate. It is true of some ordered lists of six numbers (6-tuples), and false of others. Additionally, predicates need not have anything to do with numbers: we could let \(F(a,b,c,d)\) be the predicate that asserts that \(a\) and \(b\) are the only two children of mother \(c\) and father \(d\).
Perhaps the most important reason to use predicate logic is that doing so allows for quantification. We can now express statements like “every natural number is either even or odd,” and “there is a natural number such that no number is less than it.” Think back to Calculus and the Mean Value Theorem. It states that for every function \(f\) and every interval \((a, b)\), if \(f\) is continuous on the interval \([a,b]\) and differentiable on the interval \((a,b)\), then there exists a number \(c\) such that \(a \le c \le b\) and \(f'(c)(b - a) = f(b) - f(a)\). Using the correct predicates and quantifiers, we could express this statement entirely in symbols.
There are two quantifiers we will be interested in: existential and universal.
Quantifiers
Are the statements \(\exists x (x \lt 0)\) and \(\forall x (x \ge 0)\) true? Well, first notice that they cannot both be true. In fact, they assert exactly the opposite of each other. (Note that \(x \lt y \iff \neg(x \ge y)\), although you might wonder what \(x\) and \(y\) are here, so it might be better to say \(\forall x \forall y\left(x \lt y \iff \neg(x \ge y)\right)\).) Which one is it though? The answer depends entirely on our domain of discourse, the universe over which we quantify. Usually, this universe is clear from the context. If we are only discussing the natural numbers, then \(\forall x \ldots\) means “for every natural number \(x \ldots\).” On the other hand, in calculus we care about the real numbers, so it would mean “for every real number \(x \ldots\).” If the context is not clear, we might write \(\forall x \in \N\ldots\) to mean “for every natural number \(x\)….” Of course, for the two statements above,
the second is true of the natural numbers, the first is true for any universe which includes negative numbers, such as the integers.
Some more examples: To say “every natural number is either even or odd,” we would write, using \(E\) and \(O\) as the predicates for even and odd respectively:
\begin{equation*}
\forall x (E(x) \vee O(x)).
\end{equation*}
To say “there is a number such that no number is less than it” we would write:
\begin{equation*}
\exists x \forall y (y \ge x).
\end{equation*}
Actually, I did a little translation before I wrote that down. The above statement would be literally read “there is a number such that every number is greater than or equal to it.” This of course amounts to the same thing. However, if I wanted to have a literal translation, I could have also written:
\begin{equation*}
\exists x \neg \exists y (y \lt x).
\end{equation*}
Notice also that saying that there is a number for which no number is smaller is equivalent to saying that it is not the case that for every number there is a number smaller than it:
\begin{equation*}
\neg \forall x \exists y (y \lt x).
\end{equation*}
That these three statements are equivalent is no coincidence. To understand what is going on, we will need to better understand how quantification interacts with the logical connectives, specifically negation.
What does it mean to say that it is false that there is something that has a certain property? Well, it means that everything does not have that property. What does it mean for it to be false that everything has a certain property? It means that there is something that doesn't have the property. So in symbols, we have the following:
Quantifiers and Negation
In other words, to move a negation symbol past a quantifier, you must switch the quantifier. This can be done multiple times:
\begin{equation*}
\neg \exists x \forall y \exists z P(x,y,z) \mbox{ is equivalent to } \forall x \exists y \forall z \neg P(x,y,z).
\end{equation*}
We also know how to move negation symbols through other connectives (using De Morgan's Laws) so it is always possible to rewrite a statement so that the only negation symbols that appear are right in front of a predicate. This hints at the possibility of having a standard form for all predicate statements. To get this, however, we must also understand how to move quantifiers through connectives.
Before we get too excited, note that we only need to worry about two connectives: \(\wedge\) and \(\vee\). This is because we can rewrite \(p \imp q\) as \(\neg p \vee q\) (they are logically equivalent) and \(p \iff q\) as \((p \wedge q) \vee (\neg p \wedge \neg q)\) (also logically equivalent).
Consider an example to see what can happen:
Example3.3.1
Let \(E\) be the predicate for being even, and \(O\) for being odd. Consider:
\begin{equation*}
\exists x E(x) \wedge \exists x O(x),
\end{equation*}
which says that there is a number which is even and a number which is odd. This is of course true. However there is no number which is both even and odd, so
\begin{equation*}
\exists x (E(x) \wedge O(x))
\end{equation*}
is false. Note also that
\begin{equation*}
\exists x (E(x) \vee O(x)),
\end{equation*}
while true, is not really the same thing – if \(O\) is instead the predicate for “is less than 0” then the original statement is false, but this new one is true (of the natural numbers). Changing the quantifier also doesn't help:
\begin{equation*}
\forall x (E(x) \wedge O(x))
\end{equation*}
is false. So what can we do?
The problem is that in the original sentence, the variable \(x\) is doing double duty. We want to express the fact that there is an even number and an odd number. But that even number is in no way related to that odd number. So we might as well have said
\begin{equation*}
\exists x E(x) \wedge \exists y O(y).
\end{equation*}
Now we can move the quantifiers out:
\begin{equation*}
\exists x \exists y (E(x) \wedge O(y)).
\end{equation*}
The same thing works with \(\vee\) and for \(\forall\) with either connective. As long as there is no repeat in quantified variables we can move the quantifiers outside of conjunctions and disjunctions.
A warning though: you cannot do this for \(\imp\), at least not directly.
Let's see what happens.
Example3.3.2
Consider
\begin{equation*}
\forall x P(x) \imp \exists y Q(y)
\end{equation*}
for some predicates \(P\) and \(Q\). This sentence is not the same as
\begin{equation*}
\forall x \exists y (P(x) \imp Q(y)).
\end{equation*}
Remember that \(P \imp Q\) is the same as \(\neg P \vee Q\). So the original sentence is really
\begin{equation*}
\neg \forall x P(x) \vee \exists y Q(y).
\end{equation*}
Before we move the quantifiers out, we must move the \(\forall x\) past the negation sign, which switches it to a \(\exists x\):
\begin{equation*}
\exists x \neg P(x) \vee \exists y Q(y).
\end{equation*}
Then we can finish by writing,
\begin{equation*}
\exists x \exists y (\neg P(x) \vee Q(y))
\end{equation*}
or equivalently
\begin{equation*}
\exists x \exists y (P(x) \imp Q(y)).
\end{equation*}
1
Simplify the statements (so negation appears only directly next to predicates).
- \(\neg \exists x \forall y (\neg O(x) \vee E(y))\).
- \(\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\).
There is a number \(n\) for which no other number is either less \(n\) than or equal to \(n\).
It is false that for every number \(n\) there are two other numbers which \(n\) is between.
2
Can you switch the order of quantifiers? For example, consider the two statements:
\begin{equation*}
\forall x \exists y P(x,y) \qquad \mathrm{ and } \qquad \exists y \forall x P(x,y).
\end{equation*}
Depending on what the predicate \(P(x,y)\) is, each statement might be true or false. Give an example of a predicate for which the first statement is true and the second false of the natural numbers. Can you also give an example of a (different) predicate for which the first statement is false and the second true? Explain.
