##### Definition4.1

A *set* is a collection of objects called *elements*.

The theory of sets is a language that is well-suited to describing and explaining all types of mathematical structures. Instead of starting with axioms of set theory and deducing from them all of the useful properties of sets, we will provide some set-theoretic concepts used throughout the notes and advanced mathematics. Most mathematicians can do their work without going all the way back to the underlying axioms of set theory and that is what we will do here.

A *set* is a collection of objects called *elements*.

We use capital letters, \(A, B, C, \dots\) to denote sets and lower-case letters \(a,b,c, \dots\) to denote elements of the sets. If \(a\) is an element of the set \(A\), we denote it by \(a \in A\). If \(b\) is not an element of the set \(A\), we denote it by \(b \notin A\). In this notes, we are mainly concerned with sets whose elements are mathematical objects such as numbers, functions, etc. Here are some sets that you are familiar with:

- \(\mathbb{Z}\): the set of all integers.
- \(\mathbb{Q}\): the set of all rational numbers.
- \(\mathbb{R}\): the set of all real numbers.

There are two standard ways to describe a set:

- The
*extensional method*simply lists out all the elements of the set. For example \(S = \{0, 2, 4, 6, 8, 10\}\). - The
*intensional method*describes a set by listing the common properties of the elements of the set. For example, \begin{equation*}S = \{n \in \mathbb{Z} \; | \; n \; \textrm{is even }, 0 \leq n \leq 10\}.\end{equation*} By putting "\(\in \mathbb{Z}\)" before the vertical bar, we know that we only concern with integers in this set (and not chairs, cars, etc.) This is called the*universe*. We read the first brace as "the set of all" and the vertical bar as "such that". So the expression \begin{equation*}S = \{n \in \mathbb{Z} \; | \; n \; \textrm{is even}, 0 \leq n \leq 10\}\end{equation*} is read as the set of all integer \(n\) such that \(n\) is even which is greater than or equal to \(0\) and less than or equal to \(10\). Note that this is the same set as \(S\) in the example in the extensional method. They are both the set of all even integers between \(0\) and \(10\). The general syntax of the intensional method is \begin{equation*}\{\textrm{expression} \in \textrm{universe} \; | \; \textrm{rule}\}.\end{equation*}

Two sets are *equal* if they contain exactly the same elements.

For example, the set \(\{0,2\}\) is equal to the set \(\{2,0\}\). Note that the order we describe the elements in each case are different but that does not prevent these two sets from having exactly the same elements. Order is irrelevant when we determine if two sets are equal. Also the set \(\{0,2,2\}\) is equal to the set \(\{0,2\}\). Even though the element \(2\) has been repeated twice in the first set, it is still the case that the two sets have the same elements.

Consider the set \(T = \{n \in \mathbb{Z} \; | \; n \; \textrm{is even}, -8 \lt n \leq 8\}\). Answer the following questions:

- Fill in the blanks: \(4 \underline{\hspace{10mm}} T\) because \(\underline{\hspace{15mm}}\).
- Fill in the blanks: \(-8 \underline{\hspace{10mm}} T\) because \(\underline{\hspace{15mm}}\).
- Use the extensional method to describe \(T\).
- Is the set \(\{\ell \in \mathbb{Z} \; | \; \ell \; \textrm{is even}, -8 \lt \ell \leq 8\}\) the same as \(T\)?
- Is the set \(\{2m \in \mathbb{Z}\; | \; m \in \mathbb{Z}, -4 \lt m \leq 4\}\) the same as \(T\)?

Use the extensional method to describe the following sets:

- \(\{3x+1 \; | \; x \in \mathbb{Z}\}\).
- \(\{x \in \mathbb{Z} \; | \; |x| \lt 5\}\).
- \(\{x \in \mathbb{R} \; | \; x^3+5x^2=-6x\}\).
- \(\{2a+4b \; | \; a, b \in \mathbb{Z}\}\).
- \(\{3a+4b \; | \; a,b\in \mathbb{Z}\}\).

Use the intensional method to describe the following sets:

- \(\{2,4,8,16,32,64,\dots\}\).
- \(\{1,9,25,49,81,\dots\}\).
- \(\{\dots,-\frac{3\pi}{2}, -\pi, -\frac{\pi}{2}, 0, \frac{\pi}{2}, \pi, \frac{3\pi}{2}, \dots\}\).
- \(\{\dots,-8,-3,2,7,12,17,22,\dots\}\).
- \(\{1,3,6,10,15,21,28,\dots\}\).

Can you use the intensional method to describe the following set\begin{equation*}S = \{\pi, \text{Manchester United}, \text{China}, a^2+b^2=c^2\}?\end{equation*}

The set that contains no elements is called the *empty set*, denoted by \(\emptyset\).

If we think of a set as a box containing some stuff, then the empty set is a box with nothing in it.

True or false: \(\{\emptyset \} = \emptyset\). Why or why not? Explain your answer.

