Chapter 1 Introduction to the Algebra of Sets

This is the first real chapter.

knitr::opts_chunk$set(dev = "tikz")

1.1 Sets

plot(1:10)
plot(rnorm(10), pch=19)

Figure 1.1: two plots

“A set is a Many that allows itself to be thought of as a One.” - Georg Cantor

A set is a collection of objects. The objects in a set can be anything. In probability theory, we call these objects elements or numbers or outcomes or events.

Sets usually denoted by capital letters, A, B, C, etc.
Elements of sets denoted by a, b, c, etc.

\(\hspace{10 mm}\) If a belongs to A we write

\(\hspace{20 mm} \textit{a} \in A\)

\(\hspace{10 mm}\) If a does not belong to A we write

\(\hspace{20 mm} \textit{a} \notin A\)

\(\hspace{1 mm}\) Example 1: V = {x | x is a vowel} (read “|” as “such that”)

\(\hspace{29 mm}\) = {a, e, i, o, u}

This set can be rostered, i.e. listed - A finite set.

\(\hspace{1 cc}\) Example 2: D = {x | x are points on a die}

\(\hspace{29 mm}\) = {1, 2, 3, 4, 5 , 6}
\(\vspace{1 mm}\)

This set also can be rostered.
These sets are discrete, but not all discrete sets can be rostered.

\(\hspace{1 cc}\) Example 3: P = {x | x is a prime number}
\(\vspace{1 mm}\)

This is a denumerably infinite set.

\(\hspace{1 cc}\) Example 4: T = {x | x is a triangle in the plane}

This is a nondenumerable, infinite set.

1.2 Subsets

If every element of A also belongs to B, we call A a subset of B.

This is denoted

\(\hspace{1 cc} A \in B\)

If \(A \in B\) and \(B \in A\), then A = B. \([A \subseteq B]\)

If \(A \in B\) and \(A \neq B\), then A is a proper subset of B. \([A \subset B]\)

Every set is a subset of itself.

\(\hspace{1 cc}\) Example 1: Tossing a die where outcomes are even constitutes a subset of the set of possible outcomes.

\(\hspace{2 in}\) \(\left \{ 2, 4, 6 \right \} \subset \left \{ 1, 2, 3, 4, 5, 6 \right \}\).
\(\vspace{1 mm}\)

All sets are subsets of some particular set called the Universal Set (U). This is also called in probability theory the Sample Space (S), the set of all possible simple events or outcomes of an experiment.

\(\hspace{1 cc}\) Example 2: The set of all possible outcomes for the toss of a die is

\(\hspace{2 in}\) S = {1, 2, 3, 4, 5, 6}
\(\vspace{1 mm}\)

A set having no elements is called the null or empty set, denoted \(\varnothing\).

1.3 Venn Diagrams

[British mathematician John Venn, 1834-1923; though Euler had a similar idea much earlier.]

Venn Diagrams provide geometric intuition about relations among sets, but they do not represent or substitute for formal proofs. Moreover, they are not practical when the number of sets exceeds three or so.
\(\vspace{1 mm}\)

Figure 1.2: Some caption.

1.4 Set Operations

1.4.1 1. Union

The union of sets A and B, denoted \(A \cup B\), consists of all elements belonging to A or B [or both A and B].

\(\hspace{1.5 in} x \in A\cup V \Rightarrow x\in A\) or \(x \in B\) or \(x\in\) both A and B.

Figure 1.3: Some caption.

\(\hspace{1.25 in} A \cup B\) \(\hspace{2.75 in}A \cup B\) \(\vspace{1 mm}\)

1.4.2 2. Intersection

The set of all elements belonging to both A and B, denoted by \(A \cap B\) (or sometimes AB).

\(\hspace{.25 in} x \in A \cap B \Rightarrow x \in A\) and \(x \in B\)
\(\vspace{1 mm}\)

Figure 1.4: Some caption.

\(\hspace{.25in} A \cup B = \o\) [Sets are mutually exclusive]

\(\hspace{.25 in}\) If \(x \in A\), \(x \notin B\) and vice versa.
\(\vspace{1 mm}\)

1.4.3 3. Difference

The set of elements in A that do not belong to B is called the difference of A and B and denoted A – B (sometimes A/B).

\(\hspace{.25in} x \in A - B \Rightarrow\) \(\hspace{.25in} x \in A\) and \(x \notin B\)
\(\vspace{1 mm}\)

1.4.4 4. Complement

If \(B \subset A\), then A – B is calld the complement of B relative to A, denoted

