Working with Quantifiers 2
All prime numbers are odd. We know this is false, because we know that two is a prime number and two is not odd. But let’s examine the logic that underlies that conclusion. Because in more complicated situations where we’re not familiar with the domain or with the result, all we’ll have to use is the logic itself. So let p(x) mean x is prime and O(x) mean x is odd. The sentence can be written symbolically as for all x if x is a prime, then x is odd. When we negate this, we get exist x such that not P(x). Or another way of writing it, there is an x such that P(x) and not O(x). In words: there exists a prime number for which it’s true that it’s not odd. The statement is false if the negation is true. The logic says that to prove that this statement is false, which is the same as proving that its negation is true, one must find a prime number that isn’t odd. In this case, two works because it’s not odd.Therefore, the negation is true, and it can be concluded that the original statement is false. Well, in that simple example, it seems like much ado about nothing. But in more complicated situations going through the underlying logic is often the only way forward. By now, you should have noticed the pattern of behavior that is common to these symbolic negations. When we negate a statement with a quantifier, such as “For all…”, the statement becomes an existential statement about some specific object and the quantifier jumps inside. When it does so, we can manipulate it and get the result into a positive form where the negation is at the most innermost point. We can actually turn these rules into formal symbol manipulation procedures that computer systems can follow. We showed that this statement is false by finding a counter example: 2. All prime numbers bigger than 2 are odd. In symbols, for all x bigger than 2 if x is a prime, then x is odd. What is the negation of this statement? Is it 1? There exists an x less than or equal to 2 that’s not odd? Or is it 2? There exists an x greater than 2 which is prime and not odd? Well, the correct answer is 2. It says there exists an x greater than 2 which is prime and not odd. That’s a negation of that statement. “All prime numbers are odd” Let P(x): “x is prime” O(x): x is odd. forall x [P(x) Rightarrow O(x)]. neg forall x [P(x) Rightarrow O(x)] Leftrightarrow exists x [P(x) Rightarrow O(x)] Leftrightarrow exists x [P(x) wedge neg O(x)] Modify it: There a prime that i not odd. “All prime numbers bigger than 2 are odd” (forall x >2) [P(x) Rightarrow O(x)]. Quiz: What is the negation of the statement? 1. (exists x≤2) [P(x) wedge neg O(x)] 2. (exists x>2) [P(x) wedge neg O(x)] Why is it not number one? Because the original statement is about numbers that are bigger than 2, so the negation must be about numbers that are bigger than 2. We do not simply negate each symbol inside and say, well, in terms of the ordering on the real line, if we negate something being bigger than 2 then it means it’s less than or equal to 2. That would be a symbolic negation. That would just be sort of a detailed localized negation about the ordering on the real line. But the sentence as a whole means something about all numbers that are bigger than 2. So its negation means something about all numbers that are bigger than 2. Let x stand for a person and let T be the sports team that x plays for. For any given x, let P(x) mean that x plays on T and H(x) means that x is healthy. Now look at the statement that an unhealthy player plays for team T. What does this mean in everyday English? There is an unhealthy player on the team. Now let’s negate this.nWe can create a negation by using symbolic manipulation, a technique known as line logic. By reversing the order of quantifiers, we know that when we negate an existentially quantified statement, it turns into a universal statement. Then we move the negation inside the if-then statement. Then we do not get P(x) or H(x). When we negate a conjunction, we get a disjunction. And when we double negate something, we get the original thing back. For example, p conditional q means the same as not p or q. They have the same truth table, so this can be written as P(x). In English, all players on team T are healthy means that there is not an unhealthy player on team T. Well if it is not the case that there is an unhealthy player on team T, then all players on team T must be healthy. When x is greater than 0 and y is equal to 1, then xy = 1. However, if x does not equal 0, then xy may or may not equal 1. Let x denote a person P(x): “x plays for sports team T” H(x): “x is healhty” exists x [P(x) wedge neg H(x)] “There is an unhealthy plays on tean T” Negative: forall x neg [P(x) wedge neg H(x)] p Rightarrow q forall x [neg P(x) lor H(x)] neg p lor q forall x [P(x) Rightarrow H(x)] “All players on team T are healthy” The value of a quantifier depends on what the variable denotes. If x denotes a motorist or an automobile or a healthy team player, the quantifier is nonsensical. If x denotes a natural number, it makes sense but it’s false. If x denotes a rational number, it makes sense and it’s true. However, we can make statements like this only if we know what kind of object x represents. We can state that an object is healthy only if we define what “healthy” means in this context. We just saw that forall x [A(x) lor B(x)] is not equivalent to forallxA(x) lor forallxB(x). Is forall x[A(x) wedge B(x)] equivalent to forall x A(x) wedge forall x B(x)? YES!! All athletes are big All athletes are big and strong All athletes are strong We just saw that exists x [A(x) wedge B(x)] is not equivalent to existsxA(x) wedge existsxB(x). Is exists x[A(x) lor B(x)] equivalent to exists x A(x) lor exists x B(x)? YES!! There is a good attacker There is a good defender There is a player who is a good attacker or a good defender forall is “like” wedge exists is “like” lor In order to make it more explicit: For all x in the set of rational numbers, if x is positive and there exists a y such that xy = 1, then x is greater than 0. And now we’ve got a true statement, it tells us that for every positive rational number x such that x ≥ 0, then there exists a positive rational number y such that xy = 1. But if we want to, we could be even more explicit and say for all x in Q, if x is greater than 0 then there is a y in Q. The statement xy = 1 is ambiguous when the quantifiers are not explicitly defined. Most mathematicians would agree that if you are explicit about the quantifier at the beginning of a statement, then all other quantifiers with the same scope should denote the same thing. Because there is some potential for misunderstanding or ambiguity, it’s better to be explicit everywhere as to what each quantifier denotes. forall x [x >0 Rightarrow exists y (xy =1)] Domain of quantification. (What does the x denote) To make this more explicit, i could write it as: (forall x in Q) [x >O Rightarrow exists y (xy=1)] (forall x in Q) [x >O Rightarrow (exists y in Q) (xy=1)] Mathematicians sometimes omit the quantifier x>0 Rightarrow x>0 What that means is: (something like) (forall x in R) [x>0 Rightarrow x>0] Let N be the domain of quantification Let E(x): x is even, O(x): x is odd forall x [E (x) lor O(x)] True forall x [E (x) lor forall x O(x)] False exists x [E(x) wedge O(x)] False exists x [E(x) wedge exists x O(x)] True When dealing with expressions involving quantifiers, it is important to be aware that mathematicians sometimes omit the quantifier. We write things like if x is greater than or equal to 0 then the square root of x is greater than or equal to 0. If you see an expression like this What that means is the following. For all x in R , perhaps x denotes a real number or perhaps x denominates something else . For all x in R , x greater than or equal to 0 applies to the square root of x is greater than 0 or something like that, depending on what the x denotes. There is no explicit mention of the quantifier here, but it can be understood that there is a universal quantifier in play. This is what’s known as implicit quantification. The mathematician is leaving out any explicit mention of the quantifier. It’s left implicit in the way this is written. Let N be the set of natural numbers and let E(x) mean x is even and O(x) mean x is odd. Consider the following formulas: for all x E(x) or O(x) and for all x E(x) or for all x of O(x). The first formula is true, since every natural number is either even or odd. The second one is not true, however, since there are numbers that are both even and odd. Note that if you put a “for all” statement inside brackets, you will turn a true statement into a false one or vice versa. Similarly, if you include an “exists” statement inside brackets, you may change a false statement into a true one or vice versa. When we’re taking a disjunction, we have to be very careful how we put the quantifiers together. For instance, let’s suppose we have an expression that says “x is even or x is odd”, so you have this statement: x is even and x is odd. That statement is false because it’s impossible for the same number to be both even and odd. But if you put another quantifier next to this one, it becomes true. In other words, “there exists an x such that x is both even and odd”. But if you attempt to use these symbols as expressions to manipulate, then things can go awry. We have just seen that this expression—that something is true for all values of x, such as A(x) or B(x)—is not equivalent to saying that something is true for every x. The example we looked at was where the numbers are even or odd. In this case, it would be true that for all natural numbers, the numbers are either even or odd. However, both disjuncts in this case are false; therefore, the disjunction itself is false. Instead of disjunction, we have conjunction. Are these equivalent? Well, the answer is yes. They are equivalent. Or you could argue this in an abstract form, but let’s just look at an example that’s pretty illustrative. Let’s take something like, All athletes are big and strong. Let x = athletes. A = big, B = strong. So this says all athletes are big and strong. This would say that all athletes are big. And then we would have the sentence that says all athletes are strong. It is clear from the example that if all athletes are both big and strong, then in particular they’re all big and they’re all strong. If all members of a group are tall, then they’re all tall. In other words, when universal quantification is combined with a conjunction, then you get the equivalent of these two forms. But if universal quantification is combined with a disjunction, they’re not necessarily equivalent. This isn’t a proof; it’s just an example. But if you take that example, you should be able to come up with a simple little logical argument showing that this implies that and conversely that implies that: so the answer is yes in this case. Let us look at another variant. In this case, when we had even and odd numbers, that showed that these are not necessarily equivalent. But what about this, where we have an existential quantifier combined not with a conjunction but with a disjunction? Do we have equivalency in this case? What do you think? Again, the answer is yes. These are in fact equivalent. What would be a good example? Well let’s take something like: there is a player who is a good attacker or there is a player who is a good defender. If a player is a good attacker or a good defender, then he or she must be one or the other. If the statement is true, then one of these two statements must also be true. And conversely, if a player is only a good attacker or only a good defender and nothing else, then that player is only a good attacker or only a good defender in fact. So, in the case of existential quantification, if we use it with a conjunction, then we don’t get equivalence; but if we use it with a disjunction, then we do get equivalence. The difference is that for all is like conjunction, and existence is like disjunction. For all means something’s true for all cases; and conjunction means that all of the conjuncts have to be true. Quantifiers are used in mathematical and philosophical discussions to determine the parameters of a statement. So, if we have x, y, and z as variables, they represent real numbers. The domain of quantification is the set of real numbers. In a discussion about real numbers, we may want to talk about rational numbers. A particular rational number may be mentioned as x. When discussing real numbers, it is possible to specify the domain of quantification explicitly. One can talk about a specific rational number, or all natural numbers, or all real numbers. However, introducing multiple domains of quantification in other contexts does not make sense and will limit the validity of an argument. Real number x,y,x Rational number x. [exists x in Q] (forall y in Q) (forall in N) “Every leopard has sports” (forall x in L) S(x) forall x [L(x) Rightarrow S(x)] exists x [H(x) wedge S(x)] forall x [T(x) Rightarrow neg S(x)] For example, suppose the domain of quantification is the set of animals. And then we might want to say something like, every leopard has spots. Well, how would we do that? Well, we could say: for all x in the set of leopards, x have spots. But in the next sentence, we might want to talk about tigers and then giraffes or whatever. And very soon, we could have a whole range of different domains of quantification floating around. That’s not very clean; it’s not very nice; and it certainly isn’t sensible because the discussion isn’t really about leopards or tigers or giraffes or whatever: It’s about animals. If the discussion is about animals, then the domain of quantification should be restricted to creatures that are members of the set of animals. Thus, instead of writing something like: “If an animal is a leopard then it has spots.” We should write: “For every x (where x is an animal), if x is a leopard then x has spots.” we can then say things like: “There exists an x such that x is a horse and has spots. So there’s a spotted horse.” Or we could say: “For all x, if x is a tiger then it doesn’t have spots. The point is that I’m talking about animals. When we refer to specific animals, we are not changing the domain of quantification. In this kind of situation, you could use something analogous to this expression. However, in general if you’re talking about real numbers and natural numbers, you really don’t want to introduce subdomains. You should use the analog of these expressions, and discuss if it’s a rational number or a natural number. You may have different domains of quantification. This is not an issue of right or wrong; it is an issue of whether it makes sense to work in a certain way. And using separate subdomains of quantification is fine if they are natural domains and make sense to talk about that way. But the idea of a domain of quantification tells us what we’re talking about; this is why it’s important not to introduce different domains that are not animals when discussing animals. Even if they’re subdomains, it gets complicated. Okay, that’s enough about quantifiers for now; go away and see how you get along with assignment number six.
