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?
Best Answer
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):