1.2: Sets

Intuitively, a mathematical set is a collection of mathematical objects. Unfortunately this simple characterization of sets, carelessly handled, gives rise to contradictions. Some collections will turn out not to have the properties that we demand of mathematical sets. An example of how this can occur is presented in Section 1.7. We shall not develop formal set theory from scratch here. Instead, we shall assume that certain building block sets are known, and describe ways to build new sets out of these building blocks.

Our initial building blocks will be the sets of natural numbers, integers, rational numbers and real numbers. In Chapter 8 , we shall show how to build all these from the natural numbers. One can’t go much further than this, though: in order to do mathematics, one has to start with axioms that assert that the set of natural numbers exist.

Definition: Element, \(\in\)

If \(X\) is a set and \(x\) is an object in \(X\), we say that \(x\) is an element, or member, of \(X\). This is written \[x \in X .\] We write \(x \notin X\) if \(x\) is not a member of \(X\). 

There are numerous ways to define sets. If a set has few elements, it may be defined by listing. For instance, \[X=\{2,3,5,7\}\] is the set of the first four prime numbers. In the absence of any other indication, a set defined by a list is assumed to have as elements only the objects in the list. For sets with too many elements to list, we must provide the reader with a means to determine membership in the set. The author can inform the reader that not all elements of the set have been listed, but that enough information has been provided for the reader to identify a pattern for determining membership in the set. For example, let \[X=\{2,4,6,8, \ldots, 96,98\} .\] Then \(X\) is the set of positive even integers less than 100. However, using an ellipsis to define a set may not always work: it assumes that the reader will identify the pattern you wish to characterize. Although this usually works, it carries the risk that the reader is unable to correctly identify the pattern intended by the author.

Some sets are so important that they have standard names and notations that you will need to know.

Notation. Natural numbers, \(\mathbb{N}\) The natural numbers are the elements of the set \[\{0,1,2,3, \ldots\} .\] This set is denoted by \(\mathbb{N}\).

Beware: Many authors call \(\{1,2,3, \ldots\}\) the set of natural numbers. This is a matter of definition, and there is no universal convention; logicians tend to favor our convention, and algebraists the other. In this book, we shall use \(\mathbb{N}^{+}\)to denote \(\{1,2,3, \ldots\}\).

NOTATION. \(\mathbb{N}^{+} \mathbb{N}^{+}\)is the set of positive integers, \[\{1,2,3, \ldots\} \text {. }\] NOTATION. Integers, \(\mathbb{Z} \mathbb{Z}\) is the set of integers, \[\{\ldots,-3,-2,-1,0,1,2,3, \ldots\} \text {. }\] NOTATION. Rational numbers, \(\mathbb{Q} \mathbb{Q}\) is the set of rational numbers, \[\left\{\frac{p}{q} \text { where } p, q \in \mathbb{Z} \text { and } q \neq 0\right\} \text {. }\] NOTATION. Real numbers, \(\mathbb{R} \mathbb{R}\) is the set of real numbers. A good understanding of the real numbers requires a bit of mathematical develoment. In fact, it was only in the nineteenth century that we really came to a modern understanding of \(\mathbb{R}\). We shall have a good deal to say about the real numbers in Chapter 8 .

Definition

A number \(x\) is positive if \(x>0\). A number \(x\) is nonnegative if \(x \geq 0\).

NOTATION. \(X^{+}\)If \(X\) is a set of real numbers, we use \(X^{+}\)for the positive numbers in the set \(X\).

The notation we have presented for these sets is widely used. We introduce a final convention for set names which is not as widely recognized, but is useful for set theory.

NOTATION. \(\ulcorner n\urcorner\) is the set of all natural numbers less than \(n\) : \[\ulcorner n\urcorner=\{0,1,2, \ldots, n-1\} .\] One purpose of this notation is to canonically associate any natural number \(n\) with a set having exactly \(n\) elements.

The reader should note that we have not defined the above sets. We are assuming that you are familiar with them, and some of their properties, by virtue of your previous experience in mathematics. We shall eventually define the sets systematically in Chapter \(8 .\)

A more precise method of defining a set is to use unambiguous conditions that characterize membership in the set.

Notation. \(\{x \in X \mid P(x)\}\) Let \(X\) be a (previously defined) set, and let \(P(x)\) be a condition or property. Then the set \[Y=\{x \in X \mid P(x)\}\] is the set of elements in \(X\) which satisfy condition \(P\). The set \(X\) is called the domain of the variable.

