4  Set Theory

Set theory is the study of sets, which are (informally speaking) collections of objects. The objects in a set can be anything: numbers, points in space, people, etc. Sets can be finite or infinite (more numerous?).

The basic concepts of set theory include sets, subsets, unions, intersections, power sets, products, functions, and relations. The objects in a set are called elements of the set. A subset is a set that is contained within another set. The union of two sets is the set of all elements that are in either of the two sets. The intersection of two sets is the set of all elements that are in both of the two sets. There is so much to dicusss because set theory is quite rich with ideas and results.

Set theory is a branch of mathematics that is used in many other areas of mathematics, such as geometry, algebra, and analysis. It is also used in computer science, particularly in the design and analysis of algorithms.

Set theory has a long and rich history. Some of the earliest work on sets was done by the Greek philosopher Aristotle, who studied sets of objects that could be added together to form a whole. In the late 19th century, Georg Cantor developed the axiomatic approach to set theory and made major contributions to the study of infinite sets. In the early 20th century, Kurt Gödel proved that set theory was consistent, and in the 1940s, he used set theory to prove the existence of infinitely many different types of sets.

In the axiomatic approach to set theory, sets are defined using a set of axioms, or rules. The most famous of these axioms is the Axiom of Extensionality, which states that two sets are equal if they have the same elements.

4.1 What is a set?

We leave the term set undefined. We also leave the term belonging undefined. We say \(x\) belongs to a set \(A\) and we write \(x\in A\). We instead, sometimes say \(x\) is an element of \(A\), or even \(x\) is a member of a set \(A\). We will say that a set is a collection of objects. The universe, or universal set, usually denoted by \(U,\) is the set of all elements under discussion.

For example, if \(U\) consists of the elements: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, then the equation \[ A=\{0,1,2,3,4,5\} \] describes a set \(A\) made up of the six elements \(0,\) 1, 2, 3, 4, and \(5.\)

A set is determined by its elements and not by any particular order. In other words, set \(A\) is just as easily specified by \[ A=\{5,4,3,2,1,0\}. \]

Sets are often described by properties of the elements using the set-builder notation
\[ \{ \qquad \mid \qquad \qquad \} \qquad \text{ or } \qquad \{ \qquad : \qquad \qquad \} \]

A variable is indicated before the colon, and the properties are given after the colon. For example,

\[\begin{equation} \label{setbuilder} \{n \mid n\in \mathbb{N} \text{ and $n$ is odd}\}. \end{equation}\]

represents the set of nonnegative odd integers, i.e. the set \(\{0,1,3,5,7,\ldots \}.\) The colon is alway read and so \(\eqref{setbuilder}\) can be read as “the set of all \(n\) such that \(n\) is a natural number and is odd”.

Throughout we use \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\) to denote the set of natural numbers, the set of integers, and the set of rational numbers, respectfully. Note that we include 0 among the natural numbers: \[ \mathbb{N}=\{0,1,2,3,4,5,6,\ldots\}. \]

The set of all positive, zero, or negative numbers, are called the integers. Numbers of the form \(m/n,\) where \(m,n\) are integers and \(n\neq 0\) are called the rational numbers since they are ratios of integers. The set of real numbers, rational or not, contains all the numbers in \(\mathbb{Q},\) and many others as well such as \(\sqrt{2},\) \(\sqrt{3},\) \(\sqrt[3]{3},\) \(\sqrt[5]{3},\) \(\pi,\) and \(e\) and so on.

The most basic property of belonging is that of equality. For example, if \[ A=\{x\in \mathbb{R} \mid -9+21 x-10 x^2=0\}, \quad B=\left\{\frac{3}{5},\frac{3}{2}\right\} \] then \(A=B.\) To see this notice that \(-9+21 x-10 x^2=(2x-3)(3-5x)=0\) precisely when \(x=3/5\) or \(x=3/2.\)

4.2 Principle of Extension

Extension. Two sets are equal if and only if they contain the same elements.

Definition 4.1 Two sets \(A\) and \(B\) are called equal, denoted by \(A=B,\) provided they consist of the same elements. If \(A\) and \(B\) are not equal we write \(A\neq B.\)

Let \(A\) and \(B\) be sets. If every element of \(A\) is an element of \(B,\) we say \(A\) is a subset of \(B,\) or \(B\) contains \(A,\) and we write \(A\subseteq B,\) or \(B\supseteq A.\) Notice that set inclusion \(\subseteq\) has a few nice properties. It is reflexive, meaning \(A\subseteq A\) for any set \(A\); and is transitive, meaning, if \(A \subseteq B\) and \(B\subseteq C\) then \(A\subseteq C\) for all sets \(A, B, C.\)

By the principle of extension, set inclusion is also meaning \(A\subseteq B\) and \(B\subseteq A\) together imply \(A=B.\) You might have noticed that equality is also reflexive and transitive. Equality is also symmetric, meaning if \(A=B\) then \(B=A,\) for all sets \(A, B.\)

4.3 Specification

The next principle is designed to produce new sets out of known ones. We use the notation \(P(x)\) to mean a mathematical statement \(P\) which depends on the free variable \(x.\)

Specification. To every set \(A\) and to every condition \(P(x)\) there corresponds a set \(B\) whose elements are exactly those elements \(x\) of \(A\) for which \(P(x)\) holds.

By Extension, the set \(B\) in the Specification is uniquely determined. Also by Specification, the set \(\{x\in A \mid x\neq x \},\) denoted by \(\emptyset,\) exists and is called the empty set. This of course assumes that there exists a set \(A\) in the first place, as we have assumed all along. Of course the empty set is a subset of every set. The next question that comes to mind is: are there enough sets to ensure that every set belongs to some set?

Let \(A\) and \(B\) be sets. If every element of \(A\) is an element of \(B\), we say \(A\) is a subset of \(B\), or sometimes we say \(B\) contains \(A\), and we write \(A\subseteq B\), or \(B\supseteq A\). For example, \(\{1,4,a\}\subseteq \{0,1,3,4,a,b\}\) or as another example the inclusions hold \(\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q}\subseteq \mathbb{R}.\)

Definition 4.2 A set \(A\) is called a subset of a set \(B,\) denoted by \(A\subseteq B,\) provided every element of \(A\) is also an element of \(B.\)

The symbol \(\emptyset\) is the last letter in the Danish-Norwegian alphabet.

Definition 4.3 The unique set that has no elements is called the empty set and is denoted by \(\emptyset.\)

Recall the tautologies \(p\rightarrow p\) and \(((p\rightarrow q)\land (q\rightarrow r))\rightarrow (p\rightarrow r).\)

