Proof by Contrapositive (with 'and' statement)
I just wanted to make sure that my logic here is not faulty. Up till now I've generally avoided contraposition proofs and worked only with contradiction (since we may rephrase the former in terms of the latter), so I'm having a bit of trouble wrapping my head around one point.
Suppose I have a statement of the form $A\land B\Rightarrow C$. To prove the contrapositive, I would have to prove that $\neg C\Rightarrow \neg A\lor\neg B$. Now, I'm assuming that $A$ and $B$ are true and I want to conclude $C$. But when I do a proof by contrapositive, am I still allowed to assume $A$ and $B$ are true?
As an example, Rudin defines an ordered set to be a set $S$ with an order relation $<$ that is trichotomous and transitive. I want to prove that $\leq$ is also transitive. So I start with $x,y,z$ in $S$ satisfying $x\leq y$ and $y\leq z$, and want to conclude that $x\leq z$.
The contrapositive of this is $z<x$ implies $y<x$ or $z<y$. To prove this, I assume that $x\leq y$ is true and argue that since $x=y$ or $x<y$, and both imply $z<y$, the result follows (because it's an 'or' statement).
Is this actually legitimate?
$\endgroup$ 32 Answers
$\begingroup$It's legitimate but scrappy, if I understand correctly. You've made a proof by contradiction again.
The problem with contradiction is that it doesn't tell you anything other than "my assumption is false". If you prove that $\neg B \Rightarrow \neg A$ without assuming $A$, you know that any results you end up proving along the way (before you finally end up with $\neg A$) are implied by the single assumption $\neg B$. If you prove that $\neg B \wedge A \Rightarrow \bot$, then you can't use anything you prove along the way: it only tells you that $A \Rightarrow B$, and nothing further.
Your result may be proved directly: if $x \leq y$ and $y \leq z$, then we have three possible cases of the relation between $x$ and $y$ (by trichotomy):
- $x = y$. Then $x = y \leq z$ immediately.
- $x < y$. Then:
- if $y = z$, we're done again: $x < y = z$ so $x \leq z$.
- if $y < z$, then $x < y$ and $y < z$; $<$ is known to be transitive so $x < z$, and in particular $x \leq z$.
- $x > y$ (which we already know is not the case, because $x \leq y$).
I'm going to answer the first part of your question, since I am not sure that I know the answer to the second part.
So basically, in a proof by contrapositive, you assume that ~C is true, and prove that when ~C is true, it leads to ~A and ~B. That is pretty much all you need to do.
So in response to your question, in a proof by contrapositive it does not matter whether you assume that A and B are true or not. All that matters is that you are able to assume ~C is true, and using that, prove that when ~C is true, ~A and ~B is also true. That is all. :-)
Let me know if you require clarification on my answer.
$\endgroup$
