[FOM] A question about infinite sets

Andrej Bauer andrej.bauer at andrej.com
Sun Sep 16 20:15:30 EDT 2012

In a recent MathOverflow question


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,


More information about the FOM mailing list