QuantifiersDate: 03/25/2003 at 20:45:35 From: Dan Gibson Subject: Quantifiers I am having a hard time understanding quantifiers. A lot of the time I can understand the simpler problems, but the complicated ones really throw me for a loop. Often if I think a proposition is true, it's actually false, and vice versa. I am currently working on four problems and I can't get anywhere with them. The problems are: (A=For every, E=There exists) 1. A x in {0,1}, E y in {0,1), A z in {0,1), x less than or equal to y + z. 2. A x in Reals, A y in Reals, A z in Reals, E d in Reals, s.t. x + y + z = d. 3. A x in Naturals E y in {0,1,2} (x + y)/3 is in the Naturals. 4. A x in Reals, A y in Reals, A z in Reals, x^2 + y^2 + z^2 > 0. I never know how to read a proposition if it has more than two quantifiers. Three of the above problems all have three quantifiers. Also I get confused how to read them. I know order makes a difference, but how? I would say the second and third propositions are true. This is just by looking at them. Date: 03/26/2003 at 21:49:26 From: Doctor Nbrooke Subject: Re: Quantifiers Hi Dan, and thanks for writing to Dr. Math. First we'll remember when statements involving quantifiers are true or false: For all, for each: \A x, P(x) ------------------------- \A x, P(x) is true if P(x) is true for every possible x. \A x, P(x) is false if there is an x for which P(x) is false. There exists, for some: \E x : P(x) ---------------------------------------- \E x : P(x) is true if there is an x for which P(x) is true. \E x : P(x) is false if P(x) is false for every x. Now in understanding statements with quantifiers, it is useful to translate them into English to get our heads around them. You said that you thought that statements (2) and (3) are true. Let's start with (2): \A x in R, \A y in R, \A z in R, \E d in R : x + y + z = d. For simplicity's sake, we can go ahead and group the three quantifiers on the left together, like this: \A x, y, z in R, \E d in R : x+y+z=d. Now to English, this reads "For all real numbers x, y, and z, there exists a real number d such that x + y + z = d." To prove that this is true, you have to select a real number d such that x + y + z = d. Well, let d = x + y + z; since the real numbers are closed under addition, we know that the sum of any three real numbers is itself a real number. Now our statement reads like this: \A x, y, z in R, \E d in R : x + y + z = x + y + z. This is a tautology. It is universally true for all reals x, y, and z. Now consider statement (3). \A x in N, \E y in {0,1,2} : (x+y)/3 in N. You claim that this is true. Translated, we say that "For every natural number x, there exists a y equal to 0, 1, or 2 such that (x+y)/3 is a natural number." This is indeed a true statement, but we have to prove it. Perhaps you're already familiar with the division algorithm for natural numbers: \A a, d in N \E unique q, r in N : a = qd + r and 0 <= r < d. In words, "For every natural number a (the dividend) and natural number d (the divisor), there exists a natural number q (the quotient) and natural number r (the remainder) such that a = qd + r and 0 <= r < d." This is a proven theorem, and very useful for proofs like these. Back to our original statement. We need to find a way to choose y for every possible x if we are to prove our statement true. By the division algorithm, we have that x = 3q + r for some integer q and r, where 0 <= r < 3. If r is an integer such that 0 <= r < 3, it has three possible values: 0, 1, and 2. We'll proceed by cases. Case r = 0: If r = 0, then x = 3q for some natural number q. We need to choose a y such that (x + y)/3 is in N, that is (3q + y)/3 is in N. Choose y = 0. Then (3q + y)/3 = (3q)/3 = q, which is a natural number. Case r = 1: If r = 1, then x = 3q + 1 for some natural number q. Choose y = 2. Then (x + y)/3 = ((3q + 1) +2)/3 = (3q + 3)/3 = q + 1, which is a natural number. Case r = 2: Choose y = 1. Then (x + y)/3 = ((3q + 2) + 1)/3 = (3q + 3)/3 = q+1, which is a natural number. Our cases are exhausted: We have now found a y equal to 0, 1, or 2 for all possible values of x. We finish our proof off with a Q.E.D. I hope this helps. Feel free to write back if you have any more questions. - Doctor Nbrooke, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/