# Can the natural number have an uncountable set of subsets?

Let $\mathbb{N}$ be the set of natural numbers. Let $X_{i},i\in I$ be an uncountable sequence of subsets such that $$\bigcup_{i\in I}X_{i}=\mathbb{N}$$ and $$\bigcup_{i\in J}X_{i}\subsetneq \mathbb{N}, \forall J\subset I, |J|=\aleph_{0}$$ where the inclusion is strict.

My questions are:

1) Is this possible? (in the light of the answer, I want it in absence of AC)

2) How "bad" is this if it is possible? Can we have even worse examples of this sort?

3) For generalization, if $|X|$ has certain cardinality $\gamma$. Is it possible for us to construct a sequence of subsets with cardinality $\alpha>\gamma$ and satisfies the above two similar conditions?

-
The set of all infinite sequences is uncountable so I guess this would be possible. It is definitely not possible if the sets have to be disjoint. – ruler501 Mar 24 '14 at 6:44
Just let each $X_i$ be $\mathbb{N}$. $\;$ – Ricky Demer Mar 24 '14 at 6:46
If you mean that for any countable $J$, the union is a proper subset of $\mathbb{N}$, it sounds very bad, impossible in the presence of AC. – André Nicolas Mar 24 '14 at 6:46
@AndréNicolas: Yes, that's what I meant. – Bombyx mori Mar 24 '14 at 6:48
@William: Suppose $X$ is an infinite set having no subset in bijection with $\mathbb N$. Let $S$ be the set of all finite sequences of distinct elements of $X$. Then $S$ is an infinite set having no subset in bijection with $\mathbb N$, and there is a surjection of $S$ onto $\mathbb N$. – bof Mar 24 '14 at 8:11

Using Choice freely, for every natural number $n$ we pick an $i_n$ such that $n\in X_{i_n}$. Then the set of indices picked has cardinality $\le \aleph_0$, and the union of the $X_{i_n}$ is $\mathbb{N}$. Thus, at least in the presence of Choice, the answer to "is this possible" is no.

-
Thanks! I think this is a good answer. – Bombyx mori Mar 24 '14 at 7:03

Consider the case where $S=\bigcup_{n\in\Bbb N}P_n$ and each $P_n$ is finite, but $S$ does not have a countably infinite subset. In particular, $\prod P_n=\varnothing$ (this is the typical case when we give the "socks and shoes" example).

Since $S$ is infinite, but not countable, it is uncountable. For every $s\in S$ consider $X_s=\{n\mid s\in P_n\}$. In this case clearly $\bigcup_{s\in S} X_s=\Bbb N$, but there is no $J\subseteq S$ such that $|J|=\aleph_0$ to begin with. And if we weaken this to require $|J|\leq\aleph_0$, then we still don't cover everything because $J\subseteq S$ and $|J|\leq\aleph_0$ implies that $J$ is finite.

But we can do slightly better. Consider such $S'=S\cup\Bbb N$ and partition it to pairs, $P'_k$ such that: $$P'_k=\begin{cases}P_n & k=2n\\\{k,k-1\} & k=2n+1\end{cases}$$

Then $S'$ has a countably infinite subset, but the product is still empty. In that case we can find $J$ non vacuously, but as long as the product of these pairs is empty we cannot have a well-ordered subcollection of $X_s$ covering the entire natural numbers.

Alright, so we can have this situation with countable subcovers being insufficient, what about well-ordered subcovers?

If you consider Andre's answer, you will see that if a [sub]cover is well-orderable then we can do the same trick. In particular if you consider an uncountable ordinal, then the union of that subcover was already achieved by a countable subset.

This by no mean that we can't do this in an almost trivial manner. Consider $S$ as before, or in fact any example of the failure at $|J|=\aleph_0$, and let $S'=S\cup\Bbb R$ now partition $\Bbb N$ into even and odds. The indexing with $S$ witnessing the failure will cover exactly the even integers, and $\Bbb R$ will index all the subsets of the odd integers.

We still have that every countable subcover only covers a proper subset of $\Bbb N$. Even if $\Bbb R$ is well-orderable, and as large as you want it to be. But this happens trivially, in the sense that every uncountable well-orderable cover has a countable subcover which covers the same set.

-

It is consistent with $ZFC$ that there exists a model of $ZF$ with an infinite Dedekind-finite set.

Let $X$ be such a set. Let $X_i = \omega$ for all $i \in X$.

$X$ is infinite Dedekind-finite, it is uncountable. Clearly $\bigcup_{i \in X} X_i = \omega$. Since $X$ is infinite Dedeind-finite, $X$ has no countable subsets, thus for all $J \subseteq X$ such that $|J| = \aleph_0$, $\bigcup_{i \in J} X_i \subsetneq \omega$.

If you weaken $|J| = \aleph_0$ to $|J| \leq \aleph_0$, there still is a sequence (though not the example above).

Let $X$ be an infinite Dedekind-finite set. As bof mentioned, let $S$ be the set of finite sequences of $X$ with all distinct terms. $S$ is still an infinite Dedekind-finite set. The cardinality function denoted $f$ is a surjection $f : S \rightarrow \omega$. Let $X_s = \{f(s)\}$. This sequence would work.

-
@bof Suppose my $S$ has a countably infinite subset $\{A_i : i \in \omega\}$. I believe by recursion I can define a countable infinite subset of the original $X$ by picking out new elements that appear in $A_i$. Hence this contradicts the Dedekind finiteness of $X$. Also I think the finite subsets of $X$ are in bijection with the increasing finite sequences. So it is a subset of your Dedekind-finite set. – William Mar 24 '14 at 9:10
@bof Nevermind. I kept thinking there was a linear ordering on $X$. – William Mar 24 '14 at 9:33