Geometry

Proof by contradiction

How can anyone prove that \displaystyle \sqrt{2} is not a fraction, when there are infinitely many fractions to rule out and none of them is there to calculate with?

You need

Irrational numbersMath 8 Every number has exactly one prime factorizationMath 6 Direct proofGrades 9 to 12

Unlocks

Indirect proofGeometry There are infinitely many primesDiscrete Mathematics and Proof Uncountable sets and the diagonal argumentDiscrete Mathematics and Proof

Where you are 14 in Proof techniques

Logic, proof and discrete math6

Proof techniques14

▴ 9 above Proof by contraposition The pigeonhole principle

Proof by contradiction

Combinatorial proof: counting one set two ways Proof by induction3

When you reach for it

Some statements give a direct proof nothing to start from. “\displaystyle \sqrt{2} is irrational” says that no fraction squares to 2. There are infinitely many fractions, so checking them one at a time never finishes, and there is no particular fraction on the table to calculate with. The same is true of “there are no integers x and y with ...”, “there is no largest ...”, and “at most one ...”.

A proof by contradiction turns the problem round. It assumes, for the length of the argument, that the statement is false. That negation is usually something concrete: “\displaystyle \sqrt{2} = \frac{a}{b} for some integers a and b” hands over two integers to work with. The proof reasons from the assumption, using only facts already known, until two statements appear that cannot both be true. Every step was valid, so the fault lies with the one thing that was not known to be true: the assumption. It is false, and so the statement is true.

Reach for it when the statement says that something is impossible, does not exist, or is not a member of some set (irrational means not rational), and when its negation gives you an object to name. A direct proof goes forward from what you know. A proof by contradiction adds one more thing to know, for a while, and then shows that it could never have been true.

The procedure

Why assuming the opposite proves anything

In mathematics a statement is either true or false, so exactly one of P and \neg P holds. A statement of the form Q \wedge \neg Q, “Q and not Q”, is false whatever Q says: it is a contradiction. Suppose you have proved

\neg P \rightarrow (Q \wedge \neg Q).

A conditional whose conclusion is false is true only when its hypothesis is false (the truth table of the conditional). So \neg P is false, and P is true. The truth table says the same in one comparison. Since Q \wedge \neg Q is false on every row, whatever Q is, two rows are enough:

P	\neg P	Q \wedge \neg Q	\neg P \rightarrow (Q \wedge \neg Q)
T	F	F	T
F	T	F	F

The last column matches the first, so the two statements are logically equivalent, and proving one proves the other. In the language of arguments it is modus tollens: if \neg P, then something impossible; the impossible thing does not happen; so not \neg P.

The parts of a proof by contradiction

State the claim exactly. Its opposite cannot be written down until the claim itself is pinned down, with every word that matters (what must be shown).

Assume the negation, all of it. The negation must cover every way the claim could fail (negation). For a claim about every integer, the negation is about one: the opposite of “every integer n has n^2 + n even” is “some integer n has n^2 + n odd” (negating a quantified statement). For “if P, then Q” the negation is “P, and not Q”. The common shapes:

The claim	The assumption
x is irrational	\displaystyle x = \frac{a}{b} for some integers a and b with b \neq 0
no integers x, y satisfy an equation	some integers x, y satisfy it
there is no largest such number	there is a largest one; call it N
if P, then Q	P is true and Q is false
at most one of them	at least two of them
there are infinitely many	there are only finitely many; list them all

Write the assumption as its own sentence, “Suppose, for a contradiction, that ...”, because every line after it depends on something the proof will throw away.

Reason forward. Use the assumption together with definitions and results already proved, each step with its reason, as in any proof. Name the objects the assumption supplies.

Stop at a contradiction, and say what it is. The target is two statements that cannot both hold: one derived, the other a known fact, a given, or the assumption itself. Saying which two is part of the proof. In work with integers the contradictions that come up most are these:

an integer that is both even and odd, which cannot happen because dividing by 2 leaves exactly one remainder, 0 or 1 (proof by cases);
a positive integer with two different prime factorizations, which unique factorization rules out;
a positive integer smaller than the smallest one with some property.

Conclude. “So the assumption is false, and” the claim. Everything derived from the assumption falls with it: none of it may be quoted later as a fact.

Choosing the assumption so that it gives a grip

