Sets

Another fundamental concept indispensable to our coming investigation is that of a set, which we regard to be simply a collection of objects.^2.3 Sets, as you doubtless know, can have members, or elements. For example, the set of all natural numbers $\{0, 1, 2, \ldots\}$, denoted hereafter as N, has the number 7 as an element; in symbols:

$$7 \in \mbox{{\bf N}}.$$

We may say in such cases that N contains 7, or that 7 is an element of N, or simply that 7 is in N. When some object is not a member of some set, as is true of the object $\pi = 3.14\ldots$ and the set N, we use the notation

$$\pi \not\in \mbox{{\bf N}}.$$

The number $\pi$, though not a natural number, is a real number; so, with the real numbers (= reals) denoted by R, it is true that $\pi \in \mbox{{\bf R}}$.

So far all our examples of sets have been both number-related and infinite. These are not properties all of the sets of interest to us must have. For example, the set of all characters in the English alphabet (and, indeed, the characters in any so-called natural language), though non-numerical and non-infinite (= finite), is often of interest to computer scientists, mathematicians, engineers, etc. To return to the realm of the numerical, the set of all natural numbers less than 5000 is a finite set; it can be denoted by

$$\{0, 1, 2, 3, \ldots, 5000\}.$$

Alert readers will have noticed that we have invoked the concepts of infinite and finite set without providing definitions. Precise definitions of these concepts are outside our purview, but we can rest on the following characterizations. A set that can be displayed in the form of a list from first element to last element--as in the example $\{0, 1, 2, 3, \ldots, 5000\}$ above--is finite; a set that connot be so displayed--as in the case of N, which has no last or final element--is infinite. The set containing no objects, the empty set or null set, denoted by $\emptyset$, will also be considered finite. We often use the elipsis, $\ldots$, to indicate that we are dealing with a set that cannot be listed from first element to final element. You may remember that we used the elipsis for this effect in the very first paragraph of this section, when indicating the elements of N. We also used these small but powerful ``three dots" when displaying $\pi$, in order to remind you that this number's decimal expansion is infinitely long.

It will be convenient to refer to sets by way of other sets and certain properties. For example, the finite set {1, 2, 4, 5, 6, 7} could be denoted by the expression `the set of all elements in N which are less than or equal to seven and not equal to zero.' Such expressions, as you may suspect, can quickly get rather unwieldy. Accordingly, some notation (sometimes called set-builder notation) is in order. With respect to the previous example, this notation looks like this:

$$\{n \in \mbox{{\bf N}} : n \le 7 \: \& \: n \not= 0 \}.$$

In general, given some property P and some set A, we may define the set consisting of all those members of A having P. For example, the set $\{0, 1, 2, 3, \ldots, 5000\}$, in this scheme, becomes

$$\{n \in \mbox{{\bf N}} : n \le 5000\}.$$

And, as a final exemplar of set-builder notation, the even numbers, E, are

$$\{n \in \mbox{{\bf N}} : n \mbox{ is divisible by 2}\}.$$

Notice that every element of E is also an element of N. When such a situation holds, we say that the first set is a subset of the second. In symbols, the present case is represented as $E \subseteq \mbox{{\bf N}}$. Notice that the converse is not true; that is, $\mbox{{\bf N}} \not\subseteq E$. In this case we say that E is a proper subset of N, written $E \subset \mbox{{\bf N}}$. Two sets A and B are subsets of each other if and only if A = B. It will expedite matters if we agree, from this point on, that the empty set is a subset of all sets, and that all sets are subsets of themselves. Two sets that have no elements in common are said to be disjoint.^2.4

There are three well-known and useful operations on sets worth isolating at this point, namely

• union, denoted by $\cup$
• intersection, denoted by $\cap$
• difference, denoted by -

These operations are easily defined using set-builder notation:

• union: $A \cup B = \{x : x \in A \mbox{ or } x \in B\}$
• intersection: $A \cap B = \{x : x \in A \mbox{ and } x \in B\}$
• difference: $A - B = \{x : x \in A \mbox{ and } x \not\in B\}$

The three operations obey certain ``laws," all of which are rather easily proved. One such law is ``Commutativity," which consists in the following two identities (where A and B are arbitrary sets).

$$A \cup B = B \cup A$$

$$A \cap B = B \cap A$$

Another is ``DeMorgan Laws" (for sets), which consists of these two identitites:

$$A - (B \cup C) = (A - B) \cup (A - C)$$

$$A - (B \cap C) = (A - B) \cap (A - C)$$

Another operator is the power set operator; it generates the set of all subsets of a given set. Let A = {1, 2, 3}; then the power set of A, denoted by 2^A (or , is

$$\{ A, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \emptyset\}.$$

More generally, and expressed in our notation, given that A is any set, 2 $^A = \{B : B \subseteq A\}$.

Notice that two sets with the same elements, regardless of how those elements are ordered, are one and the same. Hence, for instance, $\{1, 2, 3\} = \{3, 2, 1\}.$ However, in the case of an n-tuple, order is important. We denote n-tuples by flanking them not with the curly brackets we have used to signify sets, but rather with parentheses. So, for example, (a, b, c) is an ordered 3-tuple, or simply a triple (a pair is an ordered 2-tuple). Note that while $(a, b, c) \not= (a, c, b)$, $\{a, b, c\} = \{a, c, b\}.$