Sets and Operations on Sets

Definition of a Set

We will denote sets with uppercase letters such as $A$, $B$, ..., $X$, $Y$, $Z$, $\mathfrak{A}$, $\mathfrak{B}$, ..., $\mathfrak{Z}$, and so on.

We will denote elements of a set with lowercase letters such as $a$, $b$, ..., $x$, $y$, $z$, $\mathfrak{a}$, $\mathfrak{b}$, ..., $\mathfrak{z}$, and so on.

If the object $a$ is an element of the set $A$, we write $a \in A$.

If the object $b$ is not an element of the set $B$, we write $b \notin B$.

Writing Sets

The notation $A = \{a, b, c\}$ means that the set $A$ consists of the elements $a$, $b$, and $c$.

The notation $B = \{x : x \text{ has property } P\}$ means that the set $B$ consists of all elements $x$ that have the property $P$.

The notation $C = \{y_\gamma \}, \gamma \in \mathfrak{I}$ means that the set $C$ consists of all elements $y_\gamma$, where $\gamma$ belongs to the set $\mathfrak{I}$.

Example of a Set

Consider the set $A$ consisting of the first five natural numbers:$A = \{1, 2, 3, 4, 5\}$.

In this example the elements of the set $A$ are the numbers $1$, $2$, $3$, $4$, and $5$. We can say that the number $3$ is an element of $A$ by writing $3 \in A$, and that the number $6$ is not an element of $A$ by writing $6 \notin A$.

Definition of Set Equality

The equality of sets $A = B$ effectively means that one and the same set is being denoted by two different letters, $A$ and $B$.

Formally, we say that the sets $A$ and $B$ are equal if the following holds for every element $x$:$\forall x \in A \iff x \in B$

$\forall$ is the universal quantifier and means “for every”.

$\iff$ is the logical symbol meaning “if and only if”.

Example of Equal Sets

Consider the sets $A = \{1, 2, 3\}$ and $B = \{3, 2, 1\}$. Even though the elements are written in a different order, they contain the same elements. Therefore, by definition, the sets $A$ and $B$ are equal: $A = B$.

The Empty Set

The empty set is denoted by $\varnothing$.

Definition of a Subset

If the set $A$ is a subset of the set $B$, we write $A \subseteq B$.

It is customary to consider every set a subset of itself, that is, $A \subseteq A$.

In addition, the empty set is a subset of any set, that is,$\varnothing \subseteq A$ for any set $A$.

Example of a Subset

Consider the sets $A = \{1, 2\}$ and $B = \{1, 2, 3, 4, 5\}$. Every element of $A$ (that is, the numbers $1$ and $2$) is also an element of $B$. Therefore we can say that $A$ is a subset of $B$: $A \subseteq B$.

Theorem on Equality of Sets

That is, if $A \subseteq B$ and $B \subseteq A$, then $A = B$.

Proof of the Set Equality Theorem

Definition of a Proper Subset

If the set $A$ is a proper subset of the set $B$, we write $A \subset B$.

This means that all elements of $A$ are also elements of $B$, but there exists at least one element $x$ in $B$ that is not in $A$:$\exists x \in B : x \notin A$

$\exists$ is the existential quantifier and means “there exists”.

Example of a Proper Subset

Consider the sets $A = \{1, 2\}$ and $B = \{1, 2, 3\}$. All elements of $A$ are also elements of $B$, and the set $A$ is not equal to the set $B$. Therefore $A$ is a proper subset of $B$: $A \subset B$.

Union of Sets

The union of the sets $A$ and $B$ is denoted by $A \cup B$.

Example of a Union

If $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$, then their union is$A \cup B = \{1, 2, 3, 4, 5\}$.

For any set $A$, we have $A \cup \varnothing = A$.

Intersection of Sets

The intersection of the sets $A$ and $B$ is denoted by $A \cap B$.

Example of an Intersection

If $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$, then their intersection is$A \cap B = \{3\}$.

Disjoint Sets

If the sets $A$ and $B$ are disjoint, then their intersection equals the empty set:$A \cap B = \varnothing$

Example of Disjoint Sets

Consider the sets $A = \{1, 2\}$ and $B = \{3, 4\}$. Since they have no common elements, they are disjoint sets, and their intersection is the empty set:$A \cap B = \varnothing$.

Properties of the Empty Set

For any set $A$, we have $A \cap \varnothing = \varnothing$. Thus the empty set is equal to itself,$\varnothing = \varnothing$, and it does not intersect with any set, including itself:$A \cap \varnothing = \varnothing$.

The empty set is a subset of every set, that is, $\varnothing \subseteq A$ for any set $A$.

Set Difference

The difference of the sets $A$ and $B$ is denoted by $A \setminus B$.

Example of a Set Difference

If $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5\}$, then their difference is$A \setminus B = \{1, 2\}$.

Set Complement

The complement of $A$ in $B$ is denoted by $B \setminus A$.
In other words, this is just the set difference with a more specific name in this particular case.

Example of a Complement

If $A = \{1, 2\}$ and $B = \{1, 2, 3, 4\}$, then the complement of $A$ in $B$ is$B \setminus A = \{3, 4\}$.

By the definition of set difference, the difference of a set with itself is the empty set:$A \setminus A = \varnothing$

Theorem on Decomposing the Union of Sets

Formally, this can be written as:$A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$

Proof of the Union Decomposition Theorem