Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The premise of 'proof by contradiction' is that a true statement can never imply a false statement.

In my lectures (intro to logic), this has been brushed aside as 'obvious', but is there a formal proof for this fact?

share|improve this question
1  
How do you define "implication"? –  Omnomnomnom Aug 15 at 19:38
    
It really depends on what axioms of logic you are using. –  Thomas Andrews Aug 15 at 19:44

3 Answers 3

up vote 0 down vote accepted

If $p$ is true and $q$ is false, then $p\implies q$ is equivalent to $\neg p\vee q$, and since $\neg p$ is false and $q$ is false, $\neg p \vee q$ is also false...

share|improve this answer
    
Nitpick: be careful, in some common logical systems (such as intuitionistic logic), $\to$ is not definable in terms of $\neg$ and $\vee$ and has to be taken as primitive. –  Clive Newstead Aug 15 at 19:43
    
@Clive: Does that mean that $\to$ in intuitionistic logic hasn't invented the wheel yet? :-D –  Asaf Karagila Aug 15 at 19:51

Most mainstream logical systems have a deduction rule called modus ponens, meaning that if $p$ is true and $p \to q$ is true then $q$ is true. Thus if $p$ is true and $q$ is false, then $p \to q$ cannot be true, otherwise $q$ would be true. (And it wouldn't make much sense for $q$ to be simultaneously true and false!)

share|improve this answer

This is an assumption, that first-order logic (or propositional calculus if you will) is sound, and that our inference rules do not prove a contradiction.

Now write down the truth table for $p\implies q$, and since we assume that the basic rules of our game are "correct", this means that we have to obey this truth table when we have $p\implies q$. In particular if $p$ is true and $q$ is false then the implication itself is false.

The reason this is usually brushed aside in introductory courses is that we don't want to burden the student. We work in a mathematical system "so obviously this system is consistent". There's no need to worry about this. Later, in intermediate logic courses you will often meet a proof that first-order logic is sound.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.