In words, (1.1) is read: " \(Y\) equals the set of all (little) \(x\) in (capital) \(X\) such that \(P\) is true of \(x\) ". The symbol " \(\mid\) " in (1.1) is often written instead with a colon, viz. \(\{x \in X: P(x)\}\). In mathematics, \(P(x)\) is a often a mathematical formula. For instance, suppose \(P(x)\) is the formula " \(x^{2}=4\) ". By \(P(2)\) we mean the formula with 2 substituted for \(x\), that is \[" 2^{2}=4 "\] If the substitution results in a true statement, we say that \(P(x)\) holds at 2 , or \(P(2)\) is true. If the statement that results from the substitution is false, for instance \(P(1)\), we say that \(P(x)\) does not hold at 1 , or that \(P(1)\) is false.

Example 1.2

Consider the set \[X=\{0,1,4,9, \ldots\} .\] A precise definition of the same set is the following: \[X=\left\{x \in \mathbb{N} \mid \text { for some } y \in \mathbb{N}, x=y^{2}\right\} .\] EXAMPLE 1.3. Let \(Y\) be the set of positive even integers less than 100. Then \(Y\) can be written: \[\left\{x \in \mathbb{N} \mid x<100 \text { and there is } n \in \mathbb{N}^{+} \text {such that } x=2 \cdot n\right\}\] EXAMPLE 1.4. An interval \(I\) is a non-empty subset of \(\mathbb{R}\) with the property that whenever \(a, b \in I\) and \(a<c<b\), then \(c\) is in \(I\). A bounded interval must have one of the four forms \[\begin{aligned} (a, b) &=\{x \in \mathbb{R} \mid a<x<b\} \\ {[a, b) } &=\{x \in \mathbb{R} \mid a \leq x<b\} \\ (a, b] &=\{x \in \mathbb{R} \mid a<x \leq b\} \\ {[a, b] } &=\{x \in \mathbb{R} \mid a \leq x \leq b\} \end{aligned}\] where in the first three cases \(a\) and \(b\) are real numbers with \(a<b\) and in the fourth case we just require \(a \leq b\). Unbounded intervals have five forms: \[\begin{aligned} (-\infty, b) &=\{x \in \mathbb{R} \mid x<b\} \\ (-\infty, b] &=\{x \in \mathbb{R} \mid x \leq b\} \\ (b, \infty) &=\{x \in \mathbb{R} \mid x>b\} \\ {[b, \infty) } &=\{x \in \mathbb{R} \mid x \geq b\} \\ \mathbb{R} & \end{aligned}\] where \(b\) is some real number. An interval is called closed if it contains all its endpoints (both \(a\) and \(b\) in the first group of examples, just \(b\) in the first four examples of the second group), and open if it contains none of them. Notice that this makes \(\mathbb{R}\) the only interval that is both closed and open.

For the sake of brevity, an author may not explicitly identify the domain of the variable. Be careful of this, as the author is relying on the reader to make the necessary assumptions. For instance, consider the set \[X=\left\{x \mid\left(x^{2}-2\right)(x-1)\left(x^{2}+1\right)=0\right\} .\] If the domain of the variable is assumed to be \(\mathbb{N}\), then \[X=\{1\} .\] If the domain of the variable is assumed to be \(\mathbb{R}\), then \[X=\{1, \sqrt{2},-\sqrt{2}\} .\] If the domain of the variable is assumed to be the complex numbers, then, \[X=\{1, \sqrt{2},-\sqrt{2}, i,-i\}\] where \(i\) is the complex number \(\sqrt{-1}\). Remember, the burden of clear communication is on the author, not the reader.

Another alternative is to include the domain of the variable in the condition defining membership in the set. So, if \(X\) is the intended domain of the set and \(P(x)\) is the condition for membership in the set, \[\{x \in X \mid P(x)\}=\{x \mid x \in X \text { and } P(x)\} .\] As long as the definition is clear, the author has some flexibility with regard to notation.

1.2.1. Set Identity.

When are two sets equal? You might be inclined to say that two sets are equal provided they are the same collection of objects. Of course this is true, but equality as a relation between objects is not very interesting. However, you have probably spent a lot of time investigating equations (which are just statements of equality), and we doubt that equality seemed trivial. This is because in general equality should be understood as a relationship between descriptions or names of objects, rather than between the objects themselves. The statement \[a=b\] is a claim that the object represented by \(a\) is the same object as that represented by \(b\). For example, the statement \[5-3=2\] is the claim that the number represented by the arithmetic expression \(5-3\) is the same number as that represented by the numeral 2 .

