Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 6:44
1  
Just let each $X_i$ be $\mathbb{N}$. $\;$ –  Ricky Demer Mar 24 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 at 6:46
    
@AndréNicolas: Yes, that's what I meant. –  Bombyx mori Mar 24 at 6:48
1  
@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 at 8:11

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks! I think this is a good answer. –  Bombyx mori Mar 24 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.

share|improve this answer

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.

share|improve this answer
    
@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 at 9:10
    
@bof Nevermind. I kept thinking there was a linear ordering on $X$. –  William Mar 24 at 9:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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