# 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$:
* Associativity of $\vee$ and $\wedge$: $a\Box (b\Box c)=(a\Box b)\Box c$, $\Box \in \{\vee ,\wedge \}$
* Commutativity of $\vee$ and $\wedge$: $a\Box b=b\Box a$, $\Box \in \{\vee ,\wedge \}$
* Absorbtion laws: $a\Box (a\triangledown b)=a$, $\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
* Distributivity laws: $a\Box (b\triangledown c)=(a\Box b)\triangledown (a\Box c)$, $\{\Box ,\triangledown \}=\{\vee ,\wedge \}$
* Neutral elements: $a\vee 0=a$, $a\wedge 1=a$
* 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
* $S,\emptyset \in {\mathcal {A}}$
* $A,B\in S\Rightarrow A\cup B\in S,A\cap B\in S$
* $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).
* 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.
* 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").