Let $A\ne\emptyset$. I want to prove that if $A$ is partitionable into denumerable sets then there exists an injective function from natural numbers to the set $A$. In the hint of this question it is said that one requires Zorn's lemma to prove it. However, I don't think that I'm doing it right. Here's my approach.

Since $A$ is partitionable into denumerable sets, there exists a collection $\{P_i\}_{i\in I}\subset \mathcal{P}(A)$ such that

  • each $P_i$ is denumerable;

  • $P_i \cap P_j=\emptyset$ if $i\ne j\in I$;

  • $A = \bigcup\limits_{i\in I} P_i$.

Since each $P_i$ is denumerable, there exists an injective function $f_i:\mathbb{N}\to P_i$.

Since the $P_i$ are denumerable, each $P_i$ can be partitioned into finite chains $P_{i_k}$. Then each chain will have an upper bound, and so $P_i$ has a maximal element, which also implies that $P_i$ is finite. Let $x_i \in P_i$ be a maximal element of $P_i$. Since $f_i$ is injective, $f^{-1}(x_i):=k_i\in\mathbb{N}$ exists.


$$f(n) = \begin{cases} f_1 & n\in \{1,2,\dots, k_1\} \\ f_2 & n\in \{k_1+1,k_1+2,\dots, k_2\} \\ \vdots\\ f_m & n\in \{k_{m-1}+1,k_{m-1}+2,\dots, k_m\} \\ \vdots \end{cases} $$

Then $f:\mathbb{N}\to A$ is an injection, as required.

My questions are the following:

(1) Can we really say that each $P_i$ can be partitioned into finite chains $P_{i_k}$? I doubt this.

(2) Does there really necessarily exist a maximal element in $A$? If $A$ is partitionable into denumerable sets, this does not imply that $A$ is finite. Then $A$ does not necessarily have a maximal element.

(3) So how should Zorn's lemma be applied here exactly?


closed as unclear what you're asking by Andrés E. Caicedo, user91500, JMP, B. Goddard, MAN-MADE Sep 18 '17 at 14:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Huh? I believe that $\mathbb N\times\mathbb R$ can be partitioned into denumerable sets $P_i=\mathbb N\times\{i\},\ i\in\mathbb R$ but I don't believe there is a surjection from $\mathbb N$ to $\mathbb N\times\mathbb R.$ $\endgroup$ – bof Sep 17 '17 at 21:49
  • $\begingroup$ Perhaps you mean to say that $A$ is partitionable into countably many countable sets? $\endgroup$ – Alex Provost Sep 17 '17 at 21:51
  • $\begingroup$ Sorry, my mistake, it should be "injective function" instead of "surjective function". Editing now. $\endgroup$ – sequence Sep 18 '17 at 0:41
  • $\begingroup$ Are denumerable sets infinite? Otherwise, the injective version of the question is false as well. $\endgroup$ – Andrés E. Caicedo Sep 18 '17 at 0:46
  • 1
    $\begingroup$ Sorry, I missed "$A\ne\emptyset.$" But the problem as stated now is trivial. If $A$ is partitioned into denumerable sets (and is nonempty), then $A$ contains a denumerable set $P.$ So there is an injective map $f:\mathbb N\to P\subseteq A,$ so $f$ is an injective map from $\mathbb N$ to $A.$ $\endgroup$ – bof Sep 18 '17 at 6:20

The result is false. For each $t\in [0,1),$ define

$$A_t= \{n+t: n \in \mathbb Z\}.$$

Then each $A_t$ is denumerable, the sets $A_t$ are pairwise disjoint, and $\mathbb R = \bigcup_{t\in [0,1)}A_t.$

  • $\begingroup$ Sorry, my mistake, it should be "injective function" instead of "surjective function". Editing now. $\endgroup$ – sequence Sep 18 '17 at 0:41
  • $\begingroup$ @sequence But you still say "It is in my understanding that what needs to be proved is that $A$ is also denumerable." That's clearly false. $\endgroup$ – zhw. Sep 18 '17 at 0:54
  • $\begingroup$ Yes, you're right, I think it's more clear to me that it doesn't have to be denumerable, since by definition a denumerable set $S$ is one which has a corresponding injection from $S$ to $\mathbb{N}$, and not vice versa. @zhw. $\endgroup$ – sequence Sep 18 '17 at 5:40

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