The negation is fixed, but you may add to it any detail that does not narrow it. If \displaystyle \sqrt{2} is equal to some fraction, it is equal to one in lowest terms, because dividing the top and bottom by their greatest common divisor changes neither the value nor the fact that both are integers. So “suppose \displaystyle \sqrt{2} = \frac{a}{b} in lowest terms” claims no more than “suppose \displaystyle \sqrt{2} is rational”, yet it hands the proof a second fact to collide with.

The same idea in another form: if some positive integers have a property, then one of them is the smallest, because every non-empty set of positive integers has a smallest member (the well-ordering principle, met in strong induction and well-ordering). Assume the smallest one, then build a smaller one. Example 7 works this way.

Contradiction or contraposition

To prove “if P, then Q”, a proof by contradiction assumes P and \neg Q. If the clash it finds is with P itself, the proof has really shown \neg Q \rightarrow \neg P, which is a proof by contraposition, and it usually reads better written that way. Example 1 is of this kind. The method earns its own name when the clash is with something else: lowest terms, a parity, a prime factorization, a smallest choice.

Worked examples

Example 1

When a square is even

Prove: for every integer n, if n^2 is even, then n is even.

Solution

The claim is a conditional about every integer, so its negation is: there is an integer n with n^2 even and n odd. Suppose, for a contradiction, that n is such an integer.

Since n is odd, n = 2k + 1 for some integer k, by the definition of odd. Squaring and expanding,

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.

Because products and sums of integers are integers, 2k^2 + 2k is an integer, so n^2 is odd by definition. But n^2 was assumed even, and no integer is both even and odd. That is the contradiction, so no such n exists: every integer whose square is even is itself even.

The clash was with the hypothesis “n^2 is even”, so this is the contrapositive in disguise: the middle paragraph is a direct proof that the square of an odd number is odd. Either write-up is a proof. The fact itself is used in the next two examples.

Example 2

The square root of two is irrational

Prove that \displaystyle \sqrt{2} is irrational.

Solution

Irrational means not rational: not equal to \displaystyle \frac{a}{b} for any integers a and b with b \neq 0. Suppose, for a contradiction, that \displaystyle \sqrt{2} is rational, so \displaystyle \sqrt{2} = \frac{a}{b} for some integers a and b with b \neq 0. Take the fraction in lowest terms: if a and b share a factor, divide it out, which leaves the value unchanged. So a and b have no common factor bigger than 1.

Squaring both sides gives \displaystyle 2 = \frac{a^2}{b^2}, and multiplying by b^2,

a^2 = 2b^2.

So a^2 is 2 times an integer, which makes it even. By Example 1, a is even: a = 2k for some integer k. Substituting,

\begin{aligned} 2b^2 &= (2k)^2 = 4k^2,\\ b^2 &= 2k^2. \end{aligned}

So b^2 is even, and by Example 1 again, b is even. Now a and b are both even: they share the factor 2. This contradicts the choice of \displaystyle \frac{a}{b} in lowest terms. The assumption is false, so \displaystyle \sqrt{2} is irrational.

The proof uses no decimals at all. No calculator could have reached this conclusion, since a screen shows only finitely many digits of any number. And the lowest-terms clause is what makes the clash possible: without it, the proof would end with “a and b are both even”, which on its own contradicts nothing (Exercise 21 shows another way to finish from there).

Example 3

No integer solutions

Prove that there are no integers m and n with m^2 = 4n + 6.

Solution

The claim says no such pair exists, so its negation is that one does. Suppose, for a contradiction, that m and n are integers with m^2 = 4n + 6.

The right side factors as 4n + 6 = 2(2n + 3), and 2n + 3 is an integer, so m^2 is even. By Example 1, m is even: m = 2k for some integer k. Then m^2 = 4k^2, and the equation becomes

\begin{aligned} 4k^2 &= 4n + 6,\\ 2k^2 &= 2n + 3, \end{aligned}

dividing both sides by 2. The left side is even. The right side is 2(n + 1) + 1, which is odd. No integer is both, so this is a contradiction, and no integers m and n satisfy m^2 = 4n + 6.

A search can only confirm that small values fail. Trying every m from -200 to 200 finds no m^2 that is 6 more than a multiple of 4, but a search never finishes. The proof covers every integer at once.

Example 4

Rational plus irrational

Prove that if r is rational and x is irrational, then r + x is irrational. Use it to show that \displaystyle 3 + \sqrt{2} is irrational.

Solution

