Sets

Roughly speaking, a set is a collection of objects. The objects are called the members or the elements of the set.

Set theory is the basis for mathematics, and there are a number of axiom systems for set theory; von Neumann-G\"odel-Bernays (NBG) and Zermelo-Fraenkel-Choice (ZFC) are the most well-known. I'm going to take a somewhat informal approach to avoid unnecessary complexity.

Examples. You construct or define a set by saying what its elements are.

You can define a set by listing its elements between curly brackets:

$\{1, 2, 3, \hbox{Calvin}\}.$

The order of the elements in the list is irrelevant; thus,

$\{1, 2, 3, \hbox{Calvin}\} \quad\hbox{is the same as}\quad \{\hbox{Calvin}, 2, 1, 3\}.$

In fact, two sets are equal if and only if they have the same elements.

It's understood when you list the elements of a set that no duplicates are allowed.

You can also define a set using set constructor notation. Here's an example:

$\{n \in \integer \mid n \quad\hbox{is a perfect square}\}.$

The set constructor consists of two statements separated by a " $\mid$ ", contained in curly brackets. The two statements together give the properties which must be satisfied by an element of the set. (Thus, the " $\mid$ " functions like a logical "and".) Usually, the first statement is more general than the second.

In this case, the set consists of all integers which are perfect squares. I could write this more explicitly (but less precisely) as

$\{0, 1, 4, 9, \ldots\}.$

(This is less precise because the "..." assumes that it is clear what the pattern is.)

Here's an example using two variables:

$\{(x,y) \mid x, y \in \real \quad\hbox{and}\quad y = x^2\}.$

