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 finis, 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).

Read the rest of this entry »

Advertisement

2 Comments | 580: Topics in set theory | Tagged: , , , | Permalink
Posted by andrescaicedo

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.

I did not know about this until I read the book, and of course now I see mentions of bell-ringing everywhere.

The quote above, for example, is from the book Combinatorial Set Theory by Lorenz Halbeisen.

A nice article on the topic (in French) can be found here; coincidentally, the article also talks at the end about juggling. The video of the talk on the mathematics of juggling by Allen Knutson that we saw an excerpt of today is here. A few technical and expository articles on this topic, by renown mathematician (and juggler) Ronald Graham, and his coauthors, can be found in Graham’s page. See for example here, here, here, and here.

Leave a Comment » | 305: Abstract Algebra I | Tagged: , , , , | Permalink
Posted by andrescaicedo