2.1: Basic Concepts

A set is a collection of elements. A set is defined entirely by the elements that it contains. An element can be anything, including another set. You will notice that this is not a precise mathematical definition. Instead, it is an intuitive description of what the word “set” is supposed to mean: Any time you have a bunch of entities and you consider them as a unit, you have a set. Mathematically, sets are really defined by the operations that can be performed on them. These operations model things that can be done with collections of objects in the real world. These operations are the subject of the branch of mathematics known as set theory.

The most basic operation in set theory is forming a set from a given list of specific entities. The set that is formed in this way is denoted by enclosing the list of entities between a left brace, “{”, and a right brace, “}”. The entities in the list are separated by commas. For example, the set denoted by

\[\textit{17, π, New York City, Barack Obama, Big Ben}\nonumber\]

is the set that contains the entities 17, π, New York City, Barack Obama, and Big Ben. These entities are the elements of the set. Since we assume that a set is completely defined by the elements that it contains, the set is well-defined. Of course, we still haven’t said what it means to be an “entity.” Something as definite as “New York City” should qualify, except that it doesn’t seem like New York City really belongs in the world of Mathematics. The problem is that mathematics is supposed to be its own self-contained world, but it is supposed to model the real world. When we use mathematics to model the real world, we admit entities such as New York City and even Big Ben. But when we are doing mathematics per se, we’ll generally stick to obviously mathematical entities such as the integer 17 or the real number \pi. We will also use letters such as \(a\) and \(b\) to refer to entities. For example, when I say something like “Let A be the set \({a, b, c}\),” I mean \(a, b,\) and \(c\) to be particular, but unspecified, entities.

It’s important to understand that a set is defined by the elements that it contains, and not by the order in which those elements might be listed. For example, the notations \({a,b,c,d}\) and \({b,c,a,d}\) define the same set. Furthermore, a set can only contain one copy of a given element, even if the notation that specifies the set lists the element twice. This means that \({a, b, a, a, b, c, a}\) and \({a, b, c}\) specify exactly the same set. Note in particular that it’s incorrect to say that the set \({a,b,a,a,b,c,a}\) contains seven elements, since some of the elements in the list are identical. The notation \({a,b,c}\) can lead to some confusion, since it might not be clear whether the letters \(a, b, \text{ and } c\) are assumed to refer to three different entities. A mathematician would generally not make this assumption without stating it explicitly, so that the set denoted by \({a, b, c}\) could actually contain either one, two, or three elements. When it is important that different letters refer to different entities, I will say so explicitly, as in “Consider the set \({a, b, c}\), where \(a, b, \text{ and } c\) are distinct.”

The symbol \(\in\) is used to express the relation “is an element of.” That is, if \(a\) is an entity and \(A\) is a set, then \(a \in A\) is a statement that is true if and only if \(a\) is one of the elements of \(A\). In that case, we also say that \(a\) is a member of the set \(A\). The assertion that \(a\) is not an element of A is expressed by the notation \(a \notin A\). Note that both \(a \in A\) and \(a \notin A\) are statements in the sense of propositional logic. That is, they are assertions which can be either true or false. The statement \(a \notin A\) is equivalent to \(\neg (a \in A)\)

It is possible for a set to be empty, that is, to contain no elements whatsoever. Since a set is completely determined by the elements that it contains, there is only one set that contains no elements. This set is called the empty set, and it is denoted by the symbol ∅. Note that for any element a, the statement \(a ∈ ∅\) is false. The empty set, ∅, can also be denoted by an empty pair of braces, { }.

If A and B are sets, then, by definition, A is equal to B if and only if they contain exactly the same elements. In this case, we write A = B. Using the notation of predicate logic, we can say that A = B if and only if \(\forall x(x ∈ A ↔ x ∈ B)\).

Suppose now that \(A\) and \(B\) are sets such that every element of \(A\) is an element of \(B\). In that case,we say that \(A\) is a subset of \(B\),i.e. \(A\) is a subset of \(B\) if and only if \(\forall x(x ∈ A → x ∈ B)\). The fact that \(A\) is a subset of \(B\) is denoted by \(A ⊆ B\). Note that ∅ is a subset of every set \(B: x ∈ ∅\) is false for any \(x\), and so given any \(B\), \((x ∈ ∅ → x ∈ B)\) is true for all \(x\).

