Which proof is better?

[bunny]

Sqrt(2) is irrational.

Proof One:
Suppose Sqrt(2) = p/q where p and q are integers with no common factors.
implies 2 = p^2/q^2
implies 2q^2 = p^2
implies p^2 is even
implies p is even
implies p = 2k for some k
implies 2q^2 = (2k)^2
implies 2q^2 = 4k^2
implies q^2 = 2k^2
implies q is even
This contradicts original assumption, therefore Sqrt(2) cannot be written in the form p/q where p and q are integers with no common factors
Thus, Sqrt(2) is irrational.

Proof Two:
Suppose Sqrt(2) = p/q where p and q are integers with no common factors.
implies 2 = p^2/q^2
implies 2q^2 = p^2
since q = (a1^n1)(a2^n2)…..(ak^nk) for primes a1 to ak
and p = (b1^m1)(b2^m2)…..(bj^mj) for primes b1 to bj
this implies:
2(a1^2n1)(a2^2n2)…..(ak^2nk)=(b1^2m1)(b2^2m2)…..(b j^2mj)
This contradicts the fundamental theorem of arithmetic, since the prime decomposition of a number is unique and the power of 2 is odd on one side of this equation and even on the other.
Thus Sqrt(2) is irrational.

[madnak]

I say proof two. It's much more elegant and powerful.

[Borodog]

Proof one. Much simpler and clearer.

[jstnrgrs]

I understand proof 1 with no problem at all.

proof 2, I really have to think hard about to understand.

Therefore, I think proof 1 is better.

[SBR]

I voted neither, it probably depends on the context. I.e. proof 1 is much easier to understand therefore if you were teaching a high school class it would be "better". But the method used in proof 2 is more powerful.

[chezlaw]

p^2 is even implies p is even (in proof 1).) bothers me a bit.

Not cause its not true but p^2 is divisible by 23 therefore p is divisible by 23 wouldn't slip by so easily.

In proof 2) we get het up about p=q -> p and q have the same parity of the factor 2 which (keep dividing by two) amounts to much the same thing.

Anyway much prefer 2)

chez

[bunny]

[ QUOTE ]
p^2 is even implies p is even (in proof 1).) bothers me a bit.

Not cause its not true but p^2 is divisible by 23 therefore p is divisible by 23 wouldn't slip by so easily.

[/ QUOTE ]
Could probably solve your unease by referencing the theorem that odd numbers have odd squares and even numbers have even squares. There are a couple of unjustified steps in both but I think the gist is there.

[Borodog]

[ QUOTE ]
[ QUOTE ]
p^2 is even implies p is even (in proof 1).) bothers me a bit.

Not cause its not true but p^2 is divisible by 23 therefore p is divisible by 23 wouldn't slip by so easily.

[/ QUOTE ]
Could probably solve your unease by referencing the theorem that odd numbers have odd squares and even numbers have even squares. There are a couple of unjustified steps in both but I think the gist is there.

[/ QUOTE ]

Hmm. I took that to be intuitively obvious. Maybe it isn't.

[thylacine]

[ QUOTE ]
[ QUOTE ]
p^2 is even implies p is even (in proof 1).) bothers me a bit.

Not cause its not true but p^2 is divisible by 23 therefore p is divisible by 23 wouldn't slip by so easily.

[/ QUOTE ]
Could probably solve your unease by referencing the theorem that odd numbers have odd squares and even numbers have even squares. There are a couple of unjustified steps in both but I think the gist is there.

[/ QUOTE ]

Both proofs use that for p prime: if p divides ab then p divides a or p divides b.

[bunny]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
p^2 is even implies p is even (in proof 1).) bothers me a bit.

Not cause its not true but p^2 is divisible by 23 therefore p is divisible by 23 wouldn't slip by so easily.

[/ QUOTE ]
Could probably solve your unease by referencing the theorem that odd numbers have odd squares and even numbers have even squares. There are a couple of unjustified steps in both but I think the gist is there.

[/ QUOTE ]

Hmm. I took that to be intuitively obvious. Maybe it isn't.

[/ QUOTE ]
Ultimately it depends on the fundamental theorem of arithmetic in that it's a special case of "n^2 is divisible by prime p implies n is divisible by p also". Although I think the special case is intuitively obvious to people who have played around with numbers and arithmetic, I doubt the general case is, a la chezlaw's 23 example.

[bigpooch]

I would think Proof One is better because:

a) It's clearer; any intelligent person can folow it
b) It's concise; it's shorter
c) There are fewer algebraic symbols
d) The theorems or propositions that one needs to follow it
are simpler

