Re: Goodstein's Theorem

Hi Gene,

Thanks for the reminder of Goodstein's theorem
as an example of an interesting result that
requires extra axioms (about ordinals - orderings of
infinite sequences) to prove.

Another version of it, I can't remember
if it is a separate theorem or a restatement
of it, is the Hercules and
the Hydra battle, where Hercules
battles against a hydra which is a
kind of bushy tree shape in structure and
every time he cuts off one of its
heads, it sprouts several more at a lower
level in the tree. Sprouts numerous
heads and it seems that he could never
possibly win, but when you look at the
problem using transfinite ordinals
you see rather easily that he can.
Ends with a bush with a more
than astronomical number of twigs
all on the first level and then
from then on he just needs to
persevere for a truly enormous
but finite number of moves to get
rid of them all one at a time.
Rather fun.

It is an interesting question, whether
these undecidable theorems have to involve
rapidly growing functions, or whether
one day something which doesn't
directly refer to rapidly growing
functions, like existence
of an odd perfect number or such
like might be proved to be
independent as well.

Robert

--- In metatuning@yahoogroups.com, "Robert Walker"
<robertwalker@n...> wrote:
> Hi Gene,
>
> Thanks for the reminder of Goodstein's theorem
> as an example of an interesting result that
> requires extra axioms (about ordinals - orderings of
> infinite sequences) to prove.
>
> Another version of it, I can't remember
> if it is a separate theorem or a restatement
> of it,

The latter.

> is the Hercules and
> the Hydra battle,

Yes -- this is illustrated in the link I provided:

http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/

--- In metatuning@yahoogroups.com, "Robert Walker"
<robertwalker@n...> wrote:

> It is an interesting question, whether
> these undecidable theorems have to involve
> rapidly growing functions, or whether
> one day something which doesn't
> directly refer to rapidly growing
> functions, like existence
> of an odd perfect number or such
> like might be proved to be
> independent as well.

Ramsey functions grow quickly, but the Paris-Harrington theorem is
not directly about rapidly growing functions, but is just a theorem
of Ramsey theory. More interesting I think is Shelah's result that
the Whitehead problem (does Ext^1(A, Z)=0 mean A is a free abelian
group?) is unprovable in ZFC. In other words, if B is an abelian
group and f : B ¨ A is a surjective group homomorphism whose kernel
is isomorphic to the group of integers Z, then there exists a group
homomorphism g : A ¨ B with fg = idA. I've copied and pasted this from

http://en.wikipedia.org/wiki/Whitehead_problem

By the way, we've applied abelian groups to music theory, but what
about Ramsey theory?

Hi Gene,

http://en.wikipedia.org/wiki/Whitehead_problem

Fascinating! Thanks for pointing it out -
somehow I missed out on this one and it is
completly new to me that there are undecidable
algebraic results like that.

Yes I remember the Paris Harrington theorem,
though not very clearly now.
It does use rapidly growing functions indirectly
somehow doesn't it? I seem to remember
that its unprovability is something to
do with rapidly growing functions but
my memory is a bit hazy about it.

I enjoyed Ramsey theory though, would be fun
to try and find an application of it to tuning
indeed. I wonder - after all finding triads
and tetrads in scales is the sort of thing
you could think easily might lead to a
Ramsey theory type problems.

Robert

--- In metatuning@yahoogroups.com, "Robert Walker"
<robertwalker@n...> wrote:
> Hi Gene,
>
> http://en.wikipedia.org/wiki/Whitehead_problem
>
> Fascinating! Thanks for pointing it out -
> somehow I missed out on this one and it is
> completly new to me that there are undecidable
> algebraic results like that.

When I was a grad student and first heard this it blew me away,
because I thought of Ext as being something you could in principle
compute, and we are, after all, only talking about abelian groups. In
algebra it doesn't get much easier than that.

> Yes I remember the Paris Harrington theorem,
> though not very clearly now.
> It does use rapidly growing functions indirectly
> somehow doesn't it?

I seem to remember it's more like a nonstandard model kind of
argument, but I'd have to look it up. But Ramsey numbers are fast-
growing.

> I enjoyed Ramsey theory though, would be fun
> to try and find an application of it to tuning
> indeed. I wonder - after all finding triads
> and tetrads in scales is the sort of thing
> you could think easily might lead to a
> Ramsey theory type problems.

Exactly--"either you get this kind of a chord, or you get that kind
of a chord".