If \(A = B\), then it is automatically true that \(A ⊆ B\) and that \(B ⊆ A\). The converse is also true: If \(A ⊆ B\) and \(B ⊆ A\), then \(A = B\). This follows from the fact that for any \(x\), the statement \((x ∈ A ↔ x ∈ B)\) is logically equivalent to the statement \((x∈A→x∈B)∧(x∈B→x∈A)\). This fact is important enough to state as a theorem.

Theorem 2.1

Let \(A\) and \(B\) be sets. Then \(A = B\) if and only if both \(A ⊆ B\) and \(B ⊆ A\).

This theorem expresses the following advice: If you want to check that two sets, \(A\) and \(B\), are equal, you can do so in two steps. First check that every element of \(A\) is also an element of \(B\), and then check that every element of \(B\) is also an element of \(A\).

If \(A⊆B\) but \(A \ne B\),we say that \(A\) is a proper subset of \(B\). We use the notation \(A \varsubsetneq B\) to mean that \(A\) is a proper subset of \(B\). That is, \(A \varsubsetneq B\) if and only if \(A ⊆ B ∧ A \ne B\). We will sometimes use \(A ⊇ B\) as an equivalent notation for \(B ⊆ A\), and \(A \varsubsetneq B\) as an equivalent for \(B \varsubsetneq A\).

A set can contain an infinite number of elements. In such a case, it is not possible to list all the elements in the set. Sometimes the ellipsis “. . . ” is used to indicate a list that continues on infinitely. For example, \mathbb{N}, the set of natural numbers, can be specified as

\[\mathbb{N} = \{0,1,2,3,...\}\nonumber \]

However, this is an informal notation, which is not really well-defined, and it should only be used in cases where it is clear what it means. It’s not very useful to say that “the set of prime numbers is \({2, 3, 5, 7, 11, 13, . . . }\),” and it is completely meaningless to talk about “the set \({17, 42, 105, . . . }\).” Clearly, we need another way to specify sets besides listing their elements. The need is fulfilled by predicates.

If \(P(x)\) is a predicate, then we can form the set that contains all entities \(a\) such that \(a\) is in the domain of discourse for \(P\) and \(P(a)\) is true. The notation \(\{x|P(x)\}\) is used to denote this set. The name of the variable,\(x\), is arbitrary, so the same set could equally well be denoted as \(\{z | P (z)\}\) or \(\{r|P(r)\}\). The notation \(\{x|P(x)\}\) can be read “the set of \(x\) such that \(P(x)\).” For example, if \(E(x)\) is the predicate “\(x\) is an even number,” and if the domain of discourse for \(E\) is the set \(\mathbb{N}\) of natural numbers, then the notation \(\{x | E(x)\}\) specifies the set of even natural numbers. That is,

\[\{x|E(x)\} = \{0,2,4,6,8,...\} \nonumber \]

It turns out, for deep and surprising reasons that we will discuss later in this section, that we have to be a little careful about what counts as a predicate. In order for the notation \({x | P (x)}\) to be valid, we have to assume that the domain of discourse of \(P\) is in fact a set. (You might wonder how it could be anything else. That’s the surprise!) Often, it is useful to specify the domain of discourse explicitly in the notation that defines a set. In the above example, to make it clear that x must be a natural number, we could write the set as \({x ∈ \mathbb{N} | E(x)}\). This notation can be read as “the set of all \(x\) in \(\mathbb{N}\) such that \(E(x)\).” More generally, if \(X\) is a set and \(P\) is a predicate whose domain of discourse includes all the elements of \(X\), then the notation

\[\{x ∈ X | P (x)\} \nonumber\]

is the set that consists of all entities \(a\) that are members of the set \(X\) and for which \(P(a)\) is true. In this notation, we don’t have to assume that the domain of discourse for \(P\) is a set, since we are effectively limiting the domain of discourse to the set \(X\) . The set denoted by \({x ∈ X | P (x)}\) could also be written as \({x | x ∈ X ∧ P (x)}\).

