Boolean algebras

 I promised to talk about boolean algebras and I'll do that now. Instead of going for the full generality, let's stick with the picture drawn last time. We'll fix a set $U$ which is not empty and look at its subsets. Just for today, we'll call these subsets objects. So saying that $X$ is an object just means that $X\subseteq U$. There are three binary operations between objects that we are interested in. "Binary" here means that the operation takes two objects as its arguments and returns a third one as the result. As you guessed it, those binary operations are $\cup ,\cap ,-$. We'll also consider a unary operation ${}^{\complement }$, i.e. one that takes a single argument $X$ and returns the $X^{\complement }:=U-X$. Note here that this operation ("the complement") only makes sense if we fix an "all-enveloping set" $U$. Otherwise, the complement would be something like

$$\{x:x\notin X\}$$

which is not a set!

In addition to these, our structure will also have two constants, which are simply two distinguished objects $\mathrm{\varnothing }$ and $U$, as well as two binary relations, $=$ and $\subseteq$. Saying that these two relations are binary again means that they take two arguments, but they are different from operations in so much that they do not return an object, but rather the value true or false. For example, $\mathrm{\varnothing }\subseteq U$ is true, while $U\subseteq \mathrm{\varnothing }$ is false (since we assume that $U$ is not empty).

Here's a list of facts which are true for for all objects $X,Y,Z$.

1. $X\cup Y=Y\cup X$
2. $X\cap Y=Y\cap X$
3. $(X\cup Y)\cup Z=X\cup (Y\cup Z)$
4. $(X\cap Y)\cap Z=X\cap (Y\cap Z)$
5. $X\cap (Y\cup Z)=(X\cap Y)\cup (X\cap Z)$
6. $X\cup (Y\cap Z)=(X\cup Y)\cap (X\cup Z)$
7. $X\cap (X\cup Y)=X$
8. $X\cup (X\cap Y)=X$
9. $X\cup X^{\complement }=U$
10. $X\cap X^{\complement }=\mathrm{\varnothing }$

These identities are easy to verify. For example, for the first one, saying that $x\in X\cup Y$ is the same as saying that $x\in X$ or that $x\in Y$, which in turn is the same as saying that $x\in Y$ or that $x\in X$, which is nothing else but asserting that $x\in Y\cup X$. What can be a bit more involved is, for example, the seventh one, so let's think about it.

To verify the identity 7, we may apply the Axiom of Extensionality which tells us to just verify that (a) every element of $X\cap (X\cup Y)$ is also an element of $X$ and that (b) every element of $X$ is also an element of $X\cap (X\cup Y)$. Okay, let's check the part (a). Suppose that $x$ is an element of $X\cap (X\cup Y)$. This means that two things are true: (i) it is true that $x$ belongs to $X$ and (ii) it is true that $x$ belongs to $X\cup Y$. Well, (i) is the only thing that we need, so that's that for (a). So it remains to verify the part (b). How do we do this? Let's look at any $x\in X$. We want to show that $x$ belongs to $X\cap (X\cup Y)$. We do know that $x\in X$. We also know that every element of $X$ is also an element of $X\cup Y$, so we are sure that also $x\in X\cup Y$. Well, this is it: $x\in X$ and $x\in X\cup Y$, so we by definition $x\in X\cap (X\cup Y)$.

The identities that I listed above are not at all randomly chosen. They are in fact everything you need to know about $\cup ,\cap ,\complement$ in the algebraic sense. What I mean by this is that if you have two expressions and if they are always equal to each other, then you can show this by simply playing with the ten identities from the above list. Say, I tell you that $X=X\cup X$ is true. You might try to convince yourself of this by reasoning as we did in the previous paragraph and I have no doubt that you'll succeed in it. However, I tell you that the truth of this fact follows from the ten identities listed above and here's how:

$$X\cup X=X\cup (X\cap (X\cup Y))=X,$$

where for the first equality we apply the identity 7, while for the second one we apply 8. I'm sure that you're wondering why is this better than what we did before. I'm not saying that it is, but the list above successfully axiomatizes boolean algebras in their full generality (which we leave for some other post).

Now, I'm sure that you noted that I haven't said anything about $-$ and $\subseteq$ yet. I did tell you everything that you need to know about $\cup ,\cap ,{}^{\complement },=$ from the algebraic point of view. So, in this spirit, everything you need to know about $\subseteq$ is that $X\subseteq Y$ is true if and only if $X\cap Y^{\complement }=\mathrm{\varnothing }$, and everything you need to know about $-$ is that $X-Y=X\cap Y^{\complement }$. Feel free to play around and convince yourself of this. 😁