Sets

 

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)