We can use this notation to define the set of prime numbers in a rigorous way. A prime number is a natural number \(n\) which is greater than 1 and which satisfies the property that for any factorization \(n = xy\), where \(x\) and \(y\) are natural numbers, either \(x\) or \(y\) must be \(n\). We can express this definition as a predicate and define the set of prime numbers as

\[{n ∈ \mathbb{N} | (n > 1) ∧ ∀x∀y((x ∈ \mathbb{N} ∧ y ∈ \mathbb{N} ∧ n = xy) → (x = n ∨ y = n))}.\nonumber\]

Admittedly, this definition is hard to take in in one gulp. But this example shows that it is possible to define complex sets using predicates.

Now that we have a way to express a wide variety of sets, we turn to operations that can be performed on sets. The most basic operations on sets are union and intersection. If \(A\) and \(B\) are sets, then we define the union of \(A\) and \(B\) to be the set that contains all the elements of \(A\) together with all the elements of \(B\). The union of \(A\) and \(B\) is denoted by \(A ∪ B\). The union can be defined formally as

\[A ∪ B = \{x | x ∈ A ∨ x ∈ B\}.\nonumber\]

The intersection of \(A\) and \(B\) is defined to be the set that contains every entity that is both a member of \(A\) and a member of \(B\). The intersection of \(A\) and \(B\) is denoted by \(A ∩ B\). Formally,

\[A ∩ B = \{x | x ∈ A ∧ x ∈ B\}.\nonumber\]

An entity gets into \(A∪B\) if it is in either \(A\) or \(B\). It gets into \(A∩B\) if it is in both \(A\) and \(B\). Note that the symbol for the logical “or” operator, ∨, is similar to the symbol for the union operator, ∪, while the logical “and” operator, ∧, is similar to the intersection operator, ∩.

The set difference of two sets, \(A\) and \(B\), is defined to be the set of all entities that are members of \(A\) but are not members of \(B\). The set difference of \(A\) and \(B\) is denoted \(A \setminus B\). The idea is that \(A \setminus B\) is formed by starting with \(A\) and then removing any element that is also found in \(B\). Formally,

\[A \setminus B = \{x | x ∈ A ∧ x\notin B\}. \nonumber\]

Union and intersection are clearly commutative operations. That is, \(A ∪B = B∪A\) and \(A∩B = B∩A\) for any sets \(A\) and \(B\). However, set difference is not commutative. In general, \(A \setminus B \ne B \setminus A\).

Suppose that \(A = {a,b,c}\), that \(B = {b,d}\), and that \(C = {d,e,f}\). Then we can apply the definitions of union, intersection, and set difference to compute, for example, that:

\(A \cap B = \{a,b,c,d\}\)	\(A \cup B = \{b\}\)	\(A \setminus B = \{a,c\}\)
\(A \cap C = \{a,b,c,d,e,f\}\)	\(A \cap C = \emptyset\)	\(A \setminus C = \{a,b,c\}\)

In this example, the sets \(A\) and \(C\) have no elements in common, so that \(A∩C = ∅\). There is a term for this: Two sets are said to be disjoint if they have no elements in common. That is, for any sets \(A\) and \(B\), \(A\) and \(B\) are said to be disjoint if and only if \(A ∩ B = ∅\).

Of course, the set operations can also be applied to sets that are defined by predicates. For example, let \(L(x)\) be the predicate “\(x\) is lucky,” and let \(W(x)\) be the predicate “\(x\) is wise,” where the domain of discourse for each

Figure 2.1: Some of the notations that are defined in this section.A and B are sets, and a is an entity.

predicate is the set of people. Let \(X = \{x|L(x)\}\), and let \(Y = \{x|W(x)\}\). Then

\[X∪Y =\{x|L(x)∨W(x)\}=\{\text{ people who are lucky or wise }\}\nonumber\]

\[X∩Y =\{x|L(x)∧W(x)\}=\{\text{ people who are lucky and wise }\}\nonumber\]