If you could only pick one proof to show sqrt(2) is
irrational, which one would you pick?

On the other hand, if you wanted a "model proof" to show
that if n is not a square, sqrt(n) is irrational, then Proof
Two is more didactic.

Sometimes there are proofs that are much more complicated,
but shed light on something truly amazing or beautiful.
Most people are familiar with Euclid's proof of the
infinitude of primes, which is easy to follow. On the other
hand, a very elegant topological proof was found by
Furstenberg less than 50 years ago. This can be found at:

http://www.cut-the-knot.org/proofs/Furstenberg.shtml

That is just one example of a proof that many mathematicians
find interesting or elegant.

[evank15]

Not commenting on which one is better, but the argument used in proof 1 is known as "reductio ad absurdum", the most common method I've seen for proving root2 is irrational.

[CityFan]

Proof two depends on the fundamental theorem of arithmetic, which makes it messy an inaccessible.

In fact, proof one also depends on the fundamental theorem of arithmetic (p^2 is even
implies p is even) but I prefer to be spared the gory details.

[madnak]

[ QUOTE ]
b) It's concise; it's shorter

[/ QUOTE ]

Look again - P2 is shorter. And simpler, for that matter. It's definitely more abstract - I don't see that as a weakness.

[FortunaMaximus]

Neither. They end up saying the same thing.

[bigpooch]

Really? Depends on how you measure how long something is.
I use the number of keystrokes or characters.

Let's examine the actual text of the OP for the differences
(okay, the last line of the actual text of Proof One has an
extra comma, but materially does not differ in meaning from
the last line of Proof Two):

Proof One:

implies p^2 is even
implies p is even
implies p = 2k for some k
implies 2q^2 = (2k)^2
implies 2q^2 = 4k^2
implies q^2 = 2k^2
implies q is even
This contradicts original assumption, therefore Sqrt(2) cannot be written in the form p/q where p and q are integers with no common factors


Proof Two:

since q = (a1^n1)(a2^n2)…..(ak^nk) for primes a1 to ak
and p = (b1^m1)(b2^m2)…..(bj^mj) for primes b1 to bj
this implies:
2(a1^2n1)(a2^2n2)…..(ak^2nk)=(b1^2m1)(b2^2m2)…..(b j^2mj)
This contradicts the fundamental theorem of arithmetic,
since the prime decomposition of a number is unique and the power of 2 is odd on one side of this equation and even on the other.



Let me use keystrokes (okay, I might be off a little, since
I didn't double check!).

The keystrokes (including an end-of-line, which I take as a
delimiter for the text) for Proof One is around 283. For
Proof Two, it is around 365.

Which do you think is longer? I suppose we could put a
proof in one line of text, but it would not necessarily be
"shorter".

Sorry for being such a "super-nit"! /images/graemlins/smile.gif

[wazz]

Uh, don't they come to the same conclusion via the same lines? They are both 'reductio ad absurdiam' and they both rely on the fundamental theorem of arithmetic. I guess it's a question of which reference more external theories, so in that sense proof 2 is better. I hardly see how proof 2 is 'more powerful'.

[CityFan]

[ QUOTE ]
I guess it's a question of which reference more external theories, so in that sense proof 2 is better.

[/ QUOTE ]

You mean 2 is better because it DOES reference more external theorems, or because it doesn't?

Surely a self-contained proof is better, unless it is more complicated?

[bigpooch]

ONE
---

I would like to add that Proof One primarily uses two ideas:

[ Here, we take x,y, ... as integers. ]

The definiton of an even number.

a) An even number z is, by definition, divisible by two, so
there exists some integer k for which z = 2k. Thus, for any
integer j, the integer 2j is even. Also, by definition, an
even number has a factor of two.

Properties of square numbers. The property that is used
does NOT require the fundamental theorem of arithmetic.

b) If x^2 is even where x is an integer, then x is even.

Now, b) is equivalent to the contrapositive:

(Note that every integer is either odd or even: if one
divides an integer by two, the remainder is either zero or
nonzero)

b*) If x is not even, then x^2 is not even

or equivalently,

b**) If x is odd, then x^2 is odd.

This follows from the definition of an odd number: x is odd
implies there exists an integer m such that x = 2m+1. Also,
if n is any integer, 2n+1 is odd.

Proof of b**):

If x is odd, there is some integer m such that x = 2m+1.
x^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1.
Thus, x^2 is odd.

TWO
---

