Set Theory#

Definitions#

Domain of Discourse#

Definition: The domain of discourse is subject matter we are treating.

Elements#

Symbolic Expression

$x,y,x$ (lowercase letters)

$x_1, x_2, ... , x_n$ (lowercase letters with subscripts)

Definition

The individuals, or objects, in the domain of discourse; The “things” being counted.

Sets#

Symbolic Expression

$A,B,C$ (upper case letters)

$A_1, A_2, ... , A_n$ (uppercase letters with subscripts)

Definition

Groups of elements that share a common property.

Note

Sets are sometimes referred to as classes or collections.

Cardinality#

Symbolic Expression: $n(A)$
Definition: The number of distinct elements in a set.

Universal Set#

Symbolic Expression: $S$
Definition: The universal set S is set of all elements in the domain of discourse.

Null Set#

Symbolic Expression: $\varnothing$
Definition: The unique set which contains nothing, i.e. no elements.

Natural Numbers#

Symbolic Expresison: $\mathbb{N}$
Definition: The set of all counting numbers starting at $1, 2, 3, ...$

Real Numbers#

Symbolic Expression: $\mathbb{R}$
Definition: The set of all decimal numbers, $1, 1.01, 1.001, ...$

Notation#

List Notation#

$A = \{ a, b, c, ... \}$

In list notation, all of the elements that belong to A are explicitly written between a pair of brackets with commas separating each element.

Quantifier Notation#

$A = \{ \forall x: F(x) \}$

In quantifier notation, all of the elements that belong to A are implicitly written between a pair of brackets with a formula that specifies the conditions for membership.

Quantifier notation is sometimes referred to as set builder notation.

Corollaries#

$n(\varnothing)=0$: The number of elements in the null set (the cardinality of the null set) is 0.
$\forall x: x \notin \varnothing$: Nothing belongs to the null set
$\forall x: x \in S$: Everything belongs to the unverisal set

Venn Diagrams#

A Venn Diagram is a visual representation of sets. The universal set is represent as rectangle and sets are represented as circles within this rectangle. The simplest Venn Diagram is a graphic of a single set A shown against the universal set S,

You will sometimes set Venn Diagrams with the elements of the sets written in, as in the following picture,

../_images/sets_simple_with_elements.jpg

Venn Diagrams are useful for visualizing Relations. For this reason, we will see more complex examples of Venn Diagrams in the next section.

Relations#

Subset#

Symbolic Expression: $A \subseteq B$

A is a subset of B if all of A’s elements are contained in B.

To say the same thing in a different way, if the element x belongs to A, then the element x also belongs to B

$\forall x : x \in A \implies x \in B$

The relation of subset can be seen in the following Venn Diagram,

This diagram represents the relationship $A \subseteq B$ .

Proper Subset#

Symbolic Expression: $A \subset B$

A is a subset of B and $A \neq B$ . To say the same thing in a different way, A is wholly contained in B.

$\forall x: x \in A \implies x \in B \text{ and } A \neq B$

An equivalent way of defining a proper subset is given by,

$\forall x: x \in A \implies x \in B \text{ and } n(A) < n(B)$

This is an equivalent formulation because saying cthe cardinality of A is less than the cardinality of B and all members of A are members of B” is logically equivalent to saying “A is not identical to B and all members of A are members of B”.

Equivalence#

Symbolic Expression: $A \equiv B$

Two sets A and B are equivalent if the number of elements in A is equal to the number of elements B, i.e.,

$n(A) = n(B) \implies A \equiv B$

Equality#

Symbolic Expression: $A = B$

Two sets A and B are equal if they contain the same elements. In other words, two sets are equal if they are the same set.

$\forall x: x \in A \implies x \in B \text{ and } x \in B \implies x \in A$

An equivalent way of defining the equality of sets is given by,

$A \subseteq B \text { and } B \subseteq A$

In other words, if A is wholly contained in B and B is wholly contained in A, then the only way this can occur is if $A = B$ .

Equality is a stricter condition than equivalence. Two sets that are equal are equivalent, but two sets that equivalent are not necessarily equal. Consider the sets,

$A = \{ \text{dog}, \text{cat} \}$

$B = \{ \text{Vietnam War}, \text{Russo-Japanese War} \}$

Both of these sets are equivalent because $n(A) = n(B) = 2$ , but they are not equal. If we add C to the mix,

$C = \{ "cat", "dog" \}$

Then not only do we have $n(A) = n(C) = 2$ , but we also have $C = A$ , since they both contain the same elements.

In order words, from equality we can infer equivalence, but from equivalence, we cannot infer equality.

$A = B \implies A \equiv B$

$A \equiv B \not \Rightarrow A = B$

Operations#

Complement#

Symbolic Expression: $A^c$

$\sim A$

The set containing elements that do not belong to the set A.