\[X \setminus Y = \{x | L(X) \land \neg W(x)\} = \{\text{ people who are luck but not wise} \nonumber\]

\[Y \setminus X = \{x|W(x) \land \neg L(x)\} = \{\text{ people who are wise but not lucky }\}\nonumber\]

You have to be a little careful with the English word “and.” We might say that the set \(X ∪ Y\) contains people who are lucky and people who are wise. But what this means is that a person gets into the set \(X ∪ Y\) either by being lucky or by being wise, so \(X ∪ Y\) is defined using the logical “or” operator, \(∨\).

Sets can contain other sets as elements. For example, the notation \(\{a,{b}\}\) defines a set that contains two elements, the entity a and the set \(\{b\}\). Since the set \(\{b\}\) is a member of the set \(\{a,\{b\}\}\), we have that \(\{b\} ∈ \{a,\{b\}\}\). On the other hand, provided that \(a \ne b\), the statement \(\{b\} ⊆ \{a, \{b\}\}\) is false, since saying \(\{b\} ⊆ \{a, \{b\}\}\) is equivalent to saying that \(b ∈ \{a, \{b\}\}\), and the entity \(b\) is not one of the two members of \(\{a, \{b\}\}\). For the entity \(a\), it is true that \(\{a\} ⊆ \{a, \{b\}\}\).

Given a set \(A\), we can construct the set that contains all the subsets of \(A\). This set is called the power set of A, and is denoted \(\mathcal{P(A)}\). Formally, we define

\[\mathcal{P(A)}={X|X ⊆A}.\nonumber\]

For example, if \(A = \{a, b\}\), then the subsets of \(A\) are the empty set, \(\{a\},\{b\}\), and \(\{a, b\}\), so the power set of \(A\) is set given by

\[\mathcal{P(A)} = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}\nonumber\]

Note that since the empty set is a subset of any set, the empty set is an element of the power set of any set. That is, for any set \(A, ∅ ⊆ A\) and \(∅ ∈ \mathcal{P(A)}\). Since the empty set is a subset of itself, and is its only subset, we have that \(P(∅) = \{∅\}\). The set \(\{∅\}\) is not empty. It contains one element, namely ∅.

We remarked earlier in this section that the notation \(\{x | P(x)\}\) is only valid if the domain of discourse of \(P\) is a set. This might seem a rather puzzling thing to say—after all, why and how would the domain of discourse be anything else? The answer is related to Russell’s Paradox, which we mentioned briefly in Chapter 1 and which shows that it is logically impossible for the set of all sets to exist. This impossibility can be demonstrated using a proof by contradiction. In the proof, we use the existence of the set of all sets to define another set which cannot exist because its existence would lead to a logical contradiction.

Theorem 2.2.

There is no set of all sets

Proof. Suppose that the set of all sets exists. We will show that this assumption leads to a contradiction. Let \(V\) be the set of all sets. We can then define the set \(R\) to be the set which contains every set that does not contain itself. That is,

\[R = \{X ∈ V |X \notin X\}\nonumber\]

Now, we must have either \(R ∈ R\)or \(R \notin R\). We will show that either case leads to a contradiction.

Consider the case where \(R ∈ R\). Since \(R ∈ R\), \(R\) must satisfy the condition for membership in \(R\). A set \(X\) is in \(R\) iff \(X \notin X\). To say that \(R\) satisfies this condition means that \(R \notin R\). That is, from the fact that \(R ∈ R\), we deduce the contradiction that \(R \notin R\).

Now consider the remaining case, where \(R \notin R\). Since \(R \notin R\), \(R\) does not satisfy the condition for membership in \(R\). Since the condition for membership is that \(R \notin R\), and this condition is false, the statement \(R \notin R\) must be false. But this means that the statement \(R ∈ R\) is true. From the fact that \(R \notin R\), we deduce the contradiction that \(R ∈ R\).

Since both possible cases, \(R ∈ R\) and \(R \notin R\), lead to contradictions, we see that it is not possible for \(R\) to exist. Since the existence of \(R\) follows from the existence of \(V\) , we see that \(V\) also cannot exist.