This set consists of pairs of real numbers such that the second is the square of the first. (By the way, the last sentence gives a verbal description of the set. It's useful to say things in words when the symbols get confusin.) Here are some elements of the set:

$(-1,1), (0,0), (\sqrt{3}, 3), (1.1, 1.21), \ldots.$

In this case, I can't list the elements of the set --- when I discuss cardinality, I'll explain why --- and thus, it's particularly important to have a set constructor definition available.

You can also have sets whose elements are sets. For example,

$\{\{1, 2\}, \{3, \hbox{Calvin}\}, \pi\}$

is a set with three elements, two of which are sets with two elements.

Definition. The set with no elements is called the empty set, and is denoted $\emptyset$ or $\{\hphantom{\cdot}\}$ .

Warning. You have to be a little bit careful in constructing sets in order to avoid set-theoretic paradoxes. For example, here is Russell's paradox. Consider "the set S of all sets which are not members of themselves". Is S an element of S?

If S is an element of S, then by definition S is not a member of itself --- contradicting my assumption that S is an element of S.

If S is not an element of S, then S is an element of S, since S consists of sets which are not members of themselves. This is also a contradiction.

By the Law of the Excluded Middle, either S is an element of S, or it is not --- but both alternatives lead to contradictions.

Paradoxes of this kind are avoided by setting up axioms for set theory which do not allow the construction of sets such as this one.

Notation. If S is a set, $x \in S$ means that x is an element of S. $x \notin S$ means that x is not an element of S.

Here is some notation for some sets that occur often in mathematics.

$\integer$ is the set of integers.

$\rational$ is the set of rational numbers.

$\real$ is the set of real numbers.

$\complex$ is the set of complex numbers.

If you just want the positive integers (also known as the natural numbers, use $\integer^+$ or $\natural$ ; if you want the nonnegative integers, use $\integer^{\ge 0}$ .

Definition. Let S and T be sets. T is a subset of S if and only if $x \in T$ implies $x \in S$ . $T \subset S$ means that T is a subset of S, and $T \not\subset S$ means that T is not a subset of S.

This picture illustrates $T \subset S$ :

$\hbox{\epsfysize=1in \epsffile{sets1.eps}}$

The picture above is called a Venn diagram. Venn diagrams are often useful for picturing sets and relationships among sets. Be careful not to substitute diagrams for proofs, however!

Definition. Let S and T be sets. if and only if $S \subset T$ and $T \subset S$ . (In words, every element of S is an element of T, and every element of T is an element of S.)

The definition of set equality tells you how to prove that two sets are equal:

To prove that , try proving that $S \subset T$ and $T \subset S$ .

Notational remark. Some people use " $T \subset S$ " to mean that T is a subset of S, but is not equal to S. A subset of S other than S itself is called a proper subset of S. With this convention, you write $T \subseteq S$ to mean that T is a subset of S, possibly S itself.

I prefer to write $T \subset S$ to mean T is any subset of S. If I want T to be a proper subset of S, I'll write $T \propersubset S$ . Reason: More often than not, you want to include the possibility that , and you should use the simpler notation ( $\subset$ rather than $\subseteq$ ) for the case that occurs more often.

Example. Let

$A = \{n \in \integer \mid n = 2m \quad\hbox{for some}\quad m \in \integer\} \quad\hbox{and}\quad B = \{n \in \integer \mid n = 6m \quad\hbox{for some}\quad m \in \integer\}.$

Prove that $B \subset A$ .

To prove that $B \subset A$ , I must show that if $n \in B$ , then $n \in A$ . You can often prove set inclusion or equality by considering elements.

Let $n \in B$ . By definition of B, I have for some $m \in \integer$ . Now

Since m is an integer, so is . Therefore, n has the form $2\cdot (\hbox{an integer})$ , so by definition $n \in A$ .

Hence, $B \subset A$ .

It's common to shorten the definitions of A and B as follows:

$A = \{2m \mid m \in \integer\} \quad\hbox{and}\quad B = \{6m \mid m \in \integer\}.$

Be sure you understand the intent of these definitions. The "m" in the definition simply stands for "some integer". Thus, elements of A can be described as integers which have the form $2\cdot (\hbox{some integer})$ ; elements of B can be described as integers which have the form $6\cdot (\hbox{some integer})$ . When working with sets like these, don't get hung up on the particular letter "m".

Lemma. Let S and T be sets.

$\emptyset \subset S$ .
$S \subset S$ .

Proof. (a) To prove that $\emptyset \subset S$ , I have to prove that if $x \in \emptyset$ , then $x \in S$ . But $x \in \emptyset$ is false for all x, so the conditional statement must be true. (In this situation, you often say that the statement is vacuously true --- the condition is satisfied because there are no cases!)

(b) To prove that $S \subset S$ , I must show that if $x \in S$ , then $x \in S$ . This is trivially true --- $P \ifthen P$ is a tautology --- so $S \subset S$ .

When one is discussing sets, there is usually a "big set" which contains all the sets under discussion. This "big set" is usually called the universe; usually, it will be clear from the context what it is. For example, if I'm discussing sets of integers, the universe is the set of integers $\integer$ . If I'm discussing sets of real numbers, the universe is the set of real numbers $\real$ .

Definition. Let S and T be sets in the universe X. The complement of S is the set of elements of the universe which are not contained in S; it is denoted $\overline{S}$ or . Thus,

$\overline{S} = \{x \in X \mid x \notin S\}.$

The complement of S in T is the set of elements of T which are not elements of S; it is denoted . Thus,

$T - S = \{x \in T \mid x \notin S\}.$

Here's a picture; the shaded area is .

$\hbox{\epsfysize=1in \epsffile{sets2.eps}}$

Set complements function likes logical negations; the analogy even extends to DeMorgan's Laws, as I'll show below.

Example. If X is the universe, $\overline{X} = \emptyset$ and $\overline{\emptyset} = X$ .

Example. Let the universe be $\{1, 2, 3, 4, \hbox{Calvin}\}$ . Then

$\overline{\{1, 3\}} = \{2, 4, \hbox{Calvin}\} \quad\hbox{and}\quad \overline{\{2, 4, \hbox{Calvin}\}} = \{1, 3\}.$

In fact, for any set S, $\overline{\overline{S}} = S$ .

In this situation,

$\overline{\{1, 3\}} = \{1, 2, 3, \hbox{Calvin}\}, \quad\hbox{but}\quad \overline{\{1, 3\}} \not\subset \{1, 2, 4, \hbox{Calvin}\}.\quad\halmos$

Definition. Let S and T be sets. The union of S and T is the set whose elements are elements of S or elements of T; it is denoted $S \cup T$ . That is,

$S \cup T = \{x \mid x \in S \quad\hbox{or}\quad x \in T\}.$

Picture:

$\hbox{\epsfysize=1in \epsffile{sets3.eps}}$

Definition. Let S and T be sets. The intersection of S and T is the set whose elements are elements of both S and T; it is denoted $S \cap T$ . That is,

$S \cap T = \{x \mid x \in S \quad\hbox{and}\quad x \in T\}.$

Picture:

$\hbox{\epsfysize=1in \epsffile{sets4.eps}}$

Note that the "or" and "and" in the last two definitions are the logical "or" and "and".

Example. Let $A = \{1, 2, 3, 4, 5\}$ , let B be the set of even integers, and suppose the universe is $\integer$ . Then

$A \cup B = \{\ldots, -6, -4, -2, 0, 1, 2, 3, 4, 5, 6, 8, 10, \ldots\},$

$A \cap B = \{2, 4\},$

$A - B = \{1, 3, 5\},$

$B - A = \{\hbox{all even integers except 2 and 4}\},$

$\overline{B} = \{\hbox{all odd integers}\}.\quad\halmos$

Example. Let

$\real^{\ge 0} = \{x \in \real \mid x \ge 0\} \quad\hbox{and}\quad \real^{\le 0} = \{x \in \real \mid x \le 0\}.$

Prove that $\real^{\ge 0} \cap \real^{\le 0} = \{0\}$ .

I'll prove the result by showing that $\{0\} \subset \real^{\ge 0} \cap \real^{\le 0}$ and that $\real^{\ge 0} \cap \real^{\le 0} \subset \{0\}$ .

To prove that $\{0\} \subset \real^{\ge 0} \cap \real^{\le 0}$ , I begin by taking an element of $\{0\}$ --- but the only element of $\{0\}$ is 0. So I have to show that $0 \in \real^{\ge 0} \cap \real^{\le 0}$ .

First, $0 \in \real^{\ge 0}$ because $0 \ge 0$ . Next, $0 \in \real^{\le 0}$ because $0 \le 0$ . Since $0 \in \real^{\ge 0}$ and $0 \in \real^{\le 0}$ , it follows that $0 \in \real^{\ge 0} \cap \real^{\le 0}$ . Hence, $\{0\} \subset \real^{\ge 0} \cap \real^{\le 0}$ .

Now I have to show that $\real^{\ge 0} \cap \real^{\le 0} \subset \{0\}$ . Let $x \in \real^{\ge 0} \cap \real^{\le 0}$ . By definition of intersection, this means that $x \in \real^{\ge 0}$ and $x \in \real^{\le 0}$ .

Since $x \in \real^{\ge 0}$ , I have $x \ge 0$ . Since $x \in \real^{\le 0}$ , I have $x \le 0$ . This means that , so $x \in \{0\}$ . Therefore, $\real^{\ge 0} \cap \real^{\le 0} \subset \{0\}$ .

This proves that $\real^{\ge 0} \cap \real^{\le 0} = \{0\}$ .

Example. This is the general Venn diagram for three sets.

$\hbox{\epsfysize=1.5in \epsffile{sets5.eps}}$

Here are the Venn diagrams for some set constructed using complements, unions, and intersection:

$\matrix{\hbox{\epsfysize=1.5in \epsffile{sets6.eps}} & \hbox{\epsfysize=1.5in \epsffile{sets7.eps}} \cr A \cap B \cap C & (A \cap B) \cup C \cr}$

$\matrix{\hbox{\epsfysize=1.5in \epsffile{sets7.eps}} & \hbox{\epsfysize=1.5in \epsffile{sets8.eps}} \cr C - (A \cup B) & B - (A \cap C) \cr}\quad\halmos$

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page