Can Rewriting P -> Q as ~Q -> ~P Lead to a False Conclusion?
Date: 01/21/2006 at 00:43:08 From: Eddie Subject: P -> Q <> ~Q -> ~P A teacher told the month of her birthday (let's call it M) to Peter, and the day of her birthday (let's call it D) to John. Then, the teacher showed a set of dates, and asked Peter and John which one was her birthday: 4 Mar, 5 Mar, 8 Mar 4 Jun, 7 Jun 1 Sep, 5 Sep 1 Dec, 2 Dec, 8 Dec Peter said, "If I don't know the answer, John doesn't know, too." John said, "At first I really didn't know, but now I know." Peter said, "I know, too." What is the teacher's birthday? The first time I thought the answer was 1 Sep. Peter said John couldn't know the teacher's birthday so Peter must have Mar or Sep, since all the days in those two months appear more than once in the list. Of course, John can also figure out that Peter has either Mar or Sep by Peter's argument. John knows the day and since he now knows the answer it can't be 5 since that day happens in both Mar and Sep. That means the day must be 1, 4 or 8. Lastly, Peter said he now also knows the answer. That would happen if and only if it was Sep since Mar would still have two possibilities, 4 and 8. So her birthday must be 1 Sep. However, I know 'if P then Q' is equivalent to 'if Not Q then Not P'. But when I make that change, I get another date for the answer. "If I don't know the answer, John doesn't know, too" is changed into "If John knows the answer, I know the answer." Since only 7 and 2 directly let John know the answer, Peter could only have either Jun or Dec to make the argument true. But 7 or 2 can't be the day since John says he didn't know at first. Now that John knows it's either Jun or Dec, though, he knows the answer, so he must have 1, 4, or 8. But Peter also knows, so that can only happen if it's Jun since Dec still has two choices. So her birthday must be 4 Jun. I don't know why there will be two answers when I just change the first argument by a valid conversion: P -> Q = ~Q -> ~P. Or am I wrong somewhere in the process? Thank you for your help.
Date: 01/21/2006 at 05:35:58 From: Doctor Jacques Subject: Re: P -> Q <> ~Q -> ~P Hi Eddie, Disturbing, isn't it? At first sight, your two arguments are both correct. The point is that we cannot blindly use propositional logic here. In propositional logic, a proposition is a statement that is either true or false, and we assume that, if the same proposition is used more than once, all occurrences have the same meaning (the same truth value). However, in this case, a statement like "X knows the answer" does not satisfy that definition: such a statement can be false at some time and true some time later (this is the whole point of the riddle: at the beginning, nobody knows the answer, and, at the end, both Peter and John know it). If we were to analyze the argument in a strictly formal way, we should consider several propositions like: XKn : X (J, P) knows the answer at step n (1,2,3) XSn : X says that he knows the answer at step n and a few more, like "X knows at step m that Y does not know at step n"... We would also need to write down some implied statements explicitly, for example: XK1 -> XK2 (once you know the answer, you don't forget it) XSn -> XKn (our guys don't lie) in addition to the statements that can be derived from the set of possible dates and the statements of Peter and John. I didn't try to write that down in full (this could be interesting): the problem can be solved in a more informal way. I believe your first answer is the correct one. Let us be a little more explicit: At step 1, we know that Peter does not know the answer, since each possible month has more than one day, and nothing else has been said. By Peter's first statement (and the rule of modus ponens), this implies that John does not know the answer either, and the day cannot be 2 or 7. We also learn that Peter knows that John does not know the answer; this means that Peter knows that the day is neither 2 nor 7, and this rules out the months in which these days appear, i.e., Jun and Dec. At step 2, John first confirms that he did not know the answer (this does not tell us anything new). Now, John has just learned that the month is either Mar or Sep, and this is sufficient for him to deduce the answer. This means that the day (known to John) must appear exactly once in Mar or Sep, which leaves 1, 4, and 8. At step 3, Peter has learned that the day is 1, 4, or 8, and this is enough for him to know the answer. This means that exactly one of these days can appear in the month (known to Peter), and this rules out Mar, leaving only 1 Sep as the answer. Now, what is wrong with the second argument? It is quite correct that Peter could equivalently have said at step 1: "If John knows the answer, I know the answer" but this simply means that either John does not know the answer (meaning the day is neither 2 nor 7, which is true), or Peter knows the answer (which we know is false). However, the way you interpret it in your argument is as if Peter had said: "If I knew John knows the answer, I would know it too" (*) and this is completely different: the antecedent of that statement is not "John knows the answer", but "Peter knows that John knows the answer". By the way, it is interesting to note that, after step 2, Peter does indeed know that John knows the answer, and statement (*) would be true if Peter had said it at that time. The point is that statement (*) implies that the day must appear only once in the remaining possible months, and this has a different meaning at step 1 and step 2. Does this help? Please feel free to write back if you want to discuss this further. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Date: 01/21/2006 at 10:14:52 From: Eddie Subject: Thank you (P -> Q <> ~Q -> ~P ) Thanks, Doctor Jacques. Now I understood how my interpretation was wrong. Thank you for your help. But I do have two questions. First, you say: "We also learn that Peter knows that John does not know the answer; this means that Peter knows that the day is neither 2 nor 7, and this rules out the months in which these days appear, i.e., Jun and Dec." After I discussed this with some friends, we don't understand why Jun and Dec can be ruled out in Step 1. Isn't it possible that Peter got Jun and said the same 1st statement of "If I don't know the answer, John doesn't know, too."? Second, is a "deductive" or "inductive" argument being assumed in this question and would that cause a different answer? Should it be restricted to deductive? Thank you for your help.
Date: 01/23/2006 at 03:11:00 From: Doctor Jacques Subject: Re: P -> Q <> ~Q -> ~P Hi Eddie, First, we know--and everybody knows--that Peter does not know the answer at the beginning: the only thing Peter knows is the month, and, whichever month it is, there is always a choice of more than one day. Assuming Peter does not lie, we have the argument: "If P. does not know, J. does not know" "P. does not know" -------------------------------------- therefore, "J. does not know" Note that there is no problem of ambiguity here: "X does not know the answer" means the same thing throughout the argument. Now, this argument tells us two things: (1) the conclusion itself--John does not know. This would be true if anybody else (for example the teacher) has made that statement. (2) the fact that the statement is made by Peter. (1) tells us that the day (known to John) cannot be 2 or 7, since in either of these cases, there would only be one possible answer, and John would know it. Note that, as far as John is concerned, we have a "necessary and sufficient condition": John knows the answer in step 1 if and only if the day is 2 or 7. (2) tells us that, not only John does not know the answer, but Peter can be sure of it. Because of (1), this means that Peter knows that the day is neither 2 nor 7, and he can only be certain of that if neither of these days appears in the month he knows. For example, if the month is Jun, the day can only be 4 or 7. It is true that, if the day were 4, John would not know the answer, and Peter's first statement would still be true. However, from Peter's point of view, it is also possible that the day is 7, in which case John would know the answer, and Peter's statement would be false. This means that, if the month is Jun, it is possible that John does not know, but Peter cannot be certain of it, and cannot therefore make his statement. In fact, all this shows that there is an additional hidden assumption in this kind of problem. We already assumed that the players do not lie, meaning their statements are true propositions (assuming we make them explicit enough to specify who knows what at what time). In addition, we must assume that they are certain of what they are saying; formally, this would mean that their statements are not only true (which could happen by chance) but are also provable from the information available to the speaker at the time they are made; to put it otherwise, the players only assert things that they know to be true, not merely things that are true in fact. This is the assumption we use in the second part of the argument. In some similar problems (there are many of them...), this is made explicit by a statement like "the players are truthful and infinitely clever". Concerning your question about inductive and deductive reasoning, this is a different matter. In this case, we use only deductive reasoning (even to a pathological extent...). Inductive reasoning is the process by which you "guess" a general rule from given known facts (observations). This is mainly how physics (and many other disciplines, like engineering, medicine, ...) work: we make measurements, use them to guess a plausible law (this is inductive reasoning), derive consequences of these laws (this is deductive reasoning), and make experiments to check those consequences against the real world. In mathematics also, you can use inductive reasoning (this is not proof) in some cases. In some cases, you can guess a general formula (by inductive reasoning) from a few values computed numerically. Once you know what you should obtain, this may give you a clue about how to prove it (by deductive reasoning). Beware that "inductive reasoning" is not the same as "mathematical induction". - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Date: 01/24/2006 at 20:50:56 From: Eddie Subject: Thank you (P -> Q <> ~Q -> ~P ) Dear Doctor Jacques, You're so nice. We've really learned some new things, and one of us started to get interested in mathematics again. Thank you very much.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.