Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Math Bite: Irrationality of √m (1999)

fermatslibrary.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Math Bite: Irrationality of √m (1999)

#21

Post by jfarmer »

jameshart wrote: post #18
vog wrote: post #9

Earlier quoted context omitted.

> I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer I see what the author meant by that. I just think it was stated in a slightly exaggerated way. The "divisibility properties" of the integers are still used. That part has just has been moved to another corner of the proof, by transforming fractional equations. One of the comments in the article is…

Indeed - I think the claim that alpha can be expressed as p/q with some 'lowest q' seems to rest on divisibility properties.

No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element.

And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction).

[1]: https://en.wikipedia.org/wiki/Presburger_arithmetic

Re: Math Bite: Irrationality of √m (1999)

#22

Post by jfarmer »

vog wrote: post #9
jfarmer wrote: post #8

Earlier quoted context omitted.

By "doesn't use divisibility" I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer, not that division is never used. In particular, this proof doesn't rely on the fundamental theorem of arithmetic.

> I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer I see what the author meant by that. I just think it was stated in a slightly exaggerated way. The "divisibility properties" of the integers are still used. That part has just has been moved to another corner of the proof, by transforming fractional equations. One of the comments in the article is…

As near as I can tell, this proof would work in any well-ordered integral domain D where D's field of fractions would the role of the rationals. The analogue of the standard proof would require that D also be a unique factorization domain (or maybe the slightly weaker condition that any two elements have a GCD).

It might be the case that all these properties together "force" D to be a UFD or that the author snuck another property of the integers in there, but I've only taken a cursory look.

Re: Math Bite: Irrationality of √m (1999)

#23

Post by vog »

contravariant wrote: post #13
vog wrote: post #2

That proof is really great! It's always nice to see alternatives to well-known proofs. This demonstrates that you can always tackle problems from different angles. However, I slightly disagree with the introduction of the proof: | The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. That's quite a bold statement. It would mean…

>> The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. >That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. It doesn't, for the somewhat obvious reason that divisibility makes sense in any set that has a notion of 'multiplicat…

> According to the proof the fractions are in Q not R.

That's a circular argument. During the proof this is not given, only after the proof.

Re: Math Bite: Irrationality of √m (1999)

#24

Post by contravariant »

vog wrote: post #23
contravariant wrote: post #13

Earlier quoted context omitted.

>> The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. >That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. It doesn't, for the somewhat obvious reason that divisibility makes sense in any set that has a notion of 'multiplicat…

> According to the proof the fractions are in Q not R. That's a circular argument. During the proof this is not given, only after the proof.

During the proof it is assumed, this assumption leads to a contradiction, hence the assumption 'sqrt(m) is in Q' is false.

The reason this is not a circular argument is that they don't assume the thing they're trying to prove, but rather it's negation.

Re: Math Bite: Irrationality of √m (1999)

#25

Post by vog »

contravariant wrote: post #24
vog wrote: post #23

Earlier quoted context omitted.

> According to the proof the fractions are in Q not R. That's a circular argument. During the proof this is not given, only after the proof.

During the proof it is assumed, this assumption leads to a contradiction, hence the assumption 'sqrt(m) is in Q' is false. The reason this is not a circular argument is that they don't assume the thing they're trying to prove, but rather it's negation.

You are right. My bad.

Re: Math Bite: Irrationality of √m (1999)

#26

Post by jfarmer »

brlewis wrote: post #17

> We may assume that q is as small as possible (Estermann's key idea) Making the denominator as small as possible uses divisibility.

No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element.

And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction).

[1]: https://en.wikipedia.org/wiki/Presburger_arithmetic

Re: Math Bite: Irrationality of √m (1999)

#27

Post by brlewis »

jfarmer wrote: post #26
brlewis wrote: post #17

> We may assume that q is as small as possible (Estermann's key idea) Making the denominator as small as possible uses divisibility.

No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle ho…

alpha = p/q where p and q are positive integers.

It's finding the set of all possible q that uses divisibility, not finding the least member of that set.

Post reply on HN