To avoid Russell’s paradox, we must put limitations on the construction of new sets. We can’t force the set of all sets into existence simply by think- ing of it. We can’t form the set \(\{x | P (x)\}\) unless the domain of discourse of \(P\) is a set. Any predicate \(Q\) can be used to form a set \(\{x∈X|Q(x)\}\),but this notation requires a pre-existing set \(X\). Predicates can be used to form subsets of existing sets, but they can’t be used to form new sets completely from scratch.

The notation \(\{x ∈ A | P (x)\}\) is a convenient way to effectively limit the domain of discourse of a predicate, \(P\), to members of a set, \(A\), that we are actually interested in. We will use a similar notation with the quantifiers \(\forall\) and \(\exists\). The proposition \((\forall x \in A)(P(x))\) is true if and only if \(P(a)\) is true for every element \(a\) of the set \(A\). And the proposition \((\exists x \in A)(P(x))\) is true if and only if there is some element \(a\) of the set \(A\) for which \(P(a)\) is true. These notations are valid only when \(A\) is contained in the domain of discourse for \(P\). As usual, we can leave out parentheses when doing so introduces no ambiguity. So, for example, we might write \(\forall x \in A P(x)\).

We end this section with proofs of the two forms of the principle of math- ematical induction. These proofs were omitted from the previous chapter, but only for the lack of a bit of set notation. In fact, the principle of math- ematical induction is valid only because it follows from one of the basic axioms that define the natural numbers, namely the fact that any non- empty set of natural numbers has a smallest element. Given this axiom, we can use it to prove the following two theorems:

Theorem 2.3

Let \(P\) be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that \(P(0) \land (\forall k \in \mathbb{N} (P(k) \to P(k + 1)))\). Then \(\forall n \in \mathbb{ n}, P(N)\)

Proof. Suppose that both \(P(0)\) and \(\forall k \in \mathbb{N}(P(k) \to P(k+1)))\) are true, but that \((\forall n \in \mathbb{N}, P(n))\) is false. We show that this assumption leads to a contradiction.

Since the statement \(\forall n \in \mathbb{N}, P(n)\) is false, its negation \(\neg (\forall n \in \mathbb{N}, P(n))\), is true. The negation is quivalent to \(\exists n \in \mathbb{N}, \neg P(n)\). Let \(X = \{n \in \mathbb{N} | \neg P(n)\}\). Since \(\exists n \in \mathbb{N}, \neg P(n)\) is true, we know that \(X\) is not empty. Since \(X\) is a non-empty set of natural numbers, it has a smallest element. Let \(x\) be the smallest element of \(X\) Tha is. \(x\) is the smallest natural number sucha that \(P(x)\) is false. Since we know that \(P(0)\) is true, \(x\) cannot be 0. Let \(y = x -1\). Since \(x \ne 0\), \(y\) is a natural number. Since \(y < x\), we know by the definiton of \(x\), that \(P(y)\) is true. We also know that \(\forall k \in \mathbb{N} (P(k) \to P(k+1))\) is true. In particular, taking \(k=y\), we know that \(P(y) \to P(y+1)\). Since \(P(y)\) and \(P(y) \to P(y+1)\), we deduce by modus ponens that \(P(y+1)\) is true. But \(y+1 = x\), so we have deduced that \(P(x)\) is true. This contradicts the fact that \(P(x)\) is false. This contradiction proves the theorem.\)

Theorem 2.4

Let \(P\) be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that \(P(0)\) is true and that

\[(P(0) \land P(1) \land ... \land P(k)) \to P(k+1)\nonumber\]

is true for each natural number \(k \geq 0\). Then it is true that \(\forall n \in \mathbb{N}, P(n)\).

Proof. Suppose that \(P\) is a predicate that satisfies the hypotheses of the theorem, and suppose that the statement \(\forall n \in \mathbb{N}, P(n)\) is false. We show that this assumption leads to a contradiction.

Let \(X = \{n ∈ N | ¬P (n)\}\). Because of the assumption that \(\forall n \in \mathbb{N}, P(n)\) is false, \(X\) is non-empty. It follows that \(X\) has a smallest element. Let \(x\) be the smallest element of \(X\). The assumption that \(P(0)\) is true means that \(0 \notin X\), so we must have \(x > 0\). Since \(x\) is the smallest natural number for which \(P(x)\) is false, we know that \(P(0), P(1), ...,\) and \(P(x−1)\) are all true. From this and the fact that \((P(0)∧P(1)∧···∧P(x−1)) → P(x)\), we deduce that \(P(x)\) is true. But this contradicts the fact that \(P(x)\) is false. This contradiction proves the theorem.