The negation of the conditional is: r is rational, x is irrational, and r + x is rational. Suppose, for a contradiction, that all three hold. Write \displaystyle r = \frac{m}{n} and \displaystyle r + x = \frac{p}{q} with m, n, p, q integers, n \neq 0 and q \neq 0. Then

x = (r + x) - r = \frac{p}{q} - \frac{m}{n} = \frac{pn - mq}{qn}.

The top and bottom are integers, being built from integers by multiplying and subtracting, and qn \neq 0 because neither factor is 0. So x is rational, which contradicts x being irrational. Hence r + x is irrational.

For \displaystyle 3 + \sqrt{2}, take \displaystyle r = 3 = \frac{3}{1}, which is rational, and \displaystyle x = \sqrt{2}, which is irrational by Example 2. So \displaystyle 3 + \sqrt{2} is irrational.

The result says nothing about adding two irrational numbers. \displaystyle \sqrt{2} and \displaystyle -\sqrt{2} are both irrational (if \displaystyle -\sqrt{2} = \frac{p}{q}, then \displaystyle \sqrt{2} = \frac{-p}{q}), yet their sum is 0.

Example 5

The square root of three, by counting primes

Prove that \displaystyle \sqrt{3} is irrational, this time with unique factorization in place of parity, and find the step where the same argument fails for \displaystyle \sqrt{4}.

Solution

Suppose, for a contradiction, that \displaystyle \sqrt{3} = \frac{a}{b} for integers a and b with b \neq 0. Since \displaystyle \sqrt{3} > 0, a and b have the same sign, and changing the sign of both changes nothing, so take both positive. Squaring and multiplying by b^2,

a^2 = 3b^2.

Count how many times the prime 3 appears in the prime factorization of each side. If it appears s times in a, then it appears 2s times in a^2 = a \cdot a, an even number. If it appears t times in b, then it appears 2t times in b^2, and 2t + 1 times in 3b^2, an odd number. (s or t may be 0; the counting still holds.) Both sides are the same positive integer, and by unique factorization that integer has only one prime factorization, so its count of 3s cannot be both even and odd. That is the contradiction, and \displaystyle \sqrt{3} is irrational.

No lowest terms were needed here: the clash is between two counts, not between two fractions.

Now try \displaystyle \sqrt{4}. The same steps give a^2 = 4b^2 = 2^2 b^2. The prime 2 appears 2s times on the left and 2 + 2t times on the right, and both counts are even. No contradiction appears, and none should: \displaystyle \sqrt{4} = 2 = \frac{2}{1}. The argument works exactly when some prime appears an odd number of times in the number under the root (see Boundaries).

Example 6

A logarithm that is irrational

Prove that \log_2 3 is irrational.

Solution

\log_2 3 is the power to which 2 must be raised to give 3 (Logarithms). It is positive, because 2 raised to 0 or to any negative power is at most 1, and 3 is more than 1. Suppose, for a contradiction, that \displaystyle \log_2 3 = \frac{a}{b} for integers a and b with b \neq 0; since the value is positive, take a and b both positive. Then 2^{a/b} = 3, and raising both sides to the power b,

2^a = 3^b.

The left side is even, because a \geq 1 makes it 2 \cdot 2^{a-1}. The right side is a product of b odd numbers, so it is odd. No integer is both: contradiction. So \log_2 3 is irrational.

Its value, about 1.585, can be worked out to as many places as anyone likes, and none of those digits could have settled the question. Positivity mattered: with a = 0 the left side would be 1, which is odd, and the clash would vanish.

Example 7

The smallest denominator, and a picture

Prove again that \displaystyle \sqrt{2} is irrational, this time by assuming it is a fraction with the smallest possible positive denominator and building one with a smaller denominator.

Solution

Suppose, for a contradiction, that \displaystyle \sqrt{2} is rational. Among all the ways of writing it as \displaystyle \frac{a}{b} with integers a and b and b positive (a negative denominator can be made positive by changing both signs), choose one in which b is as small as possible. This is allowed because every non-empty set of positive integers has a smallest member. Since \displaystyle \sqrt{2} > 0, a is positive too, and squaring gives a^2 = 2b^2.

Because b^2 < 2b^2 < 4b^2, we have b^2 < a^2 < 4b^2, and for positive numbers this gives b < a < 2b. Now set

a' = 2b - a, \qquad b' = a - b.

Both are integers. a' > 0 because a < 2b; b' > 0 because a > b; and b' < b because a < 2b. Expanding,

