Prove, with the help of Zorn's lemma, that infinite set, $X$ can be represented union of disjoint countable sets.

My attempt:

I know that a countable union of countable sets must be countable. Hence $|X|\leq \aleph_0$.

Maybe, we can choose set $A_1$, such that $A\subset X$, which is countable. Now, $X-A_1$ must be countable, and we are choose countable set $A_2$ from $X-A_1$, which is disjoint from $A_1$, I assume that we can do that to get:

$$X= \bigcup_{i=1} A_i $$

Right? But if so, I used only $AC$, yes? How one can combine Zorn's lemma for this one?

  • 2
    $\begingroup$ Do you know that Zorn's Lemma is equivalent to the axiom of choice? and to the "well-ordering principle"? That each one implies the other two?. $\endgroup$
    – amWhy
    Dec 21, 2012 at 1:52

5 Answers 5


The result is trivial if you’re using countable as I do, to mean of cardinality at most $\omega$: just decompose $X$ into singletons. I’m going to assume, therefore, that you mean countably infinite.

Zorn’s lemma is equivalent to the axiom of choice, and the result can be proved in a variety of ways using different equivalents of the axiom of choice. Your argument can be made rigorous using transfinite recursion, but you’d have to know something about the infinite ordinals. However, in that case there is an easier proof using the well-ordering principle; see below.

To use Zorn’s lemma, let $\mathfrak D$ be the set of all pairwise disjoint families $\mathscr{D}$ of countably infinite subsets of $X$; $\mathfrak D$ is partially ordered by $\subseteq$. Let $\mathfrak C$ be a chain in $\langle\mathfrak D,\subseteq\rangle$. That is, $\mathfrak C$ is a collection of pairwise disjoint families of countably infinite subsets of $X$, and for $\mathscr{C}_0,\mathscr{C}_1\in\mathfrak C$, either $\mathscr{C}_0\subseteq\mathscr{C}_1$, or $\mathscr{C}_1\subseteq\mathscr{C}_0$. To apply Zorn’s lemma, we must show that $\mathfrak C$ has an upper bound in $\mathfrak D$. The obvious candidate is $\bigcup\mathfrak C$: this is certainly a collection of countably infinite subsets of $X$, so the only question is whether it’s a pairwise disjoint collection.

Let $\mathscr{C}=\bigcup\mathfrak C$, and suppose that $C_0,C_1\in\mathscr{C}$ with $C_0\ne C_1$. Then there are $\mathscr{C}_0,\mathscr{C}_1\in\mathfrak C$ such that $C_0\in\mathscr{C}_0$ and $C_1\in\mathscr{C}_1$. $\mathfrak C$ is a chain, so either $\mathscr{C}_0\subseteq\mathscr{C}_1$, or $\mathscr{C}_1\subseteq\mathscr{C}_0$. Without loss of generality assume that $\mathscr{C}_0\subseteq\mathscr{C}_1$. Then $C_0,C_1\in\mathscr{C}_1$. But $\mathscr{C}_1\in\mathfrak C$, so $\mathscr{C}_1$ is a pairwise disjoint family, and $C_0\ne C_1$, so $C_0\cap C_1=\varnothing$. Thus, $\mathscr{C}$ is pairwise disjoint and is therefore an upper bound for $\mathfrak C$ in $\mathfrak D$. $\mathfrak C$ was an arbitrary chain in $\mathfrak D$, so the hypothesis of Zorn’s lemma is satisfied, and by Zorn’s lemma we may conclude that there is a maximal chain $\mathscr{M}$ in $\mathfrak D$.

$\mathscr{M}$ is a family of pairwise disjoint, countably infinite subsets of $X$, and it’s maximal with respect to inclusion amongst all such families. If $\bigcup\mathscr{M}=X$, we’re done: $\mathscr{M}$ is a partition of $X$ into pairwise disjoint, countably infinite subsets. Suppose, then, that $\bigcup\mathscr{M}\ne X$, and let $Y=X\setminus\bigcup\mathscr{M}$. There are two cases that have to be considered.