Theorem 4.1 Let \(A\), \(B\), and \(C\) be subsets of a universal set \(U.\)

  1. \(A\subseteq A\)
  2. \((A\subseteq B \land B\subseteq C) \rightarrow A\subseteq C.\)

Proof. Let \(x\) be an arbitrary element of \(A.\) Then \(x\) is in \(A\) and so \(A\subseteq A.\) For the second statement, assume \(x\) be an arbitrary element of \(A.\) Since \(A\subseteq B,\) we have \(x\in B\) by definition of subset. Since \(B\subseteq C,\) we have \(x\in C\) by definition of subset, whence \(A\subseteq C.\)

To show that \(A=B\) one must prove that \(x\in A\leftrightarrow x\in B\); that is, \(x\in A\) if and only if \(x\in B.\) This is equivalent to proving that \(x\in A\rightarrow x\in B\) and \(x\in B\rightarrow x\in A.\) There are two parts to such a proof: first assume that \(x\in A\) and show that \(x\in B\) follows. Then assume, independently, that \(x\in B\) and show that \(x\in A\) follows.

The reader is encourage to justify each step in this proof.

Theorem 4.2 For any two subsets \(A\) and \(B\) of a universal set \(U,\) \[\begin{equation} \label{eqsetsone} A=B \leftrightarrow (A\subseteq B \land B\subseteq A). \end{equation}\]

Proof. We proceed as follows \[\begin{align*} A=B & \leftrightarrow \forall x, (x\in A \leftrightarrow x\in B) \\ & \leftrightarrow \forall x, [(x\in A\rightarrow x\in B)\land (x\in B\rightarrow x\in A)] \\ & \leftrightarrow [\forall x, x\in A \rightarrow x\in B]\land [\forall x, (x\in B\rightarrow x\in A)]\\ & \leftrightarrow (A\subseteq B) \land (B\subseteq A) \end{align*}\] as needed.

Theorem 4.3 For any two subsets \(A\) and \(B\) of a universal set \(U,\) \[\begin{equation} \label{subsetsmean} A\subseteq B \leftrightarrow \forall C (C\subseteq A \rightarrow C\subseteq B). \end{equation}\]

Proof. First we show that \[\begin{equation} \forall C, (C\subseteq A\rightarrow C\subseteq B)\rightarrow A\subseteq B. \end{equation}\] Assume that for any set \(C,\) if \(C\subseteq A,\) then \(C\subseteq B.\) Since \(A\subseteq A,\) it follows that \(A\subseteq B\) as needed. Next it must be shown that \[\begin{equation} A\subseteq B \rightarrow \forall C, (C\subseteq A \rightarrow C\subseteq B). \end{equation}\] Assume \(A\subseteq B\) and let \(C\) be any set such that \(C\subseteq A.\) Then we have \(C\subseteq A\) and \(A\subseteq B,\) and so we have \(C\subseteq B.\)

Theorem 4.4 Let \(A\) be a subset of a universal subset \(U.\) Then for all \(x\in U,\) \[\begin{equation} \label{elesubst} x\in A \leftrightarrow \{x\}\subseteq A. \end{equation}\]

Proof. The proof is left for the reader as Exercise 4.20.

Set inclusion is also antisymmetric meaning \(A\subseteq B\) and \(B\subseteq A\) together imply \(A=B\). Equality is also symmetric, meaning if \(A=B\) then \(B=A\), for all sets \(A, B\).

Theorem 4.5 For any two subsets \(A\) and \(B\) of a universal set \(U,\)

  1. \(A=B \leftrightarrow B=A,\) and
  2. \((A\subseteq B \land B\subseteq A) \rightarrow A=B.\)

Proof. The proof is left for the reader as Exercise 4.21.

4.4 Proper Subset

A subset \(B\) of a set \(A\) is said to be a proper subset of \(A\) if it is not equal to \(A\) itself. Thus all subsets of \(A\) are proper subsets except the set \(A\) itself, which is referred to as the improper subset of \(A.\)

Definition 4.4 A set \(A\) is called a proper subset of a set \(B\) provided \(A\subseteq B\) and \(A\neq B.\) We write \(A\subset B\) to denote that \(A\) is a proper subset of \(B.\)

Theorem 4.6 For any two subsets \(A\) and \(B\) of a universal set \(U,\) \[\begin{equation} A\subset B \leftrightarrow [A\subseteq B \land \exists x, (x\in B \land x\notin A)]. \label{eqsets} \end{equation}\]

Proof. Assume \(A\subset B.\) Then \(A\subseteq B\) and \(A\neq B.\) By definition of \(A\neq B,\) one must hold \[ \exists x, (x\in A\land x\notin B) \quad \text{ or }\quad \exists x, (x\in B \land x\notin A). \]

If the first one holds, then we have \(x\in B\) and \(x\notin B,\) a contradiction. Hence the former holds as needed. Conversely, assume \(A\subseteq B\) and \({\exists x, (x\in B \land x\notin A).}\) Then by definition of \(A\neq B,\) since \(B\) contains an element not in \(A,\) we have \(A\neq B.\) Therefore we have \(A\subseteq B\) and \(A\neq B,\) and thus \(A\subset B.\)

4.5 Why elelmentary set theory?

In the foundations of mathematics, Russell’s paradox, discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction. According to naive set theory, any definable collection is a set.

Let \(R\) be the set of all sets that are not members of themselves. If \(R\) is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.

This contradiction is called Russell’s paradox. Symbolically: \[ \text{If $R = \{ x \mid x \notin x \},$ then $R \in R \leftrightarrow R \not \in R$.} \] In 1908, two ways of avoiding the paradox were proposed, Russell’s type theory and the Zermelo set theory. There is a long interesting history of this problem and the reader is encourage to explore.

4.6 Axiom of Choice

In 1904, Ernst Zermelo formulated the Axiom of Choice to prove the Well-Ordering Theorem . Of course, we now know that these two statements are logically equivalent and in fact, there are many equivalents forms Adamson (1998).

Theorem 4.7 In Zermelo-Fraenkel set theory, the following statements are equivalent:

  1. (Axiom of Choice) Given any set \(X\) of pairwise disjoint non-empty sets, there exists at least one set \(B\) that contains exactly one element in common with each of the sets in \(X\). Suppes (1972)
  2. (Well-Ordering) Every set can be well-ordered. (Cantor 1883)

Said differently, and in particular, the Axiom of Choice guarantees that every finite collection of nonempty sets has a choice function. However, in Zermelo-Fraenkel set theory, this is easily proven using mathematical induction (Tourlakis 2003). The following statements are also weaker than the Axiom of Choice.

Harzheim (2005)

Theorem 4.8 Every partial order can be extended to a total order and every well-founded partial order can be extended to a well-order.