\begin{aligned} (a')^2 - 2(b')^2 &= (2b - a)^2 - 2(a - b)^2\\ &= 4b^2 - 4ab + a^2 - 2a^2 + 4ab - 2b^2\\ &= 2b^2 - a^2 = 0. \end{aligned}

So (a')^2 = 2(b')^2, and since a' and b' are positive, \displaystyle \frac{a'}{b'} = \sqrt{2}. That writes \displaystyle \sqrt{2} as a fraction with positive denominator b' < b, which contradicts the choice of b as the smallest possible. So \displaystyle \sqrt{2} is irrational.

The figure shows where a' and b' come from. If a^2 = 2b^2, a square of side a has the same area as two squares of side b. Put the two b by b squares in opposite corners of the big square. They overlap in a middle square of side b - (a - b) = 2b - a, and leave two corner squares of side a - b uncovered. Their total area equals the big square’s, so the area covered twice must equal the area not covered at all:

(2b - a)^2 = 2(a - b)^2.

Figure 1A sketch of the assumption a^2 = 2b^2, which no positive integers satisfy. The two b by b squares have the same total area as the big square, so the middle square they cover twice has the same area as the two corners they miss.

The picture can only ever be a sketch, since no positive integers make it exact. On a fraction that comes close, such as \displaystyle \frac{7}{5} with 7^2 - 2 \cdot 5^2 = -1, the same step walks down to smaller and smaller denominators until it stops (Exercise 17). An exact \displaystyle \frac{a}{b} would let the walk go on for ever through smaller and smaller positive integers, which is impossible.

Boundaries

The negation has to be complete. To prove “exactly one”, ruling out “two or more” leaves “none” open. To prove a strict inequality, ruling out “greater” leaves “equal” open. A proof that refutes only part of the negation has proved only part of the claim. The same care in proofs about figures is in indirect proof in geometry.

The contradiction must be with something true and already proved. A clash with a “fact” whose own proof used the claim goes round in a circle and proves nothing.

Nothing derived from the assumption survives it. Between the assumption and the contradiction the proof is reasoning about something that does not exist, and any fact found there is a fact about that impossible situation. Exercise 22 shows a valid-looking argument that goes wrong by starting from such an assumption and keeping its conclusion.

A contradiction must actually be reached. Copying the steps of Example 2 for \displaystyle \sqrt{4} ends at b^2 = k^2, which clashes with nothing (Exercise 18). An attempt that finds no contradiction proves nothing, either way.

Which square roots are irrational. For a positive integer n, \displaystyle \sqrt{n} is either a whole number or irrational. If every prime appears an even number of times in n, then n is the square of the number made with half as many of each prime, and \displaystyle \sqrt{n} is a whole number. Otherwise some prime p appears an odd number of times in n, and the counting in Example 5, applied to a^2 = nb^2 and the prime p, gives an even count on one side and an odd count on the other.

It can show that something exists without showing what it is. A proof by contradiction of “there is a number with this property” assumes there is none and reaches an absurdity, and it may never produce the number. The method rests on every statement being true or false, and one school of mathematics, constructive mathematics, does not accept this use of it for existence claims. Proofs like Example 2, which show a statement is false by assuming it and refuting it, are accepted there too.

Where this goes next

The argument that there are infinitely many primes, found in Euclid, is usually written as a proof by contradiction: suppose there are only finitely many, multiply them all together and add 1 (infinitely many primes). The same move, applied to a supposed list of every real number, builds a number missing from the list: the diagonal argument.

In geometry the method shows that two lines meet at most once and that one side of a triangle is shorter than the other two together: indirect proof. Assuming two objects with a property and showing they coincide is the shape of a uniqueness proof. Assuming that no container holds two items and counting is the pigeonhole principle. And the descent of Example 7, a smallest case followed by a smaller one, is the engine of well-ordering, where it proves statements about every positive integer by ruling out a smallest counterexample.

Exercises

Writing the assumption

Write the assumption that begins a proof by contradiction of each statement.

\displaystyle \sqrt{5} is irrational.
There is no largest integer.
For every integer n, n^2 + n is even.
At most one of the numbers x, y, z is negative.
For every integer n, if n^2 is odd, then n is odd.

Short proofs by contradiction

