[FOM] A question about infinite sets

[Andrej Bauer]

Ah yes, the projection of an r.e. set is an r.e. set. Thank you! We
should then look elsewhere for two non-infinite sets whose cartesian
product is infinite, it there is such a thing.

With kind regards,

Andrej

On Mon, Sep 17, 2012 at 1:17 AM, Mitchell Spector <spector at alum.mit.edu> wrote:
> 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
>>
>