Working with Quantifiers 2

Working with Quantifiers 2 All prime numbers are odd. We know this is false, because we know that two is aprime number and two is not odd. But let's examine the logic that underlies thatconclusion. Because in more complicated situations where we're not familiar with thedomain 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 writtensymbolically as for all x if x is a prime, then x is odd. When we negate this, we getexist 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 notodd. The statement is false if the negation is true. The logic says that to prove thatthis statement is false, which is the same as proving that its negation is true, onemust 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 isfalse. Well, in that simple example, it seems like much ado about nothing. But inmore complicated situations going through the underlying logic is often the only wayforward. By now, you should have noticed the pattern of behavior that is common to thesesymbolic negations. When we negate a statement with a quantifier, such as "Forall...", the statement becomes an existential statement about some specific objectand the quantifier jumps inside. When it does so, we can manipulate it and get theresult into a positive form where the negation is at the most innermost point. We canactually turn these rules into formal symbol manipulation procedures that computersystems can follow. We showed that this statement is false by finding a counter example: 2. All primenumbers bigger than 2 are odd. In symbols, for all x bigger than 2 if x is a prime, thenx is odd. What is the negation of this statement? Is it 1? There exists an x less thanor equal to 2 that's not odd? Or is it 2? There exists an x greater than 2 which isprime and not odd? Well, the correct answer is 2. It says there exists an x greaterthan 2 which is prime and not odd. That's a negation of that statement.

Why is it not number one? Because the original statement is about numbers that arebigger than 2, so the negation must be about numbers that are bigger than 2. We donot simply negate each symbol inside and say, well, in terms of the ordering on thereal line, if we negate something being bigger than 2 then it means it's less than orequal to 2. That would be a symbolic negation. That would just be sort of a detailedlocalized negation about the ordering on the real line. But the sentence as a wholemeans something about all numbers that are bigger than 2. So its negation meanssomething 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 givenx, let P(x) mean that x plays on T and H(x) means that x is healthy. Now look at thestatement that an unhealthy player plays for team T. What does this mean ineveryday English? There is an unhealthy player on the team. Now let's negate this.We can create a negation by using symbolic manipulation, a technique known as linelogic. By reversing the order of quantifiers, we know that when we negate anexistentially quantified statement, it turns into a universal statement. Then we movethe negation inside the if-then statement. Then we do not get P(x) or H(x). When wenegate 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 por q. They have the same truth table, so this can be written as P(x). In English, allplayers on team T are healthy means that there is not an unhealthy player on teamT. Well if it is not the case that there is an unhealthy player on team T, then allplayers 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.

The value of a quantifier depends on what the variable denotes. If x denotes amotorist or an automobile or a healthy team player, the quantifier is nonsensical. If xdenotes a natural number, it makes sense but it's false. If x denotes a rationalnumber, it makes sense and it's true. However, we can make statements like thisonly if we know what kind of object x represents. We can state that an object ishealthy only if we define what "healthy" means in this context. In order to make it more explicit: For all x in the set of rational numbers, if x ispositive and there exists a y such that xy = 1, then x is greater than 0. And nowwe've got a true statement, it tells us that for every positive rational number x suchthat x ≥ 0, then there exists a positive rational number y such that xy = 1. But if wewant to, we could be even more explicit and say for all x in Q, if x is greater than 0then there is a y in Q. The statement xy = 1 is ambiguous when the quantifiers arenot explicitly defined. Most mathematicians would agree that if you are explicit aboutthe quantifier at the beginning of a statement, then all other quantifiers with the samescope should denote the same thing. Because there is some potential formisunderstanding or ambiguity, it's better to be explicit everywhere as to what eachquantifier denotes.