$A^c = \{ \forall x: x \notin A \}$

The complement can be visualized with the following Venn Diagram,

Tip

The complement of a set corresponds to the English word “not”.

Example: Let S be the set of animals and let A be the set of dogs. Then $A^c$ is the set of animals that are not dogs.

Note

The complement is always taken relative to the universal set. In other words, you cannot find the complement if you do not have the universal set.

Example

$S = \{ \text{ red }, \text{ blue }, \text{ green } \}$

$A = \{ \text{ blue } \}$

$A^c = \{ \text{ red }, \text{ green } \}$

Union#

Symbolic Expression: $A \cup B$

The set containing elements that belong to either the set A or the set B.

$A \cup B = \{ \forall x: x \in A \text{ or } x \in B \}$

We have to be careful with Venn Diagrams that represent unions, because the two sets A and B might have elements in common, or they may not have elements in common.

The first case, where the two sets have no elements in common is shown below,

The union would be represented by both circles. Notice the circles do not touch. Sets that have no elements in common are called disjoint.

The second case, where the two sets have elements in common is shown in the next diagram,

The union would be represented by the entire area of both circles. Notice the circles share some elements in this case. Sets that have elements in common, but are not subsets in either direction (i.e. neither $A \subseteq B$ nor $B \subseteq A$ ), are called overlapping.

Tip

The union of two sets corresponds to the English “or”.

Example: Let A be the set of calculators. Let B represent the set of pencils. Then $A \cup B$ represents the set of calculators or pencils.

Example

$A = \{ a, b, c \}$

$B = \{ b, c, d \}$

$A \cup B = \{ a, b, c, d \}$

Intersection#

Symbolic Expression: $A \cap B$

The set containing elements that to both the set A and the set B.

$A \cap B = \{ \forall x: x \in A \text{ and } x \in B \}$

As in the union, there are two cases we need to consider when representing the interesection of two sets with a Venn Diagram. Either the sets have elements in common, or they do not.

The first case, where the two sets have elements in common is shown in the next diagram,

The intersection is represented by where the circles meet. In the case of overlapping sets, this is non-empty,

$A \cap B \neq \varnothing$

The second case, where the two sets have no elements in common is shown below,

The intersection is represented by where the circles meet. In the case of disjoint sets, the circles do not meet. Thus,

$A \cap B = \varnothing$

Tip

The intersection of two sets corresponds to the English “and”.

Example: Let A be the set of United States Senators. Let B the set of people over the age of 70. Then, $A \cap B$ represents the set of people who are both United States Senators and over the age of 70.

Example

$A = \{ a, b, c \}$

$B = \{ b, c, d \}$

$A \cap B = \{ b, c \}$

Difference#

TODO

The operation of subtracting a set $B$ from a set $A$ is equivalent to taking the intersection the sets $A$ and $B^c$ ,

$A - B = A \cap B^c$

Theorems#

All of the theorems of Set Theory can be proven in one of two ways:

By drawing a Venn Diagram of the sets in question and working out the relations between them graphically.
Writing example sets in List Notation and then applying the definitions of Operations to both sides of the equation.

Note

Most of the set theorems can be phrased in terms of sets, or in terms of cardinalities. We can do this because all of the following theorems are theorems about equality of sets. Recall that from equality we can infer equivalence,

$A = B \implies A \equiv B$

This will be important when we apply these ideas to Probability. For this reason, we will give two versions of each theorem, when possible. One version will be phrased in terms of sets and the other version will be phrased in terms of cardinalities.

Identity Theorems#

Theorem 1#

Symbolc Expression: $A \cap \varnothing = \varnothing$

Or equivalently,

$n(A \cap \varnothing) = n(\varnothing)$

The intersection of any set A with the empty set is the empty set.

Note

Notice the resemblance to zero property of multiplication,

$a \cdot 0 = 0$

Theorem 2#

Symbolic Expression: $A \cup \varnothing = A$

Or equivalently,

$n(A \cup \varnothing) = n(A)$

The union of any set A with the empty set is itself.

Note

Notice the resembalnce to the identity property of addition,

$a + 0 = a$

Theorem 3#

Symbolic Expression: $A \cap S = A$

Or equivalently,

$n(A \cap S) = n(A)$

The intersection of any set A with the universal set is itself.

Note

Notice the resemblance to the identity property of multiplication,

$a \cdot 1 = a$

Theorem 4#

Symbolic Expression: $A \cup S = S$

Or equivalently,

$n(A \cup S) = n(S)$

The union of any set A with the universal set is the universal set.

Note

This theorem does not have an analogous algebraic property. This is where set theory starts to diverge from ordinary algebra.

Theorem 5#

Symbolic Expression: $A \cup A = A$

The union of any set A with itself is itself.

Theorem 6#

Symbolic Expression: $A \cap A = A$

The intersection of any set A with itself is itself.