In the case of sets, this notion of equality is called extensionality.

Definition: Extensionality

Let \(X\) and \(Y\) be sets. Then \(X=Y\) provided that every element of \(X\) is also an element of \(Y\) and every element of \(Y\) is also an element of \(X\).

There is flexibility in how a set is characterized as long as we are clear on which objects constitute the set. For instance, consider the set equation \[\{\text { Mark Twain, Samuel Clemens }\}=\{\text { Mark Twain }\} .\] If by "Mark Twain" and "Samuel Clemens", we mean the deceased American author, these sets are equal, by extensionality, and the statement is true. The set on the left hand side of the equation has only one element since both names refer to the same person. If, however, we consider "Mark Twain" and "Samuel Clemens" as names, the statement is false, since "Samuel Clemens" is a member of the set on the left hand side of the equation, but not the right hand side. You can see that set definitions can depend on the implicit domain of the variable even if the sets are defined by listing.

Example 1.5

Consider the following six sets: \[\begin{aligned} &X_{1}=\{1,2\} \\ &X_{2}=\{2,1\} \\ &X_{3}=\{1,2,1\} \\ &X_{4}=\{n \in \mathbb{N} \mid 0<n<3\} \\ &X_{5}=\left\{n \in \mathbb{N} \mid \text { there exist } x, y, z \in \mathbb{N}^{+} \text {such that } x^{n}+y^{n}=z^{n}\right\} \\ &X_{6}=\{0,1,2\} . \end{aligned}\] The first five sets are all equal, and the sixth is different. However, while it is obvious that \(X_{1}=X_{2}=X_{3}=X_{4}\), the fact that \(X_{5}=X_{1}\) is the celebrated theorem of Andrew Wiles (his proof of Fermat’s last theorem).

1.2.2. Relating Sets.

In order to say anything interesting about sets, we need ways to relate them, and we shall want ways to create new sets from existing sets.

Definition: Subset, \(\subseteq\)

Let \(X\) and \(Y\) be sets. \(X\) is a subset of \(Y\) if every element of \(X\) is also an element of \(Y\). This is written \[X \subseteq Y .\] Superset, \(\supseteq\) If \(X \subseteq Y\), then \(Y\) is called a superset of \(X\), written \[Y \supseteq X .\] In order to show two sets are equal (or that two descriptions of sets refer to the same set), you must show that they have precisely the same elements. It is often easier if the argument is broken into two simpler arguments in which you show mutual containment of the sets. In other words, saying \(X=Y\) is the same as saying \[X \subseteq Y \text { and } Y \subseteq X,\] and verifying the two separate claims in (1.6) is often easier (or at least clearer) than showing that \(X=Y\) all at once.

Let’s add a few more elementary notions to our discussion of sets.

Definition: Proper subset, \(\subsetneq, \subsetneq\)

Let \(X\) and \(Y\) be sets. \(X\) is a proper subset of \(Y\) if \[X \subseteq Y \text { and } X \neq Y \text {. }\] We write this as \[X \subsetneq Y\] or \[Y \supsetneq X .\] DEFINITION. Empty set, \(\emptyset\) The empty set is the set with no elements. It is denoted by \(\emptyset\).

So for any set, \(X\), \[\emptyset \subseteq X \text {. }\] (Think about why this is true). Just because \(\emptyset\) is empty does not mean it is unimportant. Indeed, many mathematical questions reduce to asking whether a particular set is empty or not. Furthermore, as you will see in Chapter 8, we can build the entire real line from the empty set using set operations.

Exercise

Show that \[\{n \in \mathbb{N} \mid n \text { is odd and } n=k(k+1) \text { for some } k \in \mathbb{N}\}\] is empty.

Let’s discuss some ways to define new sets from existing sets. DEFINITION. Union, \(\cup\) Let \(X\) and \(Y\) be sets. The union of \(X\) and \(Y\), written \(X \cup Y\), is the set \[X \cup Y=\{x \mid x \in X \text { or } x \in Y\} .\] (Recall our discussion in Section 1.1 about the mathematical meaning of the word "or".)

Definition: Intersection, \(\cap\)

