Re: Co-re set with no infinite r.e. subset

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 09/07/04 

Date: Tue, 07 Sep 2004 06:48:28 -0500

On 7 Sep 2004 03:51:11 -0700, daryl@atc-nycorp.com (Daryl McCullough)
wrote:

>Is there an easy example of an infinite set of naturals that has no infinite
>r.e. subset?

not sure how easy it has to be. here's a proof that there is such a
thing that can't be -too- hard, since i didn't know the answer a
minute ago:

let s[1], s[2], ... be an enumeration of the infinite re sets.
choose n[1] in s[1]. choose m[1] > n[1]. choose n[2] > m[1]
with n[2] in s[2]. choose m[2] > n[2]. etc.

let s be the set of all the m[k]'s. then s is infinite, and
s[k] is not a subset of s since n[k] is not in s.

>It would be better if it were co-r.e., but any example would
>be nice. Thanks.

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

Relevant Pages