Case 1: If $Y$ is infinite, let $C$ be any countably infinite subset of $Y$. Then $\mathscr{M}\cup\{C\}$ is a family of pairwise disjoint, countably infinite subsets of $X$, so $\mathscr{M}\cup\{C\}\in\mathfrak D$, and clearly $\mathscr{M}\subsetneqq\mathscr{M}\cup\{C\}$. But this contradicts the maximality of $\mathscr{M}$ and is therefore impossible. Thus, we must be in

Case 2: $Y$ is finite. In that case let $C\in\mathscr{M}$ be arbitrary, and let $\mathscr{M}'=(\mathscr{M}\setminus\{C\})\cup\{C\cup Y\}$. That is, $\mathscr{M}'$ is obtained from $\mathscr{M}$ by replacing $C$ by $C\cup Y$. Then $\mathscr{M}'$ is still a collection of pairwise disjoint, countably infinite subsets of $X$, and it’s clear that $\bigcup\mathscr{M}'=\bigcup{M}\cup Y=X$, so $\mathscr{M}'$ is the desired decomposition of $X$.

If one knows something about infinite ordinals and cardinals, an easy approach is to let $\kappa=|X|$ and let $\{x_\xi:\xi<\kappa\}$ be an enumeration of $X$. Let $\Lambda=\{\eta<\kappa:\eta\text{ is a limit ordinal or }\eta=0\}$, and for each $\eta\in\Lambda$ let $X_\eta=\{x_{\eta+n}:n\in\omega\}$; then $\{X_\eta:\eta\in\Lambda\}$ is a decomposition of $X$ into pairwise disjoint, countably infinite subsets.

  • $\begingroup$ To apply Zorn's Lemma, you need that $\mathfrak D$ is indeed a set. Also, you need that a family $\mathscr{D}$ in $\mathfrak D$ is a set rather than so large as to become a class. How do you ensure that they are actually sets? $\endgroup$
    – Michael
    Sep 13, 2022 at 12:35
  • 1
    $\begingroup$ @Michael: Use the power set and separation axioms. $X$ is a set, so $\wp(X)$ is a set, so $[X]^\omega$, the family of countably infinite subsets of $X$, is a set. Then $\wp\left([X]^\omega\right)$ is a set, and hence so is $\mathfrak D$. The argument for members of $\mathfrak D$ is similar but even shorter. $\endgroup$ Sep 13, 2022 at 22:00

Recall that Zorn's lemma is a statement about partial orders. If a non-empty partial order $(P,\leq)$ has the property $\tau$, then we are guaranteed that it also have the property $\sigma$.

Therefore in order to use Zorn's lemma we should find a suitable partial order $(P,\leq)$ which has the property $\tau$, and if we have chosen the right partial order then $\sigma$ will allow us to prove what we have wanted to show.

Of course $\tau$ is the property "Every chain has an upper bound" and $\sigma$ is the property "There is a maximal element". We often search for statements that the maximality will prove. For example your question asks to find a partition into countable sets. If the partial order would have been "partial partitions of $X$ into countable sets" then a maximal element would have to be a proper partition of $X$ into countable sets (I am using ad-hoc terms, partial partition means that we take a partition of a subset of $X$, and a proper partition simply means a partition of $X$).