Prove that there is no smallest positive rational number.
Prove that there are no integers x and y with 6x + 9y = 100.
Prove that there are no integers x and y with x^2 = 4y + 3.
Prove that for every integer n, if n^2 is a multiple of 3, then n is a multiple of 3.
Prove that if r is a rational number other than 0 and x is irrational, then rx is irrational. Use it to show that \displaystyle \frac{\sqrt{2}}{7} is irrational.

Irrational numbers

Prove that \displaystyle \sqrt{5} is irrational by counting the prime 5 on each side.
Prove that \displaystyle \sqrt{6} is irrational.
Prove that \displaystyle \sqrt{3} - 4 is irrational.
Prove that \log_2 5 is irrational.
Try the argument of Example 6 on \log_4 8. Where does it break, and is \log_4 8 rational?
Prove that \displaystyle \sqrt{2} + \sqrt{3} is irrational. (Exercise 12 may be used.)
Apply the step of Example 7, (a, b) \mapsto (2b - a, a - b), three times starting from \displaystyle \frac{17}{12}. Write down each fraction and its value of a^2 - 2b^2. Why does the walk have to stop?

Reasoning

A student copies the proof of Example 2 to “prove” that \displaystyle \sqrt{4} is irrational. Follow the steps and say exactly where the proof breaks.
A proof reads: “Suppose n is even and n^2 is odd. Then n = 2k, so n^2 = 4k^2 = 2(2k^2) is even, which contradicts n^2 being odd.” Explain why this is really a direct proof, and rewrite it as one.
Explain why the negation of “every integer n has property P” is “some integer n does not have property P”, and not “no integer n has property P”.
In Example 2, explain why assuming the fraction is in lowest terms loses nothing. Then show how the proof could still be finished without that assumption.
Here is an argument. “Let N be the largest positive integer. Since N \geq 1, we have N^2 \geq N. But N^2 is a positive integer and N is the largest, so N^2 \leq N. Hence N^2 = N, and so N = 1: the largest positive integer is 1.” Every step follows from the one before. What is wrong, and what does the argument actually prove?

Answers

