2
$\begingroup$

Let $\mathscr{B}$ be a Boolean algebra and let $F$ be a finite subset of $\mathscr{B}$. Is $\left<F\right>$, the subalgebra generated by $F$, necessarily a finite subalgebra of $\mathscr{B}$?

I thinks that this is true based on following argument: Denote the elements of $F$ by $x_1,\ldots,x_n$, and consider the $2^n$ possible ways of forming $\land$(meet) of $n$ elements $x_{1}^{e_1},\ldots,x_{i}^{e_i},\ldots x_{n}^{e_n}$ where each $e_i$ can be either the empty word, or the complement symbol '. Let $A$ be the subset of $\mathscr{B}$ having just those $2^n$ values. Some of these $2^n$ ways might yield same elements of $\mathscr{B}$, hence we have a subset $A$ of $\mathscr{B}$ with at most $2^n$ elements. Then $\left<F\right>$ is isomorphic to $\mathscr{P}(A)$, the Boolean algebra of subsets of a set having $|A|$ elements.

I came up with this idea while pondering upon the image of a venn diagram with $n$ circles. I think that this argument is valid, and can be completed in a rigorous way, but I am not sure. Is this a valid argument? Is the statement true?

$\endgroup$
4
$\begingroup$

The statement is right, but your proof is not correct. For example, suppose $F=\{x_1, x_2\}$ with $x_1< x_2$ (that is, $x_1\not=x_2$ and $x_1\vee x_2=x_2$).

Then the $A$ we get consists of $$a_1=x_1\wedge x_2,\quad a_2=x_1\wedge x_2', \quad a_3=x_1'\wedge x_2,\quad a_4=x_1'\wedge x_2'.$$ But distinct elements of the powerset of $A$ do not necessarily correspond to distinct elements of $\langle F\rangle$! Namely, both $\emptyset$ and $\{a_3\}$ correspond to $\bot$, since $x_1<x_2$.

So really, the right statement is that $\langle F\rangle$ is a homomorphic image, or quotient, of $\mathcal{P}(A)$.

$\endgroup$
  • $\begingroup$ But isn't it true that $\left<F\right>$ is isomorphic to $\mathscr{P}(A)$?. I believe your point is that the $A$ I constructed has no reason to be a subalgebra. But I guess they are the atoms of $\left<F\right>$ so that $\left<F\right>$ is a finite Boolean algebra with $|A|$ atoms... thus isomorphic to $\mathscr{P}(A). $\endgroup$ – Dilemian Dec 22 '16 at 10:51
  • $\begingroup$ @Dilemian I misread, and have edited my answer. There's still a problem, though: $P(A)$ might be bigger than $\langle F\rangle$. $\endgroup$ – Noah Schweber Dec 22 '16 at 20:21
2
$\begingroup$

The free Boolean ring on $n$ generators is nothing more than the polynomial ring $\mathbb{F}_2[x_1,x_2,\dots,x_n]$ modulo the ideal generated by $x_i^2-x_i$, for $i=1,2,\dots n$, so it's essentially the set of linear combinations of monomials having degree at most $1$ in each variable, with coefficients in $\mathbb{F}_2$; there are $2^n$ such monomials, so the free Boolean ring on $n$ generators has $2^{2^n}$ elements. Since Boolean rings and Boolean algebras are the same thing, the free Boolean algebra on $n$ generators is finite.

The subalgebra generated by $F$ is a homomorphic image of a free algebra on $|F|$ generators, so it is finite as well.

Note that the homomorphism need not be injective; for instance, the Boolean subalgebra of $A=\mathscr{P}(\{1,2\})$ generated by $\{1\}$ and $\{2\}$ is $A$ itself, but the free algebra on two elements has $16$ elements. The fact is that between elements of $F$ there can be nontrivial relations, in this case $\{2\}$ is the complement of $\{1\}$.

$\endgroup$
  • $\begingroup$ That's a neat argument. I never realized that the perspective of Boolean rings made free Boolean algebras so simple to describe. $\endgroup$ – Eric Wofsey Dec 22 '16 at 21:16
  • $\begingroup$ @EricWofsey I always get lost with prenex form and the like, so I just switch to rings which I'm more familiar with. $\endgroup$ – egreg Dec 22 '16 at 21:28
0
$\begingroup$

For finite $m$ and $n,$ an $n$-generated Boolean algebra has at most $2^n$ atoms, and a finite Boolean algebra with $m$ atoms has exactly $2^m$ elements. A free Boolean algebra on $n$ generators has exactly $2^n$ atoms (which you described) and exactly $2^{2^n}$ elements.

$\endgroup$

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.