How to create infinitely many disjoint sets from infinitely many sets

Question

Suppose we have a countably infinite set $X$ and we have (countably) infinitely many subsets $A_1,A_2,\cdots\subseteq X$ which are non-empty and distinct (i.e. for any $i\neq j$ either $A_i\setminus A_j$ or $A_j\setminus A_i$ is non-empty). Is it possible (in ZF) to disjoint these sets i.e. come up with sets $B_1,B_2,\cdots\subseteq X$ that are non-empty and pairwise disjoint.

Edit: it is not necessarily the case that $X$ is in bijection with $\omega$ in our model of ZF, we know that $X$ is countably infinite from outside our model.

Answer 1

Since @Asaf Karagila seems to be AWOL, I'll set the misconception in the question straight and answer.

In $\mathsf{ZF}$, any set $X$ has a Hartogs' number $\aleph(X)$ which is the least ordinal $\alpha$ not injectible into $X$. It is always an initial ordinal - i.e. a cardinal.

A set $X$ is called infinite if $\aleph(X)\ge \aleph_0$, Dedekind infinite if $\aleph(X)>\aleph_0$ and infinite Dedekind-finite if $\aleph(X)=\aleph_0$.

If a set $X$ has a collection $\{M_i\}_{i\in\Bbb{N}}$ of non-empty mutually disjoint subsets, I'll refer to this as $X$ having a partition of size $\aleph_0$. Even if the partition covers a proper subset of $X$ it's always possible to complete the partition to cover all $X$ by adding $X\setminus\left(\bigcup_{i\in\Bbb{N}}M_i\right)$ to the partition.

As noted by @Izaak van Dongen in a comment, If $X$ is Dedekind infinite the question is trivial because there is an injection $j\colon\Bbb{N}\to X$ and $\{\{j(n)\}\colon n\in\Bbb{N}\}$ is a partition of size $\aleph_0$.

Theorem (Kuratowski): If $X$ is infinite Dedekind-finite and $\Bbb{N}$ injects into $\mathcal{P}(X)$ then $X$ has a partition of size $\aleph_0$.

Kuratowski's original proof appears in Tarski 'Sur les ensembles finis' (1924). The following proof is due to Halbeisen & Shelah 'Consequences of arithmetic for set theory' (1993).

Define a function $\tau\colon X\to\mathcal{P}(\Bbb{N})$ by $$\tau(x)=\{n\in\Bbb{N}\colon x\in A_n\}$$

This function induces an equivalence relation on $X$ via $x\equiv y\iff \tau(x)=\tau(y)$. The equivalence classes are a partition of $X$ and the cardinality of the partition is the cardinality $|\tau(X)|$.

Claim: The number of equivalence classes is infinite.

Proof: Each $A_n$ is a union of equivalence classes, so if there were only finitely many equivalence classes, there could only be finitely many distinct $A_n$. This contradicts the assumption that the $A_n$ are mutually distinct.

If the number of equivalence classes is Dedekind infinite we can finish the proof as follows - since a Dedekind infinite set has a subset of cardinality $\aleph_0$, we can find a sub-collection of equivalence classes of cardinality $\aleph_0$, and that gives us the desired partition.

The difficulty lies in the possiblity that $\tau(X)$ is also infinite Dedekind-finite.

For $S\subseteq\Bbb{N}$ and $n\in\Bbb{N}$ define $$\operatorname{pred}(S,n)=X\cap\left(\bigcap_{m\in S, m<n}A_m\right)$$

Now define a second function $\chi\colon X\to\mathcal{P}(\Bbb{N})$ by $$\chi(x)=\{n\in\Bbb{N}\colon n\in\tau(x)\land\left(\operatorname{pred}(\tau(x), n)\setminus\operatorname{pred}(\tau(x), n+1)\ne\emptyset\right)\}$$

Claim: For all $x,y\in X$, $\tau(x)=\tau(y)\iff\chi(x)=\chi(y)$.

