If $x\rightarrow y$ and $y \rightarrow z$, prove, by contradiction, that $x \rightarrow z$

Question

Say you're given $$x\Rightarrow y$$ $$y\Rightarrow z$$

Prove that $x\Rightarrow z$ by contradiction.

It seems like such a simple task, because it's easy to evaluate that it must be true. But I can't formulate a proof.

I'm starting out with "let's assume that $x \nRightarrow z$", but then, nothing.

Answer 1

Think of the negation as follows:

Suppose $\lnot (x \rightarrow z)$

$$\lnot(x \rightarrow z) \equiv \lnot (\lnot x \lor z) \equiv x \land \lnot z$$

This implies both $\color{blue} x$ and $\lnot z$, by simplification (and-elimination).

$\lnot z$ along with $y \rightarrow z$ gives you $\lnot y$ by modus tollens.

And $\lnot y$ along with $x \rightarrow y$ gives you $\color{blue}{ \lnot x}$ by modus tollens.

Now you have $\color\blue{x \land \lnot x}$.

Contradiction.

Therefore, our supposition was incorrect. Hence $\;x \rightarrow z$.