4.7 Set Operations

4.7.1 Power Sets

The next question that comes to mind is: is the collection of subsets of a set, a set itself? In other words, given a set \(A\) does there exist a set \(\mathcal{P}\) such that if \(X\subseteq A\) then \(X\in \mathcal{P}\,\)?

Definition 4.5 The set consisting of all subsets of a given set \(A\) is called the power set of \(A\) and is denoted by \(\mathcal{P}(A).\)

Theorem 4.9 If \(A\) is a set, then \(\emptyset \in \mathcal{P}(A)\) and \(A\in \mathcal{P}(A).\)

Proof. Notice that the empty set is a subset of every set (including itself). Thus, \(\emptyset \in \mathcal{P}(A)\) is immediate. The second statement follows immediately; that is, \(A\subseteq A\) implies \(A\in \mathcal{P}(A).\)

Theorem 4.10 If \(A\) has \(n\) elements, then \(\mathcal{P}(A)\) has \(2^n\) elements.

Proof. If \(n=0,\) then \(A\) is the empty set. The only subset of the empty set is the set itself; thus the number of elements in \(\mathcal{P}(A)\) is \(1\) which is \(2^0\) as needed to verify the basis step.

Assume that the statement holds for \(n.\) Let \(X\) be a set with \(n+1\) elements and assume \(x\in X.\) We claim that exactly half of the subsets of \(X\) contain \(x,\) and half do not. To see this, notice that each subset of \(X\) that contains \(x\) can be paired uniquely with a subset obtained by removing \(x\). \[ \begin{matrix} \text{ subsets of $A$ that contain $x$ } & \text{ subsets of $A$ that do not contain $x$ } \\ \hline \{x\} & \emptyset \\ \{x,y\} & \{y\} \\ \{x,z\} & \{z\} \\ \{x,y,z\} & \{y,z\} \end{matrix} \] If we let \(Y\) be the set obtained from \(X\) by deleting \(x,\) \(Y\) has \(n\) elements. By the inductive hypothesis \(\mathcal{Y}\) has exactly \(2^n\) elements. But the subsets of \(Y\) are precisely the subsets of \(X\) that do not contain \(x.\) It follows that the number of elements in \(\mathcal{Y}\) is one-half the number of elements in \(\mathcal{X}.\) Therefore, the number of elements in \(\mathcal{X}\) is twice the number of elements in \(\mathcal{Y}.\) Whence the number of elements in \(\mathcal{X}\) is \(2^{n+1}.\)

Theorem 4.11 If \(A\) is an infinite set, then \(\mathcal{P}(A)\) is also.

Proof. The proof is left for the reader as Exercise 4.1.

4.7.2 Principle of Unions

Union. For every collection of sets there exists a set that contains all the elements that belong to at least one set of the given collection.

Given a collection of sets \(\mathcal{C}\) we want their union to consist of only those elements that belong to at least one of the subsets in the collection. So we apply the principle of specification to the set \(U\) and define the union of a collection of sets as \[ \bigcup_{X\in \mathcal{C}}X=\{x\in U \mid x\in X \text{ for some $X$ in $\mathcal{C}$\}}. \] This set exists by the principle of specification and is unique by the principle of extension. In the case \(\mathcal{C}=\{A, B\}\) we usually write \[ A\cup B=\{x \mid x\in A \text{ or } x\in B\}. \]

Theorem 4.12 Let \(A,\) \(B,\) and \(C\) be sets. Then

  1. \(A\cup \emptyset =A ,\)
  2. \(A\cup B=B\cup A,\)
  3. \(A\cup (B \cup C) =(A\cup B)\cup C,\)
  4. \(A \cup A =A,\) and
  5. \(A\subseteq B\) if and only if \(A\cup B=B.\)

Proof. The proof is left for the reader as Exercise 4.2.

If \(A\) and \(B\) are sets we then define, using the principle of specification, their intersection as the set \(A \cap B=\{x\in A \mid x\in B\}.\) It is very easy to show the more familiar form, \(A\cap B=\{x \mid x\in A \text{ or } x\in B\}.\) More generally, let \(\mathcal{C}\) be a non-empty collection of sets, the principle of specification allows us to define a set \[ I=\{x \in A \mid x\in X \text{ for every $X$ in $\mathcal{C}$}\} \] where \(A\) is some set in \(\mathcal{C}.\) In fact the use of a set \(A\) is arbitrary (but necessary in order to use the principle of specification). Thus we are lead to the definition of the intersection of a collection of sets \[ \bigcap_{X\in \mathcal{C}} X=\{x\mid x\in X \text{ for all $X$ in $\mathcal{C}$ }\} \] where uniqueness is guaranteed by the principle of extension.

Theorem 4.13 Let \(A\), \(B\), and \(C\) be sets. Then

  1. \(A\cap \emptyset =\emptyset ,\)
  2. \(A\cap B=B\cap A,\)
  3. \(A\cap (B \cap C) =(A\cap B)\cap C,\)
  4. \(A \cap A =A,\) and
  5. \(A\subseteq B\) if and only if \(A\cap B=A.\)

Proof. The proof is left for the reader as Exercise 4.3.