When dealing with expressions involving quantifiers, it is important to be aware thatmathematicians sometimes omit the quantifier. We write things like if x is greaterthan or equal to 0 then the square root of x is greater than or equal to 0. If you seean expression like this What that means is the following. For all x in R , perhaps xdenotes a real number or perhaps x denominates something else . For all x in R , xgreater than or equal to 0 applies to the square root of x is greater than 0 orsomething like that, depending on what the x denotes. There is no explicit mention of the quantifier here, but it can be understood that thereis a universal quantifier in play. This is what's known as implicit quantification. Themathematician is leaving out any explicit mention of the quantifier. It's left implicit inthe 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 isodd. Consider the following formulas: for all x E(x) or O(x) and for all x E(x) or for allx 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 evenand odd. Note that if you put a "for all" statement inside brackets, you will turn a truestatement 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 viceversa. When we're taking a disjunction, we have to be very careful how we put thequantifiers 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. Thatstatement is false because it's impossible for the same number to be both even andodd. But if you put another quantifier next to this one, it becomes true. In otherwords, "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 thingscan go awry. We have just seen that this expression—that something is true for allvalues of x, such as A(x) or B(x)—is not equivalent to saying that something is truefor every x. The example we looked at was where the numbers are even or odd. Inthis case, it would be true that for all natural numbers, the numbers are either evenor odd. However, both disjuncts in this case are false; therefore, the disjunction itselfis false. Instead of disjunction, we have conjunction. Are these equivalent? Well, the answeris yes. They are equivalent. Or you could argue this in an abstract form, but let's justlook at an example that's pretty illustrative. Let's take something like, All athletes arebig and strong. Let x = athletes. A = big, B = strong. So this says all athletes are bigand strong. This would say that all athletes are big. And then we would have thesentence that says all athletes are strong. It is clear from the example that if allathletes are both big and strong, then in particular they're all big and they're allstrong. If all members of a group are tall, then they're all tall. In other words, whenuniversal quantification is combined with a conjunction, then you get the equivalentof 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 youtake that example, you should be able to come up with a simple little logicalargument showing that this implies that and conversely that implies that: so theanswer 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 wehave 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 takesomething like: there is a player who is a good attacker or there is a player who is agood defender. If a player is a good attacker or a good defender, then he or she mustbe one or the other. If the statement is true, then one of these two statements mustalso be true. And conversely, if a player is only a good attacker or only a gooddefender and nothing else, then that player is only a good attacker or only a gooddefender in fact. So, in the case of existential quantification, if we use it with a conjunction, then wedon'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 theconjuncts have to be true. Quantifiers are used in mathematical and philosophical discussions to determine theparameters of a statement. So, if we have x, y, and z as variables, they representreal numbers. The domain of quantification is the set of real numbers. In adiscussion about real numbers, we may want to talk about rational numbers. Aparticular rational number may be mentioned as x. When discussing real numbers, it is possible to specify the domain of quantificationexplicitly. One can talk about a specific rational number, or all natural numbers, or allreal numbers. However, introducing multiple domains of quantification in othercontexts does not make sense and will limit the validity of an argument. For example, suppose the domain of quantification is the set of animals. And thenwe might want to say something like, every leopard has spots. Well, how would wedo that? Well, we could say: for all x in the set of leopards, x have spots. But in thenext sentence, we might want to talk about tigers and then giraffes or whatever. Andvery soon, we could have a whole range of different domains of quantificationfloating around. That's not very clean; it's not very nice; and it certainly isn't sensiblebecause 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 berestricted to creatures that are members of the set of animals. Thus, instead ofwriting 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 thensay things like: "There exists an x such that x is a horse and has spots. So there's aspotted 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 arenot 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 theseexpressions, 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 orwrong; it is an issue of whether it makes sense to work in a certain way. And usingseparate subdomains of quantification is fine if they are natural domains and makesense to talk about that way. But the idea of a domain of quantification tells us whatwe're talking about; this is why it's important not to introduce different domains thatare not animals when discussing animals. Even if they're subdomains, it getscomplicated. Okay, that's enough about quantifiers for now; go away and see howyou get along with assignment number six.