3
$\begingroup$

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?

$\endgroup$
2
  • $\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$ Commented Dec 14, 2015 at 20:51
  • $\begingroup$ A complete atomic subalgebra is a subalgebra that happens to be complete and atomic. I will edit it, thanks. $\endgroup$ Commented Dec 14, 2015 at 20:55

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you very much. How did you manage to prove it in 20 minutes? :) amazing! $\endgroup$ Commented Dec 14, 2015 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$ Commented Dec 14, 2015 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .