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.

  • $\begingroup$ what is your definition of denumerable? we can easily partition into sets of one element. $\endgroup$ – Mark Joshi Sep 19 '17 at 3:49
  • $\begingroup$ Do you see how the Cartesian product $\mathbb N\times\mathbb R$ can be split into a collection of denumerable sets? $\endgroup$ – bof Sep 19 '17 at 3:50
  • $\begingroup$ @MarkJoshi Denumerable means infinitely countable. $\endgroup$ – sequence Sep 19 '17 at 3:51
  • $\begingroup$ @bof Yes, but I borrowed from someone else's idea (from a different post): $A_t := \{n+t:n\in \mathbb{N}\}, t\in\mathbb{R}$. Edited my post a bit. Thanks for your question. $\endgroup$ – sequence Sep 19 '17 at 3:55
  • 2
    $\begingroup$ Your questions (1) and (2) are nonsense. Here is a hint for the problem in the heading. Use ZL to get a maximal collection of pairwise disjoint denumerable subsets of $A.$ (I.e., if $\mathcal P$ is the set of all collections of pwd denumerable subsets of $A$ ordered by $\subseteq,$ use ZL to show that $(\mathcal P,\subseteq)$ has a maximal element.) Use maximality to show that the maximal collection covers all but finitely many elements of $A.$ Add those elements to one of the denumerable sets in your maximal collection. $\endgroup$ – bof Sep 19 '17 at 4:17

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your very explanatory answer! I'm actually now beginning to understand how set theory proofs and Zorn's lemma work. I'm very new to this. Can you please clarify why Zorn's lemma implies that any uncountable set contains an infinitely countable subset? $\endgroup$ – sequence Sep 19 '17 at 21:55
  • $\begingroup$ Let $A$ be infinite. Let $C$ be the set of all $(B,<_B)$ where $B\subset A $ and $<_B$ is a well-order on $B.$ Let $(B,<_B)<^*(B', <_{B'})$ iff $B\subsetneqq B'$ and $<_{B'}$ restricted to $B$ is $<_B.$... Any $<^*$-chain has an upper bound, and $C\ne \phi$ so there's a $<^*$-maximal member $(E,<_E) $ and E cannot be finite..... Any infinite well-ordered set has a countably infinite initial segment..... In fact $E=A$... Zorn's Lemma implies that every set can be well-ordered. $\endgroup$ – DanielWainfleet Sep 20 '17 at 7:14
  • $\begingroup$ Does a well-ordered set need to be an at most countable set? Sorry, I don't think I completely got your comment below. If we establish a chain with a well-order, which has a bound, and then by Z.L. we have that there exists a maximal element, how does this show us that every uncountable set has an infinitely countable subset? $\endgroup$ – sequence Sep 21 '17 at 1:28
  • $\begingroup$ NO a well-order doesn't need to be countable. If $<_B$ is a well-order of $B,$ an initial segment of $B$ is either $B$ or is $pred (x)=\{y\in B:\; y<_b x\}$ for some $x\in B$....("$pred (x)$" for "predecessors of $x$ ")... If $B$ is infinite consider the set of $x\in B$ for which $pred(x)$ is finite....Note that $B$ has a least member, a 2nd-least member, etc. $\endgroup$ – DanielWainfleet Sep 21 '17 at 5:05
  • $\begingroup$ So you say that Z.L. implies that every set can be well-ordered. But why does this mean that every uncountable set contains an at most countable set? I'd think about it this way: why is it impossible to build a chain of uncountable sets? $\endgroup$ – sequence Sep 21 '17 at 5:31

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.

| cite | improve this answer | |
  • $\begingroup$ It seems like we would need to apply infinite induction, since $A\setminus B$ is uncountable. $\endgroup$ – sequence Sep 19 '17 at 21:56
  • 2
    $\begingroup$ @sequence the only thing we need is an uncountable set admits a proper countable subset. $\endgroup$ – Vim Sep 20 '17 at 3:27

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.