Let \(A\) and \(B\) be subsets of a set \(C.\) The between \(A\) and \(B,\) known as the of \(B\) in \(A,\) is the set defined by \(A-B=\{x\in A \mid x\not\in B \}\); and the difference} between \(A\) and \(B,\) known as the of \(B\) in \(A,\) is the set defined by \(A-B=\{x\in A \mid x\not\in B \}\); and the \index{symmetric difference of \(A\) and \(B\) is defined by \(A+B=(A-B)\cup (B-A).\) Notice that the principle of specification guarantees existence and the principle of extension guarantees uniqueness of these sets for a given \(A\) and \(B.\) These sets are of course, by definition, also subsets of \(C.\)

The next question that comes to mind is: is the collection of subsets of \(C\) a set itself? In other words, given a set \(C\) does there exist a set \(\mathcal{P}\) such that if \(X\subseteq S\) then \(X\in \mathcal{P}\,\)?

4.7.3 Principle of Powers

Principle of Powers. For each set there exists a collection of sets that contains among its elements all the subsets of the given set.

Thus, given a set \(C\) we can form a collection of sets, denoted by \(\mathcal{P},\) that contains the subsets of \(C.\) We can use the principle of specification to ensure that this set will consist only of subsets of \(C\) and the principle of extension to ensure that this set is unique. We call this set the power set of \(C,\) and denote it by \(\mathcal{P}(S)=\{X \mid X\subseteq S\}\) or sometimes even \(2^S.\)

The fundamental most frequently used operations of set theory are union, intersection, and difference.

In this section we discuss these operations and some of their properties.

The union of a collection of sets is the set of all distinct elements in the collection.

Definition 4.6 Let \(A\) and \(B\) be subsets of some universal set \(U.\) The union of \(A\) and \(B\) is the set \(A\cup B\) defined by \[ A\cup B =\{x\mid x\in A \lor x\in B\}. \]

Recall that \(p\rightarrow (p\lor q)\) is a tautology. This immediately yields that for any sets \(A\) and \(B,\) \[\begin{equation} \label{subsetcup} A\subseteq A\cup B \qquad \text{ and } \qquad B\subseteq A\cup B. \end{equation}\] This follows because \(A\subseteq A\cup B\) is equivalent to \(\forall x, x\in A\rightarrow (x\in A \lor x\in B)\) by definition of subset. Similarly for \(B\subseteq A\cup B.\)

Example 4.1 Let \(U=\{1,2,3,\ldots, 10\},\) \(A=\{2,4,6\},\) \(B=\{1,3,5,7,9\}\) and \(C=\{5,10\}.\) Find and compare the sets: \(A\cup (B \cup C)\) and \((A\cup B)\cup C\)

Proof. We find \(B\cup C=\{1,3,5,7,9,10\}\) and so \[ A\cup(B\cup C)=\{1,2,3,4,5,6,7,9,10\}. \] Also, \(A\cup B=\{1,2,3,4,5,6,7,9\}\) and so \[ (A\cup B)\cup C)=\{1,2,3,4,5,6,7,9,10\}. \] Therefore we find that \(A\cup (B \cup C)=(A\cup B)\cup C\).

Theorem 4.14 Let \(A\) and \(B\) be subsets of some universal set \(U.\)

  1. \(A\cup \emptyset =A\)
  2. ( commutativity) \(A\cup B=B\cup A\)
  3. ( associativity) \(A\cup (B \cup C) =(A\cup B)\cup C\)
  4. ( idempotence) \(A \cup A =A\)
  5. \(A\subseteq B\) if and only if \(A\cup B=B\).

Proof. We prove (1) and (5) and leave the remainder of the proof for the reader as Exercise 4.5.

(1): Let \(x\) be an arbitrary element of \(A\cup \emptyset.\) Then, by definition of union, either \(x\in A\) or \(x\in \emptyset.\) Since there are no elements in \(\emptyset,\) we must have \(x\in A\); hence \(A\cup \emptyset\subseteq A.\) Conversely, follows from \(\eqref{subsetcup}\).

(5): Assume \(A\subseteq B.\) We must show that \(A\cup B=B.\) By \(\eqref{subsetcup}\) we immediately see that \(B\subseteq A\cup B.\) To show the remaining inclusion, let \(x\in A\cup B.\) Then either \(x\in A\) or \(x\in B.\) In the case that \(x\in A,\) then we have \(x\in B\) by hypothesis. Thus, in either case we have \(x\in B,\) and so \(A\cap B\subseteq B.\) Therefore, we have shown that if \(A\subseteq B,\) then \(A\cap B=B.\)

Conversely, we now assume that \(A\cup B=B\) and we wish to conclude that \(A\subseteq B.\) To do so, let \(x\) be an arbitrary element of \(A.\) Then \(x\in A\cup B\) by \(\eqref{subsetcup}\), and so \(x\in A\cup B=B.\) Hence \(A\subseteq B\) as needed.

The intersection of a collection of sets is the set that contains all elements, each of which are in each of the sets in the collection, and no other elements.

4.7.4 Principle of Intersections

Definition 4.7 Let \(A\) and \(B\) be subsets of some universal set \(U.\) The intersection of \(A\) and \(B\) is the set \(A\cap B\) defined by \[ A\cap B =\{x\mid x\in A \land x\in B\}. \]

Theorem 4.15 Let \(A\) and \(B\) be subsets of some universal set \(U.\)

  1. \(A\cap \emptyset =\emptyset\)
  2. ( commutativity) \(A\cap B=B\cap A\)
  3. ( associativity) \(A\cap (B \cap C) =(A\cap B)\cap C\)
  4. ( idempotence) \(A \cap A =A\)
  5. \(A\subseteq B\) if and only if \(A\cap B=A\).

Proof. We prove (2) and (3) and leave the remainder of the proof for the reader as Exercise 4.6.

(2): Let \(x\) be an arbitrary element in \(A\cap B.\) Then \[\begin{align*} & x\in A \cap B & \qquad & \\ & \quad \rightarrow x\in A\land x\in B & & \text{by Definition of $\cap$} \\ & \quad \rightarrow x\in B\land x\in A & & \text{by commutativity of $\land$} \\ & \quad \rightarrow x\in B \cap A & & \text{by Definition of $\cap$} \end{align*}\] Thus \(x\in A\cap B\rightarrow x\in B\cap A\) and consequently \[ A\cap B\subseteq B\cap A. \]

In a similar fashion (simply reverse the implications) one may prove that \(B\cap A\subseteq A\cap B.\) Therefore, \(A\cap B=B\cap A\).

(3): Let \(x\) be an arbitrary element in \((A \cap B)\cap C.\) Then \[\begin{align*} & x\in (A \cap B)\cap C & \qquad & \\ & \quad \rightarrow [ x\in (A \cap B) \land x\in C ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ (x\in A \land x\in B)\land x\in C ]& & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in A \land ( x\in B \land x\in C) ] & & \text{by associativity of $\land$} \\ & \quad \rightarrow [ x\in A \land ( x\in B \cap C) ]& & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in (A \cap B) \cap C ] & & \text{by Definition of $\cap$} \end{align*}\]

Thus \(x\in (A\cap B)\cap C \rightarrow x\in A\cap (B\cap C)\) and consequently \[ (A\cap B)\cap C\subseteq A\cap (B\cap C). \] In a similar fashion (simply reverse the implications) one may prove that \(A\cap (B\cap C)\subseteq (A\cap B)\cap C.\) Therefore, \(A\cap (B\cap C)=(A\cap B)\cap C.\)

Theorem 4.16 Let \(A\), \(B\), \(C\) be subsets of some universal set \(U.\)

  1. \(A\cap (B \cup C) = (A\cap B)\cup (A\cap C)\)
  2. \(A\cup (B \cap C) = (A\cup B)\cap (A\cup C)\)

Proof. We prove (1) and leave the remainder of the proof for the reader as Exercise 4.7.

