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?

  • $\begingroup$ 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. $\endgroup$
    – ruler501
    Mar 24 '14 at 6:44
  • 1
    $\begingroup$ Just let each $X_i$ be $\mathbb{N}$. $\;$ $\endgroup$
    – user57159
    Mar 24 '14 at 6:46
  • $\begingroup$ 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. $\endgroup$ Mar 24 '14 at 6:46
  • $\begingroup$ @AndréNicolas: Yes, that's what I meant. $\endgroup$ Mar 24 '14 at 6:48
  • 1
    $\begingroup$ @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$. $\endgroup$
    – 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.

  • $\begingroup$ Thanks! I think this is a good answer. $\endgroup$ Mar 24 '14 at 7:03

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.

  • $\begingroup$ @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. $\endgroup$
    – William
    Mar 24 '14 at 9:10
  • $\begingroup$ @bof Nevermind. I kept thinking there was a linear ordering on $X$. $\endgroup$
    – William
    Mar 24 '14 at 9:33

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.