A common way to support induction is via the monologue: “It’s true for zero. Since it’s true for zero it’s true for one. Since it’s true for one it’s true for two. Continuing like this we can show that it’s true for one hundred and for one hundred thousand and for every natural number.” It’s hard to imagine actually going through this proof for very large numbers—this is Nelson’s objection.
Actually, for moderately large numbers it’s easy:
“Since it’s true for numbers one higher than numbers it’s true for, it’s true for numbers two higher than numbers it’s true for.”
”....two....four....”
”....four....eight...”
”....eight....sixteen...”
Of course, if that’s not fast enough you can try:
“Since it’s true for gaps double the size of gaps it’s true for, it’s true for gaps quadruple the size it’s true for”
”...quadruple… sixteen times...”
”...sixteen times...256 times...”
So, we’ve gone from N repetitions proving it for numbers up to N, to N repititions proving it for numbers up to 2^N, to N repititions proving it for numbers up to 2^(2^N). And we could continue.
Very nice. It’s interesting to think about how hard it would be to prove the proposition “3^^^3 is a counting number” using your trick but not using induction.
You’d have to meta my trick (apply it to itself) at least once. Probably several times.
ponders
Let’s go with 4s instead of 2s.
“Since it’s true for gaps of one, and 1+1+1+1 equals four, it’s true for gaps of four”
”....4....16....”
”....16....64...” So that’s 4^N
“Since it’s true for gaps 4 times larger than it’s true for, it’s true for gaps 444*4=256 times larger”
”...256...4 294 967 296...” so that’s 4^(4^N)
“Since it’s true for gaps the fourth power of gaps it’s true for, it’s true for the 256th power of gaps it’s true for”
”...256th power....4 294 967 296th power...”
That’s 4^(4^(4^N), or 4^^4 if N=4.
But I’m really struggling to get from that to 4^^^4
Actually, for moderately large numbers it’s easy:
“Since it’s true for numbers one higher than numbers it’s true for, it’s true for numbers two higher than numbers it’s true for.” ”....two....four....” ”....four....eight...” ”....eight....sixteen...”
Of course, if that’s not fast enough you can try:
“Since it’s true for gaps double the size of gaps it’s true for, it’s true for gaps quadruple the size it’s true for” ”...quadruple… sixteen times...” ”...sixteen times...256 times...”
So, we’ve gone from N repetitions proving it for numbers up to N, to N repititions proving it for numbers up to 2^N, to N repititions proving it for numbers up to 2^(2^N). And we could continue.
Very nice. It’s interesting to think about how hard it would be to prove the proposition “3^^^3 is a counting number” using your trick but not using induction.
You’d have to meta my trick (apply it to itself) at least once. Probably several times.
ponders
Let’s go with 4s instead of 2s.
“Since it’s true for gaps of one, and 1+1+1+1 equals four, it’s true for gaps of four” ”....4....16....” ”....16....64...” So that’s 4^N
“Since it’s true for gaps 4 times larger than it’s true for, it’s true for gaps 444*4=256 times larger” ”...256...4 294 967 296...” so that’s 4^(4^N)
“Since it’s true for gaps the fourth power of gaps it’s true for, it’s true for the 256th power of gaps it’s true for” ”...256th power....4 294 967 296th power...”
That’s 4^(4^(4^N), or 4^^4 if N=4.
But I’m really struggling to get from that to 4^^^4