Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Uncountable Diagonal Problem
Replies: 52   Last Post: Jan 6, 2013 2:43 PM

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 894 Registered: 6/29/05
Re: Uncountable Diagonal Problem
Posted: Dec 30, 2012 4:32 AM

On Dec 30, 2:47 am, William Elliot <ma...@panix.com> wrote:
> A list of length eta, is a function from the ordinals < beta

I would call that a list of length beta, not eta.

> to a set of items.  Mega-sequence will be used as a synonym for list.

The usual term for such an object is "transfinite sequence".

> How long does a list without duplicates of infinite binary series (IBS)
> have to be to force the list to have every IBS?

I assume that by "series" you mean "sequence", and that by "infinite
binary series" you mean "binary sequence of length omega", in other
words, "element of {0, 1}^{omega}". And by "list without duplicates" I
suppose you mean "injective map from some ordinal". In plain language,
then, you seem to be asking the following:

"Let S = {0, 1}^{omega}. What is the least ordinal beta such that
every injective map from beta to S is surjective?"

More generally, let S be *any* infinite set. Trivially, if there is an
injective map from an ordinal beta to S, then there is an injective
map from that same ordinal beta to a proper subset of S. Even more
trivially, if there is no injective map from beta to S, then every
injective map from beta to S is surjective. Consequently, the least
ordinal beta from which every injective map from beta to S is
surjective is the same as the least ordinal beta for which there is no
injective map from beta to S; moreover, assuming the axiom of choice,
it's the same as the least ordinal beta such that |beta| > |S|.