Homework Help: What is wrong w/ this Proof

1. May 19, 2006

mattmns

In the book I am reading, there is this question that says the following:
---------
What is wrong with the following proof that 1 is the largest integer?

Proof: Let n be the largest integer. Then, since 1 is an integer we must have $1 \leq n[/tex]. On the other hand, since [itex]n^2$ is also an integer we must have $n^2 \leq n$ from which it follows that $n \leq 1[/tex]. Thus, since [itex]1 \leq n[/tex] and [itex]n \geq 1[/tex] we must have n = 1. Thus 1 is the largest integer as claimed. ---------- I know the proof should not be valid, as it is obviously not true, and in fact in the previous question was I had to prove that there does not exist a largest integer, I just cannot find what is wrong in this proof. Now, the last two sentences are valid in my opinion, if we assume that the previous part of the proof is true, so I am thinking it has nothing to do with those last two sentences. The part I don't like is where [itex]n^2$ is introduced and the dividing by n that follows. This is where I feel the proof becomes invalid, but I cannot find a reason for this yet. Any ideas? Thanks!

Last edited: May 19, 2006
2. May 19, 2006

durt

First off, the proof deals with natural numbers, not integers. The problem is the $n^2 \leq n$ bit. Saying this means that $3^2 \leq 3$, which is obviously false.

3. May 19, 2006

Quaoar

I think this is because "largest integer" is not defined in the first place.

Imagine how silly it sounds if I say "100 is the largest integer."

4. May 19, 2006

Hurkyl

Staff Emeritus
You can't find an error because it's correct:

(There exists a largest integer) ==> (1 is the largest integer)

is a true statement.

5. May 19, 2006

Curious3141

What Hurkyl is saying is that there is no problem with the steps in the proof. The conclusion "proved" from the premise is an absurd one, hence the premise (of a largest natural number) is false. This is in fact a proof by contradiction, just not written out properly.

6. May 19, 2006

mattmns

No the proof deals with integers, my book has never even defined natural numbers, here it just happens that we are using integers greater than or equal to 1. Also, how does saying $n^2 \leq n[/tex] mean [itex]3^2 \leq 3$ ??? In my opinion, all it means is that n = 1. As if we divide both sides by n, a positive integer, we get $n \leq 1$, but n is a positive integer, so n = 1.

edit... Huh, I would have never thought they would have been looking at something like that! Thanks!!

Last edited: May 19, 2006
7. May 19, 2006

AKG

The says "Let n be the largest integer." This assumes that there exists a largest integer. This is a false assumption, so the argument is invalid. It depends on how you look at it. If you regard "let n be the largest integer" a premise, then it is valid, but normally you don't look at an argument like the above in such a manner. You regard any statement made as one that ought to be derived from axioms/rules of inference. The argument above is not saying just that "if there exists a largest integer, then 1 is it," it is also implying that there is a largest integer, so it is an invalid proof.