Discrete Mathematics Study Center

Sets

A set is an unordered collection of objects.

The objects in a set are called the set's elements or members. They are usually listed inside braces. We write $x \in A$ if $x$ is an element (member) of a set $A$ .

$\{1,2,3\}$ is a set with $3$ elements. It is the same as the set $\{1,3,2\}$ (order does not matter) and the set $\{1,1,2,3,3,3,3\}$ (repetition does not matter). Typically, all objects are the same (for example, numbers), but they do not have to be: $\{ 1, 3, \text{red}, \text{blue}, \text{John} \}$ is a set.

Ellipses are used when a pattern is clear: $\{1,2,3,4,\ldots,50\}$ is the set of all integers from $1$ to $50$ , inclusive.

Some sets we use a lot:

$\mathbb{R}$ is the set of real numbers
$\mathbb{N}$ is the set of natural numbers
$\mathbb{Z}$ is the set of integers
$\mathbb{Q}$ is the set of rational numbers

It is possible to have a set with no elements: $\{\}$ . This is the empty set and is usually denoted $\emptyset$ . This is not the same as $\{ \emptyset \}$ , which is a set with one element (that happens to be a (empty) set).

The number of distinct elements in a set $S$ is called its cardinality and is denoted $|S|$ . If $|S|$ is infinite (for example, $\mathbb{Z}$ ), we say the set is infinite.

One common way to define a set is set builder notation. Here are two examples:

$\mathbb{R} = \{ r \;|\; r \text{ is a real number} \}$
$O = \{ x \;|\; x \text{ is an odd integer} \}$

Set Operations

Several operations can be performed on sets.

Union: Given two sets $A$ and $B$ , the union $A \cup B$ is the set of all elements that are in either $A$ or $B$ . For example, if $A = \{ 1,3,5 \}$ and $B = \{ 2,3,6 \}$ , then $A \cup B = \{ 1,2,3,4,5,6 \}$ . Note that $A \cup B = \{ x \;|\; (x \in A) \lor (x \in B) \}$ .
Intersection: Given two sets $A$ and $B$ , the intersection $A \cap B$ is the set of all elements that are in both $A$ and $B$ . For example, if $A = \{ 1,2,3,4 \}$ and $B = \{ 3,4,5,6 \}$ , then $A \cap B = \{ 3,4 \}$ . Note that $A \cap B = \{ x \;|\; (x \in A) \land (x \in B) \}$ . We say that $A$ and $B$ are disjoint if $A \cap B = \emptyset$ .
Difference: Given two sets $A$ and $B$ , the difference $A \setminus B$ is the set of all elements that are in $A$ but not in $B$ . For example, if $A = \{ 1,2,3,4 \}$ and $B = \{ 3,4 \}$ , then $A \setminus B = \{ 1,2 \}$ . Note that $A \setminus B = \{ x \;|\; (x \in A) \land (x \notin B) \}$ . $A \setminus B$ is also denoted $A - B$ .
Complement: Given a set $A$ , the complement $\overline{A}$ is the set of all elements that are not in $A$ . To define this, we need some definition of the universe of all possible elements $U$ . We can therefore view the complement as a special case of set difference, where $\overline{A} = U \setminus A$ . For example, if $U = \mathbb{Z}$ and $A = \{ x \;|\; x \text{ is an odd integer} \}$ , then $\overline{A} = \{ x \;|\; x \text{ is an even number} \}$ . Note that $\overline{A} = \{ x \;|\; x \notin A \}$ .
Cartesian Product: Given two sets $A$ and $B$ , the cartesian product $A \times B$ is the set of ordered pairs where the first element is in $A$ and the second element is in $B$ . We have $A \times B = \{ (a,b) \;|\; a \in A \land b \in B \}$ . For example, if $A = \{ 1,2,3 \}$ and $B = \{ a,b \}$ , then $A \times B = \{ (1,a),(1,b),(2,a),(2,b),(3,a),(3,b) \}$ .

Subsets

A set $A$ is a subset of a set $B$ if every element of $A$ is an element of $B$ . We write $A \subseteq B$ . Another way of saying this is that $A \subseteq B$ if and only if $\forall x\;(x \in A \rightarrow x \in B)$ .

For any set S, we have:

$\emptyset \subseteq S$
Proof: Must show that $\forall x\;{(x \in \emptyset \rightarrow x \in S)}$ . Since $x \in \emptyset$ is always false, the implication is always true. This is an example of a trivial or vacuous proof.
$S \subseteq S$
Proof: Must show that $\forall x\;{(x \in S \rightarrow x \in S)}$ . Fix an element $x$ . We must show that $x \in S \rightarrow x \in S$ . This implication is equivalent to $x \in S \lor x \notin S$ , which is a tautology. Therefore, by Universal Generalization, $S \subseteq S$ .

$A \subseteq B$ and

$A \neq B$ , then we say

$A$ is a proper subset of

$B$ and write

$A \subset B$ .

Power Sets

The power set of a set $A$ is the set of all subsets of $A$ , denoted $\mathcal{P}(A)$ . For example, if $A = \{1,2,3\}$ , then $\mathcal{P}(A) = \{ \emptyset, \{1\},\{2\},\{3\}, \{1,2\},\{2,3\},\{1,3\}, \{1,2,3\} \}$

Notice that $|\mathcal{P}(A)| = 2^{|A|}$ .

Set Equality

Two sets are equal if they contain the same elements. One way to show that two sets $A$ and $B$ are equal is to show that $A \subseteq B$ and $B \subseteq A$ :

$\begin{array}{lll} A \subseteq B \land B \subseteq A & \equiv & \forall x\;{((x \in A \rightarrow x \in B) \land (x \in B \rightarrow x \in A))} \\ &\equiv & \forall x\;{(x \in A \leftrightarrow x \in B)} \\ &\equiv & A = B \\ \end{array}$

Note: it is not enough to simply check if the sets have the same size! They must have exactly the same elements. Remember, though, that order and repetition do not matter.