Probability Theory/The algebra of sets

Boolean algebras

Within the subject of algebra, there is a structure called algebra. In order to meet our needs, we need to strongly modify this concept to obtain Boolean algebras.

Definition 1.1 (Boolean algebras):

A Boolean algebra is a set $A$ together with two binary operations $\vee$ and $\wedge$, an unary operation $\neg$ and $0,1\in A$ such that the following axioms hold for all $a,b,c\in A$:

1. Associativity of $\vee$ and $\wedge$: $a\Box (b\Box c)=(a\Box b)\Box c$, $\Box \in \{\vee ,\wedge \}$
2. Commutativity of $\vee$ and $\wedge$: $a\Box b=b\Box a$, $\Box \in \{\vee ,\wedge \}$
3. Absorbtion laws: $a\Box (a\triangledown b)=a$, $\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
4. Distributivity laws: $a\Box (b\triangledown c)=(a\Box b)\triangledown (a\Box c)$, $\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
5. Neutral elements: $a\vee 0=a$, $a\wedge 1=a$
6. Complementation laws: $a\vee \neg a=1$, $a\wedge \neg a=0$

Fundamental example 1.2 (logic):

If we take $A=\{\bot ,\top \}$ and $\vee ,\wedge ,\neg$ to be the usual operations from logic, we obtain a Boolean algebra.

Fundamental example and theorem 1.3:

Let $S$ be an arbitrary set, and let ${\mathcal {A}}\subset 2^{S}$ such that

1. $S,\emptyset \in {\mathcal {A}}$
2. $A,B\in S\Rightarrow A\cup B\in S,A\cap B\in S$
3. $A\in S\Rightarrow {\overline {A}}\in S$, where ${\overline {A}}$ denotes the complement of $A$.

We set

• $1:=S$,
• $0:=\emptyset$,
• $\vee :=\cup$,
• $\wedge :=\cap$, and
• $\neg A:={\overline {A}}$ for all $A\subseteq S$.

Then $({\mathcal {A}},0,1,\vee ,\wedge ,\neg )$ is a Boolean algebra, called an algebra of subsets of $S$.

Proof: Closedness under the operations follows from 1. - 3. We have to verify 1. - 6. from definition 1.1.

1.

${\begin{aligned}A\cup (B\cup C)&=\{x\in S:x\in A\vee (x\in B\cup C)\}\\&=\{x\in S:x\in A\vee (x\in B\vee x\in C)\}\\&=\{x\in S:(x\in A\vee x\in B)\vee x\in C)\}\\&=\{x\in S:(x\in A\cup B)\vee x\in C\}\\&=(A\cup B)\cup C\end{aligned}}$

${\begin{aligned}A\cap (B\cap C)&=\{x\in S:x\in A\wedge (x\in B\cap C)\}\\&=\{x\in S:x\in A\wedge (x\in B\wedge x\in C)\}\\&=\{x\in S:(x\in A\wedge x\in B)\wedge x\in C)\}\\&=\{x\in S:(x\in A\cap B)\wedge x\in C\}\\&=(A\cap B)\cap C\end{aligned}}$

2.

$A\cup B=\{x\in S:x\in A\vee x\in B\}=\{x\in S:x\in B\vee x\in A\}=B\cup A$

$A\cap B=\{x\in S:x\in A\wedge x\in B\}=\{x\in S:x\in B\wedge x\in A\}=B\cap A$

3.

${\begin{aligned}A\cup (A\cap B)&=\{x\in S:x\in A\vee x\in (A\cap B)\}\\&=\{x\in S:x\in A\vee (x\in A\wedge x\in B)\}\\&=\{x\in S:(x\in A\vee x\in A)\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\}=A\end{aligned}}$

${\begin{aligned}A\cap (A\cup B)&=\{x\in S:x\in A\wedge x\in (A\cup B)\}\\&=\{x\in S:x\in A\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:(x\in A\vee x\in A)\wedge (x\in A\vee x\in B)\}\\&=\{x\in S:x\in A\vee (x\in A\wedge x\in B)\}\\&=\{x\in S:x\in A\}=A\end{aligned}}$

4.

${\begin{aligned}A\cup (B\cap C)&=\{x\in S|x\in A\vee x\in (B\cap C)\}\\&=\{x\in S|x\in A\vee (x\in B\wedge x\in C)\}\\&=\{x\in S|(x\in A\vee x\in B)\wedge (x\in A\vee x\in C)\}\\&=\{x\in S|(x\in A\cap B)\wedge (x\in A\cap C)\}\\&=(A\cap B)\cup (A\cap C)\end{aligned}}$

${\begin{aligned}A\cap (B\cup C)&=\{x\in S|x\in A\wedge x\in (B\cup C)\}\\&=\{x\in S|x\in A\wedge (x\in B\vee x\in C)\}\\&=\{x\in S|(x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)\}\\&=\{x\in S|(x\in A\cup B)\vee (x\in A\cup C)\}\\&=(A\cup B)\cap (A\cup C)\end{aligned}}$

5.

$A\cap S=\{x\in S|x\in A\wedge x\in S\}=\{x\in S|x\in A\wedge \top \}=\{x\in S|x\in A\}=A$

$A\cup \emptyset =\{x\in S|x\in A\vee x\in \emptyset \}=\{x\in S|x\in A\vee \bot \}=\{x\in S|x\in A\}=A$

6.

${\begin{aligned}A\cup {\overline {A}}&=\{x\in S|x\in A\vee (x\in {\overline {A}})\}\\&=\{x\in S|x\in A\vee (x\notin A)\}\\&=\{x\in S|\top \}\\&=S\end{aligned}}$

${\begin{aligned}A\cap {\overline {A}}&=\{x\in S|x\in A\wedge (x\in {\overline {A}})\}\\&=\{x\in S|x\in A\wedge (x\notin A)\}\\&=\{x\in S|\bot \}\\&=S\end{aligned}}$

We thus see that the laws of a Boolean algebra are "elevated" from the Boolean algebra of logic to the Boolean algebra of sets.

Exercises

• Exercise 1.1.1: Let $A$ be a Boolean algebra and $a\in A$. Prove that $a\wedge a=a$ and $a\vee a=a$.

Notation

During the remainder of the book, we shall adhere to the following notation conventions (due to Felix Hausdorff).

1. If the sets $A_{1},\ldots ,A_{n}$ are pairwise disjoint, we shall write $\sum _{j=1}^{n}A_{j}$ for $\bigcup _{j=1}^{n}A_{j}$; with this notation we already indicate that the $A_{j}$ are pairwise disjoint. That is, if we encounter an expression such as $\sum _{j=1}^{n}A_{j}$ and the $A_{j}$ are sets, the $A_{j}$ are assumed to be pairwise disjoint.
2. If $A,B$ are sets and $A\subseteq B$, we replace $B\setminus A$ by $B-A$. This means: In any occasion where you find the notation $B-A$ within this book, it means $B\setminus A$ and $A\subseteq B$ (note that in this way a set obtains a unique "additive inverse").