Let \(A\) and \(B\) be two sets. We say that *\(A\) is a subset of \(B\)* provided that every element of \(A\) is an element of \(B\). We denote it by \(A \subset B\).

Fill in the blanks:

- If \(A\) is a subset of \(B\), then we know that \begin{equation*}\underline{\hspace{3mm}} \; x \in \underline{\hspace{5mm}}, \text{we have} \; \; \underline{\hspace{5mm}} \; \in \; \underline{\hspace{5mm}}.\end{equation*}
- If \(A\) is not a subset of \(B\), then we know that \begin{equation*}\underline{\hspace{3mm}} \; x \in \underline{\hspace{5mm}}, \text{we have} \; \; \underline{\hspace{5mm}} \; \not\in \; \underline{\hspace{5mm}}.\end{equation*}

Let \(A\) and \(B\) be two sets. If \(A\) is a subset of \(B\) and \(A\) and \(B\) are not equal, we say that *\(A\) is a proper subset of \(B\)*. We denote it by \(A \subsetneq B\).

Consider the set \(S = \{1, \mathbb{Z}, \{1\}, -1, \{1,-1\}, \{-1,\{1\}\}\)

- Is \(\mathbb{Z}\) an element of \(S\) or a subset of \(S\) or both?
- Give three different elements of \(S\).
- Give three different subsets of \(S\).
- Is it possible to give an example that is the answer to the preceding two questions? If so, how many can you give?
- How many elements are there in \(S\)?

Describe a general strategy for proving that \(A \subset B\). Use your strategy to fill in the blanks.

Let \(A, B, C\) be three sets. If \(A \subset B\) and \(B \subset C\), show that \(A \subset C\).

For any set \(S\), show that \(\emptyset \subset S\) and \(S \subset S\).

Let \(A\) and \(B\) be two sets. Recall that \(A\) and \(B\) are equal provided that they have exactly the same elements. As a result, we may say that \(A = B\) if and only if \(A \subset B\) and \(B \subset A\). Here is what the general structure for proof of \(A = B\) looks like.

Prove that \(X = Y\) where \(X\) is the set of odd numbers and \(Y = \{2n+1 \; | \; n \in \mathbb{Z}\}\).

We can use set operations to build new sets from old sets.

Let \(A\) and \(B\) be two sets of some universal set \(U\). *The union of \(A\) and \(B\)*, denoted by \(A \cup B\), is the set that contains all elements in \(A\) and all elements in \(B\). \begin{equation*} A \cup B = \{ x \in U\; | \; x \in A \; \; \textrm{or} \; \; x \in B\}.\end{equation*}

*The intersection of \(A\) and \(B\)*, denoted by \(A \cap B\), is the set that contains elements that are both in \(A\) and in \(B\).\begin{equation*}A \cap B = \{x \in U \; | \; x \in A \; \; \textrm{and} \; \; x \in B\}.\end{equation*} If \(A \cap B = \emptyset\), then we say that \(A\) and \(B\) are *disjoint*.

*The complement of \(A\) in \(U\)*, denoted by \(A^C\), is the set that contains all elements in \(U\) but not in \(A\).\begin{equation*}A^C = \{x \in U \; | \; x \notin A\}.\end{equation*}

Can you see how \(\cup\) is related to \(\lor\), how \(\cap\) is related to \(\land\), and how \({\cdot}^C\) is related to \(\sim\)?

Suppose that \(U = \{n \in \mathbb{Z} \; | \; 1 \leq n \leq 10\}\). Let \(X = \{1,2,3,4,5\}\), \(Y = \{1,3,5\}\), and \(Z = \{2,4,6,8\}\). Find each of the following:

- \(X \cap Z\).
- \(X \cap Y\).
- \(X \cup Z\).
- \(X \cup Y\).
- \(Y \cap Z\).
- \(Y^C\).
- \(Z^C\).
- \(X \cap Y^C\).
- \(Y \cap X^C\).
- \((X \cup Y)^C\).
- \(X^C \cap Y^C\).

We can use the so-called *Venn diagrams* to visually describe the constructions. The shaded region of each diagram shows the visual description of the set described below the diagram.

Venn diagram can be very useful when you try to understand a set-theoretical statement or even get the essence of why the statement might be true. But a Venn diagram is *not* a substitute for a rigorous proof. You can use Venn diagrams to guide your thinking but simply drawing a Venn diagram does not constitute a proof.

Let \(A, B\) and \(C\) be three sets. Prove or disprove: \(A \subset (B \cap C)\) if and only if \(A \subset B\) and \(A \subset C\).

Let \(A, B\) and \(C\) be three sets. Prove or disprove: \(A \subset (B \cup C)\) if and only if \(A \subset B\) or \(A \subset C\).

Let \(A, B\) and \(C\) be three sets in the same universal set \(U\). Show that \begin{equation*}A \cap (B \cup C) = (A \cap B) \cup (A \cap C).\end{equation*}

(Can you give a similar version in logic and convince yourself that it is true as well?)

Let \(A\) and \(B\) be two sets in the same universal set \(U\). Show that \(A \subset B\) if and only if \(B^C \subset A^C\).

Let \(A\) and \(B\) be two sets in the same universal set \(U\).

- Show that \(A \subset A \cup B\).
- Show that \(A \subset B\) if and only if \(A \cup B = B\).

Prove the DeMorgan's Law of sets. Let \(A\) and \(B\) be two sets in the same universal set \(U\).

- \((A \cup B)^C = A^C \cap B^C.\)
- \((A \cap B)^C = A^C \cup B^C.\)

(Can you see the resemblance of the DeMorgan's Law of sets and the DeMorgan's Law of logic in Task 2.36?)

Let \(S\) be a set. The *power set of \(S\)*, denoted by \(P(S)\), is the set of all subsets of \(S\).

Recall the set \begin{equation*}S = \{1, \mathbb{Z}, \{1\}, -1, \{1,-1\}, \{-1,\{1\}\}\}\end{equation*} studied in Task 4.11, fill in the table with T (true) or F (false).

\(\in S\) | \(\subset S\) | \(\in P(S)\) | \(\subset P(S)\) | |

\(1\) | ||||

\(\{1\}\) | ||||

\(\mathbb{Z}\) | ||||

\(-1,\{1\}\) | ||||

\(\{-1,1\}\) | ||||

\(\{-1,\{1\}\}\) |

- Find \(P(\{1\}), P(\{1,2\})\) and \(P(\{1,2,3\})\).
- For any set \(S\) with \(n\) elements where \(n\) is a positive integer, guess how many elements \(P(S)\) will have.
- Does your guess work for \(\{a,b,c,d\}\) and \(\emptyset\)? (If not, revise your guess.)

For any two sets \(A\) and \(B\), show that \(P(A \cap B) = P(A) \cap P(B).\)

- For any two sets \(A\) and \(B\), show that \(P(A) \cup P(B) \subset P(A \cup B)\).
- Is it true that \(P(A \cup B) \subset P(A) \cup P(B)\) for any \(A\) and \(B\)? If so, prove it; if not provide a counter-example.
- Is it ever possible that \(P(A \cup B) \subset P(A) \cup P(B)\)? In other words, can you find two sets \(A\) and \(B\) such that \(P(A \cup B) \subset P(A) \cup P(B)\)?

Let \(A\) and \(B\) be two sets. the *product of \(A\) and \(B\)* is \begin{equation*}A \times B = \{(a,b) \; | \; a \in A, b\in B\}.\end{equation*} We read \(A \times B\) as "\(A\) cross \(B\)".

Let \(A = \{1,2\}\) and \(B = \{2,3,4\}\). Find \(A \times A\) and \(B \times B\). Find \(A \times B\) and \(B \times A\). Is \(A \times B = B \times A\)? Explain your answer.

If \(A\), \(B\), \(C\) and \(D\) are four sets, prove or disprove \begin{equation*}(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D).\end{equation*}

If \(A\), \(B\), \(C\) and \(D\) are four sets, prove or disprove \begin{equation*}(A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D).\end{equation*}

The definition of a set has a flaw. The fact that we can describe a collection of things does not guarantee that the object we have described is a set! For instance, we may be able to think about the collection of all possible sets, but this collection cannot itself be considered a set without leading to paradox. First let us consider a riddle.

In the town of Seville, the (male) barber shaves all the men, and only the men, who do not shave themselves. Let \(S\) be the set of all men in the town who do not shave themselves. Who shaves the barber? Is the barber an element of \(S\)? Is he not an element of \(S\)?

The riddle has good answer. It is simply a colloquial rendition of a set-theoretic paradox universally called Russell's paradox after the British mathematician Bertrand Russell, who formulated it. Before we present Russell's paradox, we need a definition.

A set \(S\) is said to be *ordinary* if \(S \notin S\).

For example, if \(S\) is the set of all chairs, then \(S \notin S\) because \(S\) itself is not *a* chair. So the set of all chairs is ordinary. Here is an example of a non-ordinary set. If \(T\) is the collection of all abstract ideas, then \(T\) itself is an abstract idea. Thus \(T \in T\).

Let us consider \(\mathcal{S} = \{ S \; | \; S \; \textrm{is an ordinary set}\}\), that is, \(\mathcal{S}\) is the collection of all possible ordinary sets. Is \(\mathcal{S} \in \mathcal{S}\)? Is \(\mathcal{S} \notin \mathcal{S}\)? What should we say about \(\mathcal{S}\)? Is \(\mathcal{S}\) a set?

Eventually, two German mathematicians Ernst Zermelo and Abraham Fraenkel got this settled. Basically, they came up with a list of axioms for set theory that rules out the possibility of Russell's paradox or any paradoxes of the same nature. This is called the *Zermelo-Fraenkel set theory* and it is the most common foundation of mathematics.