J. Munkres. Topology. (2013) Chapter 1: Set Theory and Logic. 1: Fundamental Concepts
Munkres uses some unusual notation in his book - in particular, he uses \(a \times b\) for the ordered pair \((a,b)\). I'm going to be using my own preferred notation throughout these notes, to make things consistent between books.
The book begins with a recap of naive set theory, going into quite some depth (up to the Well-Ordering Theorem). So let's begin at the beginning:
Basic Notation
We write \(a \in A\) iff \(A\) is a set and \(a\) is a member of \(A\), and \(a \notin A\) iff \(a\) is not a member of \(A\).
Two sets are equal iff they have exactly the same elements.
We say \(A\) is a subset of \(B\), or \(B\) includes \(A\), and write \(A \subseteq B\), iff every element of \(A\) is an element of \(B\). We say \(A\) is a proper subset of \(B\), or \(B\) properly includes \(A\), and write \(A \subsetneq B\), iff in addition \(A \neq B\).
We write \(\{a,b,c\}\) for the set whose elements are exactly \(a\), \(b\) and \(c\). We write \(\{x : P(x)\}\) or \(\{x \mid P(x)\}\) for the set whose elements are exactly those objects \(x\) such that \(P(x)\) is true.
The Union of Sets and the Meaning of "Or"
The union of sets \(A\) and \(B\) is the set \(A \cup B := \{ x \mid x \in A \text{ or } x \in B \}\), where "or" means inclusive or.
The Intersection of Sets, the Empty Set, and the Meaning of "If ... Then"
The intersection of sets \(A\) and \(B\) is the set \(A \cap B := \{x \mid x \in A \text{ and } x \in B\}\).
The empty set \(\emptyset\) is the set with no members.
Sets \(A\) and \(B\) are disjoint iff \(A \cap B = \emptyset\).
For any set \(A\), we have \(A \cup \emptyset = A\), \(A \cap \emptyset = \emptyset\), and \(\emptyset \subseteq A\) ("vacuously").
Contrapositive and Converse
The contrapositive of "If \(P\) then \(Q\)" is "If not \(Q\) then not \(P\)". A statement and its contrapositive are logically equivalent.
The converse of "If \(P\) then \(Q\)" is "If \(Q\) then \(P\)". Not every statement is logically equivalent to its converse.
We write \(P \Rightarrow Q\) for "If \(P\) then \(Q\)" and \(P \Leftrightarrow Q\) ("\(P\) iff \(Q\)") for "\(P \Rightarrow Q\) and \(Q \Rightarrow P\)".
Negation
The negation of a statement \(P\) is the statement "Not \(P\)".
The Difference of Two Sets
The difference of sets \(A\) and \(B\), or the complement of \(B\) relative to \(A\), is the set \(A - B := \{x \mid x \in A \text{ and } x \notin B \}\).
Rules of Set Theory
Distributive Laws:
\[ \begin{align} A \cap (B \cup C) & = (A \cap B) \cup (A \cap C) \\ A \cup (B \cap C) & = (A \cup B) \cap (A \cup C) \end{align} \]
De Morgan's Laws:
\[ \begin{align} A - (B \cup C) & = (A - B) \cap (A - C) \\ A - (B \cap C) & = (A - B) \cup (A - C) \end{align} \]
Collections of Sets
The power set of a set \(A\), written \(\mathcal{P} A\), is the set of all subsets of \(A\).
Arbitrary Unions and Intersections
If \(\mathcal{A}\) is a set of sets, then its union is the set \( \bigcup \mathcal{A} := \{ x \mid \exists A \in \mathcal{A}. x \in A \} \), and if \(\mathcal{A} \neq \emptyset\) then its intersection is the set \{ \bigcap \mathcal{A} := \{ x \mid \forall A \in \mathcal{A}. x \in A \} \).
Cartesian Products
Given sets \(A\) and \(B\), the Cartesian product \(A \times B\) is the set of all ordered pairs \((a,b)\) where \(a \in A\) and \(b \in B\).
Exercises
Exercise 1
Check the distributive laws for \(\cup\) and \(\cap\) and De Morgan's laws.
Solution
\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
For any object \(x\) we have \[ \begin{align} x \in A \cap (B \cup C) & \Leftrightarrow x \in A \text{ and } (x \in B \text{ or } x \in C) \\ & \Leftrightarrow (x \in A \text{ and } x \in B) \text{ or } (x \in A \text{ and } x \in C) \\ & \Leftrightarrow x \in (A \cap B) \cup (A \cap C) \end{align} \]
\(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
For any object \(x\) we have \[ \begin{align} x \in A \cup (B \cap C) & \Leftrightarrow x \in A \text{ or } (x \in B \text{ and } x \in C) \\ & \Leftrightarrow (x \in A \text{ or } x \in B) \text{ and } (x \in A \text{ or } x \in C) \\ & \Leftrightarrow x \in (A \cup B) \cap (A \cup C) \end{align} \]
\(A - (B \cup C) = (A - B) \cap (A - C)\)
For any object \(x\) we have \[ \begin{align} x \in A - (B \cup C) & \Leftrightarrow x \in A \text{ and it is not the case that } (x \in B \text{ or } x \in C) \\ & \Leftrightarrow x \in A \text{ and } x \notin B \text{ and } x \notin C \\ & \Leftrightarrow x \in (A - B) \cap (A - C) \end{align} \]
\(A - (B \cap C) = (A - B) \cup (A - C)\)
For any object \(x\) we have \[ \begin{align} x \in A - (B \cap C) & \Leftrightarrow x \in A \text{ and it is not the case that } (x \in B \text{ and } x \in C) \\ & \Leftrightarrow (x \in A \text{ and } x \notin B) \text{ or } (x \in A \text{ and } x \notin C) \\ & \Leftrightarrow x \in (A - B) \cup (A - C) \end{align} \]
Exercise 2
Determine which of the following statements are true for all sets \(A\), \(B\), \(C\), and \(D\). If a double implication fails, determine whether one or the other of the possible implications holds. If an equality fails, determine whether the statement becomes true if the “equals” symbol is replaced by one or the other of the inclusion symbols \(\subseteq\) or \(\supseteq\).
(a)
\(A \subseteq B \text{ and } A \subseteq C \Leftrightarrow A \subseteq B \cup C \)
Solution
The left-to-right implication holds: if \(A \subseteq B\) and \(A \subseteq C\) then every element of \(A\) is an element of both \(B\) and \(C\), hence certainly an element of \(B \cup C\).
The right-to-left implication does not hold. Counterexample: let \(A = \{0,1\}\), \(B = \{0\}\) and \(C = \{1\}\). Then \(A\) is a subset of \(B \cup C\) (in fact \(A = B \cup C\)) but \(A\) is not a subset of either \(B\) or \(C\).
(b)
\(A \subseteq B \text{ or } A \subseteq C \Leftrightarrow A \subseteq B \cup C \)
Solution
The left-to-right implication holds: if \(A \subseteq B\) then every element of \(A\) is an element of \(B\) and therefore an element of \(B \cup C\). Thus \(A \subseteq B \cup C\). Similarly, if \(A \subseteq C\) then \(A \subseteq B \cup C\).
The right-to-left implication does not hold. The same counterexample as for part (a) works here: let \(A = \{0,1\}\), \(B = \{0\}\) and \(C = \{1\}\). Then \(A\) is a subset of \(B \cup C\) (in fact \(A = B \cup C\)) but \(A\) is not a subset of either \(B\) or \(C\).
(c)
\(A \subseteq B \text{ and } A \subseteq C \Leftrightarrow A \subseteq B \cap C \)
Solution
The statement is true. We have \[ \begin{align} & A \subseteq B \text{ and } A \subseteq C \\ \Leftrightarrow & \text{every member of } A \text{ is a member of } B \text{ and every member of } A \text{ is a member of } C \\ \Leftrightarrow & \text{every member of } A \text{ is a member of } B \text{ and a member of } C \\ \Leftrightarrow & A \subseteq B \cap C \end{align} \]
(d)
\(A \subseteq B \text{ or } A \subseteq C \Leftrightarrow A \subseteq B \cap C \)
Solution
The right-to-left implication holds. From (c) we know that if \(A \subseteq B \cap C\) then \(A \subseteq B\) and \(A \subseteq C\), and so "\(A \subseteq B\) or \(A \subseteq C\)" is true.
The left-to-right implication does not hold. Counterexample: take \(A = \{0\}\), \(B = \{0\}\) and \(C = \emptyset\). Then \(A \subseteq B\) but \(A \nsubseteq B \cap C = \emptyset\).
(e)
\[A - (A - B) = B\]Solution
We have \(A - (A - B) \subseteq B\). For any object \(x\), if \(x \in A - (A - B)\), then \(x \in A\) and it is not the case that \((x \in A \text{ and } x \notin B)\), and so we must have \(x \in B\).
We do not have \(B \subseteq A - (A - B)\) in general. Counterexample: take \(A = \emptyset\) and \(B = \{0\}\). Then \(A - (A - B) = \emptyset\) and so \(B \nsubseteq A - (A - B)\).
(f)
\[ A - (B - A) = A - B \]Solution
We have \(A - B \subseteq A - (B - A)\). For any object \(x\), if \(x \in A - B\), then \(x \in A\) and \(x \notin B\), so certainly \(x \notin B - A\). Thus \(x \in A - (B - A)\).
We do not have \(A - (B - A) \subseteq A - B\) in general. Take \(A = \{0\}\) and \(B = \{0\}\). Then \(A - (B - A) = \{0\}\) but \(A - B = \emptyset\).
(g)
\[ A \cap (B - C) = (A \cap B) - (A \cap C) \]Solution
The statement is true. For any object \(x\), we have
\[ \begin{align} x \in A \cap (B - C) & \Leftrightarrow x \in A \text{ and } x \in B \text{ and } x \notin C \\ & \Leftrightarrow x \in A \text{ and } x \in B \text{ and it is not the case that } (x \in A \text{ and } x \in C) \\ & \Leftrightarrow x \in (A \cap B) - (A \cap C) \end{align} \](h)
\[ A \cup (B - C) = (A \cup B) - (A \cup C) \]Solution
We have \((A \cup B) - (A \cup C) \subseteq A \cup (B - C)\). Let \(x \in (A \cup B) - (A \cup C)\). If \(x \in A\) then of course \(x \in A \cup (B - C)\). If \(x \notin A\), then we have \(x \in B\) (since \(x \in A \cup B\)) and \(x \notin C\) (since \(x \notin A \cup C\)). Therefore \(x \in B - C\), and so \(x \in A \cup (B - C)\). Thus \(x \in A \cup (B - C)\) in either case.
We do not have \(A \cup (B - C) \subseteq (A \cup B) - (A \cup C)\) in general. Counterexample: let \(A = \{0\}), \(B = \emptyset\), \(C = \emptyset\). Then \(A \cup (B - C) = \{0\}\) and \((A \cup B) - (A \cup C) = \emptyset\).
(i)
\[ (A \cap B) \cup (A - B) = A \]Solution
The statement is true. For any object \(x\), we have
\[ \begin{align} x \in (A \cap B) \cup (A - B) & \Leftrightarrow (x \in A \text{ and } x \in B) \text{ or } (x \in A \text{ and } x \notin B) \\ & \Leftrightarrow x \in A \text{ and } (x \in B \text{ or } x \notin B) \\ & \Leftrightarrow x \in A \end{align} \](j)
\[ A \subseteq C \text{ and } B \subseteq D \Rightarrow A \times B \subseteq C \times D \]Solution
The statement is true. Assume \(A \subseteq C\) and \(B \subseteq D\). Given \((a,b) \in A \times B\), we have \(a \in C\) because \(A \subseteq C\) and \(b \in D\) because \(B \subseteq D\), hence \((a,b) \in C \times D\).
(k)
The converse of (j).
Solution
The converse of (j) is not true. Take \(A = C = D = \emptyset\) and \(B = \{0\}\). Then \(A \times B = C \times D = \emptyset\) but \(B \nsubseteq D\).
(l)
The converse of (j), assuming that \(A\) and \(B\) are nonempty.
Solution
Yes, if \(A \times B \subseteq C \times D\) and \(A\) and \(B\) are nonempty then \(A \subseteq C\) and \(B \subseteq D\).
Proof
Assume \(A \times B \subseteq C \times D\) and \(A\) and \(B\) are nonempty. Let \(x \in A\); we will prove \(x \in C\). Pick some element \(b \in B\). Then we have \((x,b) \in A \times B\) and so \((x,b) \in C \times D\). Therefore \(x \in C\) as required.
Thus \(A \subseteq C\). We prove \(B \subseteq D\) similarly. \(\Box\)
(m)
\[ (A \times B) \cup (C \times D) = (A \cup C) \times (B \cup D) \]Solution
We have \((A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)\). Let \((x,y) \in (A \times B) \cup (C \times D)\). Then either \((x,y) \in A \times B\) or \((x,y) \in C \times D\). In the first case, we have \(x \in A\) and \(y \in B\), hence \(x \in A \cup C\) and \(y \in B \cup D\). In the second case, we also have \(x \in A \cup C\) and \(y \in B \cup D\) similarly. So we have \((x,y) \in (A \cup C) \times (B \cup D)\) in either case.
We do not have \((A \cup C) \times (B \cup D) \subseteq (A \times B) \cup (C \times D)\) in general. Counterexample: let \(A = \{0\}\), \(B = \emptyset\), \(C = \emptyset\) and \(D = \{0\}\). Then \((A \cup C) \times (B \cup D) = \{(0,0)\}\) but \((A \times B) \cup (C \times D) = \emptyset\).
(n)
\[ (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) \]Solution
This statement is true. For any \((x,y)\), we have
\[ \begin{align} (x,y) \in (A \times B) \cap (C \times D) & \Leftrightarrow x \in A \text{ and } y \in B \text{ and } x \in C \text{ and } y \in D \\ & \Leftrightarrow (x,y) \in (A \cap C) \times (B \cap D) \end{align} \](o)
\[ A \times (B - C) = (A \times B) - (A \times C) \]Solution
The statement is true. For any \((x,y)\), we have
\[ \begin{align} (x,y) \in A \times (B - C) & \Leftrightarrow x \in A \text{ and } y \in B \text{ and } y \notin C \\ & \Leftrightarrow (x,y) \in (A \times B) - (A \times C) \end{align} \](p)
\[ (A - B) \times (C - D) = (A \times C - B \times C) - A \times D \]Solution
The statement is true. For any \((x,y)\), we have
\[ \begin{align} (x,y) \in (A-B) \times (C-D) & \Leftrightarrow x \in A \text{ and } x \notin B \text{ and } y \in C \text{ and } y \notin D \\ & \Leftrightarrow x \in A \text{ and } y \in C \text{ and it is not the case that } (x \in B \text{ and } y \in C) \\ & \text{ and it is not the case that } (x \in A \text{ and } y \in D) \\ & \Leftrightarrow (x,y) \in (A \times C - B \times C) - A \times D \end{align} \](q)
\[ (A \times B) - (C \times D) = (A - C) \times (B - D) \]Solution
We have \((A - C) \times (B - D) \subseteq (A \times B) - (C \times D)\). Let \((x,y) \in (A-C) \times (B - D)\). Then we have \(x \in A\), \(x \notin C\), \(y \in B\) and \(y \notin D\). Hence \((x,y) \in A \times B\) and \((x,y) \notin C \times D\), so \((x,y) \in (A \times B) - (C \times D)\) as required.
We do not have \((A \times B) - (C \times D) \subseteq (A - C) \times (B - D)\) in general. Counterexample: let \(A = B = C = \{0\}\) and \(D = \emptyset\). Then \((A \times B) - (C \times D) = \{(0,0)\}\) but \((A-C) \times (B-D) = \emptyset\).
Exercise 3
(a)
Write the contrapositive and converse of the following statement: "If \(x < 0\) then \(x^2 - x > 0 \)," and determine which (if any) of these three statements is true.
Solution
The contrapositive is "If \(x^2 - x \leq 0\) then \(x \geq 0\)." The converse is "If \(x^2 - x > 0\) then \(x < 0\)."
Assuming \(x\) ranges over the real numbers, the original statement is true. If \(x < 0\) then we have \(x^2 > 0\) and \(-x > 0\) hence \(x^2 - x > 0\).
The contrapositive is therefore true, because it is logically equivalent to the original statement.
The converse is false. Counterexample: let \(x = 2\). Then \(x^2 - x = 2 > 0\) but \(x \nless 0\).
(b)
Do the same for the statement "If \(x > 0\) then \(x^2 - x > 0\)."
Solution
The contrapositive is the statement: "If \(x^2 - x \leq 0\) then \(x \leq 0\)." The converse is the statement "If \(x^2 - x > 0\) then \(x > 0\)."
The original statement is false. Counterexample: let \(x = 1\). Then \(x > 0\) but \(x^2 - x = 0\).
The contrapositive is therefore false, because it is logically equivalent to the original statement.
The converse is false. Counterexample: let \(x = -1\). Then \(x^2 - x = 2 > 0\) but \(x \not> 0\).
Exercise 4
Let \(A\) and \(B\) be sets of real numbers. Write the negation of each of the following statements:
(a)
For every \(a \in A\), it is true that \(a^2 \in B\).
Solution
There exists \(a \in A\) such that \(a^2 \notin B\).
(b)
For at least one \(a \in A\), it is true that \(a^2 \in B\).
Solution
For every \(a \in A\), it is true that \(a^2 \notin B\).
(c)
For every \(a \in A\), it is true that \(a^2 \notin B\).
Solution
There exists \(a \in A\) such that \(a^2 \in B\).
(d)
For at least one \(a \notin A\), it is true that \(a^2 \in B\).
Solution
For every \(a \notin A\), it is true that \(a^2 \notin B\).
Exercise 5
Let \(\mathcal{A}\) be a nonempty collection of sets. Determine the truth of each of the following statements and of their converses:
(a)
\[ x \in \bigcup \mathcal{A} \Rightarrow x \in A \text{ for at least one } A \in \mathcal{A} \]Solution
The statement and its converse are both true; this is the definition of \( \bigcup \mathcal{A} \).
(b)
\[ x \in \bigcup \mathcal{A} \Rightarrow x \in A \text{ for every } A \in \mathcal{A} \]Solution
The statement is not true. Counterexample: let \(x = 0\) and \(\mathcal{A} = \{ \{0\}, \{1\} \}\). Then \(x \in \bigcup \mathcal{A} = \{0,1\}\) but there is some \(A \in \mathcal{A}\) with \(x \notin A\), namely \(A = \{1\}\).
The converse is true. Assume \(x \in A\) for every \(A \in \mathcal{A}\). Pick some \(A \in \mathcal{A}\) (remember \(\mathcal{A}\) is nonempty). Then \(x \in A \in \mathcal{A}\) so \(x \in \bigcup \mathcal{A}\).
(c)
\[ x \in \bigcap \mathcal{A} \Rightarrow x \in A \text{ for at least one } A \in \mathcal{A} \]Solution
The statement is true. Let \(x \in \bigcap \mathcal{A}\). Pick some \(A \in \mathcal{A}\) (remember \(\mathcal{A}\) is nonempty). Then \(x \in A\) as required.
The converse is not true. Counterexample: let \(x = 0\) and \(\mathcal{A} = \{ \{0\}, \{1\} \}\) Then \(x \in A\) for one \(A \in \mathcal{A}\), but \(x \notin \bigcap \mathcal{A} = \emptyset\).
(d)
\[ x \in \bigcap \mathcal{A} \Rightarrow x \in A \text{ for every } A \in \mathcal{A} \]Solution
The statement and its converse are both true; this is the definition of \(\bigcap \mathcal{A}\).
Exercise 6
Write the contrapositive of each of the statements of Exercise 5.
Solution
(a)
If \(x \notin A\) for every \(A \in \mathcal{A}\) then \(x \notin \bigcup \mathcal{A}\).
(b)
If \(x \notin A\) for some \(A \in \mathcal{A}\) then \(x \notin \bigcup \mathcal{A}\).
(c)
If \(x \notin A\) for every \(A \in \mathcal{A}\) then \(x \notin \bigcap \mathcal{A}\).
(d)
If \(x \notin A\) for some \(A \in \mathcal{A}\) then \(x \notin \bigcap \mathcal{A}\).
Exercise 7
Given sets \(A\), \(B\), and \(C\), express each of the following sets in terms of \(A\), \(B\), and \(C\), using the symbols \(\cup\), \(\cap\) and \(-\).
\[ \begin{align} D & = \{ x \mid x \in A \text{ and } (x \in B \text{ or } x \in C) \}, \\ E & = \{ x \mid (x \in A \text{ and } x \in B) \text{ or } x \in C \}, \\ F & = \{ x \mid x \in A \text{ and } (x \in B \Rightarrow x \in C) \}. \end{align} \]Solution
\[ \begin{align} D & = A \cap (B \cup C) \\ E & = (A \cap B) \cup C \\ F & = A - (B - C) \end{align} \]Exercise 8
If a set \(A\) has two elements, show that \(\mathcal{P} A\) has four elements. How many elements does \(\mathcal{P} A\) have if \(A\) has one element? Three elements? No elements? Why is \(\mathcal{P} A\) called the power set of \(A\)?
Solution
If \(A = \{a,b\}\) with \(a \neq b\) then \(\mathcal{P} A = \{ \emptyset, \{a\}, \{b\}, \{a,b\} \} \) and so \( \mathcal{P} A \) has four elements.
Similarly, if \(A\) has one element then \(\mathcal{P} A\) has two elements. If \(A\) has three elements then \(\mathcal{P} A\) has 8 elements. If \(A\) has no elements then \(\mathcal{P} A\) has one element.
A power set probably gets its name because its size is 2 to the power \(n\), where \(n\) is the size of \(A\). (I'm fairly sure this is the answer Munkres was expecting. The name "potenzmenge" was chosen by Zermelo in 1908 and he did not say why he chose that word, but \(2^n\) is called a "potenzfunktion" in German.)
Exercise 9
Formulate and prove De Morgan's laws for arbitrary unions and intersections.
Solution
For any set \(A\) and nonempty set of sets \(\mathcal{B}\) we have \(A - \bigcup \mathcal{B} = \bigcap \{ A - B \mid B \in \mathcal{B} \}\).
Proof
For any object \(x\) we have
\[ \begin{align} x \in A - \bigcup \mathcal{B} & \Leftrightarrow x \in A \text{ and it is not the case that there exists } B \in \mathcal{B} \text{ such that } x \in B \\ & \Leftrightarrow \text{for every } B \in \mathcal{B}, \text{ we have } x \in A \text{ and } x \notin B \\ & \Leftrightarrow x \in \bigcap \{ A - B \mid B \in \mathcal{B} \} & \Box \end{align} \]For any set \(A\) and nonempty set of sets \(\mathcal{B}\) we have \(A - \bigcap \mathcal{B} = \bigcup \{ A - B \mid B \in \mathcal{B} \}\).
Proof
For any object \(x\) we have
\[ \begin{align} x \in A - \bigcap \mathcal{B} & \Leftrightarrow x \in A \text{ and it is not the case that for all } B \in \mathcal{B} \text{ we have } x \in B \\ & \Leftrightarrow \text{there exists } B \in \mathcal{B} \text{ such that } x \in A \text{ and } x \notin B \\ & \Leftrightarrow x \in \bigcup \{ A - B : B \in \mathcal{B} \} & \Box \end{align} \]Exercise 10
Let \(\mathbb{R}\) denote the set of real numbers. For each of the following subsets of \(\mathbb{R} \times \mathbb{R}\), determine whether it is equal to the Cartesian product of two subsets of \(\mathbb{R}\).
(a)
\[ \{(x,y) \mid x \text{ is an integer} \} \]Solution
This is equal to \( \mathbb{Z} \times \mathbb{R} \).
(b)
\[ \{(x,y) \mid 0 < y \leq 1 \} \]Solution
This is equal to \( \mathbb{R} \times \{ y \mid 0 < y \leq 1 \} \).
(c)
[ \{ (x,y) \mid y > x \} \]Solution
This is not equal to the Cartesian product of two subsets of \(\mathbb{R}\).
(d)
\[ \{ (x,y) \mid x \text{ is not an integer and } y \text{ is an integer} \} \]Solution
This is equal to \( (\mathbb{R} - \mathbb{Z}) \times \mathbb{Z} \).
(e)
\[ \{ (x,y) \mid x^2 + y^2 = 1 \} \]Solution
This is not equal to the Cartesian product of two subsets of \(\mathbb{R}\).
Comments
Post a Comment