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:

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

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:

The set constructor consists of two statements separated by a " ", contained in curly brackets. The two statements together give the properties which must be satisfied by an element of the set. (Thus, the " " 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

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

Here's an example using two variables:

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:

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,

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
or .

* 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,
means that x is an * element* of S. means that x is not an element of S.

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

is the set of * integers*.

is the set of * rational
numbers*.

is the set of * real numbers*.

is the set of * complex numbers*.

If you just want the positive integers (also known as the * natural numbers*, use or
; if you want the nonnegative integers, use .

* Definition.* Let S and T be sets. T is a * subset* of S if and only if implies .
means that T is a subset of S, and means that T is not a subset of S.

This picture illustrates :

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 and . (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 and .

* Notational remark.* Some people use
" " 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 to mean that T is a subset of S, possibly S itself.

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

* Example.* Let

Prove that .

To prove that , I must show that if , then .
*You can often prove set inclusion or equality by considering
elements.*

Let . By definition of B, I have for some . Now

Since m is an integer, so is . Therefore, n has the form , so by definition .

Hence, .

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

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 ; elements of B can
be described as integers which have the form . When working with sets like these, don't get hung
up on the particular letter "m".

* Lemma.* Let S and T be sets.

- .
- .

* Proof.* (a) To prove that , I have to prove that if , then
. But 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 , I must show that if , then . This is trivially true --- is a tautology --- so .

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 . If I'm discussing sets of real numbers, the
universe is the set of real numbers .

* 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
or . Thus,

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

Here's a picture; the shaded area is .

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, and .

* Example.* Let the universe be . Then

In fact, for any set S, .

In this situation,

* 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 . That is,

Picture:

* 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
. That is,

Picture:

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

* Example.* Let , let B be
the set of even integers, and suppose the universe is
. Then

* Example.* Let

Prove that .

I'll prove the result by showing that and that .

To prove that , I begin by taking an element of --- but the only element of is 0. So I have to show that .

First, because . Next, because . Since and , it follows that . Hence, .

Now I have to show that . Let . By definition of intersection, this means that and .

Since , I have . Since , I have . This means that , so . Therefore, .

This proves that .

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

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

Copyright 2007 by Bruce Ikenaga