[FOM] A question about infinite sets

[Robert Lubarsky]

For the specific computability theory question Andrej asks, no. Given an
enumeration of an infinite subset of AxB, projecting onto the two
coordinates gives enumerations of subsets of A and B. Using classical
reasoning, one of those has to have infinite range. Thinning the enumeration
gives an injection.

I believe the larger goal (of non-infinite A & B with infinite product) can
be achieved. I think in terms of topological models in a forcing style; this
is morally the same as sheaves over the same topological space. Let the
space consist of injections from N into NxN. An open set is given by both
positive and negative information. The positive info is a finite initial
segment of such an injection. The negative info consists of finitely many
integers (the forbidden numbers) for each of the first and second
componenets, the meaning of which is that the new part of any extension of
the positive info (i.e. a longer initial segment) may not contain any
forbidden numbers.

The generic itself is a 1-1 enumeration of a set of pairs. Suppose an open
set U forces "f is a function from N to N." Say that the positive info in U
uses exactly k many integers in the first components. Shrink (i.e. extend,
for all you forcing-theorists out there) U using at most one new integer in
the first componenets and forcing the values of f(0), f(1), ... , f(k+1).
(How can that be done? Let F \in U have first components consisting of the
same k-many integers as in U's positive info -- if all of those are
forbidden by U, then allow one more. By the hypothesis on U, and the def of
top semantics, F has neighborhoods forcing each of those values f(i). The
intersection of those neighborhoods suffices.) Either there is a repetition
in that list, so f is not 1-1; or there is an integer not yet occurring in
U's positive info, which can then be added to U's negative info, forcing f
not to be into the first components.

Bob Lubarsky


-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of
Andrej Bauer
Sent: Sunday, September 16, 2012 8:16 PM
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


-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2012.0.2221 / Virus Database: 2437/5268 - Release Date: 09/14/12