---

Exercises

1. If we don’t make the assumption that \(a, b,\) and \(c\) are distinct, then the set denoted by \({a, b, c}\) might actually contain either \(1, 2, or 3\) elements. How many different elements might the set \(\{ a, b, \{a\}, \{a, c\}, \{a, b, c\} \}\) contain? Explain your answer
2. Compute \(A∪B, A∩B,\) and \(A \setminus B\) for each of the following pairs of set
   
   a) \(A = \{a,b,c\}, B = \emptyset\)
   b) \(A = \{1,2,3,4,5\}, B = \{2,4,6,8,10\}\)
   c) \(A = \{a,b\}, B = \{a,b,c,d\}\)
   d) \(A = \{a,b,\{a,b\}\}, B = \{\{a\},\{a,b\}\}\)
3. Recall that \mathbb{N} represents the set of natural numbers. That is, \(\mathbb{N} = \{0, 1, 2, 3, . . . \}\). Let \(X=\{n∈N|n≥5\}\),let \(Y =\{n∈N|n≤10\}\),and let \(Z=\{n∈\mathbb{N} | n \text{ is an even number }\}\). Find each of the following sets:
   

   a) \(X \cap Y\)	b) \(X \cup Y\)	c) \(X \setminus Y\)	d) \(\mathbb{N} \setminus Z\)
   e) \(X \cap Z\)	f) \(Y \cup Z\)	g) \(Y \cup Z\)	h) \(Z \setminus \mathbb{N}\)

4. Find \(\matcal{P\{1, 2, 3\}}. (It has eight elements.)
5. Assume that \(a\) and \(b\) are entities and that \(a \ne b\). Let \(A\) and \(B\) be the sets defined by \(A = \{a, \{b\}, \{a,b\}\}\) and \(B = \{a, b, \{a,\{b\}\}\}\). Determine whether each of the following statements is true or false. Explain your answers.
   

   a) \(b \in A\)	b) \(\{a,b\} ⊆ A\)	c)\(\{a,b\} ⊆ B\)
   d) \(\{a,b\} \in B\)	e)\(\{a,\{b\}\} \in A\)	f)\(\{a,\{b\}\} \in B\)

6. Since \(\mathcal{P(A)}\) is a set, it is possible to form the set \(\mathcal{P(P(A))}\). What is \(\mathcal{P(P(\emptyset))}\)? What is \(\mathcal{P(P(\{a,b\}))}\)? (It has sexteen elements.)
7. In the English sentence, “She likes men who are tall, dark, and handsome,” does she like an intersection or a union of sets of men? How about in the sentence, “She likes men who are tall, men who are dark, and men who are handsome?”
8. If \(A\) is any set, what can you say about \(A∪A\)? About \(A∩A\)? About \(A \setminus A\)? Why?
9. Suppose that \(A\) and \(B\) are sets such that \(A ⊆ B\). What can you say about \(A∪B\)? About \(A∩B\)? About \(A \setminus B\)? Why?
10. Suppose that \(A, B,\) and \(C\) are sets. Show that \(C ⊆ A∩B\) if and only if \((C ⊆ A) ∧ (C ⊆ B)\).
11. Suppose that \(A,B,\) and \(C\) are sets,and that \(A⊆B\) and \(B⊆C\).Show that \(A ⊆ C\).
12. Suppose that \(A\) and \(B\) are sets such that \(A ⊆ B\). Is it necessarily true that \(\mathcal{P(A)} ⊆ \mathcal{P(B)}\) ? Why or why not?
13. Let \(M\) be any natural number, and let \(P(n)\) be a predicate whose domain of discourse includes all natural numbers greater than or equal to \(M\). Suppose that \(P(M)\) is true, and suppose that \(P(k) → P(k + 1)\) for all \(k ≥ M\). Show that \(P(n)\) is true for all \(n ≥ M\).