🗊Презентация Quantifiers

Quantifiers

To formulate more complex mathematical statements, we use the quantifiers there exists, To formulate more complex mathematical statements, we use the quantifiers there exists, written , and for all, written . If P(x) is a predicate, then • x : P(x) means, “There exists an x such that P(x) holds.” • x : P(x) means, “For all x, it is the case that P(x) holds.” So for example, if x denotes a real number, then • x : x = 4 is true, since 2 is an x for which = 4. On the other hand, x : = 4 is clearly false; not all numbers, when squared, are equal to 4. • x : +1 > 0 is true, but x : > 2 is false, since for example x = 1 doesn’t satisfy the predicate. On the other hand, x : > 2 is true, since x = 2 is an example that satisfies it.

Whenever we see a variable in a quantified expression, there’s an underlying assumption that the variable comes from some base set. So to go back to x : + 1 > 0, this is true because we specified that x was a real number. But it would be false if we specified that x was drawn from the complex numbers, since then x = i would not satisfy the predicate. Whenever we see a variable in a quantified expression, there’s an underlying assumption that the variable comes from some base set. So to go back to x : + 1 > 0, this is true because we specified that x was a real number. But it would be false if we specified that x was drawn from the complex numbers, since then x = i would not satisfy the predicate. Often we’ll keep the underlying set implicit, but it is important to be careful about this.

Negating quantified statements. Earlier we said that x : > 2 is false, because we were able to think of an x (x = 1) that fails to satisfy the predicate. This suggests how to negate a statement: we flip to , and then negate the predicate inside. That is, • the negation of x : P(x) is x : P(x). This, incidentally, is where the term “counterexample” comes from. If x : P(x) is false, then x : P(x) — and the x that exists to satisfy P(x) is the counterexample to the claim x : P(x). On the other hand, to negate x : P(x), we must claim that P(x) fails to hold for any possible x. So again we flip the quantifier and then negate the predicate: • the negation of x : P(x) is x : P(x).

Quantifiers in standard English usage. If we think about it, this is all familiar from standard English usage. For example, if someone says, “Everyone at Cornell is at least 18 years old,” you might reply, “No, I know someone at Cornell who’s under 18.” What are you doing when you say this? • At least subconsciously, you’re interpreting this statement as “ x at Cornell, x is at least 18 years old.” • To disagree with this, you’re negating the statement by flipping the and then negating the predicate: “ x at Cornell such that x is not at least 18 years old.” • Note also that we’re careful about the set over which x is being quantified: the set is all people at Cornell. The same thing happens in the reverse direction, from : if someone says, “There’s an NBA player who makes over ten million dollars a year,” you might disagree by saying, “No, every NBA player makes under ten million dollars a year.”

Nested Quantifiers Most serious mathematical statements use nested quantifiers. For example, • Suppose we claimed, “For every real number, there’s a real number larger than it.” We’d write this as x y : y > x. • Or if we wanted to claim, “There exists a Boolean formula such that every truth assignment to its variables satisfies it,” we could write this as formula F assignments A : A satisfies F. The difference between a statement that says x y and a statement that says x y is something to watch out for. For example, if we’re talking about real numbers, then our earlier example x y : y > x is true. But writing it with the quantifiers in the other order, it would become false: y x : y > x. This version would require there to be a single number that’s greater than every number.

Negating Nested Quantifiers To negate a sequence of nested quantifiers, you flip each quantifier in the sequence and then negate the predicate. So the negation of x y : P(x, y) is x y : P(x, y) and So the negation of x y : P(x, y) andx y : P(x, y). Again, after some thought, this make sense intuitively. For example, let’s take the definition of an unbounded sequence from calculus. If we have an infinite sequence of real numbers a1 a2 a3 · · ·, then we say it’s unbounded if for every number x, it eventually grows larger than x. You can already see the quantifiers lurking in here: x n : > x. Now, some sequences, like 1, 4, 9, 16, 25, 36, . . ., are unbounded, and some, like are not. What does it mean for a sequence not to be unbounded: there is an upper bound x such that every number in the sequence is at most x. In fact, we could have derived this mechanically by negating the definition of unboundedness. If “unbounded” means x n : an > x, then “not unbounded” must mean (flipping quantifiers) x n : > x . Notice that this is what just said, but here we worked it out without even thinking about what the symbols mean.

Nested Quantifiers in Standard English Usage People manipulate sequences of two nested quantifiers in conversation all the time. For example, if someone says, “Everyone experiences moments of doubt,” you might reply, “No, I know someone who seems never to have experienced any moments of doubt in their whole life.” What are you doing here? • You’re interpreting the statement as “ people p time t : p experiences doubt at time t.” • To disagree with this, you’re negating the statement by flipping each quantifier and then negating the predicate: “ person p times t : p did not experience doubt at time t.” (It appears that you added “in their whole life” just for effect ... )

More than two nested quantifiers There’s no problem writing longer sequences of nested quantifiers, but it’s a general rule of thumb that people really have to work, cognitively, to handle more than two. This is why most of us have such a hard time digesting the definition of a limit when we first learn it in calculus: f(x) = b means : (0 < |x − a| < δ) |f(x) − b| < . Given their complexity, it’s interesting to ask how often sentences with three nested quantifiers come up in standard conversation. There are certainly examples. Here’s one that requires a very mild knowledge of baseball, in which all three quantifiers are hidden.

Quantifiers and Proofs As we discussed earlier, our main interest in quantifiers for the purposes of this course is to manipulate mathematical statements in a careful way. When faced with a mathematical claim, understanding its quantifier is often a very good strategy for thinking about how to work out a proof. For example: • If the statement has the form x : P(x), then the global outline is likely have the form: Consider any possible x, and show that it satisfies the property P(x). • If the statement has the form : P(x), then the global outline is different: One needs to specify a particular x, and then show it satisfies P(x). It’s particularly useful to watch for the role that plays in proofs. When you come to a , it generally means: At this point, you have to describe an x that does what you want.

Quantifiers and Proofs by Contradiction Of course, one can try looking for alternate strategies, and proof by contradiction is one useful example of this. If you’re trying to prove x :P(x), and you don’t see how to describe the x you need, you can try supposing it’s false and looking for a contradiction. Supposing it’s false, concretely, means assuming x : P(x). You’re now in a situation where you can assume that P(x) holds for all x, and start looking for a contradiction. Analogously, if you don’t see how to get started proving a statement like x : P(x), you can similarly negate it and start searching for a contradiction. This means you can start by assuming x : P(x), which lets you assume the existence of a counterexample x for which P(x) holds.