Suppose \displaystyle \sqrt{5} is rational: \displaystyle \sqrt{5} = \frac{a}{b} for some integers a and b with b \neq 0.
Suppose there is a largest integer: an integer N with N \geq n for every integer n.
Suppose some integer n has n^2 + n odd. One failure is enough to make “every” false, so the negation is about one integer, not all of them.
Suppose at least two of x, y, z are negative.
Suppose there is an integer n with n^2 odd and n even. The negation of “if P, then Q” is “P and not Q”.
Suppose r is the smallest positive rational number, \displaystyle r = \frac{p}{q}. Then \displaystyle \frac{r}{2} = \frac{p}{2q} is rational, and since r > 0, \displaystyle 0 < \frac{r}{2} < r. That is a positive rational smaller than the smallest one, a contradiction.
Suppose 6x + 9y = 100 for integers x, y. Then 100 = 3(2x + 3y), and 2x + 3y is an integer, so 100 is a multiple of 3. But 100 = 3 \cdot 33 + 1 leaves remainder 1 on division by 3, and a number has only one remainder. Contradiction.
Suppose x^2 = 4y + 3 for integers x, y. If x is even, x = 2k and x^2 = 4k^2, a multiple of 4. If x is odd, x = 2k + 1 and x^2 = 4(k^2 + k) + 1, one more than a multiple of 4. So x^2 leaves remainder 0 or 1 on division by 4, while 4y + 3 leaves remainder 3. A number has only one remainder, so this is a contradiction.
Suppose n^2 is a multiple of 3 and n is not. Then n = 3k + 1 or n = 3k + 2 for some integer k. In the first case n^2 = 3(3k^2 + 2k) + 1; in the second n^2 = 3(3k^2 + 4k + 1) + 1. Either way n^2 leaves remainder 1 on division by 3, so it is not a multiple of 3. Contradiction.
Suppose \displaystyle r = \frac{m}{n} with m \neq 0, n \neq 0, x irrational, and \displaystyle rx = \frac{p}{q} rational with q \neq 0. Since r \neq 0 we can divide: \displaystyle x = \frac{p}{q} \div \frac{m}{n} = \frac{pn}{qm}, with qm \neq 0. So x is rational, a contradiction. For the number given, \displaystyle \frac{\sqrt{2}}{7} = \frac{1}{7} \cdot \sqrt{2}, with \displaystyle \frac{1}{7} rational and not 0 and \displaystyle \sqrt{2} irrational (Example 2), so it is irrational.
Suppose \displaystyle \sqrt{5} = \frac{a}{b} with a, b positive integers. Then a^2 = 5b^2. The prime 5 appears 2s times in a^2, an even number, and 2t + 1 times in 5b^2, an odd number. One positive integer has one prime factorization, so this is a contradiction.
Suppose \displaystyle \sqrt{6} = \frac{a}{b} with a, b positive integers. Then a^2 = 6b^2 = 2 \cdot 3 \cdot b^2. The prime 2 appears an even number of times, 2s, in a^2, and 1 + 2t times in 6b^2, an odd number. That contradicts unique factorization.
Take r = -4, which is rational, and \displaystyle x = \sqrt{3}, irrational by Example 5. By Example 4, \displaystyle r + x = \sqrt{3} - 4 is irrational.
\log_2 5 > 0 because 5 > 1. Suppose \displaystyle \log_2 5 = \frac{a}{b} with a, b positive integers. Then 2^a = 5^b. The left side is even since a \geq 1; the right side is a product of odd numbers and so odd. Contradiction.
Supposing \displaystyle \log_4 8 = \frac{a}{b} gives 4^a = 8^b, and both sides are even, so the parity clash never comes. In fact 4^a = 2^{2a} and 8^b = 2^{3b} are equal whenever 2a = 3b, for instance a = 3, b = 2. So \displaystyle \log_4 8 = \frac{3}{2}, which is rational: \displaystyle 4^{3/2} = (\sqrt{4})^3 = 8.
Suppose \displaystyle \sqrt{2} + \sqrt{3} = r with r rational. Squaring, \displaystyle (\sqrt{2} + \sqrt{3})^2 = 5 + 2\sqrt{6} = r^2, so \displaystyle \sqrt{6} = \frac{r^2 - 5}{2}. The right side is rational, being built from a rational number by squaring, subtracting and halving. That contradicts Exercise 12.
The fractions are \displaystyle \frac{7}{5}, \displaystyle \frac{3}{2} and \displaystyle \frac{1}{1}. The values of a^2 - 2b^2 run 1 (for \displaystyle \frac{17}{12}), then -1, 1, -1: the step changes the sign of a^2 - 2b^2 and keeps its size, because (2b - a)^2 - 2(a - b)^2 = -(a^2 - 2b^2). The denominators fall 12, 5, 2, 1. At \displaystyle \frac{1}{1} the condition b < a fails and the next denominator would be 0, so the walk stops. If a^2 - 2b^2 were 0, it would stay 0 at every step and b < a < 2b would always hold, so the denominators would fall for ever, which positive integers cannot do.
From a^2 = 4b^2, a^2 is even, so a is even, a = 2k. Then 4k^2 = 4b^2, so b^2 = k^2. In Example 2 the corresponding line was b^2 = 2k^2, which made b even. Here nothing makes b even, so no clash with lowest terms appears, and there is no contradiction: indeed \displaystyle \sqrt{4} = \frac{2}{1}.
The assumption “n^2 is odd” is never used until the last line, where it is contradicted. The real work, from n = 2k to n^2 = 2(2k^2), is a direct proof. Written directly: let n be even, so n = 2k for an integer k; then n^2 = 2(2k^2) with 2k^2 an integer, so n^2 is even.
“Every integer has P” fails as soon as one integer lacks P, so its exact opposite is “at least one integer lacks P”. “No integer has P” is far stronger: both statements can be false at once, as with “every integer is even” and “no integer is even”. A proof that refuted only the stronger one would leave open the case where some integers have P and some do not.
If \displaystyle \sqrt{2} = \frac{a}{b}, let d be the greatest common divisor of a and b. Then \displaystyle \frac{a/d}{b/d} has the same value, integer top and bottom, a non-zero bottom, and no common factor bigger than 1. So any fraction for \displaystyle \sqrt{2} gives one in lowest terms, and the extra assumption claims nothing new. Without it, the proof shows a and b are both even; then \displaystyle \frac{a/2}{b/2} is another fraction for \displaystyle \sqrt{2} with the same property, so its top and bottom are even too, and so on. The positive denominator |b| would halve for ever, staying a positive integer each time, which is impossible.
The first sentence assumes a largest positive integer exists, and it does not: N + 1 is always larger. From a false assumption, valid steps can reach a false conclusion. Read correctly, the argument proves “if there were a largest positive integer, it would be 1”. Since 2 > 1, there is none, which is a proof by contradiction that no largest positive integer exists.