## Dedekind infinite power sets

November 15, 2012

Write $A\preceq B$ to indicate that there is an injection from $A$ into $B$, and $A\preceq^* B$ to mean that either $A=\emptyset$, or else there is a surjection from $B$ onto $A$. It is a result of Kuratowski that (provably in $\mathsf{ZF}$) if $\omega\preceq\mathcal P(X)$, then in fact $\omega\preceq^* X$, and therefore $\mathcal P(\omega)\preceq \mathcal P(X)$. This appears as Théorème B in pages 94-95 of

Alfred Tarski. Sur les ensembles ﬁnis, Fund. Math. 6 (1924), 45–95.

To prove this result, note that it suffices to find a countably infinite family of disjoint subsets of $X$. Suppose $(m_n\mid n<\omega)$ is an injection of  $\omega$ into $\mathcal P(X)$. These sets induce a partition of $X$: Consider the equivalence classes of the relation $x\sim y$ iff

$\forall n(x\in m_n\Longleftrightarrow y\in m_n)$.

It is natural to attempt to show that these equivalence classes can be enumerated. Of course, the class of $x$ is completely specified by the list of values of $n$ such that $x\in m_n$, but this list may be “wasteful” in the sense that it may contain redundant information. For example, if $m_3\subsetneq m_{27}$, and we know that $x\in m_3$, then we automatically know that $x\in m_{27}$, and there is no need to include $27$ in our list if we already included $3$. (On the other hand, if all we know is that $x\in m_{27},$ then including $3$ in the list is certainly providing us with more information.) This suggests to assign to each $x\in X$ the set $F(x)=\{n_0,n_1,\dots\}\subseteq\omega$ defined recursively as follows: Let $n_0$ be least such that $x\in m_{n_0}$, if it exists. If $n_0$ is defined, let $n_1>n_0$ be least such that $x\in m_{n_1}$ and $m_{n_1}\not\supset m_{n_0}$, if it exists, and note that this is the same as requiring that $m_{n_1}\cap m_{n_0}\subsetneq m_{n_0}$. Similarly, if $n_1$ is defined, let $n_2>n_1$ be least such that $x\in m_{n_2}$, and $m_{n_2}\cap m_{n_1}\cap m_{n_0}\subsetneq m_{n_1}\cap m_{n_0}$, if it exists, etc.

Clearly, for any $x,y\in X$, $x\sim y$ iff $F(x)\sim F(y)$. There are now two possibilities:

• Case 1. For some $x$, the set $F(x)$ is infinite.

In this case, we are done (and we do not even need to bother enumerating the classes), because the sequence

$m_{n_0}\setminus m_{n_1}, (m_{n_0}\cap m_{n_1})\setminus m_{n_2},(m_{n_0}\cap m_{n_1}\cap m_{n_2})\setminus m_{n_3},\dots$

is a countably infinite collection of non-empty disjoint subsets of $X$.

• Case 2. All sets $F(x)$ are finite.

In this case we are done as well, because there is a (canonical) bijection between $\omega$ and $\text{Fin}(\omega)$, which means that we have enumerated the equivalence classes (and, of course, there are infinitely many, since the sets $m_n$ are all distinct, and each is a union of equivalence classes).

## 305 – Campanology

February 24, 2012

Campanology, or bell ringing, is an English tradition, where a round of cathedral bells is rung by permuting their order. The book discusses some examples of the possible patterns used in practice (the Plain Lead on four bells, and the Plain Bob Minimus). Additional examples can be found in the Wikipedia link, and links are provided there to a few additional sites, such as bellringing.org.

I strongly recommend that you read Section 3.5 in the book dealing with this topic. It introduces through an example the useful notion of cosets, and also it is quite interesting. For example, it shows how several ideas from group theory were used in practice since the seventeenth century, predating the introduction of the concepts by Galois and his contemporaries, and in a completely different setting.