[FOM] A question about infinite sets

[Mitchell Spector]

Andrej Bauer 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?



Andrej,

Maybe I'm missing something because I don't know topos theory, but if this is just a question about 
standard recursion theory, the answer is that there cannot be two such sets A and B.


Let A and B be sets satisfying 1) and 2).  If S is any r.e. subset of A x B, then we can prove that 
S must be finite, as follows:

I'll use the notation f"X = {f(x) | x belongs to X}.

Let p and q be the two projection functions, defined so that p(<m,n>) = m and q(<m,n>) = n for all 
natural numbers m and n.  The functions p and q are recursive.

Then p"S is an r.e. subset of A, so p"S must be finite.

Similarly, q"S is an r.e. subset of B, so q"S must be finite.

But S is a subset of p"S x q"S.

It follows that S must be finite.



By the way, the same idea can be used to show in ZF (without the axiom of choice) that the Cartesian 
product of two Dedekind-finite sets must be Dedekind-finite.



Regards,

Mitchell
--
Mitchell Spector
E-mail: spector at alum.mit.edu



>
> With kind regards,
>
> Andrej
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>