I'm having some trouble with a homework question. I have the following

$P \rightarrow \neg P$

This looks like a contradiction to me. This should never be true! Yet, if I transform it using $p \rightarrow q := \neg p \vee q$, I get $\neg P \vee \neg P$, which is $\neg P$, which is satisfiable!

$P \rightarrow (\neg P \rightarrow P)$

Similarly, the same thing happens here. I look at this, and I see the part inside parentheses and say "so this is basically just $P \rightarrow (false)$- that's true half of the time"

But no, if I use that equation, I get $P \rightarrow (P \vee P) = P \rightarrow P$, which is a tautology.

Where am I going wrong?

-
You say it "should never be true". Have you actually drawn up a truth table to discover when it is true? – Chris Eagle Nov 5 '12 at 16:56
$p \rightarrow q$ 'says nothing' about $q$ when $p$ is false. – copper.hat Nov 5 '12 at 17:03

As Berci noted, implications in propositional logic are fraught with problems when interpreted in ordinary speech. Some people find it helpful to think of an implication $p\rightarrow q$ as a promise that whenever $p$ is true, $q$ will be guaranteed to be true. For instance, let $p$ = "It is sunny" and $q$ = "I'll ride my bike to work". When it's sunny, you're keeping your promise by riding your bike, so the implication will be true. On the other hand, if it's sunny and you drive to work, you've broken your promise and so the implication will be false. Notice, though, that if it's not sunny, you haven't broken your promise whether you ride your bike or not: in other words, if $p$ is false, then $p\rightarrow q$ will be true no matter what value $q$ has.

Now consider the implication $p\rightarrow\neg p$. It may seem to be contradictory ("If it's sunny, then it's not") at first glance, but it's not in the case where $p$ is false, since, recall, you're not breaking any promises. In other words, you've correctly observed that $p\rightarrow \neg p$ is false in case $p$ is true, but is true when $p$ is false, so actually isn't a contradiction.

-

Note that $P \rightarrow \lnot P$ is equivalent to $\lnot P \lor \lnot P$ which essentially is an assertion that $\lnot P$.

$\lnot P$ is true whenever $P$ is false. So the implication $P\rightarrow \lnot P$ is "satisfiable" whenever the truth value of $P$ is false.

Likewise, given $$P \rightarrow (P \rightarrow \lnot P),\tag{1}$$ then $(1)$ is true when $P$ is false; this is because, as we've seen, the conclusion of implication $(1)$ is equivalent to $\lnot P$. So again, we have $P \rightarrow \lnot P$, and thus $\lnot P$, true when $P$ is false.

Now we'll address the non-equivalent (to $(1)$) statement:

$$P \rightarrow (\lnot P \rightarrow P)\tag{2}$$ $$\iff P \rightarrow (\lnot\lnot P \lor P)$$ $$\iff P \rightarrow (P \lor P)$$ $$\iff P \rightarrow P$$

$P \rightarrow P$ can be read as $(\lnot P \lor P)$ which, as you observed, is a tautology.

Note that this can readily be seen as a tautology without deducing ($P \lor \lnot P$) from $P \rightarrow P$ because...

$\ast$ An implication is false if and only if its premise is true and its conclusion is false.

So given the implication $P \rightarrow P$, either P is true or else P is false: i.e. either true $\rightarrow$ true, or else false $\rightarrow$ false. And so, knowing $(\ast)$ the implication $P \rightarrow P$ cannot ever be false: Whatever the truth-value of $P$, it will never be true that the premise P will be true, while the conclusion P is false. When the premise $P$ is true, then the conclusion, $P$, is true.

As others here have pointed out, material implication ($\rightarrow$), as used in logic, does not correlate well with our intuitive, informal (and sometimes formal) understanding(s) of implication.

John Corcoran wrote a great paper on this problem, surveying the various meanings of implication, both classifying those meanings/uses, and pointing out the differences between them in an effort to better capture what implication means in various contexts. (For anyone interested, I highly recommend that you read Corcoran's "Meanings of Implication," Dialogos 9 (1973) 59–76. Reprinted in R. Hughes, Ed., Philosophical companion to first order logic. Indianapolis: Hackett. 1993.)

-
@Brian Thanks for your edit...I was editing while you edited! It seems that I sometimes need to see my post before recognizing a missed $...especially when writing comments! – amWhy Nov 5 '12 at 17:19 You’re welcome. I actually hesitated, since you had just done an edit and were likely to catch the problem yourself, but the temptation to make such an easy quick fix was too great. :-) I often don’t catch little things like that until I see it, especially in comments. – Brian M. Scott Nov 5 '12 at 17:25 See also this post, and many others like it, which all address the meaning of material implication and how to better understand it. – amWhy Nov 5 '12 at 20:44 Observe that$ P \rightarrow \neg P$is not a contradiction. When$P$is false, it is true. - Using the equivalence of$p\rightarrow q$and$\neg p\vee q$is the right idea here. Saying$P\rightarrow\neg P$, is then precisely the statement$\neg P$, as you observed. On the other hand,$\neg P\rightarrow P$becomes$P$by this reasoning, so$P\rightarrow(\neg P\rightarrow P)$becomes$P\rightarrow P$becomes$\neg P\vee P$, a tautology - As you just learned, the logical implication$P\to Q$is not the best for expressing implication in the most intuitive sense. There are a lot approach to help this, for example in intuitionistic logic, modal logic$\Box(P\to Q)$, etc. - Note that in Heyting Arithmetic,$0 = 1 \to \neg 0 = 1$. So the fact that you can have truths of the form$\varphi \to \neg\varphi\$ doesn't distinguish the classical truth-functional from the intuitionist conditional. – Peter Smith Nov 5 '12 at 20:03