[FOM] A question about infinite sets

[Noah David Schweber]

If I understand the recursion-theory version of the question correctly,
there can be no such pair of sets. For suppose C were an infinite r.e.
subset of AxB. Let C={c_0, c_1, . . .} be a computable enumeration of C,
and let c_i(0) (resp. c_i(1)) denote the left (resp. right) component of
c_i. Since C is infinite, one of the following sets must be infinite:

D:={c_i(0): i is a natural number} or E:={c_i(1): i is a natural number}.

Now D is clearly a subset of A, and E is clearly a subset of B, and D and
E are both r.e. since C is, so either A or B must have an infinite r.e.
subset.



 - Noah Schweber

On Sun, 16 Sep 2012 20:15:30 -0400, Andrej Bauer <andrej.bauer at andrej.com>
wrote:
> In a recent MathOverflow question
> 
>  
http://mathoverflow.net/questions/107215/monomorphisms-from-natural-numbers-objects-into-products
> 
> someone asked, in the context of topos theory, whether A or B must be
> infinite in order for the cartesian product  to A x B to be infinite.
> Here "A is infinite" means "there is an injection N -> A". I showed
> that this need not always be so, but the question remained whether we
> can find a topos and non-infinite objects A and B such that A x B is
> infinite. I think we might be able to find such objects in the
> effective topos, but my recursion theory is not strong enough to
> answer the question. Perhaps someone on the list can do it.
> 
> 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?
> 
> With kind regards,
> 
> Andrej
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom