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.