Skip to main content

Exercises Exercises

1.

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of a set \(X\text{.}\) Express each of the following sets in mathematical notation using the symbols \(\cup\text{,}\) \(\cap\text{,}\) and \(\setminus\text{.}\)

(a)

The elements of \(X\) that belong to \(A\) and \(B\text{,}\) but not \(C\text{.}\)

(b)

The elements of \(X\) that belong to \(C\) and either \(A\) or \(B\text{.}\)

(c)

The elements of \(X\) that belong to \(A\) but not to both \(B\) and \(C\text{.}\)

(d)

The elements of \(X\) that belong to none of the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{.}\)

(e)

The elements of \(X\) that fail to belong to at least two of the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{.}\)

(f)

The elements of \(X\) that fail to belong to at most one of the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{.}\)

2.

Let \(X \subset Y \subset Z\text{.}\) Prove or disprove.

(a)

\(C_Y(X) \subset C_Z(X)\text{.}\)

(b)

\(Z \setminus (Y \setminus X) = X \cup (Z \setminus Y)\text{.}\)

3.

Let \(A\) and \(B\) be subsets of a universal set \(U\text{.}\) Prove the associative and distributive laws. That is, prove each of the following.

(a)

\((A \cap B) \cap C = A \cap (B \cap C)\)

(b)

\((A \cup B) \cup C = A \cup (B \cup C)\)

(c)

\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) \item\(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)

4.

Prove DeMorgan’s Laws. That is, let \(\{A_{\alpha}\}\) be a collection of sets indexed by a set \(I\) in some universal set \(U\text{.}\) Prove that

(a)

\(\displaystyle \left(\bigcup_{\alpha \in I} A_{\alpha}\right)^c = \bigcap_{\alpha \in I} A_{\alpha}^c\)

(b)

\(\displaystyle \left(\bigcap_{\alpha \in I} A_{\alpha}\right)^c = \bigcup_{\alpha \in I} A_{\alpha}^c\)

5.

What familiar set is \(\emptyset \times A\) for any set \(A\text{?}\) Explain.

6.

If \(A\) is a set, the power set of \(A\text{,}\) denoted \(2^A\) is the collection of all subsets of \(A\text{.}\)

(a)

List the elements of \(\ds 2^{\{1,2\}}\text{.}\)

(b)

If \(A\) is a set with three elements, how many elements are in \(2^A\text{?}\)

(c)

If \(A\) is a set with \(n\) elements, make a conjecture about the number of elements in \(2^A\text{.}\) Prove your conjecture?

7.

If \(A\) is a set, the power set of \(A\text{,}\) denoted \(2^A\) is the collection of all subsets of \(A\text{.}\) (See Exercise 6.) Critique each of the following statements. Doe the statement make sense or not? If not, explain why and then correct the statement to something that is true (and non-trivial).

(a)

If \(A\) is a set, then \(A \in 2^A\text{.}\)

(b)

If \(A\) is a set, then \(A \subset 2^A\text{.}\)

(c)

If \(A\) is a set, then \(\{A\} \subset 2^A\text{.}\)

(d)

If \(A\) is a set, then \(\emptyset \in 2^A\text{.}\)

(e)

If \(A\) is a set, then \(\emptyset \subset 2^A\text{.}\)

(f)

If \(A\) and \(B\) are sets and \(A \subseteq B\text{,}\) then \(2^A \subseteq 2^B\text{.}\)

8.

Let \(A\) and \(B\) be sets, both of which have at least two distinct members. Prove that there is a subset \(W \subset A \times B\) that is not the Cartesian product of a subset of \(A\) with a subset of \(B\text{.}\) [Thus, not every subset of a Cartesian product is the Cartesian product of a pair of subsets.]

9.

Let \(I\) be the set of real numbers that are greater than \(0\text{.}\) For each \(x \in I\text{,}\) let \(A_x\) be the open interval \((0,x)\text{.}\) Prove that \(\bigcap_{x \in I} A_x = \emptyset\text{,}\) \(\bigcup_{x \in I} A_x = I\text{.}\) For each \(x \in I\text{,}\) let \(B_x\) be the closed interval \([0,x]\text{.}\) Prove that \(\bigcap_{x \in I} B_x = \{0\}\text{,}\) \(\bigcup_{x \in I} B_x = I \cup \{0\}\text{.}\)

10.

For each of the following, answer true if the statement is always true. If the statement is only sometimes true or never true, answer false and provide a concrete example to illustrate that the statement is false. If a statement is true, explain why. As an example of a true statement, consider the statement
Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets such that \(A \cap B = A \cap C\) and \(A \cap B \neq \emptyset\text{.}\)
Then \(B \cap C \neq \emptyset\text{.}\) We can justify the truth of this statement with a short argument. Since \(A \cap B \neq \emptyset\text{,}\) there is an element \(x \in A \cap B\text{.}\) Then \(x \in B\text{.}\) Since \(A \cap B = A \cap C\text{,}\) we also must have \(x \in A \cap C\text{,}\) which implies that \(x \in C\text{.}\) Thus, \(x \in B \cap C\) and \(B \cap C \neq \emptyset\text{.}\) As an example of a false statement, consider the statement
Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets such that \(A \cap B = A \cap C\text{.}\)
Then \(B = C\text{.}\) We can show that this statement is false by providing a counterexample. For example, let \(A = \{0,1\}\text{,}\) \(B=\{1\}\text{,}\) and \(C = \{1,2\}\text{.}\) Then \(A \cap B = \{1\} = A \cap C\text{,}\) but \(B \neq C\text{.}\)

(a)

If \(A\text{,}\) \(B\text{,}\) and \(C\) are sets and \(A \subseteq B\) and \(A \subseteq C\text{,}\) then \(A \subseteq (B \cap C)\text{.}\)

(b)

If \(A\text{,}\) \(B\text{,}\) and \(C\) are sets and \(A \subseteq C\) and \(B \subseteq C\text{,}\) then \((A \cup B) \subseteq C\text{.}\)

(c)

If \(A\) and \(B\) are subsets of a set \(X\) and \(A \subseteq B\text{,}\) then \((X \setminus A) \subseteq (X \setminus B)\text{.}\)

(d)

If \(A\) and \(B\) are subsets of a set \(X\) and \(A \subseteq B\text{,}\) then \((X \setminus B) \subseteq (X \setminus A)\text{.}\)

(e)

If \(A\) and \(B\) are sets, then \((A \cup B) \setminus B = A\text{.}\)

(f)

If \(A\) and \(B\) are sets, then \(A \setminus (A \setminus B) = B\text{.}\)

(g)

If \(A\text{,}\) \(B\text{,}\) and \(C\) are sets, then \(A \cap (B \setminus C) = (A \cap B) \setminus (A \cap C)\text{.}\)

(h)

If \(A\) and \(C\) are subsets of a set \(X\text{,}\) then \((A \setminus C) = A \cap (X \setminus C)\text{.}\)

(i)

There are no elements of the set \(\{\emptyset\}\text{.}\)

(j)

There are two distinct objects that belong to the set \(\{\emptyset, \{\emptyset\}\}\text{.}\)