The idea, if so, is a little bit like in forcing (which you haven't studied yet). We approximate the object we want to end up with. Only where forcing requires us to add more sets to the universe, Zorn's lemma ensures the existence of the object we were looking for within the universe.

What sort of approximations can we have? Well, as I hinted we will use partitions of subsets of $X$. Namely we take the ordered set, $$\Big(\{\mathcal A\mid\exists Y\subseteq X:\mathcal A\text{ is a partition of }Y\text{ into countable sets}\},\subseteq\Big)$$

Do note that as Brian remarked, using countable in the broad sense (to include finite) this is trivial, so I will assume that countable means infinitely countable.

The reason we chose $\subseteq$ as our order is simple, this is an approximation of partitions, so when we added a new part we partition a larger subset, and we get close to the full approximation that we wanted.

Now we need to show that every chain has an upper bound. While this is not always the case, when it comes to things ordered by inclusion taking the union of the chain is often the best way to show the existence of an upper bound. After all what is a chain? It is a collection of partial partitions which are "coherent" with one another. So suppose that $\{A_i\mid i\in I\}$ is a chain in our ordered set, let $A=\bigcup\{A_i\mid i\in I\}$, we will show that $A$ is a partial partition of $X$ into countable sets. That is we will show that $A$ is a partition of some subset of $X$ into countable parts.

Claim: Let $Y_i=\bigcup A_i$ be the set partitioned by $A_i$, then we have that $\{Y_i\mid i\in I\}$ is a $\subseteq$-chain in $\mathcal P(X)$. Take $Y=\bigcup\{Y_i\mid i\in I\}$. Then $A$ is a partition of $Y$ into countable parts.

Proof. First the easy part, every set in $A$ is coming from some $A_i$ and there is countable. So it remains to show that $A$ is a partition of $Y$ in order to finish this part of the proof. But this is also true, given two parts in $A$ they both appear in some $A_i$ and therefore are either disjoint or equal; and every point in $Y$ appear in some $Y_i$, and therefore in a set within $A_i$ and so it appears in $A$. Lastly none of the $A_i$ had the empty set, so $A$ cannot have the empty set as an element. $\square$

We have shown [read: hand-waved our way around] that $A$ is a partition of $Y$ into countable parts. Do note that $Y$ may or may not be the whole set $X$. We don't know, and for now we don't care either. We just want to know that every chain is bounded.

So let's recap. What do we have here? We have a partial order which meets Zorn's conditions, and by Zorn's lemma it has a maximal element. But how does that help us?

Let $A$ be a maximal element whose existence is guaranteed by Zorn's lemma. We would have liked it if $A$ was a partition of $X$. While this is not necessarily the case, it is not a big problem.

Claim: Let $Y=\bigcup A$, then $X\setminus Y$ is finite.

Proof. Suppose not, then there is some $B\subseteq X\setminus Y$ which is countably infinite, and $A'=A\cup\{B\}$ is a partition of $Y\cup B$. Because $B\cap Y=\varnothing$ we have that $A\subsetneqq A'$ in contradiction to maximality. $\square$

So we have a maximal element and we know it partitions almost everything, but now it's fine. Take some $B\in A$ and let $A'$ be the partition obtained by replacing $B$ by $B\cup X\setminus Y$. This is a countable set, because we only added a finite number of element, and $A'$ is still a maximal partition, otherwise we could add another part to it, and we could have added the same part to $A$, in contradiction to its maximality.

So what is $A'$? It is a partition of $X$ and every part in $A'$ is countably infinite, as requested.

  • 1
    $\begingroup$ I was hoping to write a short answer explaining how to use Zorn's lemma. Instead I wrote a long answer trying to explain how to use Zorn's lemma... $\endgroup$
    – Asaf Karagila
    Dec 21, 2012 at 10:12

In your solution you presented an informal argument that avoids a direct use of Zorn's Lemma. It does use, as you say, AC, which is equivalent to Zorn's Lemma so you did not really avoid using it.

To obtain a formal proof that uses Zorn's Lemma start by considering the set $P$ of all disjoint collections of countable subsets of $X$. That is, a typical element in $P$ is a collection $\{C_i\}_{i \in I}$ with $C_i\subseteq X$ is countable and for $i\ne j$, in $I$, holds that $C_i\cap C_j=\emptyset$.

Order $P$ by inclusion and apply Zorn's Lemma, with proper care.


Examining the Wikipedia articles.

Zorn's lemma
Well-ordering theorem

one can't help but appreciate a 'natural proof flow':

enter image description here

The proof

$\quad$ Zorn's lemma $\Rightarrow$ Well-ordering theorem

is straightforward, and we can answer, in a 'natural' way, the OP's question using the Well-ordering theorem.

Let $X$ be any infinite set. Make $X$ into a well-ordered set with the relation $\le$, so that for any $x \in X$, we can denote by $\sigma(x)$ the 'next' element; this defines an injective function on $X$.

We can also (kind of) go backwards, defining $\sigma^{-1}(x) = y$ if $\sigma(y) = x$ and if no $y$ exists then $\sigma^{-1}(x) = x$. Let $\Lambda \subset X$ consists of all the elements $\lambda \in X$ with $\sigma^{-1}(\lambda) =\lambda$. The sets

$\tag 1 X_{\lambda} = \{x \; | \; x = \sigma^n(\lambda) \text{, } \, n \in \mathbb N \}$

partition $X$ into a family of countable subsets, with at most one of those sets (a trailing $\le$ segment) being finite. We can shove this finite set into, say, $X_{\lambda_0}$, with $\lambda_0$ the smallest element in $X$. This creates the the sought for partition of $X$.

Exercise: Show that for any $x \in X$, the set $\{ \sigma^m(x) \, | \, m \in \mathbb Z\}$ must 'bump into a wall' on the $m$ negative side.

  • $\begingroup$ Great proof, thank you for the insight! $\endgroup$
    – orangeskid
    Nov 6, 2022 at 4:24

Just some comments on the result: the fact that $X$ is a disjoint union of countable infinite sets is equivalent to

$$X\simeq Y \times \mathbb{N}$$ for some set $Y$. Now we get

$$X \times \mathbb{N} \simeq (Y \times \mathbb{N}) \times \mathbb{N}= Y \times (\mathbb{N} \times \mathbb{N}) \simeq Y \times \mathbb{N}\simeq X$$ Therefore, for every infinite set $X$ we have
$$X \simeq X \times \mathbb{N}$$

Note the stronger result $$X \simeq X \times X$$ This result is shown (see here) again using Zorn's lemma. In some cases the result is easy to show, for instance when $X \simeq 2^{Z}$, since then $X\times X = X^2 \simeq 2^{2 Z} \simeq 2^Z \simeq X$.

  • 1
    $\begingroup$ How about using $\quad \text{For every infinite set } X \text{ with } |X| \gt \aleph_0 \text{ there exist a set } Z \text{ such that } |X| = 2^{|Z|}$ $\quad$ as an axiom? $\endgroup$ Nov 6, 2022 at 19:17
  • 1
    $\begingroup$ @CopyPasteIt: Hmn... the set of cardinals is well ordered. But we might have some cardinals that are not " the next one after $Z$" for any $Z$ ( which should be then $2^Z$). So that would make such a cardinal not of this form. I think the strong continuous hypothesis would make any successor ( of $Z$) cardinal $2^Z$, but not the others. Now, I don't know if there are such (not a successor) cardinals. Still an interesting proposal. Also i just found this $\endgroup$
    – orangeskid
    Nov 6, 2022 at 19:24
  • 1
    $\begingroup$ Thanks for the find on Inaccessible cardinals. I guessed that $\quad$ consistency of ZFC implies consistency of ZFC+"there are no strong inaccessibles" $\quad$ (well, at least in my layman understanding of set theory). $\endgroup$ Nov 6, 2022 at 20:22
  • $\begingroup$ @CopyPasteIt: Yes.... It's funny how we don't really know about these things...By the way, it seems that even $A\sqcup A \simeq A$ for $A$ infinite is a big deal -- just a bit weaker than AC (cf here ) $\endgroup$
    – orangeskid
    Nov 7, 2022 at 4:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .