Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Ordinal numbers and non-recursively enumerable sets
Posted:
Feb 23, 2012 2:45 PM
|
|
In article
<00019b02-db4c-4641-a59e-e3b6d5391f77@l14g2000vbe.googlegroups.com>,
Dick <DBatchelo1@aol.com> wrote:
> Ordinals count the number of elements in a set. Does every set have an
> appropriate ordinal?
>
> An infinite recursively enumerable set obviously has the associated
> ordinal ³omega.² If Achilles is chasing the tortoise he is halfway at
> event 1, 3/4 the way at event 2 etc. He reaches the tortoise at event
> omega. However, he may choose to consider each of these a subgoal and
> measure his progress towards achieving this subgoal in the same way.
> In this case, he actually reaches the tortoise at event ³omega^2"
> I believe that any constructable ordinal can be interpreted in this
> way. (My imagination fails beyond omega^2.)
> Not all sets are recursively enumerable. A ³productive set², S has the
> property that it has a recursive ³productive function², f. If A is any
> recursively enumerable subset of S then f(A) is a member of S that is
> not in A.
> What is the appropriate ordinal number to associate with S? I think
> that it is ³omega-1-CK², the ³Church-Kleene ordinal, the smallest
> ordinal that is larger than any constructable ordinal.
It's hard to say what the answer is since it's not at all
clear what you mean by the appropriate ordinal associated
with a set. Luckily there's a bit of utter nonsense below,
so one might not feel constrained to worry about whether
there's anything real behind what's above:
> Another kind of set that is not recursively enumerable is an ³immune²
> set. An immune set has the property that it does not contain ANY
> infinite recursively enumerable subset. (Immune sets do exist.)
> A particular immune set will contain a maximal recursively enumerable
> subset. Suppose that this contains n¹ members.
What? Any finite set is re. So an immune set does not contain
a maximal re subset.
> What ordinal should be
> associated with such a set? You can¹t number off more than n¹ items.
> However, to say that its ordinal is n¹ seems ridiculous; it is
> fundamentally different from a finite set with n¹ elements. Perhaps
> we should define a new ordinal; ³blob², and say that an immune set
> contains ³blob+n² items. The trouble that I see with this is that I
> can see no way to claim that two sets with ³blob² elements have the
> same number of elements. Certainly there is no mapping from one to the
> other.
>
> Perhaps it is meaningless to try to associate an ordinal with an
> immune set. Can anyone help me?
--
David C. Ullrich
|
|
|
|