\({B}'_{A}\left [ \textup{or } \bar{B} _{A} \textup{ or } - B_{A} \right ]\)

If A=U, U-B is called simply the complement of B denoted

\({B}'\left [ \textup{or } \bar{B} \textup{ or } \sim B\right ]\)

\(\vspace{1 in}\)

\(\pagebreak\)

1.5 Some Theorems Involving Sets

You should be able to prove the following:

Theorem 1-1.\(\hspace{10 mm}\) If \(A \subset B\) and \(B \subset C\), then \(A \subset C\).

\(\hspace{32 mm} x \in A \Rightarrow x \in B \Rightarrow x \in C\).

\(\hspace{32 mm}\) Then \(x \in A \Rightarrow x \in C\).
\(\vspace{1 mm}\)

Theorem 1-2.\(\hspace{10 mm} A \cup B = B \cup A\).¹ \(\vspace{1 mm}\)

Theorem 1-3.\(\hspace{10 mm} A\cup ( B \cup C ) = (A \cup B) \cup C = A \cup B \cup C\).² \(\vspace{1 mm}\)

Theorem 1-4. \(\hspace{10 mm} A \cap B = B \cap A\).
³ \(\vspace{1 mm}\)

Theorem 1-5.\(\hspace{10 mm} A\cap ( B \cap C ) = (A \cap B) \cap C = A \cap B \cap C\).
⁴ \(\vspace{1 mm}\)

Theorem 1-6. \(\hspace{10 mm} A \cap(B \cup C) = (A \cap B) \cup (A \cap C)\).⁵ \(\vspace{1 mm}\)

Theorem 1-7. \(\hspace{10 mm} A \cup(B \cap C) = (A \cup B) \cap (A \cup C)\).⁶

Theorem 1-8. \(\hspace{10 mm} A - B = A \cap {B}'\).
\(\vspace{1 mm}\)

Theorem 1-9. \(\hspace{10 mm}\) If \(A \subset B\), then \({B}' \subset {A}'\).
\(\vspace{1 mm}\)

Theorem 1-10. \(\hspace{10 mm} A \cup \o = A\). \(A \cap \o = \o\).
\(\vspace{1 mm}\)

Theorem 1-11. \(\hspace{10 mm} A \cup U = U\). \(A \cap U = A\).
\(\vspace{1 mm}\)

Theorem 1-12a. \(\hspace{10 mm} {(A \cup B)}' = {A}' \cap {B}'\).⁷ \(\vspace{1 mm}\)

Theorem 1-12b.\(\hspace{10 mm} {(A \cap B)}' = {A}' \cup {B}'\).⁸ \(\vspace{1 mm}\)

Theorem 1-13. \(\hspace{10 mm} A = (A \cap B) \cup (A \cap {B}')\). \(\vspace{1 mm}\)

\(\pagebreak\)

Principle of Duality: Any true relation remains true if we replace ‘\(\cup\)’ by ‘\(\cap\)’, ‘\(\cap\)’ by ‘\(\cup\)’, sets by their complements and if we reverse inclusion symbols ‘\(\subset\)’ and ‘\(\supset\)’.

Consider the following sets:

\(\hspace{10 mm}\) U = {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4}

\(\hspace{10 mm}\) A = {\(-\sqrt{2}\), \(\pi\), 0}

\(\hspace{10 mm}\) B = {5, 1/2, \(-\sqrt{2}\), -4}

\(\hspace{10 mm}\) C = {1/2, -4}

Use these sets to illustrate Theorems 2-13.

\(A \cup B\) = {\(1/2, 0, \pi, 5, -\sqrt{2}, -4\)} = \(B \cup A\).
\(A \cup (B \cup C) = (A \cup B) \cup C = A \cup B \cup C\) = {\(1/2, 0, \pi, 5, -\sqrt{2}, -4\)}.
\(A \cap B\) = {\(-\sqrt{2}\)} = \(B \cap A\).
\(A \cap (B \cup C)\) = \(A \cap\) ({1/2, -4}) = {\(-\sqrt{2}, \pi, 0\)} \(\cap\) {1/2, -4} = \(\o\)
\(A \cap (B \cap C)\) = {\(-\sqrt{2}, \pi, 0\)} \(\cap\) {\(5, 1/2, -\sqrt{2}, -4\)} = \((A \cap B) \cup (A \cap C)\) = {\(-\sqrt{2}\)} \(\cup \o\) = {\(-\sqrt{2}\)}.
\(A \cup (B \cap C)\) = {\(-\sqrt{2}, \pi\), 0} \(\cup\) {1/2,-4} = {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4}.
= \((A \cup B) \cap (A \cup C)\) = {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4} \(\cap\) {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4} = {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4}.
\(B - A = B \cap {A}'\)
{\(5, 1/2, -\sqrt{2}, -4\)} - {\(-\sqrt{2}, \pi\), 0} = {5, 1/2, -4} = {\(5, 1/2, -\sqrt{2}, -4\)} \(\cap\) {5, 1/2, -4}.
\(C \subset B\)
{1/2, -4} \(\subset\) {\(5, 1/2, -\sqrt{2}, -4\)}.
\({C}'\) = {\(0, \pi, 5, -\sqrt{2}\)}.
\({B}'\) = {0, \(\pi\)} \(\Rightarrow {B}' \subset {A}'\).
\(A \cup U\) = {1/2, 0, \(\pi\), 5, \(-\sqrt{2}\), -4}.
\((A \cup {B})'\) = \(\o\). \({A}' \cap {B}'\) = {5, 1/2, -4} \(\cap\) {\(\pi\), 0} = \(\o\).
\((A \cap B)'\) = {1/2, 0, \(\pi\), 5, -4}.
\({A}' \cup {B}'\) = {5, 1/2, -4} \(\cup\) {\(\pi\), 0} = {1/2, 0, \(\pi\), 5, -4}.
(A \(\cap\) B) \(\cup\) (A \(\cap {B}'\)) = {1/2} \(\cup\) {\(-\sqrt{2}, \pi, 0\)} \(\cap\) {\(\pi\), 0} = {\(-\sqrt{2}, \pi\), 0} = A.

Commutative law for unions↩
Associative law for unions↩
Commutative law for intersections↩
Associative law for intersections↩
First distributive law↩
Second distributive law↩
DeMorgan’s First Law↩
DeMorgan’s Second Law↩