Let $I$ be a set and $P(I)$ its power set. I want to prove:

Set $E(I)$ of all equivalence relations on set $I$ and set $A(I)$ of all complete atomic subalgebras (i.e. subalgebras that are atomic and complete) of boolean power set algebra $P(I)$ have same cardinality.

Note that every equivalence relation on $I$ defines unique complete atomic subalgebra of $P(I)$ boolean algebra (with equivalence classes as atoms). So we have that $\left\lvert E(I) \right\rvert$ $\le$ $\left\lvert A(I) \right\rvert$

I tried to prove the other inequality (find injection) but I failed to prove that in complete atomic boolean subalgebra of $P(I)$ boolean algebra $\inf B$ equals to intersection of all elements of $B$ where $B$ is set of elements of this subalgebra. (equivalently: every (nonzero) element of complete atomic boolean subalgebra of $P(I)$ algebra can be written as union of atoms). If the above statement is true then such complete atomic subalgebra defines a partition of set $I$. Also, I was unable to find a counterexample.

Any sugestions?

  • $\begingroup$ There is some subtlety in the terminology here: is a "complete subalgebra" a subalgebra that happens to be complete, or is it a "sub-complete algebra", i.e. a subalgebra which is also closed under infinite joins and meets in $P(I)$? (Note that actually every complete subalgebra in the second sense is atomic.) You seem to be assuming the first interpretation, but I would assume the second unless context suggested otherwise... $\endgroup$ – Eric Wofsey Dec 14 '15 at 20:51
  • $\begingroup$ A complete atomic subalgebra is a subalgebra that happens to be complete and atomic. I will edit it, thanks. $\endgroup$ – Martin Dec 14 '15 at 20:55

This isn't true if $I$ is infinite. It is easy to see that $|E(I)|=2^{|I|}$; I claim that $|A(I)|=2^{2^{|I|}}$.

To show this, let $\beta I$ be the Stone space of $P(I)$, i.e. the space of ultrafilters on $I$. Note that $\beta I$ is the free compact Hausdorff space on the set $I$ (with elements of $I$ corresponding to the principal ultrafilters). So any map $I\to \beta I$ extends uniquely to a continuous map $\beta I\to \beta I$. It follows that any map $I\to \beta I$ with dense image extends to a continuous surjection $\beta I\to \beta I$, which is then dual to an injective homomorphism $P(I)\to P(I)$. Since the principal ultrafilters are dense in $\beta I$, we can construct maps $I\to \beta I$ with dense image by splitting $I$ into two subsets of cardinality $|I|$, mapping one of them onto all the principal ultrafilters, and then mapping the rest wherever we want. Thus there are $|\beta I|^{|I|}$ different maps $I\to\beta I$ with dense image. Since $|\beta I|=2^{2^{|I|}}$ (by a well-known theorem of Hausdorff; see this answer, for instance), this means there are $2^{2^{|I|}}$ such maps.

We have thus shown that there are $2^{2^{|I|}}$ different injective homomorphisms $P(I)\to P(I)$. However, we aren't done, because different homomorphisms might correspond to the same subalgebra. If two injective homomorphisms $f,g:P(I)\to P(I)$ have the same image, then $f^{-1}\circ g$ defines an automorphism $h:P(I)\to P(I)$ such that $g=f\circ h$. There are only $2^{|I|}$ such automorphisms (since each one comes from a bijection $I\to I$), and so each subalgebra can only come from $2^{|I|}$ different injective homomorphisms $P(I)\to P(I)$. Thus there must actually be $2^{2^{|I|}}$ different subalgebras of $P(I)$ that are isomorphic to $P(I)$ (and hence complete and atomic).

(If you want to express this all directly in terms of $P(I)$ without using topological properties of $\beta I$, you can do so as follows. Let $S$ be any set of ultrafilters on $P(I)$ containing all the principal ultrafilters. Define a homomorphism $f:P(I)\to P(S)$ by $f(A)=\{U\in S: A\in U\}$. Since $S$ contains all the principal ultrafilters, it is easy to see this $f$ is injective. If $|S|=|I|$, we can can then compose $f$ with an isomorphism $P(S)\to P(I)$ to get an injective homomorphism $f':P(I)\to P(I)$. Moreover, we can recover the set $S$ from $f'$ as the set of inverse images of the principal ultrafilters under $f'$. Since there are $2^{2^{|I|}}$ different such sets $S$ with $|S|=|I|$, this gives $2^{2^{|I|}}$ different injective homomorphisms $P(I)\to P(I)$.)

In conclusion, I expect that you were actually intended to use the other definition of "complete subalgebra"; i.e. a complete subalgebra is a subalgebra which is complete and such that the inclusion map preserves infinite joins and meets. With that definition, your argument works fine to give a canonical bijection between $E(I)$ and $A(I)$.

  • $\begingroup$ Thank you very much. How did you manage to prove it in 20 minutes? :) amazing! $\endgroup$ – Martin Dec 14 '15 at 21:28
  • $\begingroup$ Well, every complete atomic Boolean algebra is isomorphic to $P(S)$ for some set $S$. An injective homomorphism $P(S)\to P(I)$ corresponds to a continuous surjection $\beta S\to \beta I$, which corresponds to a map $S\to \beta I$ with dense image. So if you want to count how many complete atomic Boolean subalgebras of $P(I)$ there are, you are interested in maps to $\beta I$ with dense image. Taking $S=I$ then allows you to control the fact that multiple homomorphisms might have the same image (since there are only $2^{|I|}$ automorphisms of $P(I)$). $\endgroup$ – Eric Wofsey Dec 14 '15 at 21:38

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.