Proof Two uses the Fundamental Theorem of Arithmetic, and
although I agree that Proof Two is quite elegant, it still
boils down to the definition of odd and even numbers
(consider the exponents). So, essentially, Proof Two only
uses two ideas: a theorem and the definition of an even
number. Of course, one of the ideas (the theorem), is not
necessarily obvious to a layperson.


BETTER?
-------

It is somewhat subjective, and those that chose Proof Two
may have been swayed by the "aesthetics", and if that were
the only (or primary) criteria for choosing which is better,
then I would have chosen Proof Two. The primary reason for
choosing Proof One is that it does not rely on more complex
results and that was what I was trying to convey in my
previous post on this thread (e.g., proofs of the
infinitude of primes).

I think Proof One is better for the layperson or somebody
who wants to prove results from more basic or obvious
results.

Proof Two is better to illustrate how powerful a theorem can
be to prove other results or to give an elegant proof.

[madnak]

The text is irrelevant. Either proof could be expressed very gracefully, given the appropriate cypher. In fact, relatively basic symbols would suffice to render each of these proofs down to <100 keystrokes.

Proof One has more steps, however.

[madnak]

[ QUOTE ]
I hardly see how proof 2 is 'more powerful'.

[/ QUOTE ]

Proof Two is more extensible and more intuitive, and therefore has a more powerful impact on the understanding. I read Proof One, I learn that 2 is irrational. I read Proof Two, I learn why 2 is irrational. I learn about other roots, I can even extend some of the understanding to exponential functions, to discrete math, to combinatorics... Proof Two is eye-opening.

[bunny]

[ QUOTE ]
Proof Two is more extensible and more intuitive, and therefore has a more powerful impact on the understanding. I read Proof One, I learn that 2 is irrational. I read Proof Two, I learn why 2 is irrational. I learn about other roots, I can even extend some of the understanding to exponential functions, to discrete math, to combinatorics... Proof Two is eye-opening.

[/ QUOTE ]
This is why I prefer two as well - it leaves you with some insight into why the result holds, rather than with just a fact about a number. I do think it is harder to understand (although this is partly because it requires more complicated notation which doesnt translate to the internet so well - on paper the notation is not so clumsy imo).

My rather limited survey (around 50 mathematicians) shows a pretty clear (and predictable) distinction between pure mathematicians who prefer the second and applied mathematicians who prefer the first. There have been some exceptions, but not very many.

[CityFan]

Count me as another exception then. I like proof one. I can extend it to other roots fairly easily if I like, too.

I like generality, but if you want to be general then prove a general result.

[holmansf]

I am rather surprised that so many people favor proof 1. I think proof 2 is way better. I think folks are just scared of the "fundamental theorem of arithmetic," even though it is used implicitly in proof 1.

[bunny]

[ QUOTE ]
I am rather surprised that so many people favor proof 1. I think proof 2 is way better. I think folks are just scared of the "fundamental theorem of arithmetic," even though it is used implicitly in proof 1.

[/ QUOTE ]
Well, of course it hinges on what people think makes a good proof which was intentionally left unspecified. I'm more surprised that there arent more "neither" answers, since I had kinda expected this forum to be full of "maths is just a language game - premises to conclusions according to set rules, it doesnt matter how you get there" type people.

[bunny]

[ QUOTE ]
Count me as another exception then. I like proof one. I can extend it to other roots fairly easily if I like, too.

I like generality, but if you want to be general then prove a general result.

[/ QUOTE ]
You dont think proof two generalises more readily? Just replace "2" with "p for any prime p". I think this is its strength - generalising proof one is not so straightforward (although clearly possible since they ultimately depend on the same thing).

[bigpooch]

Technically, Proof One DOES NOT use the fundamental theorem
of arithmetic, but rather uses the result that the square of
an odd integer is odd (or equivalently, if a square of an
integer is even, then the integer is even).

[bigpooch]

Not just that, but from Proof Two, the following proposition
can be readily proven:

For any positive integer, its kth root (where k is an
integer >=2), on the positive real line, is either a
positive integer or irrational (there is no such result that
is rational but not an integer).

[bigpooch]

So, because I studied both pure and applied mathematics,
would you say that I was an applied mathematician or an
exception? /images/graemlins/smile.gif

[FortunaMaximus]

lol, depends on the rule. /images/graemlins/smirk.gif

[bunny]

[ QUOTE ]
So, because I studied both pure and applied mathematics,
would you say that I was an applied mathematician or an
exception? /images/graemlins/smile.gif

[/ QUOTE ]
I would say you were corrupted but I will pray for your platonic soul.
/images/graemlins/tongue.gif