# The logic involved in contradiction via the irrationality of $\sqrt{2}$ as an example

I first want to issue my own interpretation of the proof that $\sqrt{2}$ is irrational.

First, for the sake of contradiction, let's assume it is in fact rational. This means we can write $\sqrt{2} = \frac{a}{b}$ where $\gcd(a,b)=1$ for integers $a,b$ with $b \neq 0$. Then $2b^2 = a^2$ which means $a^2$ is even, which also implies $a$ itself is even. So let $a=2k$ for some integer $k$. Then $2b^2 = (2k)^2 = 4k^2$, or $b^2 = 2k^2$. This means $b^2$ is even, and that $b$ is even too. But if $a$ anad $b$ are both even, then $\gcd(a,b) \neq 1$, a contradiction. Therefore $\sqrt{2}$ is irrational.

Now, I am curious logically where all of these statements fall and what proves what, what contradicts what and implies what, what the premises are, etc. Because I almost feel like there are multiple premises here:

Now technically I don't think the gcd condition is "necessary" for the number to be rational but I don't see where else to put it unless we treat it as another assumption or premise. Or maybe it's a compound premise?

Are we taking two premises:

$p_1 = (\sqrt{2}$ is a rational $\frac{a}{b}$ for integers $a,b$ where $b \neq 0)$

$p_2 = (\gcd(a,b) = 1)$

Then our "main premise" we care to prove:

$p = p_1 \land p_2$

And then from $p$ we use valid operations on $\sqrt{2} = \frac{a}{b}$ and ultimately arrive at a conclusion $q = (\gcd(a,b) \neq 1) = \lnot p_2$.

Since we are saying it is true that $p_2$ and $\lnot p_2$ are true at the same time this already implies a contradiction but I can't help but feel like I've structured this incorrectly.

What exactly are the premises? What are the implications? What are the conclusions? Where is the contradiction and where does it prove that the claim "$\sqrt{2}$ is rational" must be a false premise?

• The basic premise is the assumption about the rationality of $\sqrt 2$. The basic rule of inference used is negation introduction. The conclusion is the negation of the premise: the irrationality of $\sqrt 2$. Commented Mar 23, 2018 at 6:54
• Of course, a certain amount of "background knowledge" regarding arithmetic is needed, like e.g. the fact that a rational number $r$ can be expressed as the ratio of two integers (this is the def of rational), and so on. Commented Mar 23, 2018 at 6:55
• @MauroALLEGRANZA - I agree with you, this is what I tried to explain in my answer. Commented Mar 23, 2018 at 9:05

The assumption is merely $p1$: $\sqrt{2}$ is rational, i.e. $\sqrt{2}=\frac{a}{b}$ for some whole numbers $a$ and $b$.

However, we can then point out that if we can write $\sqrt{2}$ as a ratio in some way, then by dividing out the common factors between $a$ and $b$, it follows that we can write it as a ratio where the numerator and denominator have no common factors, i.e. where they are relative prime.

In other words, if $\sqrt{2}=\frac{a}{b}$ for some whole numbers $a$ and $b$, then $\sqrt{2}=\frac{a}{b}$ for some whole numbers $a$ and $b$ where $gcd(a,b) = 1$

You might think that this latter claim is $p1 \land p2$, but that is not correct, since in the expression $p1 \land p2$ the $a$ and $b$ in $p1$ need not be the same $a$ and $b$ in $p2$ ... in fact, in $p1$ the $a$ and $b$ are existentially quantified, whereas in $p2$ they are free variables: So, $p2$ isn't even a 'stand-alone' claim; it only makes sense within the context of $p1$.

In logic: we go from:

$$\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b})$$

to:

$$\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b} \land gcd(a,b)=1)$$

which is not the same as

$$\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b}) \land gcd(a,b)=1$$

This is a crucial thing to note, since the $a$ and $b$ in the claim

$$\sqrt{2}=\frac{a}{b} \text{ for some whole numbers } a \text{ and }b$$

need not be the same $a$ and $b$ in the claim:

$$\sqrt{2}=\frac{a}{b} \text{ for some whole numbers } a \text{ and }b \text{ where } gcd(a,b)=1$$

which is again why you can;t treat $p2$ as a 'stand-alone' claim: are you referring to $a$ and $b$ as stated to exist in the context of the former claim, or in the context of the latter claim? This is not clear, and so you should not treat $p2$ as a claim in and of itself.

As such, you should also not say: "Well, the proof shows that $p1 \land p2$ leads to a contradiction ... but it seems that the only contradiction we reach is that we get $\neg p2$ .. so why should we reject $p1$? Again, there is no such thing as $p1 \land p2$ ... there is $p1$, i.e.:

$$\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b})$$

and then there is the claim that follows from $p1$, which is:

$$\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b} \land gcd(a,b)=1)$$

and this latter claim is not $p1 \land p2$, but rather the 'integration' of $p1$ and '$p2$', as '$p2$' ends up within the scope of the existential of $p1$. So, we could write this as '$p1 \land p2$', but maybe it's best to just write it as claim $p1'$.

So, we have:

$$p1 \rightarrow \ p1'$$

And then of course we show:

