[FOM] A question about infinite sets

[Laurent Bartholdi]

>
> Let me translate into pure recursion theory. We seek two subsets A and
> B of the natural numbers, with the following properties:
>
> 1) There is no infinite r.e. subset of A.
> 2) There is no infinite r.e. subset of B.
> 3) There is an infinite r.e. subset of A x B = { <m, n> | m in A and n
> in B }, where <m, n> is a standard pairing.
>
> Are there two such sets?
>
> Let A,B be such sets. Let T be a Turing machine enumerating an infinite
subset of AxB. Then construct the following Turing machines T_A, T_B:

T_A runs T to obtain pairs (a,b). It stores the entries a, and as soon as
it obtained a pair that was not yet seen, it outputs it.

T_B does the same thing, but with coordinate b.

Either T_A or T_B is a Turing machine that returns an infinite sequence of
elements in its respective set.

-- 
Prof. Dr. Laurent Bartholdi   \ laurent.bartholdi<at>gmail<dot>com
G.-A. Universität zu Göttingen \ Phone: +49 551 39 7826
Bunsenstraße 3-5                \ Secr: +49 551 39 7752
D-37073 Göttingen, Germany       \ Fax: +49 551 39 22674
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120917/40439a45/attachment.html>