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
{\displaystyle A}
∨
{\displaystyle \vee }
∧
{\displaystyle \wedge }
¬
{\displaystyle \neg }
0
,
1
∈
A
{\displaystyle 0,1\in A}
a
,
b
,
c
∈
A
{\displaystyle a,b,c\in A}
Associativity of
∨
{\displaystyle \vee }
∧
{\displaystyle \wedge }
a
◻
(
b
◻
c
)
=
(
a
◻
b
)
◻
c
{\displaystyle a\Box (b\Box c)=(a\Box b)\Box c}
◻
∈
{
∨
,
∧
}
{\displaystyle \Box \in \{\vee ,\wedge \}}
Commutativity of
∨
{\displaystyle \vee }
∧
{\displaystyle \wedge }
a
◻
b
=
b
◻
a
{\displaystyle a\Box b=b\Box a}
◻
∈
{
∨
,
∧
}
{\displaystyle \Box \in \{\vee ,\wedge \}}
Absorbtion laws:
a
◻
(
a
▽
b
)
=
a
{\displaystyle a\Box (a\triangledown b)=a}
{
◻
,
▽
}
=
{
∨
,
∧
}
{\displaystyle \{\Box ,\triangledown \}=\{\vee ,\wedge \}}
Distributivity laws:
a
◻
(
b
▽
c
)
=
(
a
◻
b
)
▽
(
a
◻
c
)
{\displaystyle a\Box (b\triangledown c)=(a\Box b)\triangledown (a\Box c)}
{
◻
,
▽
}
=
{
∨
,
∧
}
{\displaystyle \{\Box ,\triangledown \}=\{\vee ,\wedge \}}
Neutral elements:
a
∨
0
=
a
{\displaystyle a\vee 0=a}
a
∧
1
=
a
{\displaystyle a\wedge 1=a}
Complementation laws:
a
∨
¬
a
=
1
{\displaystyle a\vee \neg a=1}
a
∧
¬
a
=
0
{\displaystyle a\wedge \neg a=0}
Fundamental example 1.2 (logic) :
If we take
A
=
{
⊥
,
⊤
}
{\displaystyle A=\{\bot ,\top \}}
∨
,
∧
,
¬
{\displaystyle \vee ,\wedge ,\neg }
Fundamental example and theorem 1.3 :
Let
S
{\displaystyle S}
A
⊂
2
S
{\displaystyle {\mathcal {A}}\subset 2^{S}}
S
,
∅
∈
A
{\displaystyle S,\emptyset \in {\mathcal {A}}}
A
,
B
∈
S
⇒
A
∪
B
∈
S
,
A
∩
B
∈
S
{\displaystyle A,B\in S\Rightarrow A\cup B\in S,A\cap B\in S}
A
∈
S
⇒
A
¯
∈
S
{\displaystyle A\in S\Rightarrow {\overline {A}}\in S}
A
¯
{\displaystyle {\overline {A}}}
A
{\displaystyle A}
We set
1
:=
S
{\displaystyle 1:=S}
0
:=
∅
{\displaystyle 0:=\emptyset }
∨
:=
∪
{\displaystyle \vee :=\cup }
∧
:=
∩
{\displaystyle \wedge :=\cap }
¬
A
:=
A
¯
{\displaystyle \neg A:={\overline {A}}}
A
⊆
S
{\displaystyle A\subseteq S}
Then
(
A
,
0
,
1
,
∨
,
∧
,
¬
)
{\displaystyle ({\mathcal {A}},0,1,\vee ,\wedge ,\neg )}
algebra of subsets of
S
{\displaystyle S}
.
Proof : Closedness under the operations follows from 1. - 3. We have to verify 1. - 6. from definition 1.1.
1.
A
∪
(
B
∪
C
)
=
{
x
∈
S
:
x
∈
A
∨
(
x
∈
B
∪
C
)
}
=
{
x
∈
S
:
x
∈
A
∨
(
x
∈
B
∨
x
∈
C
)
}
=
{
x
∈
S
:
(
x
∈
A
∨
x
∈
B
)
∨
x
∈
C
)
}
=
{
x
∈
S
:
(
x
∈
A
∪
B
)
∨
x
∈
C
}
=
(
A
∪
B
)
∪
C
{\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}}}
A
∩
(
B
∩
C
)
=
{
x
∈
S
:
x
∈
A
∧
(
x
∈
B
∩
C
)
}
=
{
x
∈
S
:
x
∈
A
∧
(
x
∈
B
∧
x
∈
C
)
}
=
{
x
∈
S
:
(
x
∈
A
∧
x
∈
B
)
∧
x
∈
C
)
}
=
{
x
∈
S
:
(
x
∈
A
∩
B
)
∧
x
∈
C
}
=
(
A
∩
B
)
∩
C
{\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}}}
2.
A
∪
B
=
{
x
∈
S
:
x
∈
A
∨
x
∈
B
}
=
{
x
∈
S
:
x
∈
B
∨
x
∈
A
}
=
B
∪
A
{\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}
A
∩
B
=
{
x
∈
S
:
x
∈
A
∧
x
∈
B
}
=
{
x
∈
S
:
x
∈
B
∧
x
∈
A
}
=
B
∩
A
{\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}
3.
A
∪
(
A
∩
B
)
=
{
x
∈
S
:
x
∈
A
∨
x
∈
(
A
∩
B
)
}
=
{
x
∈
S
:
x
∈
A
∨
(
x
∈
A
∧
x
∈
B
)
}
=
{
x
∈
S
:
(
x
∈
A
∨
x
∈
A
)
∧
(
x
∈
A
∨
x
∈
B
)
}
=
{
x
∈
S
:
x
∈
A
∧
(
x
∈
A
∨
x
∈
B
)
}
=
{
x
∈
S
:
x
∈
A
}
=
A
{\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}}}
A
∩
(
A
∪
B
)
=
{
x
∈
S
:
x
∈
A
∧
x
∈
(
A
∪
B
)
}
=
{
x
∈
S
:
x
∈
A
∧
(
x
∈
A
∨
x
∈
B
)
}
=
{
x
∈
S
:
(
x
∈
A
∨
x
∈
A
)
∧
(
x
∈
A
∨
x
∈
B
)
}
=
{
x
∈
S
:
x
∈
A
∨
(
x
∈
A
∧
x
∈
B
)
}
=
{
x
∈
S
:
x
∈
A
}
=
A
{\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}}}
4.
A
∪
(
B
∩
C
)
=
{
x
∈
S
|
x
∈
A
∨
x
∈
(
B
∩
C
)
}
=
{
x
∈
S
|
x
∈
A
∨
(
x
∈
B
∧
x
∈
C
)
}
=
{
x
∈
S
|
(
x
∈
A
∨
x
∈
B
)
∧
(
x
∈
A
∨
x
∈
C
)
}
=
{
x
∈
S
|
(
x
∈
A
∩
B
)
∧
(
x
∈
A
∩
C
)
}
=
(
A
∩
B
)
∪
(
A
∩
C
)
{\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}}}
A
∩
(
B
∪
C
)
=
{
x
∈
S
|
x
∈
A
∧
x
∈
(
B
∪
C
)
}
=
{
x
∈
S
|
x
∈
A
∧
(
x
∈
B
∨
x
∈
C
)
}
=
{
x
∈
S
|
(
x
∈
A
∧
x
∈
B
)
∨
(
x
∈
A
∧
x
∈
C
)
}
=
{
x
∈
S
|
(
x
∈
A
∪
B
)
∨
(
x
∈
A
∪
C
)
}
=
(
A
∪
B
)
∩
(
A
∪
C
)
{\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}}}
5.
A
∩
S
=
{
x
∈
S
|
x
∈
A
∧
x
∈
S
}
=
{
x
∈
S
|
x
∈
A
∧
⊤
}
=
{
x
∈
S
|
x
∈
A
}
=
A
{\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}
A
∪
∅
=
{
x
∈
S
|
x
∈
A
∨
x
∈
∅
}
=
{
x
∈
S
|
x
∈
A
∨
⊥
}
=
{
x
∈
S
|
x
∈
A
}
=
A
{\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}
6.
A
∪
A
¯
=
{
x
∈
S
|
x
∈
A
∨
(
x
∈
A
¯
)
}
=
{
x
∈
S
|
x
∈
A
∨
(
x
∉
A
)
}
=
{
x
∈
S
|
⊤
}
=
S
{\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}}}
A
∩
A
¯
=
{
x
∈
S
|
x
∈
A
∧
(
x
∈
A
¯
)
}
=
{
x
∈
S
|
x
∈
A
∧
(
x
∉
A
)
}
=
{
x
∈
S
|
⊥
}
=
S
{\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}}}
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
A
{\displaystyle A}
a
∈
A
{\displaystyle a\in A}
a
∧
a
=
a
{\displaystyle a\wedge a=a}
a
∨
a
=
a
{\displaystyle a\vee a=a}
Infinite numbers of subsets
edit
During the remainder of the book, we shall adhere to the following notation conventions (due to Felix Hausdorff ).
If the sets
A
1
,
…
,
A
n
{\displaystyle A_{1},\ldots ,A_{n}}
∑
j
=
1
n
A
j
{\displaystyle \sum _{j=1}^{n}A_{j}}
⋃
j
=
1
n
A
j
{\displaystyle \bigcup _{j=1}^{n}A_{j}}
A
j
{\displaystyle A_{j}}
∑
j
=
1
n
A
j
{\displaystyle \sum _{j=1}^{n}A_{j}}
A
j
{\displaystyle A_{j}}
A
j
{\displaystyle A_{j}}
If
A
,
B
{\displaystyle A,B}
A
⊆
B
{\displaystyle A\subseteq B}
B
∖
A
{\displaystyle B\setminus A}
B
−
A
{\displaystyle B-A}
B
−
A
{\displaystyle B-A}
B
∖
A
{\displaystyle B\setminus A}
A
⊆
B
{\displaystyle A\subseteq B}
