If $A$ is infinite set then it is partitionable into denumerable (infinitely countable) sets

Question

Let $A$ be a non-empty set, such that $\mathbb{N}\preceq A$. Prove that this implies that $A$ is partitionable into denumerable sets.

A hint to this question says that Zorn's lemma is required to prove it. But I'm not very confident when it comes to Zorn's lemma. So I would appreciate your input.

Here's what we are given:

That $\aleph_0 \le |A|$, which means that $A$ is infinite. Also, we are given that there exists an injection from $\mathbb{N}$ to $A$.

Let $\{P_i\}_{i\in I}$ be a partition of $A$. What needs to be shown here is that $P_i$ can be denumerable sets, even if $A$ is uncountable. Now, to apply Zorn's lemma, it is necessary to show that each $P_i$ can be split into chains which have upper bounds. This will lead to the fact that each $P_i$ has a maximal element.

So the questions that I have are the following:

(1) If each $P_i$ has a maximal element, how does this indicate that $P_i$ is denumerable? E.g., $(0,1]$ has the maximal element, $1$, but it is not denumerable.

(2) What is a good example of a chain contained in $P_i$? My guess is that these can be nested sets. For example, one could create a Cantor-like set contained in $P_i$.

Would appreciate your clarification.

Answer 1

Zorn's Lemma implies that every infinite set has a countably infinite subset.

Let $A$ be an infinite set. Let $C$ be the set of all pairwise-disjoint families of countably infinite subsets of $A.$ We have $C\ne \phi$ because $\{B\}\in C$ for some (any) countably infinite $B\subset A.$ We want to find some $c\in C$ with $\cup c=A.$

Consider the relation $\subsetneqq$ on $C$ which for brevity I will call $<.$ Note that $<$ is transitive and irreflexive.

(I). Suppose $\sigma\in C$ and $\sigma$ is $<$-maximal. That is, $\forall \tau \in C\;(\neg (\sigma < \tau))$.

(Ia). $\sigma \ne \phi$ because $\phi<\{B\}$ for any countably infinite $B\subset A.$

(Ib). $A$ \ $\cup \sigma$ must be finite. Otherwise there exists a countably infinite $B\subset (A$ \ $\cup \sigma)$ but then $\sigma \cup \{B\}\in C$ and $\sigma<\sigma \cup \{B\},$ contradicting the $<$-maximality of $\sigma.$

Now since $\sigma \ne \phi$ and $A$ \ $\cup \sigma$ is finite, we can take some (any) $s\in \sigma$ and let $c=(\sigma \setminus \{s\})\cup \{s\cup (A$ \ $\cup \sigma)\}.$ Then $c\in C$ and $\cup c=A.$

So it suffices to show that $C$ has a $<$-maximal member.

(II). A $<$-chain is a subset $D$ of $C$ such that $\forall d,d'\in D\;( d=d'\lor d<d'\lor d'<d).$ And a $<$-upper bound for any $E\subset C$ (if there is one) is an $x\in C$ such that $\forall e\in E\;(e=x\lor e<x).$

Since $C\ne \phi,$ if we can show that every $<$-chain has a $<$-upper bound, Zorn's Lemma will imply that $C$ does have a $<$-maximal member.

Let $D$ be a $<$-chain. Let $x=\cup D.$

Suppose $c_1,c_2\in x$ with $c_1\ne c_2.$ There exist $d_1,d_2\in D$ with $c_1\in d_1$ and $c_2\in d_2.$ Since $D$ is a $<$-chain we have (by the def'n of $<$) $\;d_1\subset d_2$ or $d_2\subset d_1.$

If $d_1\subset d_2$ then $c_1,c_2$ are unequal members of $d_2$ and $d_2\in C,$ so $c_1,c_2$ are disjoint countably infinite subsets of $A.$

If $d_2\subset d_1$ then $c_1,c_2$ are unequal members of $d_1$ and $d_1\in C ,$ so $c_1,c_2$ are disjoint countably infinite subsets of $A.$

Therefore $x\in C.$ And $x$ is a $<$-upper bound for $D$ because $\forall d\in D\; (d\subset x),$ which is the same as $\forall d\in D\;(d=x \lor d<x).$................... QED.

Answer 2

I think there's a rather straightforward approach that doesn't need ordering here. We just consider two cases: 1) if $A$ is infinitely countable then we simply break it down into singletons; 2) if $A$ is uncountable, let $B$ be an infinitely countable subset of $A$, then $\{b\},b\in B$ together with $A\setminus B$ is a desired partition.