Turing Compliant?

[Tim Peters]

[Graham Matthews, in the midst of explaining the conventional distinction
 between "unbounded" and "infinite" wrt Turing machines]
> We won't even bring up that the cardinality of this set is even larger
> than the simply unbounded enumerable sets.

[Travis Oliphant}
> I suppose I shouldn't go there but the infinitity of infinities is a
> concept that has always enchanted me.
>
[William Tanksley]
> Not to mention the number of infinities -- are there more than two of them
> (countable and uncountable)?  Cohen proved that the question isn't
> answerable

Don't go provoking Uncle Timmy into joining a thread, or c.l.py will never
have peace again.

Long before Cohen, Cantor proved that the number of infinities is, as Travis
intimates, "infinite".  Specifically that given any set S, the powerset of S
(set of all subsets of S) has cardinality strictly greater than the
cardinality of S.  In its simplest form, this is the "diagonalization"
argument that proves the set of reals can't be put into 1-to-1
correspondence with the ints.  The same kind of trick can be pulled on the
powerset of reals, though, and ad infinitum.

What Cohen proved is much trickier to explain, although easy to state
<wink>:  both the Generalized Continuum Hypothesis (GCH) and its negation
are consistent with the usual axioms of set theory.  Cantor proved that
there's an infinite sequence of ever-increasing cardinals, via his powerset
construction.  GCH says that "the next" cardinal after the cardinality of a
set S is in fact the cardinality of S's powerset.

For many years this was a topic of hot debate:  it takes some time to
appreciate just how big the set of all integers really is, and a much longer
time to appreciate just how much larger (quite amazingly & mind-bogglingly
larger -- really!) the set of reals is.  The set of reals is *so* frigging
"big" that many workers felt there must be at least one cardinal between
that of the ints and that of the reals.  But they were never able to
construct a set with intermediate cardinality, and Cohen proved that-- given
the accepted axioms --it was impossible either to prove that such a beast
existed, or that it didn't.

That doesn't mean the question is undecidable "in reality", it means only
that the common axioms aren't strong enough to decide it one way or the
other.  There's since been a very long & difficult search for other axioms
we could add that *would* decide it one way or the other; unfortunately,
last I knew all such attempts added highly technical axioms with a decidedly
contrived flavor.  You don't want that in an axiom system.

Some people have since decided that mathematics is purely an invention, and
there is no Platonic truth about the matter waiting to be discovered.  You
can find them over in comp.lang.perl.misc, despite that Guido is likely one
of them <wink>.

> -- the first proof-by-example of Godel's Law.

Thou shalt not commit adultery?  Or don't say things you don't mean unless
you can't prove they're unprovable?  Or an axiom saved is an axiom earned?

Note that G's Incompleteness Theorem constructed a specific, concrete
example of an undecidable proposition, so in that sense it came with its own
first example.  In a larger sense, independence of axioms is a very old
phenomenon, e.g. that Euclid's parallel postulate is independent of the
other axioms of plane geometry (so is, in the same sense, "undecidable" wrt
them).

unfortunately-this-means-python-and-perl-may-eventually-
    meet-at-a-point-ly y'rs  - tim