Informally, a set is a collection of things called its
elements, members, or objects.
Sometimes the word collection is used in place of set to clarify a sentence.
For example, "a collection of sets" seems clearer than "a set of
sets." We say that a set contains its elements, or that the elements
belong to the set, or that the elements are in the set. If S is a set and x is an element in S, then we write
x Î S.
If x is not an element of S,
then we write x Ï S. If x Î S and
y Î
S, we often denote this fact by the
shorthand notation x, y Î
S.
A set is defined by
describing its elements in some way. For example, a gaggle is a set whose
members are geese, a pride is a set whose members are lions, and a pod is a set
whose members are whales. One way to define a set is to explicitly name its
elements. A set defined in this way is denoted by listing its elements,
separated by commas, and surrounding the listing with braces. For example, the
set S consisting of the letters x, y,
and z is denoted by
S = {x,y,z}.
Sets can have other
sets as elements. For example, the set A
= {x, {x, y}} has two elements. One element is x, and the other element is {x,
y}. So we can write x Î A and
{x, y} Î A.
We often use the
three-dot ellipsis, ... , to informally denote a
sequence of elements that we do not wish to write down. For example, the set
{1,2,3,4,5,6,7,8,9, 10, 11,12}
can be denoted in
several different ways with ellipses, two of which are
{1,2,
...,12} and {1,2,3, ...,11, 12}.
The set with no
elements is called the empty set – some
people refer to it as the null set.
The empty set is denoted by { } or more often by the symbol Æ.
A set with one
element is called a singleton. For
example, {a} and {b} are singletons. Two sets A and B are equal if each element of A
is an element of B and conversely
each element of B is an element of A. We denote the fact that A and B are equal sets by writing
A = B.
We can use equality
to demonstrate two important characteristics of sets:
There is no particular order or arrangement of the
elements.
There are no redundant elements.
For example, the
set whose elements are are g, h, and u can be represented in many ways, four
of which are
{u,g, h} = {h, u,g} = {h, u,g, h} = {u,g, h, u,g}.
In other words,
there are many ways to represent the same set. If the sets A and B are not equal, we write A
≠ B.
Suppose we start
counting the elements of a set S, one element per second of time with a stop
watch. If S = Æ, then we don't
need to start, because there are no elements to count. But if S ≠ Æ, we agree to start
the counting after we have started the timer. If a point in time is reached
when all the elements of S have been
counted, then we stop the timer, or in some cases we might need to have one of
our descendants stop the timer. In this case we say that S is a finite set. If the
counting never stops, then S is an infinite set. Familiar infinite sets are
sometimes denoted by listing a few of the elements followed by an ellipsis. We
reserve some letters to denote specific sets that we'll refer to throughout the
course. For example, the set of natural numbers will be denoted by N and the set of integers by Z. So we can write
N = {0,1,2,3,...} and Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}.
Many sets are hard
to describe by a listing of elements. Examples that come to mind are the
rational numbers, which we denote by Q,
and the real numbers, which we denote by R.
On the other hand, any set can be defined by stating a property that the
elements of the set must satisfy. If P
is some property, then there is a set S
whose elements have property P, and
we denote S by
S = {x | x has property P},
which we read as "S is the set of all x such that x has
property P." For example, we can
write Gaggle = {x | x is a goose} and say that Gaggle is the
set of all x such that x is a goose.
If A
and B are sets and every element of A is also an element of B, then we say that A is a subset of B and
write
A Ì B.
The collection of
all subsets of a set S is called the power
set of S, which we denote by
power(S). For example, if S = {a, b, c},
then the power set of S can be written
as follows:
power(S) = {Æ, {Ia}, {b}, {c}, {a,
b}, {a, c}, {b, c}, S}.
An interesting
programming problem is to construct the power set of a finite set.
In dealing with
sets, it's often useful to draw a picture in order to visualize the situation.
A Venn diagram – named after the
logician John Venn (834-1923) – consists of one or more closed curves in which
the interior of each curve represents a set. For example, the Venn diagram in
Figure 1.1 represents the fact that A
is a proper subset of B and x is an element of B that does not occur in A.
Figure 1.1 Venn
diagram of proper subset A Ì B.
We can use the
subset definition to give a precise definition of set equality: Two sets are
equal if they are subsets of each other. In more concise form we can write
A = B means A Ì B and B Ì A. (1.1)