Let \(X\) and \(Y\) be sets. The intersection of \(X\) and \(Y\), written \(X \cap Y\), is the set \[X \cap Y=\{x \mid x \in X \text { and } x \in Y\} .\] DEFINITION. Set difference, \(\backslash\) Let \(X\) and \(Y\) be sets. The set difference of \(X\) and \(Y\), written \(X \backslash Y\), is the set \[X \backslash Y=\{x \in X \mid x \notin Y\} .\] DEFInITION. Disjoint Let \(X\) and \(Y\) be sets. \(X\) and \(Y\) are disjoint if \[X \cap Y=\emptyset .\] Oftentimes one deals with sets that are subsets of some fixed given set \(U\). For example, when dealing with sets of natural numbers, the set \(U\) would be \(\mathbb{N}\).

Definition: Complement

Let \(X \subseteq U\). The complement of \(X\) in \(U\) is the set \(U \backslash X\). When \(U\) is understood from the context, the complement of \(X\) is written \(X^{c}\).

What about set operations involving more than two sets? Unlike arithmetic, in which there is a default order of operations (powers, products, sums), there is not a universal convention for the order in which set operations are performed. If intersections and unions appear in the same expression, then the order in which the operations are performed can matter. For instance, suppose \(X\) and \(Y\) are disjoint, nonempty sets, and consider the expression \[X \cap X \cup Y \text {. }\] If we mean for the intersection to be executed before the union, then \[(X \cap X) \cup Y=X \cup Y .\] If, however we intend the union to be computed before the intersection, then \[X \cap(X \cup Y)=X .\] Since \(Y\) is nonempty and disjoint from \(X\), \[(X \cap X) \cup Y \neq X \cap(X \cup Y) .\] Consequently, the order in which set operations are executed needs to be explicitly prescribed with parentheses.

Example 1.7

Let \(X=\mathbb{N}\) and \(Y=\mathbb{Z} \backslash \mathbb{N}\). Then \[(X \cap X) \cup Y=\mathbb{N} \cup Y=\mathbb{Z} .\] However \[X \cap(X \cup Y)=\mathbb{N} \cap \mathbb{Z}=\mathbb{N} .\] DEFINITION. Cartesian product, Direct product, \(X \times Y\) Let \(X\) and \(Y\) be sets. The Cartesian product of \(X\) and \(Y\), written \(X \times Y\), is the set of ordered pairs \[\{(x, y) \mid x \in X \text { and } y \in Y\} .\] The Cartesian product is also called the direct product.

Example 1.8

Let \[X=\{1,2,3\}\] and \[Y=\{1,2\} .\] Then \[X \times Y=\{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\} .\] Note that the order matters - that is \[(1,2) \neq(2,1) .\] So \(X \times Y\) is a set with six elements. Since direct products are themselves sets, we can easily define the direct product of more than two factors. For example, let \(X, Y\) and \(Z\) be sets, then \[(X \times Y) \times Z=\{((x, y), z) \mid x \in X, y \in Y, z \in Z\} .\] Formally, \[(X \times Y) \times Z \neq X \times(Y \times Z),\] because \(((x, y), z)\) and \((x,(y, z))\) are not the same. However in nearly every application, this distinction is not important, and mathematicians generally consider the direct product of more than two sets without regard to this detail. Therefore you will generally see the Cartesian product of three sets written without parentheses, \[X \times Y \times Z \text {. }\] In this event you may interpret the direct product as either side of statement 1.8.

With some thought, you can conclude that we have essentially described the Cartesian product of an arbitrary finite collection of sets. The elements of the Cartesian product \(X \times Y\) are ordered pairs. Our characterization of the Cartesian product of three sets, \(X, Y\) and \(Z\), indicates that its elements could be thought of as ordered pair of elements of \(X \times Y\) and \(Z\), respectively. From a practical point of view, it is simpler to think of elements of \(X \times Y \times Z\) as ordered triples. We generalize this as follows.

Definition: Cartesian product, Direct product, \(\prod_{i=1}^{n} X_{i}\)

Cartesian product, Direct product, \(\prod_{i=1}^{n} X_{i}\) Let \(n \in\) \(\mathbb{N}^{+}\), and \(X_{1}, X_{2}, \ldots, X_{n}\) be sets. The Cartesian product of \(X_{1}, \ldots, X_{n}\), written \(X_{1} \times X_{2} \times \ldots \times X_{n}\), is the set \[\left\{\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid x_{i} \in X_{i}, 1 \leq i \leq n\right\} .\] This may also be written \[\prod_{i=1}^{n} X_{i} .\] When we take the Cartesian product of a set \(X\) with itself \(n\) times, we write it as \(X^{n}\) : \[X^{n}:=\overbrace{X \times X \times \cdots \times X}^{n \text { times }} .\]