Proof: Since $\chi$ is defined in terms of $\tau(x),\tau(y)$ and the sets $\{A_n\}_{n\in\Bbb{N}}$, if $\tau(x)=\tau(y)$ then $\chi(x)=\chi(y)$. Conversely, assume $\tau(x)\ne\tau(y)$. Let $n_0$ be the least $n$ on which $\tau(x),\tau(y)$ differ. w.l.o.g assume $n_0\not\in\tau(y), n_0\in\tau(x)$. Notice that $y\in\operatorname{pred}(\tau(y),n_0)=\operatorname{pred}(\tau(x),n_0)$ but $y\not\in\operatorname{pred}(\tau(x),n_0+1)$ because $y\not\in A_{n_0}$ and $n_0\in\tau(x)$. Since $n_0\in\tau(x)$ and $y\in\operatorname{pred}(\tau(x),n_0)\setminus\operatorname{pred}(\tau(x),n_0+1)\ne\emptyset$ it follows that $n_0\in\chi(x)$. OTOH, $n_0\not\in\chi(y)$ because $n_0\not\in\tau(y)$. So $\chi(x)\ne\chi(y)$.

So $\tau, \chi$ induce the same equivalence relation on $X$ and it seems we haven't made any progress.

However, one of the following must be true

• There exists some $x_0\in X$ such that $\chi(x_0)$ is an infinite subset of $\Bbb{N}$. In this case, the sets $\{\operatorname{pred}(\tau(x_0),n)\setminus\operatorname{pred}(\tau(x_0),n+1)\}_{n\in\chi(x_0)}$ constitute a partition of $X$ of size $\aleph_0$.
• $\chi(x)$ is a finite subset of $\Bbb{N}$ for all $x\in X$. But then $\chi$ maps into the set $\mathcal{P}_{\operatorname{fin}}(\Bbb{N})$ of all finite subsets of $\Bbb{N}$. This latter set is known to have cardinality $\aleph_0$. The most popular way of showing it is to associate $n\in\Bbb{N}$ with the set of all $m\in\Bbb{N}$ such that $2^m$ appears in the binary representation $n$. So $\chi(X)$ is an infinite subset of a set of cardinality $\aleph_0$, and so $|\chi(X)|=\aleph_0$. The equivalence classes of $\chi$ (which are the same as $\tau$!) are a partition of $X$ of size $\aleph_0$.$\Box$

Additional references on the subject: Azriel Levy 'the independence of various definitions of finiteness' (1958), John K. Truss 'Classes of Dedekind finite cardinals' (1974), Supakun Panasawatwong 'Dedekind-finite cardinals and model-theoretic structures' (2019).

Answer 2

Yes! In fact, define $B_1 = A_1$ and recursively, $$B_n := A_n \setminus \left( \bigcup_{k=1}^{n-1} B_{k} \right).$$ Then the sets $B_1, \ldots$ are disjoint. In fact, suppose $B_i \cap B_j \neq \emptyset$ for some $i < j$. Let $x\in B_i\cap B_j$. Then $x\in B_j = A_j \setminus \left( \bigcup_{k=1}^{j-1} B_{k} \right)$, so in particular $x\notin B_i$, which is a contradiction.

Moreover, we have that $$\bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty} B_n.$$ The inclusion "$\supset$" is clear since $B_n \subset A_n$ for all $n$. On the other hand, if $x\in \bigcup_{n=1}^{\infty} A_n$, we find a minimal $n_0$ with $x\in A_{n_0}$. Then $x\notin B_k$ for all $k < n_0$, hence $$x\in B_{n_0} = A_{n_0} \setminus \left( \bigcup_{k=1}^{n_0-1} B_{k} \right).$$

Edit: As has been pointed out in the comments, the sets $B_n$ defined as above may happen to be empty. To avoid this you can either simply remove all empty $B_n$ from your collection of sets, or use another approach.