[FOM] A question about infinite sets

[Oosten, J. van]

If X is an r.e. subset of A x B then, since p_0X={a | for some b, <a,b>\in X} is r.e. and a subset of A, it must be finite; likewise, p_1X must be finite. So X, being a subset of p_0X x p_1X, is finite.

Am I missing something?

________________________________________
From: fom-bounces at cs.nyu.edu [fom-bounces at cs.nyu.edu] on behalf of Andrej Bauer [andrej.bauer at andrej.com]
Sent: Monday, September 17, 2012 2:15 AM
To: Foundations of Mathematics
Subject: [FOM] A question about infinite sets

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