Geekage and Christmas Slack

[lederhosen]

First off, a reminder that I am a slack and disorganised person. As such I'm not very good with Christmases, prone to forgetting people I should remember or not getting around to doing stuff I should do. So, because I will inevitably miss somebody or something I ought to do, this is my Christmas "I love you all" post :-)

And some maths geekage, reworded from this site:

Proof That All Positive Integers Are Equal

Note that if we can prove "if A and B are positive integers less than or equal to n, then A=B" [let's call this statement S(n)], for all positive integer n, then the above follows.

Note that S(n) is trivially true for n=1: if A and B are positive integers less than or equal to one, they must equal one (and hence, one another).

Next, we look at an inductive step. Let's suppose that the above statement S(n) is true for all values of n up to and including some k.

Now, let's suppose A and B are less than or equal to k+1.

Therefore, A-1 and B-1 are less than or equal to k. Thus, A-1 = B-1, and so A=B.

Therefore, is S(n) is true for all values of n up to and including k, it's true for all values of n up to and including k+1. Having proved that S(n) is true for n=1, it follows that it is true for all positive integer n.

It took me a while to spot the trick here... a gold star to the first one who gets it :-)

Comments

[chaos-crafter.livejournal.com]

First one that springs to mind is the claim that...
Now, let's suppose A and B are less than or equal to k+1.

Therefore, A-1 and B-1 are less than or equal to k. Thus, A-1 = B-1, and so A=B.


First part is OK, Second part (A-1,B-1 =< k) is OK, but A-1 = B-1 is not implied by the prior statements.

Is that the key detail?
It sort of gets lost 'cause you're busy thinking in terms of the S function, so you think in terms of S(A-1)=S(B-1) not A-1=B-1

[lederhosen.livejournal.com]

First part is OK, Second part (A-1,B-1 =< k) is OK, but A-1 = B-1 is not implied by the prior statements.

How so? The prior part implies that any two positive integers =< k must be equal...

[panacea1.livejournal.com]

This kind of thing is the reason I barely graduated from college. Am highly prone to writing things like "Because it's patently absurd, that's why; here's the counterexample" on exam papers.

That having been said, I -think- the problem is that you never actually proved S(n) was true for k>1, and if I recall correctly you have to do so in order to be inductive over the integers. Show it's true for 1, show it's true for some integer k>1, and it's got to be true for the rest of them...

[lederhosen.livejournal.com]

Usually, induction only requires that you prove S(1) and "if S(k), then S(k+1)".

New thought.

[shadow-5tails.livejournal.com]

This could be as whacked as my previous comment seems to me now.  I'm probably just proving my ignorance.  Again.  But...

Take the example that k=1.

If A and B =< k=1, and there are four possibilities.

(A,B) = (1,1), (1,2), (2,1), (2,2)

In the first and last case, A=B, and all is good.

But in BOTH of the cases where A != B, taking A-1 and B-1 leaves you with a zero somewhere along the way. If you are constrained to working with positive integers, things break here, since 0 isn't one.

Is that it, or am I as idiotic as I feel at the end of a working day?

[shadow-5tails.livejournal.com]

Er, and of course "k=1" should be "k+1" in the third line.

I must be as idiotic as I feel...

Re: New thought.

[lederhosen.livejournal.com]

Got it :-) The fallacy is the unspoken assumption that A-1 and B-1 will still be positive integers. This allows us to sneak in a claim that amounts to "1=2", and from there anything can be proven...

[shadow-5tails.livejournal.com]

I can't believe that's actually it.

So, do I get rewarded, sirrah?

[lederhosen.livejournal.com]

But of course.

*plots*

[ambitious-wench.livejournal.com]

You said: "if A and B are positive integers less than or equal to n, then A=B" [let's call this statement S(n)], for all positive integer n, then the above follows."

There are a whole lot of positive integers. A doesn't HAVE to equal B all the time.

They could be different numbers, right?

Or am I way off here?
Edie
(And I made a point of not reading the other comments first.)

[lederhosen.livejournal.com]

Way off :-)

The whole point of the 'proof' is to show that A *does* have to equal B. If you can show that (a) "all positive integers LE k equal one another" implies "all positive integers LE (k+1) equal one another", and (b) that all positive integers LE 1 equal one another, then the rest of the proof is ironclad.

(b) is perfectly true, and (a) is... very nearly true.

[sythyry.livejournal.com]

A-1 need not be a positive integer, even if A is a positive integer; so the induction hypothesis does not apply. (That's why I like structural induction rather than induction on numbers. Much harder to make that sort of mistake.)

[lederhosen.livejournal.com]

Remind me, which one's structural induction?