(1): Let \(x\) be an arbitrary element in \(A\cap (B \cup C).\) Then \[\begin{align*} & x\in A\cap (B \cup C) & \qquad & \\ & \quad \rightarrow [ x\in A \land x\in B\cup C ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ x\in A \land (x\in B \lor x\in C) ]& & \text{by Definition of $\cup$} \\ & \quad \rightarrow [ (x\in A \land x\in B) \lor (x\in A \land x\in C) ] & & \text{by distributivity of $\land$} \\ & \quad \rightarrow [ (x\in A \cap B) \lor (x\in A \cap C) ] & & \text{by Definition of $\cap$} \\ & \quad \rightarrow [ (x\in A \cap B) \cup (A \cap C) ] & & \text{by Definition of $\cup$} \end{align*}\]

Thus \(x\in A\cap (B \cup C) \rightarrow x\in (A\cap B)\cup (A\cap C)\) and consequently \[ A\cap (B \cup C) \subseteq (A\cap B)\cup (A\cap C). \]

In a similar fashion (simply reverse the implications) one may prove that \((A\cap B)\cup (A\cap C) \subseteq A\cap (B \cup C).\) Therefore, \(A\cap (B \cup C)=(A\cap B)\cup (A\cap C).\)

4.7.5 Relative Complement

The relative complement of \(B\) with respect to a set \(A\) is the set of elements in \(A\) but not in \(B.\)

Definition 4.8 Let \(A\) and \(B\) be subsets of some universal set \(U.\) The relative complement of \(B\) in \(A\) is the set \(A-B\) defined by \[ A-B =\{x\mid x\in A \land x\notin B\}. \] The relative complement of \(B\) in \(A\) is also denoted by \(A\setminus B.\)