$$p1' \rightarrow \bot$$

And thus:

$$p1 \rightarrow \bot$$

And therefore:

$$\neg p1$$

• What is the difference between integration and conjunction exactly? I don't see any difference other than a syntax difference of using quotation marks Commented Mar 23, 2018 at 17:49
• @user525966 'integration; is not any kind of official operation. But what I tried to explain the post is that when we combine the claim $\exists a,b (\sqrt{2}=\frac{a}{b})$ with $gcd(a,b)=1$, what we want is: $\exists a,b (\sqrt{2}=\frac{a}{b} \land gcd(a,b)=1)$, which is not the same as $\exists a,b (\sqrt{2}=\frac{a}{b}) \land gcd(a,b)=1$. That's what I meant by saying that $p2$ becomes 'integrated' as part of the existential claim, rather than being conjuncted with it. This is important, because that shows that $p2$ really isn't a 'stand-alone' claim. Commented Mar 23, 2018 at 17:53
• Oh I see, just wrapping the gcd condition inside the quantifiers so we're talking about the same variables here. And then once we find that gcd(a,b) is not 1, what does that mean exactly? It shows that $p_1$ is false, but we had taken it to be true earlier. And then somehow we walk away from this saying "it must be irrational then" even though we also have this gcd bit to consider. How do we prove the problem is with the fractional representation and not the gcd bit? Commented Mar 23, 2018 at 17:58
• (I am trying to be fully rigorous about this because I want to understand beyond a shadow of a doubt how something like this works with contradiction and "compound conditions" and how we walk away from this knowing that $\sqrt{2}$ is irrational) Commented Mar 23, 2018 at 18:01
• @user525966 The logic is really solid .. you just need to do it step by step. So, rather than thinking: '$p1$ is false because of the gcd bit', think: $p1$ (which is $\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b})$) implies $\exists a,b \in \mathbb{Z} (\sqrt{2} = \frac{a}{b} \land gcd(a,b)=1)$, and the latter is false 'because of the gcd bit'. But if the latter is false, and if that is implied by $p1$, then $p1$ is false too. Commented Mar 23, 2018 at 18:47

For $\frac ab$ to be rational, it is not necessary that $a,b$ be coprime. For example,$\frac{14}{10}$ is rational.

However, if $x$ is rational it is always possible to write $x=\frac ab$ with $a,b$ coprime. For example, if $x=\frac{14}{10}$ then we can write $x=\frac75$.

This is nothing more than "reducing to lowest terms" or "cancelling common factors". It is a well known fact and I should think that it is quite acceptable to use it without proof in your argument. So really the only assumption you are making is that $\sqrt2$ is rational.

• I understand this, but I am specifically asking how it would be logically worked into this via proof by contradiction, since it is not necessary, but it is often used as proof of contradiction logically Commented Mar 23, 2018 at 4:22
• It's not necessary, but it's useful. You can use any previously known fact in a proof. I'm not sure I understand your problem. Commented Mar 23, 2018 at 4:28
• I guess I would say, how does finding $p_2$ false ultimately allow me to imply that $\lnot p_1$ is actually true? Commented Mar 23, 2018 at 4:54
• @user525966 If sqrt(2) was rational, it would be able to be written as a fraction of coprime integers.This argument shows that you can't represent root 2 that way, so it's irrational. Commented Mar 23, 2018 at 5:01
• No I know that, I am asking about the formality/logical proof of such Commented Mar 23, 2018 at 5:21

In your proof, you are taking the conjunction of two premises: \begin{align} p_1 &= \sqrt{2} \text{ is rational} \\ q &= \text{all the axioms that define rational numbers and the algebraic operations on integers.} \end{align}

Note that $p_1$ is the negation of the thesis of the theorem you want to prove, while $q$ is the implicit hypothesis of the theorem you want to prove.

From $q$ and $p_1$ you infer that there exist two integers $a$ and $b$ such that: \begin{align} p_2 &= a \text{ and } b \text{ are coprime} \\ \lnot p_2 &= a \text{ and } b \text{ are not coprime} \end{align} From this contradiction it follows that $q \land p_1$ does not hold, and this amounts to say (in classical logic) that either $q$ or $p_1$ does not hold. So, if you assume $q$ (i.e. all the axioms that define rational numbers and the algebraic operations on integers), then $\lnot p_1$ must hold, i.e. $\sqrt{2}$ is not rational.

Clearly, this is a simplified explanation of the logic structure of the proof of the irrationality of $\sqrt{2}$. For a fine-grained representation of the logical structure of this proof, you should use first-order logic instead of propositional logic.

You can view it as $p_1 \land p_2$, however, we already know that $p_2$ is a true statement. That is we know that we can write a rational number in that form.

Hence starting from $p_1 \land p_2$, if we get a false statement, then we know that $p_1 \land p_2$ is false. With the extra knowledge that $p_2$ is true, $p_1$ must be false.

If a number $r$ is rational, then among multiple expressions of the form $a/b$ equal to $r$ there must be one expression with $\gcd(a,b)=1$. (This is got by repeated cancellation).

Now start your proof with this specific choice of $a/b$, then you can avoid compound statements.