Proof by contradiction

[c1jeong]

Proposition If $n^{2}$ is a multiple of 3 then $n$ is a multiple of 3 .

Proof by contradiction Suppose $n^{2}$ is a multiple of 3 and $n$ is not. $n^{2}=3 k$ and $n=3 l+m$ for $k>l \geq 0$ and $1 \leq m \leq 2$. $$\begin{align} 3 k =n^{2} \ =(3 l+m)^{2} \ =9 l^{2}+6 l m+m^{2} \ m^{2} =3 k-9 l^{2}-6 l m \ =3\left(k-3 l^{2}-2 l m\right) \ \frac{m^{2}}{3} =k-3 l^{2}-2 l m \end{align} $$ Case I) $m=1$

$\frac{1}{3}=k-3 l^{2}-2 l m$

Since the rhs is integer it is contradiction. Case II) $m=2$

$\frac{4}{3}=k-3 l^{2}-2 l m$

the same as case I. Therefore if $n^{2}$ is a multiple of 3 then $n$ is also.

[jjdosa]

I want to add a bit more precision to @c1jeong's proof. In classical logic, the implication can be written in terms of disjunction together with negation

$$ (\neg p \lor q) \leftrightarrow (p \to q) $$

(in intuitonistic logic, for comparison, only one direction is valid $(\neg p \lor q) \rightarrow (p \to q)$ )

In order to prove the implication $p \rightarrow q$ by proof by contradiction, the negation of the proposition we want to prove is

$$ \begin{align} \neg (p \to q) \ \leftrightarrow \neg (\neg p \lor q) \ \leftrightarrow (p \land \neg q) \ \end{align} $$

In this particular problem, $p = n^2 \text{ is multiple of }3$, $q = n \text{ is multiple of }3$. Therefore we suppose, as @c1jeong did,

$$ n^2 \text{ is a multiple of } 3 \text{ and } n \text{ is not.} $$

to reach the contradiction. Since then the remaining can proceed as @c1jeong did.

I hope these finely granulated steps are helpful in avoiding confusion about proof by contradiction.

PS) I am sorry that I am bringing up intuitionistic logic often if it makes you confused. As I am interested in formal proof, I feel the understanding of intuitionistic logic is a must, especially considering its close relationship to computer programming and category theory. If you are not interested, don't mind ignoring it. 😃 If you are interested, the wiki page about intuitionistic logic is informative. It's interesting that the four-color theorem was proved by using intuitionistic logic.

[c1jeong]

I feel I should be familiar with the notations in logic. Thank you for sharing ideas in relation to programming.