View source for Probability Theory/The algebra of sets


== Boolean algebras ==

Within the subject of algebra, there is a structure called  [[w:Algebra over a field|algebra]]. In order to meet our needs, we need to strongly modify this concept to obtain Boolean algebras.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.1 (Boolean algebras)''':

A '''Boolean algebra''' is a set <math>A</math> together with two binary operations <math>\vee</math> and <math>\wedge</math>, an unary operation <math>\neg</math> and <math>0, 1 \in A</math> such that the following axioms hold for all <math>a, b, c \in A</math>:
# Associativity of <math>\vee</math> and <math>\wedge</math>: <math>a \Box (b \Box c) = (a \Box b) \Box c</math>, <math>\Box \in \{\vee, \wedge\}</math>
# Commutativity of <math>\vee</math> and <math>\wedge</math>: <math>a \Box b = b \Box a</math>, <math>\Box \in \{\vee, \wedge\}</math>
# Absorbtion laws: <math>a \Box (a \triangledown b) = a</math>, <math>\{\Box, \triangledown\} = \{\vee, \wedge\}</math>
# Distributivity laws: <math>a \Box (b \triangledown c) = (a \Box b) \triangledown (a \Box c)</math>, <math>\{\Box, \triangledown\} = \{\vee, \wedge\}</math>
# Neutral elements: <math>a \vee 0 = a</math>, <math>a \wedge 1 = a</math>
# Complementation laws: <math>a \vee \neg a = 1</math>, <math>a \wedge \neg a = 0</math>}}

'''Fundamental example 1.2 (logic)''':

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

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Fundamental example and theorem 1.3''':

Let <math>S</math> be an arbitrary set, and let <math>\mathcal A \subset 2^S</math> such that
#<math>S, \emptyset \in \mathcal A</math>
#<math>A, B \in S \Rightarrow A \cup B \in S, A \cap B \in S</math>
#<math>A \in S \Rightarrow \overline A \in S</math>, where <math>\overline A</math> denotes the complement of <math>A</math>.
We set
*<math>1 := S</math>,
*<math>0 := \emptyset</math>,
*<math>\vee := \cup</math>,
*<math>\wedge := \cap</math>, and
*<math>\neg A := \overline A</math> for all <math>A \subseteq S</math>.
Then <math>(\mathcal A, 0, 1, \vee, \wedge, \neg)</math> is a Boolean algebra, called an '''algebra of subsets of <math>S</math>'''.}}

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

1.

:<math>\begin{align}
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{align}</math>

:<math>\begin{align}
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{align}</math>

2.

:<math>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</math>

:<math>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</math>

3.

:<math>\begin{align}
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{align}</math>

:<math>\begin{align}
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{align}</math>

4.

:<math>\begin{align}
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{align}</math>

:<math>\begin{align}
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{align}</math>

5.

:<math>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</math>

:<math>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</math>

6.

:<math>\begin{align}
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{align}</math>

:<math>\begin{align}
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{align}</math>

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 <math>A</math> be a Boolean algebra and <math>a \in A</math>. Prove that <math>a \wedge a = a</math> and <math>a \vee a = a</math>.

== Inclusion ==

== Infinite numbers of subsets ==

== Limits ==

== Notation ==

During the remainder of the book, we shall adhere to the following notation conventions (due to [[w:Felix Hausdorff|Felix Hausdorff]]).
#If the sets <math>A_1, \ldots, A_n</math> are pairwise disjoint, we shall write <math>\sum_{j=1}^n A_j</math> for <math>\bigcup_{j=1}^n A_j</math>; with this notation we already indicate that the <math>A_j</math> are pairwise disjoint. That is, if we encounter an expression such as <math>\sum_{j=1}^n A_j</math> and the <math>A_j</math> are sets, the <math>A_j</math> are assumed to be pairwise disjoint.
#If <math>A, B</math> are sets and <math>A \subseteq B</math>, we replace <math>B \setminus A</math> by <math>B - A</math>. This means: In any occasion where you find the notation <math>B - A</math> within this book, it means <math>B \setminus A</math> and <math>A \subseteq B</math> (note that in this way a set obtains a unique "additive inverse").

{{BookCat}}