When all sets under consideration are considered to be subsets of a given set \(U,\) the absolute complement of \(A\) is the set of all elements in \(U\) but not in \(A,\) and is denoted by \(A',\) that is, the complement of a set \(A\) is defined by \[ A'=\{x\in U \mid x\not\in A\}. \] To be redundant, by definition \(A'=U-A.\)

Example 4.2 Let \(S=\{a,b,c\},\) \(T=\{1,a\},\) and \(V=\{1,2,3,c\}.\) Find and compare the sets, \((S-T)-V\) and \(S-(T-V).\)

Proof. We find \(S-T=\{b,c\}\) and \(T-V=\{a\},\) and so \((S-T)-V=\{b\}\) and \(S-(T-V)=\{b,c\}.\) Thus, \((S-T)-V\subseteq S-(T-V).\)

4.7.6 De Morgan’s Laws

Theorem 4.17 Let \(A\) and \(B\) be subsets of some universal set \(U.\)

  1. \((A \cup B)'=A' \cap B'\)
  2. \((A \cap B)'=A' \cup B'\).

Proof. We prove (1) and leave the remainder of the proof for the reader as Exercise 4.8. Let \(x\) be an arbitrary element in \((A \cup B)'.\) Then \[\begin{align*} & x\in (A \cup B)' & \qquad & \\ & \quad \rightarrow [x\notin A \cup B] & & \text{by Definition of complement} \\ & \quad \rightarrow [\neg(x\in A \cup B)] & & \text{by Definition of $\notin$} \\ & \quad \rightarrow [\neg(x\in A \lor x\in B)] & & \text{by Definition of $\cup$} \\ & \quad \rightarrow [\neg(x\in A) \land \neg(x\in B)] & & \text{DeMorgan's Law} \\ & \quad \rightarrow [x\notin A \land x\notin B] & & \text{by Definition of $\notin$} \\ & \quad \rightarrow [x\in A' \land x\in B'] & & \text{by Definition of complement} \\ & \quad \rightarrow [x\in A' \cap B'] & & \text{by Definition of $\cap$} \end{align*}\]

Thus \(x\in (A \cup B)' \rightarrow x\in A' \cap B'\) and consequently \((A \cup B)' \subseteq x\in A' \cap B'.\) In a similar fashion (simply reverse the implications) one may prove that \(A' \cap B' \subseteq (A \cup B)'.\) Therefore, \((A \cup B)'=A' \cap B'\).

Theorem 4.18 Let \(A\) and \(B\) be subsets of some universal set \(U.\)

  1. \((A')'=A\)
  2. \(\emptyset '=U\)
  3. \(U'=\emptyset\)
  4. \(A \cap A'=\emptyset\)
  5. \(A \cup A' =U\)
  6. \(A-B=A\cap B'\)

Proof. The proof is left for the reader as Theorem 4.18.

Theorem 4.19 Let \(A\) and \(B\) be subsets of some universal set \(U.\)

  1. \(A \subseteq B\) if and only if \(B'\subseteq A'\)
  2. \(A\subseteq B\) if and only if \(A-B=\emptyset\)

Proof. We prove (1) and leave the remainder of the proof for the reader as Exercise 4.9. Assume \(A\subseteq B\) and let \(x\) be an arbitrary element in \(B'.\) Thus, \(x\notin B.\) Assume for a contradiction that \(x\in A.\) By hypothesis, we have \(x\in B\) and \(x\notin B.\) Thus, \(x\in A'\) must occur. Conversely, assume \(B'\subseteq A'\) and let \(x\) be an arbitrary element of \(A.\) Assume for a contradiction that \(x\in B'.\) By hypothesis, we have \(x\in A\) and \(x\notin A.\) Thus, \(x\in B\) must occur.

4.7.7 Symmetric Difference

The symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection.

Definition 4.9 If \(A\) and \(B\) are sets, we define the symmetric difference of \(A\) and \(B\) by \[ A\bigtriangleup B=(A-B)\cup (B-A). \]

Theorem 4.20 Let \(A\) and \(B\) be subsets of some universal set \(U.\) Then \[\begin{equation} \label{symmdiff} A\bigtriangleup B=(A\cup B)-(A\cap B). \end{equation}\]

Proof. Let \(x\) be an arbitrary element of \(A\bigtriangleup B.\) Then \[\begin{align*} & x\in A\bigtriangleup B & \\ & \qquad \rightarrow x\in (A-B) \cup (B-A) & \\ & \qquad \rightarrow x\in A-B \lor x\in B-A & \\ & \qquad \rightarrow (x\in A \land x\notin B) \lor (x\in B\land x\notin A) & \\ & \qquad \rightarrow (x\in B\land x\notin A) \lor (x\in A \land x\notin B) & \\ & \qquad \rightarrow [(x\in A\land x\notin A) \lor (x\in B\land x\notin A)] \\ & \qquad \qquad \qquad \lor [(x\in A \land x\notin B)\lor (x\in B \land x\notin B)] \\ & \qquad \rightarrow [(x\in A \lor x\in B)\land x\notin A)] \lor [(x\in A \lor x\in B) \land x\notin B)] & \\ & \qquad \rightarrow (x\in A \lor x\in B) \land (x \notin A \lor x\notin B) & \\ & \qquad \rightarrow (x\in A \lor x\in B) \land \neg (x\in A \land x\in B) & \\ & \qquad \rightarrow x\in (A\cup B) \land \neg (x\in A \cap B) & \\ & \qquad \rightarrow x\in (A\cup B) \land x\notin A\cap B & \\ & \qquad \rightarrow x\in (A\cup B) -(A\cap B) & \end{align*}\] The justification of the above steps and the remainder of the proof is left for the reader as Exercise 4.10.

Theorem 4.21 Let \(A\), \(B\), and \(C\) be subsets of some universal set \(U.\)

  1. \(A\bigtriangleup B=B\bigtriangleup A\)
  2. \(A\bigtriangleup (B\bigtriangleup C)=(A\bigtriangleup B)\bigtriangleup C\)
  3. \(A\bigtriangleup \emptyset = A\)
  4. \(A\bigtriangleup A=\emptyset\)

Proof. The proof is left for the reader as Exercise 4.11.

Theorem 4.22 Let \(A\) and \(B\) be sets. Then

  1. \(A+B=B+A,\)
  2. \(A+(B+C)=(A+B)+C,\)
  3. \(A+\emptyset = A,\) and
  4. \(A+A=\emptyset .\)

Proof. The proof is left for the reader as Exercise 4.12.

A collection of sets is called disjoint if they have no elements in common.

Definition 4.10 If \(A\) and \(B\) are sets and \(A\cap B=\emptyset,\) then \(A\) and \(B\) are disjoint sets .

Theorem 4.23 Let \(A\) and \(B\) be subsets of some universal set \(U.\) Then \(A\) and \(B\) are disjoint if and only if \(A\cup B=A\bigtriangleup B.\)

Proof. The proof is left for the reader as Exercise 4.13.

4.7.8 Principle of Pairing

Principle of Pairing. For any two sets there exists a set that they both belong to.

For example, suppose \(a\) and \(b\) are sets that are elements of the set \(A,\) then by the principle of specification the set \(\{a, b\}:=\{x\in A \mid x=a \text{ or } x=b \}\) exists, and by the principle of extension is unique. This set is called the pair (or unordered pair) formed by \(a\) and \(b.\) Given any set \(a\) we have the pair \(\{a,a\}\) which is usually just denoted by \(\{a\},\) and is called the singleton set of \(a.\)

Let \(\mathcal{C}\) denote a collection of sets. By the following principle we can define the set \(U\) consisting of those elements \(x\) such that if \(x\in X\) for some \(X\in \mathcal{C},\) then \(x\in U.\)

An ordered pair \((a, b)\) is a pair of mathematical objects. The order in which the objects appear in the pair is significant: the ordered pair \((a, b)\) is different from the ordered pair \((b, a)\) unless \(a = b.\) (In contrast, the unordered pair \(\{a, b\}\) equals the unordered pair \(\{b, a\}.\))

4.7.9 Cartesian Product

Definition 4.11 Given any two sets \(A\) and \(B,\) the Cartesian product of \(A\) and \(B\) is the set \(A\times B\) defined by \[ A\times B =\{(a,b)\mid a\in A \land b\in B)\}. \]

Theorem 4.24 If \(A\), \(B\), and \(C\) are sets, then

  1. \(A\times (B\cup C)=(A\times B)\cup (A\times C)\)
  2. \(A\times (B\cap C)=(A\times B)\cap (A\times C)\)
  3. \(A\times (B- C)=(A\times B)- (A\times C)\)
  4. \(A\times (B\bigtriangleup C)=(A\times B)\bigtriangleup (A\times C)\)

Proof. The proof is left for the reader as Exercise 4.14.

The idea of ordered pair can be extended to more than two elements. Given \(n\) elements \(a_1, a_2, \ldots, a_n,\) where \(n\geq 3,\) we can define the ordered \(n\)-tuple \((a_1, a_2, \ldots a_n),\) in which \(a_1\) is the first element, \(a_2\) is the second element, and so on, and \(a_n\) is the \(n\)-th element. We can now generalize the idea of Cartesian product.

Definition 4.12 Given any \(n\) sets \(A_1, A_2, \ldots, A_n,\) the Cartesian product of \(A_1, A_2, \ldots, A_n\) is the set defined by \[ A_1\times A_2 \times \cdots \times A_n =\{(a_1, a_2, \ldots, a_n) \mid a_i\in A_i \text{ for each $i,$ $1\leq i \leq n$}\}. \]

It follows immediately, \[ (a_1, a_2, \ldots, a_n)=(b_1, b_2, \ldots, b_n) \text{ if and only if $a_i=b_i$ for each $i,$ $1\leq i \leq n.$} \] Also notice that \(A_1\times A_2 \times \cdots \times A_n=\emptyset\) if and only if \(A_i=\emptyset\) for some \(i,\) \(1\leq i \leq n.\) For this reason, when working with Cartesian products of sets, it is normally the case that each of the sets is nonempty.

Example 4.3 Prove or disprove that \[ \mathcal{P}(A\times B)=\mathcal{P}(A)\times \mathcal{P}(B), \] for any sets \(A\) and \(B.\)

The ordered pair of \(a\) and \(b,\) with first coordinate \(a\) and second coordinate \(b\) is defined as the set \(\{\{a\},\{a,b\}\}\) and is denoted more naturally by \((a,b).\) The reader should show that this definition is well-defined by proving the following lemma.

Lemma 4.1 If \((a,b)\) and \((x,y)\) are ordered pairs and if \((a,b)=(x,y)\) then \(x=a\) and \(y=b.\)

Proof. The proof is left as an exercise for the reader as Exercise 4.16.

The next question that comes to mind is: if \(A\) and \(B\) are sets, does there exist a set that contains all the ordered pairs \((a,b)\) with \(a\in A\) and \(b\in B.\) Surely so; for example, \(\{a\}\subseteq A\) and \(\{b\}\subseteq B,\) and therefore \(\{a,b\}\subseteq A\cup B.\) Thus, by definition, \((a,b)=\{\{a\},\{a,b\}\}\subseteq \mathcal{P}(A\cup B).\) It follows that \({(a,b)\in \mathcal{P}(\mathcal{P}(A\cup B)).}\) We can do much better than this though.

The Cartesian product of two sets is a set of ordered pairs. Conversely, every set of ordered pairs is a subset of the Cartesian product of two sets. By the above argument, every set of ordered pairs is contained in some subset, via \[ (a,b)\in \mathcal{P}(\mathcal{P}(A\cup B)) \quad \text{whenever } \quad a\in A, b\in B. \] By the principle of specification, we define a set \[ A\times B = \{x \in \mathcal{P}(\mathcal{P}(A\cup B)) \mid x=(a,b) \text{ for some $a\in A$ and $b\in B$}\}. \] By the principle of extension, this set is unique; and is called the Cartesian product of \(A\) and \(B.\) Thus, as desired, the Cartesian product of two sets is a set of ordered pairs. Conversely, let \(P\) be a set that consists of ordered pairs and let \(x\in P.\) Then by definition of ordered pair \(x=\{\{a\},\{a,b\}\}\) for some \(a\) and for some \(b.\) Since \(P\) is a set consisting of sets, we form the union and observe \(\{a,b\}\in \cup_{X\in P} P.\)

Observe further that \({\cup_{X\in P} P:=P'}\) is a set consisting of sets, so it follows both \(a\) and \(b\) are elements of \[ U:=\bigcup_{Y\in P'} \bigcup_{X\in P} P. \] Let \(A\) and \(B\) be such that \(A=B=U.\) Thus \(P,\) a set of ordered pairs, is a subset of the Cartesian product of two sets, namely \(U\times U.\) We can use the principle of specification to refine the sets \(A\) and \(B,\) namely \[ A=\{ a \in U \mid (a,b) \in P \text{ for some } b \} \] and \[ B=\{ b \in U \mid (a,b) \in P \text{ for some } a \}. \] These sets are unique by the principle of extension and are called the projections of \(P\) onto the first and second coordinates, respectively.

Theorem 4.25 Let \(A\), \(B\), \(X\), and \(Y\) be sets. Then

  1. \((A \cup B)\times X=(A\times X)\cup (B\times X),\)
  2. \((A \cap B)\times (X\cap Y)=(A\times X)\cap (B\times Y),\)
  3. \((A-B)\times X=(A\times X)-(B\times X),\)
  4. \(\left( A=\emptyset \text{ or } B=\emptyset \right)\) if and only if \(A\times B=\emptyset,\) and
  5. If \(A\times B\neq \emptyset\) then, \(\left( A\subseteq X \text{ and } B\subseteq Y \right)\) if and only if \(A\times B \subseteq X\times Y.\)

Proof. The proof is left for the reader as Exercise 4.15.

4.7.10 Finite Families

Given any \(n\) sets \(A_1, A_2, \ldots, A_n,\) we define their union to be the set \[ A_1 \cup A_2 \cup \cdots \cup A_n =\{x\mid x\in A_i \text{ for some } i, 1\leq i \leq n\}. \] and their intersection to the the set \[ A_1 \cap A_2 \cap \cdots \cap A_n =\{x\mid x\in A_i \text{ for all } i, 1\leq i \leq n\}. \] These sets can be written as \[ \bigcup_{i=1}^n A_i \qquad \text{and}\qquad \bigcap_{i=1}^n A_i \] respectively.

Example 4.4 For \(i\in \{1,2,3,\ldots, 10\},\) define \[ A_i=[-i,10-i]. \] Find \(A_1,\) \(A_2, \ldots, A_{10}\) and then find \(\bigcup_{i=1}^{10} A_i\) and \(\bigcap_{i=1}^{10} A_i.\)

Solution. We find that \[ A_1=[-1,9], \quad A_2=[-2,8], \quad \ldots, \quad A_{10}=[-10,0]. \] Hence \[\begin{equation} \bigcup_{i=1}^{10} A_i=[-10,9] \qquad \text{and} \qquad \bigcap_{i=1}^{10} A_i=[-1,0]. \end{equation}\] as needed.

Example 4.5 For \(k\in \{1,2,\ldots, 100\},\) define \[ B_k=\{r\in \mathbb{Q} \mid -1\leq k \cdot r \leq 1\}. \] Find \(B_k\) for \(1\leq k\leq 100,\) compare these sets, and then find \(\bigcup_{k=1}^{100} B_k\) and \(\bigcap_{k=1}^{100} B_k.\)

Solution. We find \[\begin{align*} & B_1=\{r\in \mathbb{Q} \mid -1 \leq r \leq 1\}, \\ & \qquad & B_2=\left\{\{r\in \mathbb{Q} \mid -\frac{1}{2} \leq r \leq \frac{1}{2}\right\}, \\ & \qquad \cdots \qquad \cdots \\ & & B_{100}=\left\{r\in \mathbb{Q} \mid -\frac{1}{100} \leq r \leq \frac{1}{100}\right\}, \end{align*}\] and so \[ B_{100}\subseteq B_{99} \subseteq B_{98} \subseteq \cdots \subseteq B_2 \subseteq B_1. \] It follows that \[ \bigcup_{k=1}^{100} B_k=B_1 \qquad \text{and} \qquad \bigcap_{k=1}^{100} B_k=B_{100}. \] as needed.

4.7.11 Families of Sets

Let \(I\) be a nonempty set, and suppose that for each element \(i\in I\) there is associated a set \(A_i.\) We then call \(I\) an index set for the collection of sets \(\mathcal{P}(A)=\{ A_i \mid i\in I\}.\)

Definition 4.13 Let \(I\) be an indexed set and suppose that \(\mathcal{P}(A)=\{A_i\mid i\in I\}\) is a collection of sets. Then

  1. the \(\mathcal{P}(A)\) union of the collection is defined to be the set \[ \bigcup_{i\in I} A_i =\{x\mid x\in A_i \text{ for some } i\in I\}, \]
  2. the \(\mathcal{P}(A)\) intersection of the collection is defined to be the set \[ \bigcap_{i\in I} A_i =\{x\mid x\in A_i \text{ for each } i\in I\}. \]

Theorem 4.26 Given the collection of sets \(\{A_i \mid i\in \mathbb{N}\}\) the following properties hold.

  1. If \(A_i \subseteq A_{i+1}\) for all \(i\in \mathbb{N},\) then \(\bigcap_{i=1}A_i=A_1.\)
  2. If \(A_i \supseteq A_{i+1}\) for all \(i\in \mathbb{N},\) then \(\bigcup_{i=1}A_i=A_1.\)

Proof. We prove (1) and leave (2) for the reader as Exercise 4.17. Let \(T=\cap_{i=1}A_i=A_0\) and let \(x\) be an arbitrary element of \(T.\) Then \(x\in A_i\) for each \(i\in \mathbb{N},\) and this certainly implies that \(x\in A_1.\) So \(T\in A_1.\) Conversely, assume \(x\in A_1.\) Since \(A_i \subseteq A_{i+1}\) for all \(i\in \mathbb{N},\) we have that \(A_1\subseteq A_i\) for every \(i\in \mathbb{N},\) and hence \(x\in T.\) This shows that \(A_1\subseteq T\); hence we conclude that \(T=A_1.\)

Example 4.6 Let \(n\in \mathbb{N}\) and let \[ A_n=\{m\in \mathbb{Z} \mid -n \leq m \land 2^m\leq n\}. \] Use Theorem 4.26 to find \(\bigcap_{i=1}^{\infty} A_i\) and \(\bigcup_{i=1}^{\infty} A_i.\)

Solution. We find that \[\begin{align*} & A_1=\{-1,0\}, & & A_2=\{-2,-1,0,1\}, \\ & A_3=\{-3,-2,-1,0,1\}, & & A_4=\{-3,-2,-1,0,1,2\} \end{align*}\] and so on. Note that \(A_1\subseteq A_2 \subseteq A_3 \subseteq \cdots.\) Hence by Theorem 4.26, we have \[ \bigcap_{n=1}^\infty A_n=A_1 \] The reader should verify that \(\bigcup_{n=1}^\infty A_n=\mathbb{Z}.\)

Example 4.7 Let \(I=(0,1),\) and for \(i\in I,\) define \(A_i=(-i,i).\) Find \(\bigcap_{i\in I} A_i\) and \(\bigcup_{i\in I} A_i.\)

Solution. For example, \[ A_{1/2}=\left(-\frac{1}{2},\frac{1}{2}\right) \qquad \text{and}\qquad A_{\sqrt{2}/3}=\left(-\frac{\sqrt{2}}{3},\frac{\sqrt{2}}{3}\right). \] Notice that if \(0<i<j<1,\) then \(\{0\}\subset A_i \subset A_j \subset (-1,1).\) It follows that \[ \label{intexatwo} \bigcup_{i\in I} A_i =(-1,1) \qquad \text{and} \qquad \bigcap_{i\in I} A_i =\{0\} \] by Theorem 4.26.

Theorem 4.27 (Extended DeMorgan Laws) Let \(\{A_i \mid i\in I\}\) be a collection of sets indexed by \(I.\) Then

  1. \(\left(\bigcup_{i\in I} A_i\right)' =\bigcap_{i\in I} A_i'\)
  2. \(\left(\bigcap_{i\in I} A_i\right)' =\bigcup_{i\in I} A_i'\)

Proof. We prove(1) and leave (2) for the reader as Exercise 4.18. Let \(x\) be an arbitrary element in \(\left(\cup_{i\in I} A_i\right)'.\) Then \[\begin{align*} & x\in \left(\cup_{i\in I} A_i\right)' & \qquad & \\ & \quad \rightarrow [x\notin \cup_{i\in I} A_i] & & \text{by Definition of complement} \\ & \quad \rightarrow [\neg(x\in \cup_{i\in I} A_i)] & & \text{by Definition of $\notin$} \\ & \quad \rightarrow [\neg(\exists i\in I, x\in A_i)] & & \text{by Definition of $\cup$} \\ & \quad \rightarrow [\forall i\in I, x\notin A_i] & & \text{by logic rule} \\ & \quad \rightarrow [\forall i\in I, x\in A_i'] & & \text{by Definition of complement} \\ & \quad \rightarrow [x\in \cap_{i\in I} A_i'] & & \text{by Definition of $\cap$} \end{align*}\]

Thus \(x\in \cap_{i\in I} A_i'\) and consequently \[ \left(\cup_{i\in I} A_i\right)' \subseteq x\in \cap_{i\in I} A_i'. \] In a similar fashion (simply reverse the implications) one may prove the reverse containment. Therefore, we conclude \[ \left(\cup_{i\in I} A_i\right)' = \cap_{i\in I} A_i'. \] as desired.

Let \(I\) be a nonempty set, and suppose that for each element \(i\in I\) there is associated a set \(A_i\). We then call \(I\) an index set for the collection of sets \(\mathcal{A}=\{A_i \mid i\in I\}\).

Definition 4.14 Let \(I\) be an indexed set and suppose that \(\mathcal{A}=\{A_i\mid i\in I\}\) is a collection of sets. Then

  1. the union of the collection \(\mathcal{A}\) is defined to be the set \[ \bigcup_{i\in I} A_i =\{x\mid x\in A_i \text{ for some } i\in I\}, \]
  2. the intersection of the collection \(\mathcal{A}\) is defined to be the set \[ \bigcap_{i\in I} A_i =\{x\mid x\in A_i \text{ for each } i\in I\}. \]

Theorem 4.28 (Ascending and Descending Chains of Sets) Given the collection of sets \(\{A_i \mid i\in \mathbb{N}\}\) the following properties hold.

  1. If \(A_i \subseteq A_{i+1}\) for all \(i\in \mathbb{N}\), then \(\bigcap_{i=1}A_i=A_1\).
  2. If \(A_i \supseteq A_{i+1}\) for all \(i\in \mathbb{N}\), then \(\bigcup_{i=1}A_i=A_1\).

Proof. We prove (1) and leave (2) for the reader as Exercise 4.19.

Let \(T=\cap_{i=1}A_i=A_0\) and let \(x\) be an arbitrary element of \(T\). Then \(x\in A_i\) for each \(i\in \mathbb{N}\), and this certainly implies that \(x\in A_1\). Sp \(T\in A_1\).

Conversely, assume \(x\in A_1\). Since \(A_i \subseteq A_{i+1}\) for all \(i\in\mathbb{N}\), we have that \(A_1\subseteq A_i\) for every \(i\in \mathbb{N},\) and hence \(x\in T.\) This shows that \(A_1\subseteq T\); hence we conclude that \(T=A_1\).

4.8 Exercises

Exercise 4.1 Prove Theorem 4.11.

Exercise 4.2 Prove Theorem 4.12.

Exercise 4.3 Prove Theorem 4.13.

Exercise 4.4 Prove Theorem 4.18.

Exercise 4.5 Finish the proof of Theorem 4.14.

Exercise 4.6 Finish the proof of Theorem 4.15.

Exercise 4.7 Finish the proof of Theorem 4.16.

Exercise 4.8 Finish the proof of Theorem 4.17.

Exercise 4.9 Finish the proof of Theorem 4.19.

Exercise 4.10 Finish the proof of Theorem 4.20.

Exercise 4.11 Prove Theorem 4.21.

Exercise 4.12 Prove Theorem 4.22.

Exercise 4.13 Prove Theorem 4.23.

Exercise 4.14 Finish the proof of Theorem 4.24.

Exercise 4.15 Finish the proof of Theorem 4.25.

Exercise 4.16 Prove Lemma 4.1.

Exercise 4.17 Finish the proof of Theorem 4.26.

Exercise 4.18 Finish the proof of Theorem 4.27.

Exercise 4.19 Finish the proof of Theorem 4.28.

Exercise 4.20 Prove Theorem 4.4.

Exercise 4.21 Prove Theorem 4.5.