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
together with two binary operations
and
, an unary operation
and
such that the following axioms hold for all
:
- Associativity of
and
:
, ![{\displaystyle \Box \in \{\vee ,\wedge \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ff195437d6e49e7d87b42b3cf6dac548bea745a)
- Commutativity of
and
:
, ![{\displaystyle \Box \in \{\vee ,\wedge \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ff195437d6e49e7d87b42b3cf6dac548bea745a)
- Absorbtion laws:
, ![{\displaystyle \{\Box ,\triangledown \}=\{\vee ,\wedge \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a1e0b39e38b3dc3e2beb33f56d718db4dfdcf7)
- Distributivity laws:
, ![{\displaystyle \{\Box ,\triangledown \}=\{\vee ,\wedge \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a1e0b39e38b3dc3e2beb33f56d718db4dfdcf7)
- Neutral elements:
, ![{\displaystyle a\wedge 1=a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/342bb18c985f0ce6a6dc319454d6ae0178374712)
- Complementation laws:
, ![{\displaystyle a\wedge \neg a=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/663edb0d73db4441d4c5cfe99dc68385aa7d99de)
Fundamental example 1.2 (logic):
If we take
and
to be the usual operations from logic, we obtain a Boolean algebra.
Fundamental example and theorem 1.3:
Let
be an arbitrary set, and let
such that
![{\displaystyle S,\emptyset \in {\mathcal {A}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3d2c5060a79f067e2299d7c1d09f71427d015fb)
![{\displaystyle A,B\in S\Rightarrow A\cup B\in S,A\cap B\in S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ae78a6ddd12c6360998f0248648feda4a3b4ead)
, where
denotes the complement of
.
We set
,
,
,
, and
for all
.
Then
is a Boolean algebra, called an algebra of subsets of
.
Proof: Closedness under the operations follows from 1. - 3. We have to verify 1. - 6. from definition 1.1.
1.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fab3e133f5c17efd8348c64742a08bcdfd4ad8f)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df96c551c909c1d1be7f51302507f4c7ac52c739)
2.
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/284f730630acbf359925dc523881a5df8dccfb7b)
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0516104cb2607288d43e983ce0c97be960336d8)
3.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1334a42c6f54a1f9d9f836f02e10e63abf6d4e0e)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af16e85896a4b95219a0da2c8a2adbe328ee235a)
4.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b9e1370f4258035c1a536daa57b35e6a62a8b3e)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdfce81795515ea9e86ef5eed8a6bd53f3c4b6d1)
5.
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f84633eb6ebb4441c0b470408c86864db6fa84f)
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab5b46a41358ad2e2dc421a278259d1cde207574)
6.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/731eba4adec878b8ece3755b11b071d20688f13b)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f85932de7383abc394f15a13fd8f032b0303e8)
We thus see that the laws of a Boolean algebra are "elevated" from the Boolean algebra of logic to the Boolean algebra of sets.
- Exercise 1.1.1: Let
be a Boolean algebra and
. Prove that
and
.
During the remainder of the book, we shall adhere to the following notation conventions (due to Felix Hausdorff).
- If the sets
are pairwise disjoint, we shall write
for
; with this notation we already indicate that the
are pairwise disjoint. That is, if we encounter an expression such as
and the
are sets, the
are assumed to be pairwise disjoint.
- If
are sets and
, we replace
by
. This means: In any occasion where you find the notation
within this book, it means
and
(note that in this way a set obtains a unique "additive inverse").