Live data from Hacker News

A proof of proof by infinite descent

relatedwork.blogspot.com

11–20 of 60 posts

Re: A proof of proof by infinite descent

#11
I like that the article uses the concrete example of proving √2 is not rational to demonstrate the abstract priciples of induction, while also not hand-waving away the formal details of the general case.

I got a little caught up on on the proof of (no) infinite descent by well-founded induction without a base case. I thought, "something is wrong; (∀y∈X.y⊏x⟹¬Φ(y)) only implies ¬Φ(x) if you assume (∀y∈X.y⊏x⟹¬Φ(y)) in the firsts place". But that's actually fine, because the principle of well-founded induction lets you assume it out of thin air, and as long as it implies ¬Φ(x), you're good.

The intuition of this, to me at least, is that well-founded induction has an implicit base case of the empty set. (∀y∈X.y⊏x⟹Ψ(y))⟹Ψ(x) means Ψ(x) is required to be automatically true if ∄y∈X, so (∀y∈X.y⊏x⟹Ψ(y)) may be assumed out of thin air and then used inductively for all the cases where ∃y∈X.

Back to the specific example, ¬Φ(x) is automatically true if ∄y∈X because Φ(x) implies ∃y∈X. However note that this base case doesn't need to be explicitly shown, because it's included in the general case.

Re: A proof of proof by infinite descent

#12
> a well-founded relation ⊏ is a well-ordering if and only if it relates every distinct pair of elements, i.e. x1≠x2 implies either x1⊏x2 or x2⊏x1.

The author here explains well-founded relation prior to this. I want to add an example here. Consider the set of positive real numbers. If we use the natural ordering < then we have a total order. But that's not a well-ordering. If x were to be the least element you could always divide it by 2 to get a lesser element. So there's no least element in the set of positive reals using the conventional < ordering. However, the amazing thing is that assuming axiom of choice, such a well ordering exists.

Re: A proof of proof by infinite descent

#14
post #12

> a well-founded relation ⊏ is a well-ordering if and only if it relates every distinct pair of elements, i.e. x1≠x2 implies either x1⊏x2 or x2⊏x1. The author here explains well-founded relation prior to this. I want to add an example here. Consider the set of positive real numbers. If we use the natural ordering < then we have a total order. But that's not a well-ordering. If x were to be the least element you could…

I think maybe you're overlooking "a well-founded relation ⊏ is a well-ordering …". < on the reals is not well-founded. Remember, a well-founded relation requires all leftward chains to be finite. Together with the rest of the given definition, it implies a unique least element.

Re: A proof of proof by infinite descent

#15
post #12

> a well-founded relation ⊏ is a well-ordering if and only if it relates every distinct pair of elements, i.e. x1≠x2 implies either x1⊏x2 or x2⊏x1. The author here explains well-founded relation prior to this. I want to add an example here. Consider the set of positive real numbers. If we use the natural ordering < then we have a total order. But that's not a well-ordering. If x were to be the least element you could…

I think maybe you're overlooking "a well-founded relation ⊏ is a well-ordering …". < on the reals is not well-founded. Remember, a well-founded relation requires all leftward chains to be finite. Together with the rest of the given definition, it implies a unique least element.

Yes you are right. My bad. I edited my original comment.

Re: A proof of proof by infinite descent

#16
post #2

> I imagine that one could also prove that √−1 is not rational I feel like this was a marvellous joke but I can’t prove it.

I think that the reasoning is the same:

* sqrt(-1) = a/b

* a^2 = -1 * b^2

Then either a^2 or b^2 are negative but a square can't be negative, so contradiction and sqrt(-1) is not rational.

The main "problem" with this proof (and the original with sqrt(2)) is "how to prove that a^2 >= 0" (or that "if a^2 is even, then a is even")

The first one is easy to prove:

* a^2 = sign(a)^2 * abs(a)^2

* abs(a) >= 0 for any a

* sign(a) = 1 or -1 for any a so sign(a)^2 = 1 (either 1*1 or -1*-1)

* so a^2 >= 0

The second one may be proved:

* Assume a is even, then a=2n, then a^2=4n^2=2*(2n^2) so a is even => a^2 is even

* Assume a is odd, then a=2n+1, then a^2=4n^2+4n+1=2*(2n^2+2n)+1, then a^2 is odd

* a is either even or odd

* So the only possibility for a^2 to be even is for a to be even

Re: A proof of proof by infinite descent

#17
post #2

> I imagine that one could also prove that √−1 is not rational I feel like this was a marvellous joke but I can’t prove it.

Taking the square root of -1 is not only an irrational thing to do but bloody daft. QED 8)

i tends to pop out as a construction so I suspect you can probably prove it is both rational and irrational or neither, depending on the fine print.

Here's a discussion: https://math.stackexchange.com/questions/823970/is-i-irratio...

Re: A proof of proof by infinite descent

#18
post #4
post #3

Earlier quoted context omitted.

You'd be surprised at the number of things that appear to be self-evidently true that turn out to depend on tacit assumptions. For example, is 7 prime? Not if you're doing modular arithmetic.

i think they were joking, but i can't prove it

Maybe -i can.

Re: A proof of proof by infinite descent

#19
post #6

Earlier quoted context omitted.

It's also independently pretty tedious to explain that 7 is prime to a proof checker.

Is it? You can tell the checker about the remainder of division by 2 to 6.

Maybe also need to show that there are no other naturals between 1 and 7? And also that numbers greater than 7 can't be a divisor of 7?

Re: A proof of proof by infinite descent

#20

I like that the article uses the concrete example of proving √2 is not rational to demonstrate the abstract priciples of induction, while also not hand-waving away the formal details of the general case. I got a little caught up on on the proof of (no) infinite descent by well-founded induction without a base case. I thought, "something is wrong; (∀y∈X.y⊏x⟹¬Φ(y)) only implies ¬Φ(x) if you assume (∀y∈X.y⊏x⟹¬Φ(y)) in t…

> well-founded induction has an implicit base case of the empty set

Yes, but that still means the reasoning that proves the induction has to be valid for the empty set--i.e., "if P is true for all y less than x, then P is true for x" has to be validly proven for the case that there are no y less than x--which of course is the case for the natural number 0 in ordinary mathematical induction.

Post reply on HN