1.3 More scary notation
It is often the case that we want to prove statements that assert something is true for every element of a set. For example, “Every number has an additive inverse.” You should note that the truth of that statement is relative because it depends on what is meant by “number.” If we are talking about natural numbers, it is clearly false: 3’s additive inverse isn’t in the set under consideration. If we are talking about integers or any of the other sets we’ve considered, the statement is true.
A statement that begins with the English words “every” or “all” is called universally quantified. It is asserted that the statement holds for everything within some universe. It is probably clear that when we are making statements asserting that a thing has an additive inverse, we are not discussing human beings or animals or articles of clothing — we are talking about objects that it is reasonable to add together: numbers of one sort or another.
When being careful — and we should always strive to be careful! — it is important to make explicit what universe (known as the universe of discourse) the objects we are discussing come from. Furthermore, we need to distinguish between statements that assert that everything in the universe of discourse has some property, and statements that say something about a few (or even just one) of the elements of our universe. Statements of the latter sort are called existentially quantified.
Adding to the glossary or translation lexicon we started earlier, there are symbols which describe both these types of quantification. The symbol \(\forall\), an upside-down A, is used for universal quantification, and is usually translated as “for all.” The symbol \(\exists\), a backwards E, is used for existential quantification, it’s translated as “there is” or “there exists.” Lets have a look at a mathematically precise sentence that captures the meaning of the one with which we started this section. \[\forall x \in {\mathbb Z}, \; \exists y \in {\mathbb Z}, \; x+y=0.\]
Parsing this as we have done before with an English translation in parallel, we get:
| \(\forall x\) | \(\in {\mathbb Z}\) | \(\exists y\) |
| For every number \(x\) | in the set of integers | there is a number \(y\) |
| \(\in {\mathbb Z}\) | \(x+y=0\) |
| in the integers | having the property that their sum is \(0\). |
Exercise 1.1 Which type of quantification do the following statements have?
- Every dog has his day.
- Some days it’s just not worth getting out of bed.
- There’s a party in somebody’s dorm this Saturday.
- There’s someone for everyone.
A couple of the examples in the exercise above actually have two quantifiers in them. When there are two or more (different) quantifiers in a sentence, you have to be careful about keeping their order straight. The following two sentences contain all the same elements except that the words that indicate quantification have been switched. Do they have the same meaning?
For every student in James Woods High School, there is some item of cafeteria food that they like to eat.
There is some item of cafeteria food that every student in James Woods High School likes to eat.
1.3.1 Exercises
How many quantifiers (and what sorts) are in the following sentence?
“Everybody has some friend that thinks they know everything about a sport.”
The sentence “Every metallic element is a solid at room temperature.” is false. Why?
The sentence “For every pair of (distinct) real numbers there is another real number between them.” is true. Why?
Write your own sentences containing four quantifiers. One sentence in which the quantifiers appear \(\forall \exists \forall \exists\) and another in which they appear \(\exists \forall \exists \forall\).