This post presents a collection of over 90 set theory exercises with detailed, pedagogically-driven solutions, designed to reinforce the theoretical skills covered while studying this foundational branch of mathematics.
The exercises accompany the theoretical post “What Are Sets?“, the key ideas of which are summarized below.
Objective
This collection gives you systematic practice in:
- Determining sets from logical and algebraic conditions.
- Distinguishing membership (\( \in \)) from inclusion (\( \subset \)) in specific contexts.
- Evaluating the truth value of quantified statements about sets.
- Simplifying algebraic expressions involving set operations.
- Applying the inclusion-exclusion principle to cardinality problems.
- Proving equalities and inclusions formally via double inclusion and logical equivalences.
- Integrating all of the above in problems of increasing complexity.
Document structure
The exercises are arranged around the theoretical summary below, progressing from direct computation to formal proof. The post includes a quick-reference summary of the key concepts needed to work through the exercises.
Theoretical summary
Set theory is the foundational language of mathematics. All of algebra, calculus, probability, and statistics are built on top of it. What follows is a quick-reference summary of the ideas you’ll need throughout these exercises.
Primitive concepts and notation
A set is any well-defined collection of objects. There are three primitive ideas: the set itself, the element, and the membership relation (\( \in \)).
| Object | Notation |
|---|---|
| Sets | Capital letters: \( A, B, C \) |
| Elements | Lowercase letters: \( a, b, c \) |
| Membership | \( x \in A \) — “\( x \) belongs to \( A \)” |
| Non-membership | \( x \notin A \) — “\( x \) does not belong to \( A \)” |
A set can be described by extension (listing its elements: \( A = \{1, 2, 3\} \)) or by comprehension (via a property: \( A = \{x \in \mathbb{Z} \mid P(x)\} \)).
Connection with quantifiers: Set-builder notation draws directly on the quantifiers studied in the previous chapter. Inclusion \( A \subset B \) is defined using \( \forall \), and its negation uses \( \exists \).
Special sets
| Set | Notation | Description |
|---|---|---|
| Empty set | \( \emptyset \) or \( \{\} \) | No elements. \( \emptyset \subset A \) for every \( A \) |
| Universal set | \( U \) | Contains every element under consideration |
| Singleton | \( \{a\} \) | Exactly one element |
Relations between sets
| Relation | Formal definition |
|---|---|
| Inclusion \( A \subset B \) | \( \forall x: x \in A \implies x \in B \) |
| Equality \( A = B \) | \( A \subset B \) and \( B \subset A \) (double inclusion) |
| Disjoint | \( A \cap B = \emptyset \) |
Critical distinction: \( a \in A \) (membership — \( a \) is an element of \( A \)) is completely different from \( \{a\} \subset A \) (inclusion — the singleton \( \{a\} \) is a subset of \( A \)). Confusing \( \in \) with \( \subset \) is the most common mistake in set theory exercises.
Set operations
Each operation corresponds to a logical connective — carried over directly from propositional logic:
| Operation | Symbol | Definition | Connective |
|---|---|---|---|
| Union | \( A \cup B \) | \( \{x \mid x \in A \vee x \in B\} \) | \( \vee \) |
| Intersection | \( A \cap B \) | \( \{x \mid x \in A \wedge x \in B\} \) | \( \wedge \) |
| Difference | \( A – B \) | \( \{x \mid x \in A \wedge x \notin B\} \) | \( \wedge \neg \) |
| Complement | \( A’ \) | \( U – A = \{x \mid x \notin A\} \) | \( \neg \) |
| Sym. difference | \( A \triangle B \) | \( (A – B) \cup (B – A) \) | XOR \( (\oplus) \) |
Key properties:
| Law | Statement |
|---|---|
| De Morgan 1 | \( (A \cup B)’ = A’ \cap B’ \) |
| De Morgan 2 | \( (A \cap B)’ = A’ \cup B’ \) |
| Difference | \( A – B = A \cap B’ \) |
| Distributive | \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) |
| Absorption | \( A \cup (A \cap B) = A \) |
| Double complement | \( (A’)’ = A \) |
Power set
The power set \( \mathcal{P}(A) \) is the set of all subsets of \( A \):
\[ \mathcal{P}(A) = \{X \mid X \subset A\} \]
If \( n(A) = n \), then \( n[\mathcal{P}(A)] = 2^n \).
Essential properties:
- \( X \in \mathcal{P}(A) \iff X \subset A \)
- \( \emptyset \in \mathcal{P}(A) \) and \( A \in \mathcal{P}(A) \) for every \( A \)
- \( A \subset B \implies \mathcal{P}(A) \subset \mathcal{P}(B) \)
- \( \mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B) \)
Cardinality and the inclusion-exclusion principle
The cardinality \( n(A) \) counts the distinct elements of \( A \). For finite sets:
- For two sets: \[ n(A \cup B) = n(A) + n(B) – n(A \cap B) \]
- For three sets: \[ n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C) \]
The intersection terms are subtracted because when individual cardinalities are added together, shared elements get counted more than once.
Solved exercises
Exercise 1
Let \( A = \{1, 2, 3, 4, 5, 6\} \) and \( B = \{0, 1, 4, 6, 7, 8, 9\} \). Let \( m \) be the number of nonempty subsets of \( A \) that are disjoint from \( B \), and \( n \) the number of nonempty subsets of \( B \) that are disjoint from \( A \). Find \( m + n \).
Solution:
Recall that two sets are disjoint when they share no elements — that is, their intersection is empty.
Step 1 — Identify the common elements. Let’s see which elements \( A \) and \( B \) share:
\[ A \cap B = \{1, 4, 6\} \]
These three elements (1, 4, and 6) appear in both sets. Any subset of \( A \) containing any of them will not be disjoint from \( B \), since that element also belongs to \( B \).
Step 2 — Find \( m \). For a subset of \( A \) to be disjoint from \( B \), it can only contain elements of \( A \) that are not in \( B \). Those elements are:
\[ A – B = \{2, 3, 5\} \]
So we can only use 2, 3, and 5 to build subsets of \( A \) that are disjoint from \( B \). A 3-element set has \( 2^3 = 8 \) subsets in total, but since we need nonempty ones, we subtract 1:
\[ m = 2^3 – 1 = 7 \]
We can verify by listing them: \( \{2\},; \{3\},; \{5\},; \{2,3\},; \{2,5\},; \{3,5\},; \{2,3,5\} \). There are exactly 7. ✓
Step 3 — Find \( n \). By the same reasoning, for a subset of \( B \) to be disjoint from \( A \), it can only contain elements of \( B \) that are not in \( A \):
\[ B – A = \{0, 7, 8, 9\} \]
This gives us 4 elements, so the number of nonempty subsets is:
\[ n = 2^4 – 1 = 15 \]
Result:
\[ m + n = 7 + 15 = 22 \]
Exercise 2
Let \( A = \{3, \{2, 8\}, 5\} \). Determine the truth value of each statement:
- (a) \( \exists X \in \mathcal{P}(A) \mid 2 \in X \)
- (b) \( \forall X \in \mathcal{P}(A) \mid \{3\} \subset X \)
- (c) \( \exists X \in \mathcal{P}(A) \mid \{2, 8\} \subset X \)
Solution:
Before evaluating the statements, let’s carefully identify the elements of \( A \). This set has exactly three elements:
- The number \( 3 \)
- The set \( \{2, 8\} \) (treated as a single element of \( A \))
- The number \( 5 \)
It’s essential not to confuse: the numbers 2 and 8 are not elements of \( A \); they sit inside one of \( A \)’s elements, namely the set \( \{2, 8\} \).
Now let’s compute the power set \( \mathcal{P}(A) \), which has \( 2^3 = 8 \) elements:
\[ \mathcal{P}(A) = \left\{ \emptyset, \{3\}, \{\{2,8\}\}, \{5\}, \{3, \{2,8\}\}, \{3, 5\}, \{\{2,8\}, 5\}, A \right\} \]
(a) \( \exists X \in \mathcal{P}(A) \mid 2 \in X \)
We’re looking for some \( X \in \mathcal{P}(A) \) that contains the number 2 as an element. The only things that can appear inside subsets of \( A \) are its own elements: \( 3 \), \( \{2, 8\} \), and \( 5 \). The number 2 is none of those.
For instance, \( \{\{2,8\}\} \in \mathcal{P}(A) \) contains the set \( \{2,8\} \), but not the number 2 by itself.
The statement is false. ✗
(b) \( \forall X \in \mathcal{P}(A) \mid \{3\} \subset X \)
This asks whether \( \{3\} \subset X \) holds for every \( X \in \mathcal{P}(A) \). To disprove a “for all”, one counterexample is enough:
- \( X = \{5\} \in \mathcal{P}(A) \), but \( 3 \notin \{5\} \), so \( \{3\} \not\subset \{5\} \). ✗
Since at least one \( X \) fails the condition, the statement is false. ✗
(c) \( \exists X \in \mathcal{P}(A) \mid \{2, 8\} \subset X \)
For \( \{2, 8\} \subset X \) we would need \( 2 \in X \) and \( 8 \in X \). But as shown in (a), the number 2 never appears in any \( X \in \mathcal{P}(A) \) — and the same holds for 8. So \( \{2, 8\} \) cannot be a subset of any element of \( \mathcal{P}(A) \).
Clarification: The set \( \{2, 8\} \) is an element of \( A \), not a subset. The fact that \( \{2, 8\} \in A \) does not imply \( \{2, 8\} \subset A \). Membership (\( \in \)) and inclusion (\( \subset \)) are entirely different relations: membership links an element to a set, while inclusion compares the elements of two sets.
The statement is false. ✗
Exercise 3
Let \( A = \{\{a\}, b, \{b\}\} \), where \( n(X) \) denotes the number of elements of a set \( X \). Determine the truth value of each statement:
- (a) \( \{\{b\}\} \subset \mathcal{P}(A) \)
- (b) \( \{a, b\} \in \mathcal{P}(A) \)
- (c) \( n[\mathcal{P}(A)] = 8 \)
- (d) \( X \subset A \to \mathcal{P}(X) \subset \mathcal{P}(A) \)
Solution:
Let’s identify the elements of \( A \) first. This set has exactly three:
- The set \( \{a\} \)
- The element \( b \)
- The set \( \{b\} \)
Note that \( b \) and \( \{b\} \) are different things: one is an element, the other is a set that contains that element. Also, \( a \) is not an element of \( A \) — what belongs to \( A \) is the set \( \{a\} \).
The power set \( \mathcal{P}(A) \) has \( 2^3 = 8 \) subsets:
\[ \mathcal{P}(A) = \left\{ \emptyset, \{\{a\}\}, \{b\}, \{\{b\}\}, \{\{a\}, b\}, \{\{a\}, \{b\}\}, \{b, \{b\}\}, A \right\} \]
(a) \( \{\{b\}\} \subset \mathcal{P}(A) \)
For \( \{\{b\}\} \subset \mathcal{P}(A) \), every element of \( \{\{b\}\} \) must belong to \( \mathcal{P}(A) \). Its only element is \( \{b\} \).
Is \( \{b\} \in \mathcal{P}(A) \)? Yes — since \( b \in A \), the singleton \( \{b\} \) is a subset of \( A \), and every subset of \( A \) belongs to \( \mathcal{P}(A) \).
The statement is true. ✓
(b) \( \{a, b\} \in \mathcal{P}(A) \)
For \( \{a, b\} \in \mathcal{P}(A) \), the set \( \{a, b\} \) must be a subset of \( A \), which requires both of its elements to belong to \( A \):
- \( b \in A \) ✓
- \( a \in A \)? No. What belongs to \( A \) is the set \( \{a\} \), not the element \( a \) alone. So \( a \notin A \). ✗
Since \( a \notin A \), the set \( \{a, b\} \) is not a subset of \( A \) and therefore does not belong to \( \mathcal{P}(A) \).
The statement is false. ✗
(c) \( n[\mathcal{P}(A)] = 8 \)
Since \( A \) has 3 elements, its power set has \( 2^3 = 8 \) subsets (listed above). So \( n[\mathcal{P}(A)] = 8 \).
The statement is true. ✓
(d) \( X \subset A \to \mathcal{P}(X) \subset \mathcal{P}(A) \)
This is a general property of power sets. The argument goes:
- If \( X \subset A \), then every element of \( X \) also belongs to \( A \).
- Let \( Y \in \mathcal{P}(X) \), i.e., \( Y \subset X \).
- Since \( Y \subset X \) and \( X \subset A \), by transitivity of inclusion: \( Y \subset A \).
- Therefore \( Y \in \mathcal{P}(A) \).
- Since every element of \( \mathcal{P}(X) \) also belongs to \( \mathcal{P}(A) \), we conclude \( \mathcal{P}(X) \subset \mathcal{P}(A) \).
Let’s verify with a concrete example: take \( X = \{b, \{b\}\} \subset A \).
- \( \mathcal{P}(X) = \{ \emptyset, \{b\}, \{\{b\}\}, \{b, \{b\}\} \} \)
- Each of these subsets does indeed appear in \( \mathcal{P}(A) \). ✓
The statement is true. ✓
Exercise 4
Let \( \{a, c\} \subset \mathbb{R} \), \( c \neq 0 \), \( A = \{a + cx \mid x \in \mathbb{R}\} \), \( b \in A \), and \( B = \{b + cy \mid y \in \mathbb{R}\} \). Prove that \( A = B \).
Proof:
To show two sets are equal, we use double inclusion: if \( A \subset B \) and \( B \subset A \), then \( A = B \).
Part I — \( A \subset B \):
We must show that every element of \( A \) also belongs to \( B \).
(1) Since \( b \in A \), by the definition of \( A \), there exists \( x_1 \in \mathbb{R} \) such that:
\[ b = a + cx_1 \implies a = b – cx_1 \]
(2) Let \( k \in A \) be arbitrary. Then there exists \( x \in \mathbb{R} \) such that \( k = a + cx \).
(3) Substituting the expression for \( a \) from (1):
\[ k = (b – cx_1) + cx = b + c(x – x_1) \]
(4) Since \( x, x_1 \in \mathbb{R} \), we have \( (x – x_1) \in \mathbb{R} \). Setting \( y = x – x_1 \):
\[ k = b + cy, \quad y \in \mathbb{R} \]
which is exactly the form of an element of \( B \). Therefore \( k \in B \).
(5) Since \( k \) was an arbitrary element of \( A \), we conclude \( A \subset B \). ✓
Part II — \( B \subset A \):
Now we must show that every element of \( B \) also belongs to \( A \).
(1) Let \( k \in B \) be arbitrary. Then there exists \( y \in \mathbb{R} \) such that \( k = b + cy \).
(2) Since \( b \in A \), there exists \( x_1 \in \mathbb{R} \) such that \( b = a + cx_1 \). Substituting:
\[ k = (a + cx_1) + cy = a + c(x_1 + y) \]
(3) Since \( x_1, y \in \mathbb{R} \), we have \( (x_1 + y) \in \mathbb{R} \). Setting \( x = x_1 + y \):
\[ k = a + cx, \quad x \in \mathbb{R} \]
which is exactly the form of an element of \( A \). Therefore \( k \in A \).
(4) Since \( k \) was an arbitrary element of \( B \), we conclude \( B \subset A \). ✓
Conclusion: Since \( A \subset B \) and \( B \subset A \), we have \( A = B \). ∎
Note: Intuitively, \( A \) and \( B \) describe the same family of real numbers, just written from different starting points (\( a \) and \( b \) respectively). Since \( b \) is already in \( A \), the shift \( c \cdot (\text{real}) \) sweeps through exactly the same values in both cases.
Exercise 5
Let \( A = \{\mathcal{P}(\{a\}), \mathcal{P}(\emptyset)\} \). Find:
- (a) \( \mathcal{P}(A) \)
- (b) Analyze the truth or falsity of:
- \( b_1: [\emptyset \notin \mathcal{P}(A) \wedge \emptyset \subset \mathcal{P}(A)] \to \{\{\emptyset\}\} \subset \mathcal{P}(A) \)
- \( b_2: \{\emptyset, \{a\}\} \in \mathcal{P}(A) \to \{\emptyset\} \in \mathcal{P}(A) \)
- (c) Build the simplified logical expression for \( b_1 \to b_2 \).
Solution:
(a) Let’s start by computing the power sets that define \( A \):
- \( \mathcal{P}(\{a\}) = \{\emptyset, \{a\}\} \) — the subsets of \( \{a\} \) are the empty set and \( \{a\} \) itself.
- \( \mathcal{P}(\emptyset) = \{\emptyset\} \) — the only subset of \( \emptyset \) is \( \emptyset \) itself.
Substituting into the definition of \( A \):
\[ A = \{\{\emptyset, \{a\}\}, \{\emptyset\}\} \]
The set \( A \) has two elements:
- Element 1: \( \{\emptyset, \{a\}\} \)
- Element 2: \( \{\emptyset\} \)
Now, \( \mathcal{P}(A) \) has \( 2^2 = 4 \) subsets:
\[ \mathcal{P}(A) = \{\emptyset, \{\{\emptyset, \{a\}\}\}, \{\{\emptyset\}\}, A \} \]
That is: the empty set, the singleton containing the first element, the singleton containing the second element, and \( A \) itself.
(b) Let’s evaluate the atomic propositions:
Proposition \( b_1 \): \( [\emptyset \notin \mathcal{P}(A) \wedge \emptyset \subset \mathcal{P}(A)] \to \{\{\emptyset\}\} \subset \mathcal{P}(A) \)
Evaluating each part:
- \( \emptyset \in \mathcal{P}(A) \): Yes — the empty set is a subset of every set, so \( \emptyset \in \mathcal{P}(A) \). True.
- \( \emptyset \notin \mathcal{P}(A) \): The negation of the above. False.
- \( \emptyset \subset \mathcal{P}(A) \): Yes — the empty set is a subset of every set. True.
- \( \{\{\emptyset\}\} \subset \mathcal{P}(A) \): We need \( \{\emptyset\} \in \mathcal{P}(A) \). The elements of \( \mathcal{P}(A) \) are \( \emptyset \), \( \{\{\emptyset, \{a\}\}\} \), \( \{\{\emptyset\}\} \), and \( A \). The set \( \{\emptyset\} \) is none of them — note that \( \{\emptyset\} \neq \{\{\emptyset\}\} \), they have different nesting levels. So \( \{\emptyset\} \notin \mathcal{P}(A) \). False.
Evaluating \( b_1 \):
\[ b_1 = (\text{F} \wedge \text{T}) \to \text{F} = \text{F} \to \text{F} = \text{T} \]
The proposition \( b_1 \) is true (an implication with a false antecedent is always true). ✓
Proposition \( b_2 \): \( \{\emptyset, \{a\}\} \in \mathcal{P}(A) \to \{\emptyset\} \in \mathcal{P}(A) \)
- \( \{\emptyset, \{a\}\} \in \mathcal{P}(A) \): This asks whether \( \{\emptyset, \{a\}\} \) is a subset of \( A \), which would require \( \emptyset \in A \) and \( \{a\} \in A \). The elements of \( A \) are \( \{\emptyset, \{a\}\} \) and \( \{\emptyset\} \) — neither \( \emptyset \) nor \( \{a\} \) is an element of \( A \) (they are elements of the elements of \( A \)). So \( \{\emptyset, \{a\}\} \not\subset A \). False.
- \( \{\emptyset\} \in \mathcal{P}(A) \): We already saw that \( \{\emptyset\} \) is not a subset of \( A \) (because \( \emptyset \notin A \)). False.
Evaluating \( b_2 \):
\[ b_2 = \text{F} \to \text{F} = \text{T} \]
The proposition \( b_2 \) is true. ✓
(c) Assign variables to each atomic proposition:
| Variable | Proposition | Value |
|---|---|---|
| \( p \) | \( \emptyset \in \mathcal{P}(A) \) | T |
| \( q \) | \( \emptyset \subset \mathcal{P}(A) \) | T |
| \( r \) | \( \{\{\emptyset\}\} \subset \mathcal{P}(A) \) | F |
| \( s \) | \( \{\emptyset, \{a\}\} \in \mathcal{P}(A) \) | F |
| \( t \) | \( \{\emptyset\} \in \mathcal{P}(A) \) | F |
Expressing \( b_1 \) and \( b_2 \) in terms of these variables:
\[ b_1: (\neg p \wedge q) \to r \equiv (p \vee \neg q) \vee r \]
\[ b_2: s \to t \equiv \neg s \vee t \]
Then:
\[ b_1 \to b_2 \equiv [(p \vee \neg q) \vee r] \to [\neg s \vee t] \]
Applying the equivalence \( X \to Y \equiv \neg X \vee Y \):
\[ \equiv \neg[(p \vee \neg q) \vee r] \vee (\neg s \vee t) \]
Applying De Morgan to the first term:
\[ \equiv [(\neg p \wedge q) \wedge \neg r] \vee \neg s \vee t \]
Verification: \( [(\text{F} \wedge \text{T}) \wedge \text{T}] \vee \text{T} \vee \text{F} = \text{F} \vee \text{T} \vee \text{F} = \text{T} \) ✓
Exercise 6
Let \( U = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} \), \( A = \{2, 4, 6, 8\} \), \( B = \{1, 3, 5, 7, 9\} \), and \( C = \{3, 4, 5\} \). Find a subset \( X \) of \( U \) such that \( X \subset C \), \( X \not\subset A \), and \( X \not\subset B \). How many solutions are there?
Solution:
The three conditions \( X \) must satisfy are:
- \( X \subset C \): \( X \) must be a subset of \( C = \{3, 4, 5\} \).
- \( X \not\subset A \): \( X \) must not be a subset of \( A = \{2, 4, 6, 8\} \).
- \( X \not\subset B \): \( X \) must not be a subset of \( B = \{1, 3, 5, 7, 9\} \).
Step 1 — Unpack conditions 2 and 3.
Let’s see which elements of \( C \) belong to \( A \) and which to \( B \):
- \( C \cap A = \{4\} \) — only 4 is in both.
- \( C \cap B = \{3, 5\} \) — both 3 and 5 are in both.
- \( C – A = \{3, 5\} \) — elements of \( C \) not in \( A \).
- \( C – B = \{4\} \) — elements of \( C \) not in \( B \).
For \( X \not\subset A \), the set \( X \) must contain at least one element that is not in \( A \). Since \( X \subset C \), that element must come from \( C – A = \{3, 5\} \). In other words, \( X \) must contain 3, 5, or both.
For \( X \not\subset B \), the set \( X \) must contain at least one element that is not in \( B \). That element must come from \( C – B = \{4\} \). In other words, \( X \) must contain 4.
Step 2 — Summarize the constraints.
\( X \) must be a subset of \( \{3, 4, 5\} \) that:
- Contains 4 (to avoid being a subset of \( B \)).
- Contains at least one of \( \{3, 5\} \) (to avoid being a subset of \( A \)).
Step 3 — List all solutions.
The subsets of \( C \) containing 4 are: \( \{4\} \), \( \{3, 4\} \), \( \{4, 5\} \), \( \{3, 4, 5\} \).
We discard \( \{4\} \) because it contains no element from \( \{3, 5\} \) and is therefore a subset of \( A \).
The solutions are:
| \( X \) | \( X \subset C \) | \( X \not\subset A \) | \( X \not\subset B \) |
|---|---|---|---|
| \( \{3, 4\} \) | ✓ | ✓ (\( 3 \notin A \)) | ✓ (\( 4 \notin B \)) |
| \( \{4, 5\} \) | ✓ | ✓ (\( 5 \notin A \)) | ✓ (\( 4 \notin B \)) |
| \( \{3, 4, 5\} \) | ✓ | ✓ (\( 3, 5 \notin A \)) | ✓ (\( 4 \notin B \)) |
There are 3 solutions.
Exercise 7
Let \( A = \{a, \{a\}, \{\emptyset\}, \emptyset\} \). Determine the truth value of each statement:
- (1) \( \{a\} \in A \wedge \{a\} \subset A \)
- (2) \( \{a\} \subset A \wedge \{\{a\}\} \subset A \)
- (3) \( \{\emptyset\} \subset A \wedge \{\{\emptyset\}\} \subset A \)
- (4) \( \emptyset \subset A \wedge \emptyset \in A \)
- (5) \( \{a, \emptyset\} \subset A \wedge \{\{a\}, \{\emptyset\}\} \subset A \)
Solution:
Let’s carefully identify the four elements of \( A \):
| Element | Description |
|---|---|
| \( a \) | An individual element |
| \( \{a\} \) | The set containing \( a \) |
| \( \{\emptyset\} \) | The set containing the empty set |
| \( \emptyset \) | The empty set |
Keep in mind the key distinction:
- Membership \( (\in) \): \( x \in A \) means \( x \) is one of the four elements listed above.
- Inclusion \( (\subset) \): \( S \subset A \) means every element of \( S \) belongs to \( A \).
(1) \( \{a\} \in A \wedge \{a\} \subset A \)
- \( \{a\} \in A \): Is \( \{a\} \) one of the elements of \( A \)? Yes, it’s the second one. T ✓
- \( \{a\} \subset A \): Does every element of \( \{a\} \) belong to \( A \)? Its only element is \( a \), and \( a \in A \). T ✓
\( \text{T} \wedge \text{T} = \) True ✓
Notice that \( \{a\} \) satisfies both relations with \( A \): it is an element of \( A \) and also a subset of \( A \). This is possible because both \( \{a\} \) and its member \( a \) belong to \( A \).
(2) \( \{a\} \subset A \wedge \{\{a\}\} \subset A \)
- \( \{a\} \subset A \): \( a \in A \). T ✓
- \( \{\{a\}\} \subset A \): Its only element is \( \{a\} \), and \( \{a\} \in A \). T ✓
\( \text{T} \wedge \text{T} = \) True ✓
(3) \( \{\emptyset\} \subset A \wedge \{\{\emptyset\}\} \subset A \)
- \( \{\emptyset\} \subset A \): Its only element is \( \emptyset \). Is \( \emptyset \in A \)? Yes, it’s the fourth element. T ✓
- \( \{\{\emptyset\}\} \subset A \): Its only element is \( \{\emptyset\} \). Is \( \{\emptyset\} \in A \)? Yes, it’s the third element. T ✓
\( \text{T} \wedge \text{T} = \) True ✓
Same pattern as (2): \( \{\emptyset\} \) and \( \emptyset \) are distinct objects, but both belong to \( A \).
(4) \( \emptyset \subset A \wedge \emptyset \in A \)
- \( \emptyset \subset A \): The empty set is a subset of every set. T ✓
- \( \emptyset \in A \): \( \emptyset \) is explicitly listed as the fourth element of \( A \). T ✓
\( \text{T} \wedge \text{T} = \) True ✓
Again, \( \emptyset \) satisfies both relations: it is a subset of \( A \) (universally) and an element of \( A \) (by construction).
(5) \( \{a, \emptyset\} \subset A \wedge \{\{a\}, \{\emptyset\}\} \subset A \)
- \( \{a, \emptyset\} \subset A \): We need \( a \in A \) and \( \emptyset \in A \). Both are elements of \( A \). T ✓
- \( \{\{a\}, \{\emptyset\}\} \subset A \): We need \( \{a\} \in A \) and \( \{\emptyset\} \in A \). Both are elements of \( A \). T ✓
\( \text{T} \wedge \text{T} = \) True ✓
Summary: All five statements are true. This is possible because \( A \) was built with elements at two levels: both \( a \) and \( \emptyset \), and their “wrapped” versions \( \{a\} \) and \( \{\emptyset\} \), all belong to \( A \).
Exercise 8
Let \( A = \{7n + 2 \mid n \in \mathbb{Z}\} \), \( B = \{7n – 26 \mid n \in \mathbb{Z}\} \), \( C = \{4n + 1 \mid n \in \mathbb{Z}\} \), and \( D = \{2n + 1 \mid n \in \mathbb{Z}\} \). Analyze and justify:
- (a) \( A = B \)
- (b) \( C = D \)
Solution:
(a) \( A = B \)
Let’s list some elements to see what they look like:
- \( A = \{\dots, -12, -5, 2, 9, 16, 23, \dots\} \) (substituting \( n = \dots, -2, -1, 0, 1, 2, 3, \dots \))
- \( B = \{\dots, -40, -33, -26, -19, -12, -5, 2, 9, \dots\} \) (substituting \( n = \dots, -2, -1, 0, 1, 2, 3, 4, 5, \dots \))
Both appear to generate the same numbers. Let’s prove it by double inclusion.
Part I — \( A \subset B \): Let \( k \in A \), so \( k = 7n + 2 \) for some \( n \in \mathbb{Z} \).
We want to write \( k \) in the form \( 7m – 26 \):
\[ 7n + 2 = 7m – 26 \implies 7m = 7n + 28 \implies m = n + 4 \]
Since \( n \in \mathbb{Z} \), we have \( m = n + 4 \in \mathbb{Z} \). Therefore \( k = 7m – 26 \) with \( m \in \mathbb{Z} \), so \( k \in B \). ✓
Part II — \( B \subset A \): Let \( k \in B \), so \( k = 7m – 26 \) for some \( m \in \mathbb{Z} \).
We want to write \( k \) in the form \( 7n + 2 \):
\[ 7m – 26 = 7n + 2 \implies 7n = 7m – 28 \implies n = m – 4 \]
Since \( m \in \mathbb{Z} \), we have \( n = m – 4 \in \mathbb{Z} \). Therefore \( k = 7n + 2 \) with \( n \in \mathbb{Z} \), so \( k \in A \). ✓
Conclusion: \( A = B \). ∎
Note: Both sets consist of the integers that leave a remainder of 2 when divided by 7. The difference between the formulas \( 7n + 2 \) and \( 7n – 26 \) is just a shift of 28, which is a multiple of 7 — so they produce the same values.
(b) \( C = D \)?
Let’s list some elements:
- \( C = \{\dots, -7, -3, 1, 5, 9, 13, 17, \dots\} \) (steps of 4)
- \( D = \{\dots, -5, -3, -1, 1, 3, 5, 7, 9, \dots\} \) (steps of 2 — all odd integers)
\( C \) skips by 4 while \( D \) includes every odd integer. Let’s analyze:
\( C \subset D \): Let \( k \in C \), so \( k = 4n + 1 \) for some \( n \in \mathbb{Z} \).
Rewriting: \( k = 4n + 1 = 2(2n) + 1 \). Setting \( m = 2n \), we get \( k = 2m + 1 \) with \( m \in \mathbb{Z} \), so \( k \in D \). ✓
\( D \subset C \)? Let \( k \in D \), so \( k = 2m + 1 \) for some \( m \in \mathbb{Z} \).
We want to write \( k \) in the form \( 4n + 1 \):
\[ 2m + 1 = 4n + 1 \implies 2m = 4n \implies n = \frac{m}{2} \]
But \( n \) must be an integer, and \( \frac{m}{2} \in \mathbb{Z} \) only when \( m \) is even. If \( m \) is odd, \( n \) is not an integer.
Counterexample: \( 3 \in D \) (with \( m = 1 \): \( 2(1) + 1 = 3 \)), but for \( 3 \in C \) we would need \( 4n + 1 = 3 \implies n = \frac{1}{2} \notin \mathbb{Z} \). So \( 3 \notin C \). ✗
Conclusion: \( C \neq D \). We have \( C \subsetneq D \) — \( C \) is a proper subset of \( D \) — but \( D \not\subset C \). In other words, every element of \( C \) is odd, but not every odd integer belongs to \( C \).
Exercise 9
Let \( A = \{\{0, 1\}, \{2, 4, 8\}, \emptyset\} \), \( B = \{0, 1, 4, 8\} \), and \( C = \{\emptyset, \{\emptyset\}, \{0\}, \{1\}, 2, \{4\}, \{8\}\} \). State whether each claim is true or false:
(a) \( \emptyset \subset A \) ; \( \emptyset \in A \) ; \( \{C\} \subset B \) ; \( B \subset A \) ; \( \{1\} \in A \)
(b) \( \{1, 8\} \in B \) ; \( \{\{\emptyset\}, \{1\}\} \subset C \) ; \( \{0, 1\} \subset C \) ; \( \{\emptyset, \{\emptyset\}, \{1\}\} \subset C \)
(c) \( \{\emptyset\} \subset B \) ; \( \{\emptyset, 1, 2, \{8\}\} \subset B \) ; \( \emptyset = \{\emptyset\} \) ; \( \{0, 1\} \in A \) ; \( \{0, 1\} \subset A \)
(d) \( \{0, 1\} \subset B \) ; \( \{0, 1\} \in C \) ; \( \{1\} \subset \{0, 1\} \) ; \( \{1\} \in \{\{1\}\} \)
Solution:
Let’s identify the elements of each set:
| Set | Elements |
|---|---|
| \( A \) | \( \{0, 1\} \), \( \{2, 4, 8\} \), \( \emptyset \) — 3 elements (all are sets) |
| \( B \) | \( 0 \), \( 1 \), \( 4 \), \( 8 \) — 4 elements (all are numbers) |
| \( C \) | \( \emptyset \), \( \{\emptyset\} \), \( \{0\} \), \( \{1\} \), \( 2 \), \( \{4\} \), \( \{8\} \) — 7 elements (a mix of sets and one number) |
(a)
- \( \emptyset \subset A \): The empty set is a subset of every set. T ✓
- \( \emptyset \in A \): \( \emptyset \) is listed as the third element of \( A \). T ✓
- \( \{C\} \subset B \): This requires \( C \in B \). The elements of \( B \) are numbers (0, 1, 4, 8), and \( C \) is a 7-element set — not one of them. F ✗
- \( B \subset A \): This requires every element of \( B \) to belong to \( A \). But is \( 0 \in A \)? No — the elements of \( A \) are sets (\( \{0,1\} \), \( \{2,4,8\} \), \( \emptyset \)), not individual numbers. F ✗
- \( \{1\} \in A \): The elements of \( A \) are \( \{0, 1\} \), \( \{2, 4, 8\} \), and \( \emptyset \). The set \( \{1\} \) is none of them. F ✗
(b)
- \( \{1, 8\} \in B \): The elements of \( B \) are individual numbers, not sets. \( \{1, 8\} \) is not an element of \( B \). F ✗
- \( \{\{\emptyset\}, \{1\}\} \subset C \): We need \( \{\emptyset\} \in C \) and \( \{1\} \in C \). Both are listed as elements of \( C \). T ✓
- \( \{0, 1\} \subset C \): We need \( 0 \in C \) and \( 1 \in C \). What appears in \( C \) are \( \{0\} \) and \( \{1\} \), not the numbers 0 and 1 themselves (recall: \( 0 \neq \{0\} \)). F ✗
- \( \{\emptyset, \{\emptyset\}, \{1\}\} \subset C \): We need \( \emptyset \in C \), \( \{\emptyset\} \in C \), and \( \{1\} \in C \). All three are listed as elements of \( C \). T ✓
(c)
- \( \{\emptyset\} \subset B \): We need \( \emptyset \in B \). The elements of \( B \) are 0, 1, 4, 8 — \( \emptyset \) is none of them. F ✗
- \( \{\emptyset, 1, 2, \{8\}\} \subset B \): We need all four elements in \( B \). Already \( \emptyset \notin B \), \( \{8\} \notin B \) (\( B \) contains the number 8, not the set \( \{8\} \)), and \( 2 \notin B \). F ✗
- \( \emptyset = \{\emptyset\} \): No. \( \emptyset \) has no elements, while \( \{\emptyset\} \) has exactly one (namely \( \emptyset \) itself). They are distinct objects. F ✗
- \( \{0, 1\} \in A \): \( \{0, 1\} \) is the first element of \( A \). T ✓
- \( \{0, 1\} \subset A \): We would need \( 0 \in A \) and \( 1 \in A \). The elements of \( A \) are sets, not individual numbers. F ✗
Notice the contrast: \( \{0, 1\} \in A \) is true but \( \{0, 1\} \subset A \) is false. Being an element of a set and being a subset of it are completely different relations.
(d)
- \( \{0, 1\} \subset B \): We need \( 0 \in B \) and \( 1 \in B \). Both are elements of \( B \). T ✓
- \( \{0, 1\} \in C \): The elements of \( C \) are \( \emptyset \), \( \{\emptyset\} \), \( \{0\} \), \( \{1\} \), 2, \( \{4\} \), and \( \{8\} \). The set \( \{0, 1\} \) is none of them. F ✗
- \( \{1\} \subset \{0, 1\} \): We need \( 1 \in \{0, 1\} \). Yes. T ✓
- \( \{1\} \in \{\{1\}\} \): The only element of \( \{\{1\}\} \) is \( \{1\} \). So \( \{1\} \in \{\{1\}\} \). T ✓
Summary:
| Statement 1 | Statement 2 | Statement 3 | Statement 4 | Statement 5 | |
|---|---|---|---|---|---|
| (a) | T | T | F | F | F |
| (b) | F | T | F | T | — |
| (c) | F | F | F | T | F |
| (d) | T | F | T | T | — |
Exercise 10
Let \( A = \{2, \{3, 4\}, \{5\}, 6\} \). Determine the truth value of each statement:
- (a) \( \exists X \in \mathcal{P}(A) \mid 4 \in X \)
- (b) \( \exists X \in \mathcal{P}(A) \mid \{6\} \subset X \)
- (c) \( \exists X \in \mathcal{P}(A) \mid \{5\} \subset X \)
- (d) \( \exists X \in \mathcal{P}(A) \mid \{3, 4\} \subset X \)
Solution:
Let’s identify the four elements of \( A \):
| Element | Type |
|---|---|
| \( 2 \) | Number |
| \( \{3, 4\} \) | Set (a single element of \( A \)) |
| \( \{5\} \) | Set (a single element of \( A \)) |
| \( 6 \) | Number |
The subsets of \( A \) — that is, elements of \( \mathcal{P}(A) \) — can only contain combinations of these four elements. The numbers 3, 4, and 5 individually are not elements of \( A \); they sit inside elements of \( A \).
(a) \( \exists X \in \mathcal{P}(A) \mid 4 \in X \)
We’re looking for a subset \( X \) of \( A \) containing the number 4. But 4 is not an element of \( A \) — it sits inside the set \( \{3, 4\} \), which is an element of \( A \). Since no subset of \( A \) can contain something that doesn’t belong to \( A \), no such \( X \) exists.
The statement is false. ✗
(b) \( \exists X \in \mathcal{P}(A) \mid \{6\} \subset X \)
For \( \{6\} \subset X \), we need \( 6 \in X \). Since \( 6 \in A \), any subset of \( A \) containing 6 works. For example, \( X = \{2, 6\} \in \mathcal{P}(A) \) satisfies \( \{6\} \subset \{2, 6\} \). ✓
The statement is true. ✓
(c) \( \exists X \in \mathcal{P}(A) \mid \{5\} \subset X \)
For \( \{5\} \subset X \), we would need \( 5 \in X \). But the number 5 is not an element of \( A \) — what belongs to \( A \) is the set \( \{5\} \).
Don’t confuse \( \{5\} \in A \) (true — the set \( \{5\} \) is an element of \( A \)) with \( 5 \in A \) (false — the number 5 is not).
Since no subset of \( A \) contains the number 5, the set \( \{5\} \) cannot be a subset of any \( X \in \mathcal{P}(A) \).
The statement is false. ✗
(d) \( \exists X \in \mathcal{P}(A) \mid \{3, 4\} \subset X \)
For \( \{3, 4\} \subset X \), we would need \( 3 \in X \) and \( 4 \in X \). But neither 3 nor 4 is an element of \( A \) — they sit inside the set \( \{3, 4\} \), which is an element of \( A \).
Same situation as (c): \( \{3, 4\} \in A \) (true — it’s an element) but \( \{3, 4\} \subset A \) (false — because \( 3 \notin A \) and \( 4 \notin A \)).
The statement is false. ✗
Summary:
| Part | Result | Key reason |
|---|---|---|
| (a) | F | \( 4 \notin A \) — it’s inside \( \{3,4\} \) |
| (b) | T | \( 6 \in A \) — take \( X = \{2, 6\} \) |
| (c) | F | \( 5 \notin A \) — what belongs is \( \{5\} \) |
| (d) | F | \( 3 \notin A \) and \( 4 \notin A \) — \( \{3,4\} \) belongs as a block |
Exercise 11
Let the universal set be \( U = \{\emptyset, 2, \frac{2}{3}, 5\} \) with subsets:
- \( A = \{x \in U \mid x \text{ is even} \vee x \text{ is prime}\} \)
- \( B = \{x \in U \mid x \neq \emptyset \wedge x \text{ is not an integer}\} \)
- \( C = \{x \in U \mid x \text{ is a number} \vee x = \emptyset\} \)
Find: (a) \( B’ – A \), (b) \( (A \cup B) – (B \cap C) \), (c) \( (C – B) \cap A \).
Solution:
Step 1 — Determine each set by checking every element.
For \( A \): \( x \) is even or \( x \) is prime.
| \( x \) | Even? | Prime? | \( p \vee q \) | \( x \in A \)? |
|---|---|---|---|---|
| \( \emptyset \) | No (not a number) | No | F | No |
| \( 2 \) | Yes | Yes | T | Yes ✓ |
| \( \frac{2}{3} \) | No | No | F | No |
| \( 5 \) | No | Yes | T | Yes ✓ |
\[ A = \{2, 5\} \]
For \( B \): \( x \neq \emptyset \) and \( x \) is not an integer.
| \( x \) | \( x \neq \emptyset \) | Not an integer? | \( p \wedge q \) | \( x \in B \)? |
|---|---|---|---|---|
| \( \emptyset \) | No | — | F | No |
| \( 2 \) | Yes | No (it’s an integer) | F | No |
| \( \frac{2}{3} \) | Yes | Yes | T | Yes ✓ |
| \( 5 \) | Yes | No (it’s an integer) | F | No |
\[ B = \left\{\frac{2}{3}\right\} \]
For \( C \): \( x \) is a number or \( x = \emptyset \).
| \( x \) | A number? | \( x = \emptyset \) | \( p \vee q \) | \( x \in C \)? |
|---|---|---|---|---|
| \( \emptyset \) | No | Yes | T | Yes ✓ |
| \( 2 \) | Yes | No | T | Yes ✓ |
| \( \frac{2}{3} \) | Yes | No | T | Yes ✓ |
| \( 5 \) | Yes | No | T | Yes ✓ |
\[ C = U = \left\{\emptyset, 2, \frac{2}{3}, 5\right\} \]
We’ll also need the complement of \( B \):
\[ B’ = U – B = \{\emptyset, 2, 5\} \]
Step 2 — Compute the operations.
(a) \( B’ – A = \{\emptyset, 2, 5\} – \{2, 5\} = \{\emptyset\} \)
We remove from \( B’ \) the elements that belong to \( A \) (namely 2 and 5), leaving only \( \emptyset \).
(b) \( (A \cup B) – (B \cap C) \)
- \( A \cup B = \{2, 5\} \cup \left\{\frac{2}{3}\right\} = \left\{2, 5, \frac{2}{3}\right\} \)
- \( B \cap C = \left\{\frac{2}{3}\right\} \cap U = \left\{\frac{2}{3}\right\} \)
- \( (A \cup B) – (B \cap C) = \left\{2, 5, \frac{2}{3}\right\} – \left\{\frac{2}{3}\right\} = \{2, 5\} \)
(c) \( (C – B) \cap A \)
- \( C – B = \left\{\emptyset, 2, \frac{2}{3}, 5\right\} – \left\{\frac{2}{3}\right\} = \{\emptyset, 2, 5\} \)
- \( (C – B) \cap A = \{\emptyset, 2, 5\} \cap \{2, 5\} = \{2, 5\} \)
Results:
| Operation | Result |
|---|---|
| \( B’ – A \) | \( \{\emptyset\} \) |
| \( (A \cup B) – (B \cap C) \) | \( \{2, 5\} \) |
| \( (C – B) \cap A \) | \( \{2, 5\} \) |
Exercise 12
Let \( A = \{x \in \mathbb{N} \mid x > 4 \to x = 6\} \), \( B = \{x \in \mathbb{N} \mid x > 0 \wedge x \leq 5\} \), \( C = \{x \in \mathbb{Z} \mid \neg(x > 1 \to x^2 = 4x – 3)\} \). Find \( M = (A \cap B) – (B \cap C) \).
Solution:
Finding \( A \):
The condition is \( x > 4 \to x = 6 \). Using the logical equivalence \( p \to q \equiv \neg p \vee q \):
\[ x > 4 \to x = 6 \equiv x \leq 4 \vee x = 6 \]
So \( A \) contains all natural numbers that are either \( \leq 4 \) or equal to 6:
\[ A = \{1, 2, 3, 4, 6\} \]
Finding \( B \):
The condition is \( x > 0 \wedge x \leq 5 \). Since every natural number already satisfies \( x > 0 \), this reduces to \( x \leq 5 \):
\[ B = \{1, 2, 3, 4, 5\} \]
Finding \( C \):
The condition is \( \neg(x > 1 \to x^2 = 4x – 3) \). Using \( \neg(p \to q) \equiv p \wedge \neg q \):
\[ \neg(x > 1 \to x^2 = 4x – 3) \equiv x > 1 \wedge x^2 \neq 4x – 3 \]
For which integers does \( x^2 = 4x – 3 \) hold? Solving:
\[ x^2 – 4x + 3 = 0 \implies (x – 1)(x – 3) = 0 \implies x = 1 \text{ or } x = 3 \]
So \( x^2 = 4x – 3 \) is true only for \( x = 1 \) and \( x = 3 \). For every other integer, \( x^2 \neq 4x – 3 \).
Combining both conditions (\( x > 1 \) and \( x^2 \neq 4x – 3 \)):
- \( x = 1 \) is excluded because \( 1 > 1 \) is false.
- \( x = 3 \) is excluded because \( 3^2 = 4(3) – 3 \), so \( x^2 = 4x – 3 \) holds.
- Every other integer \( > 1 \) satisfies both conditions.
\[ C = \{x \in \mathbb{Z} \mid x > 1 \wedge x \neq 3\} = \{\dots, 2, 4, 5, 6, 7, 8, \dots\} \]
Correction: The original textbook claims \( C = \{3\} \), which is wrong. The error comes from confusing the solutions of \( x^2 = 4x – 3 \) (the values that satisfy the equation) with those satisfying \( x^2 \neq 4x – 3 \) (the values that don’t). The condition requires \( \neq \), so we must exclude \( x = 1 \) and \( x = 3 \), not include them.
Step 2 — Compute \( M \).
First, the intersections:
\[ A \cap B = \{1, 2, 3, 4, 6\} \cap \{1, 2, 3, 4, 5\} = \{1, 2, 3, 4\} \]
For \( B \cap C \), we check which elements of \( B = \{1, 2, 3, 4, 5\} \) belong to \( C \):
| \( x \) | \( x > 1 \) | \( x^2 \neq 4x – 3 \) | \( x \in C \) |
|---|---|---|---|
| 1 | No | — | No |
| 2 | Yes | \( 4 \neq 5 \) ✓ | Yes |
| 3 | Yes | \( 9 \neq 9 \)? No | No |
| 4 | Yes | \( 16 \neq 13 \) ✓ | Yes |
| 5 | Yes | \( 25 \neq 17 \) ✓ | Yes |
\[ B \cap C = \{2, 4, 5\} \]
Finally:
\[ M = (A \cap B) – (B \cap C) = \{1, 2, 3, 4\} – \{2, 4, 5\} = \{1, 3\} \]
Exercise 13
Let \( A = \{x \in \mathbb{Z} \mid x^2 – 10x – 24 = 0\} \), \( B = \{x \in \mathbb{Z} \mid -3 \leq x \leq 2\} \), \( C = \{x \in \mathbb{Z} \mid 4 – x^2 = 0\} \), and \( D = \{x \in \mathbb{N} \mid 2 + 3x = 7 – 2x\} \). Find the truth value of:
- (a) \( (D \cup A) – C = \{1/3, 2\} \)
- (b) \( (A \cup B) – (D \cup \{12\}) \neq B \)
- (c) \( [(A \cap B) \cup D] \cap C \subset C \)
- (d) \( (D – A) \cap [(A \cup B) – (C \cup D)] = D \)
Solution:
Step 1 — Determine each set.
For \( A \): solve \( x^2 – 10x – 24 = 0 \).
\[ x = \frac{10 \pm \sqrt{100 + 96}}{2} = \frac{10 \pm 14}{2} \implies x = 12 \text{ or } x = -2 \]
\[ A = \{-2, 12\} \]
For \( B \): the integers between \( -3 \) and \( 2 \):
\[ B = \{-3, -2, -1, 0, 1, 2\} \]
For \( C \): solve \( 4 – x^2 = 0 \implies x^2 = 4 \implies x = \pm 2 \):
\[ C = \{-2, 2\} \]
For \( D \): solve \( 2 + 3x = 7 – 2x \implies 5x = 5 \implies x = 1 \). Since \( 1 \in \mathbb{N} \):
\[ D = \{1\} \]
Step 2 — Evaluate each statement.
(a) \( (D \cup A) – C = \{1/3, 2\} \)
- \( D \cup A = \{1\} \cup \{-2, 12\} = \{-2, 1, 12\} \)
- \( (D \cup A) – C = \{-2, 1, 12\} – \{-2, 2\} = \{1, 12\} \)
We remove \( -2 \) (it belongs to \( C \)), while 1 and 12 stay. The result \( \{1, 12\} \neq \{1/3, 2\} \).
The statement is false. ✗
(b) \( (A \cup B) – (D \cup \{12\}) \neq B \)
- \( A \cup B = \{-3, -2, -1, 0, 1, 2, 12\} \)
- \( D \cup \{12\} = \{1, 12\} \)
- \( (A \cup B) – (D \cup \{12\}) = \{-3, -2, -1, 0, 2\} \)
Comparing with \( B = \{-3, -2, -1, 0, 1, 2\} \): the result is missing 1, which \( B \) contains. They’re different.
The statement is true. ✓
(c) \( [(A \cap B) \cup D] \cap C \subset C \)
- \( A \cap B = \{-2, 12\} \cap \{-3, -2, -1, 0, 1, 2\} = \{-2\} \)
- \( (A \cap B) \cup D = \{-2\} \cup \{1\} = \{-2, 1\} \)
- \( \{-2, 1\} \cap C = \{-2, 1\} \cap \{-2, 2\} = \{-2\} \)
Is \( \{-2\} \subset C = \{-2, 2\} \)? Yes — \( -2 \in C \).
The statement is true. ✓
(d) \( (D – A) \cap [(A \cup B) – (C \cup D)] = D \)
- \( D – A = \{1\} – \{-2, 12\} = \{1\} \) (1 is not in \( A \), so it stays)
- \( C \cup D = \{-2, 2\} \cup \{1\} = \{-2, 1, 2\} \)
- \( (A \cup B) – (C \cup D) = \{-3, -2, -1, 0, 1, 2, 12\} – \{-2, 1, 2\} = \{-3, -1, 0, 12\} \)
- \( \{1\} \cap \{-3, -1, 0, 12\} = \emptyset \)
The result is \( \emptyset \), but \( D = \{1\} \neq \emptyset \).
The statement is false. ✗
Summary:
| Part | Result |
|---|---|
| (a) | False |
| (b) | True |
| (c) | True |
| (d) | False |
Exercise 14
Which of the following statements are equivalent to \( x \in [B \cap (A – C)]’ \)?
- (a) \( x \notin [B \cap (A – C)] \)
- (b) \( x \notin B \vee x \notin (A – C) \)
- (c) \( x \in B’ \vee x \in A’ \vee x \in C \)
- (d) \( x \in (B \cap A)’ \wedge x \in C \)
Solution:
First, let’s unpack the original proposition. By definition of complement:
\[ x \in [B \cap (A – C)]’ \equiv x \notin [B \cap (A – C)] \]
Now let’s check each statement:
(a) \( x \notin [B \cap (A – C)] \)
This is exactly the definition of complement applied to the original proposition.
\( \therefore \) Equivalent. ✓
(b) \( x \notin B \vee x \notin (A – C) \)
Applying De Morgan’s Law to \( x \notin [B \cap (A – C)] \):
\[ x \notin [B \cap (A – C)] \equiv \neg(x \in B \wedge x \in (A – C)) \equiv x \notin B \vee x \notin (A – C) \]
\( \therefore \) Equivalent. ✓
(c) \( x \in B’ \vee x \in A’ \vee x \in C \)
We transform step by step using complement and De Morgan:
\[ x \in B’ \vee x \in A’ \vee x \in C \] \[ \equiv x \notin B \vee x \notin A \vee x \in C \] \[ \equiv x \notin B \vee (x \notin A \vee x \in C) \]
Now, \( x \notin A \vee x \in C \equiv \neg(x \in A \wedge x \notin C) \equiv x \notin (A – C) \) (by De Morgan and the definition of difference). Therefore:
\[ \equiv x \notin B \vee x \notin (A – C) \]
Which is the same as (b), already shown to be equivalent.
\( \therefore \) Equivalent. ✓
(d) \( x \in (B \cap A)’ \wedge x \in C \)
Transforming:
\[ x \in (B \cap A)’ \wedge x \in C \equiv x \notin (B \cap A) \wedge x \in C \equiv x \in C – (B \cap A) \]
This describes elements that are in \( C \) but outside \( B \cap A \). However, the original proposition \( x \notin [B \cap (A – C)] \) includes elements that are not in \( C \) at all.
Counterexample: If \( x \notin A \), \( x \notin B \), and \( x \notin C \), then \( x \notin [B \cap (A – C)] \) is true, but \( x \in (B \cap A)’ \wedge x \in C \) is false (since \( x \notin C \)).
\( \therefore \) Not equivalent. ✗
Summary: Statements (a), (b), and (c) are equivalent to the original proposition. Statement (d) is not.
Exercise 15
Given \( A \subset B \), simplify: \( \{[(B \cup A) \cap (B^c_B \cap C)] \cup A^c_B\} \cup B’ \)
where \( X^c_B \) denotes the complement of \( X \) relative to \( B \) (i.e., \( B – X \)), and \( B’ \) denotes the complement of \( B \) with respect to the universal set \( U \).
Solution:
We simplify step by step, using the hypothesis \( A \subset B \).
Step 1 — Simplify \( B \cup A \).
Since \( A \subset B \), every element of \( A \) is already in \( B \):
\[ B \cup A = B \]
Step 2 — Simplify \( B^c_B \).
The complement of \( B \) relative to \( B \) is \( B – B = \emptyset \). Therefore:
\[ B^c_B \cap C = \emptyset \cap C = \emptyset \]
Step 3 — Substitute into the inner expression.
\[ (B \cup A) \cap (B^c_B \cap C) = B \cap \emptyset = \emptyset \]
Step 4 — Simplify the bracketed group.
\[ [\emptyset] \cup A^c_B = A^c_B = B – A \]
Step 5 — Join with \( B’ \).
The expression becomes:
\[ (B – A) \cup B’ \]
Rewriting \( B – A = B \cap A’ \) and applying the distributive law:
\[ (B \cap A’) \cup B’ = (B \cup B’) \cap (A’ \cup B’) = U \cap (A’ \cup B’) = A’ \cup B’ \]
Step 6 — Apply De Morgan.
\[ A’ \cup B’ = (A \cap B)’ \]
Step 7 — Use the hypothesis \( A \subset B \).
Since \( A \subset B \), we have \( A \cap B = A \). Therefore:
\[ (A \cap B)’ = A’ \]
Result:
\[ \{[(B \cup A) \cap (B^c_B \cap C)] \cup A^c_B\} \cup B’ = A’ = U – A \]
Despite its complex appearance, the expression simplifies to the complement of \( A \). ∎
Exercise 16
Given \( A \subset B \) and \( (A \cup B) \cap C = \emptyset \), simplify:
\[ P = \{[A – (B \cap C)] \cup (A \cup C)’ – (B – A)\} \]
Solution:
Step 1 — Derive consequences of the hypotheses.
From \( A \subset B \):
- \( A \cup B = B \)
- \( A \cap B = A \)
Substituting \( A \cup B = B \) into the second hypothesis:
\[ (A \cup B) \cap C = B \cap C = \emptyset \]
Also, since \( A \subset B \) and \( B \cap C = \emptyset \), it follows that \( A \cap C = \emptyset \).
Step 2 — Simplify \( A – (B \cap C) \).
Since \( B \cap C = \emptyset \):
\[ A – (B \cap C) = A – \emptyset = A \]
Step 3 — Simplify \( (A \cup C)’ \).
By De Morgan:
\[ (A \cup C)’ = A’ \cap C’ \]
Step 4 — Compute \( (A \cup C)’ – (B – A) \).
\[ (A’ \cap C’) – (B – A) = (A’ \cap C’) \cap (B – A)’ = (A’ \cap C’) \cap (B’ \cup A) \]
Distributing:
\[ = (A’ \cap C’ \cap B’) \cup (A’ \cap C’ \cap A) = (A’ \cap B’ \cap C’) \cup \emptyset \]
since \( A’ \cap A = \emptyset \). Applying De Morgan:
\[ = (A \cup B \cup C)’ \]
Since \( A \subset B \), we have \( A \cup B = B \), so:
\[ = (B \cup C)’ \]
Step 5 — Combine the results.
\[ P = A \cup (B \cup C)’ \]
Correction: The original textbook concludes \( P = A’ \), which is incorrect. The error comes from misidentifying \( C_B(A) = B – A \) as simply \( A \), which throws off the entire simplification.
Numerical check: Let \( U = \{1,\ldots,6\} \), \( A = \{1\} \), \( B = \{1,2,3\} \), \( C = \{4,5\} \). The hypotheses hold. Then \( P = \{1\} \cup \{6\} = \{1,6\} \), while \( A’ = \{2,3,4,5,6\} \). Clearly \( P \neq A’ \), but \( P = A \cup (B \cup C)’ = \{1\} \cup \{6\} \). ✓
Result:
\[ P = A \cup (B \cup C)’ \]
Exercise 17
For \( a, b \in \mathbb{Q} \), sets \( A \) and \( B \) satisfy \( B \neq \emptyset \), \( A \cup B \) is a singleton, \( A = \{a^2 + 2b,, b^2 + 1\} \), and \( A \cup B = \{a + 4b,, b + 1 – 3a\} \). Find \( A \cap B \).
Solution:
Step 1 — Deduce the structure of \( A \) and \( B \).
If \( A \cup B \) is a singleton (has exactly one element) and \( B \neq \emptyset \), then:
- Since \( B \subset A \cup B \), \( B \) has at most one element. As \( B \neq \emptyset \), \( B \) is a singleton.
- Since \( A \subset A \cup B \), \( A \) also has at most one element — so \( A \) is a singleton too.
- With both being singletons sharing their union: \( A = B = A \cup B \).
Step 2 — Condition for \( A \) to be a singleton.
\( A = \{a^2 + 2b,, b^2 + 1\} \) is a singleton when its two expressions are equal:
\[ a^2 + 2b = b^2 + 1 \] \[ a^2 = b^2 – 2b + 1 = (b – 1)^2 \] \[ a = \pm(b – 1) \quad \cdots (1) \]
Step 3 — Condition for \( A \cup B \) to be a singleton.
\( A \cup B = \{a + 4b,, b + 1 – 3a\} \) is a singleton when:
\[ a + 4b = b + 1 – 3a \implies 4a + 3b = 1 \quad \cdots (2) \]
Step 4 — Solve the system.
Case I: \( a = b – 1 \). Substituting into (2):
\[ 4(b – 1) + 3b = 1 \implies 7b = 5 \implies b = \frac{5}{7}, \quad a = -\frac{2}{7} \]
Checking \( A = A \cup B \) requires \( a^2 + 2b = a + 4b \):
\[ \left(-\frac{2}{7}\right)^2 + 2 \cdot \frac{5}{7} = \frac{4}{49} + \frac{70}{49} = \frac{74}{49} \] \[ -\frac{2}{7} + 4 \cdot \frac{5}{7} = \frac{18}{7} = \frac{126}{49} \]
\( \frac{74}{49} \neq \frac{126}{49} \), so \( A \neq A \cup B \). Discarded. ✗
Case II: \( a = -(b – 1) = 1 – b \). Substituting into (2):
\[ 4(1 – b) + 3b = 1 \implies 4 – b = 1 \implies b = 3, \quad a = -2 \]
Verifying \( A = A \cup B \):
\[ a^2 + 2b = (-2)^2 + 2(3) = 4 + 6 = 10 \] \[ b^2 + 1 = 3^2 + 1 = 10 \quad ✓ \quad (A = \{10\}) \] \[ a + 4b = -2 + 12 = 10 \] \[ b + 1 – 3a = 3 + 1 + 6 = 10 \quad ✓ \quad (A \cup B = \{10\}) \]
So \( A = A \cup B = \{10\} \). ✓
Result:
With \( a = -2 \) and \( b = 3 \): \( A = B = \{10\} \), therefore:
\[ A \cap B = \{10\} \]
Exercise 18
Let \( A = \{\emptyset\} \), \( B = \mathcal{P}(A) \), \( C = B – A \), and \( D = \mathcal{P}(C) \). Find \( B \cap D \).
Solution:
We build each set step by step, paying careful attention to nesting levels.
Compute \( B = \mathcal{P}(A) \):
\( A = \{\emptyset\} \) has one element (\( \emptyset \)). Its subsets are:
\[ B = \mathcal{P}(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\} \]
That is, \( B = \{\emptyset, A\} \) — a 2-element set.
Compute \( C = B – A \):
We remove from \( B \) any element that belongs to \( A = \{\emptyset\} \):
- \( \emptyset \in A \)? Yes (it’s \( A \)’s only element). Remove it. ✗
- \( \{\emptyset\} \in A \)? No — \( \{\emptyset\} \neq \emptyset \) (different nesting levels). Keep it. ✓
\[ C = \{\{\emptyset\}\} \]
Compute \( D = \mathcal{P}(C) \):
\( C = \{\{\emptyset\}\} \) has one element (\( \{\emptyset\} \)). Its subsets are:
\[ D = \mathcal{P}(\{\{\emptyset\}\}) = \{\emptyset, \{\{\emptyset\}\}\} \]
Find \( B \cap D \):
Comparing element by element:
| Element | \( \in B \)? | \( \in D \)? | \( \in B \cap D \)? |
|---|---|---|---|
| \( \emptyset \) | Yes | Yes | Yes ✓ |
| \( \{\emptyset\} \) | Yes | No (\( \{\emptyset\} \neq \{\{\emptyset\}\} \)) | No |
| \( \{\{\emptyset\}\} \) | No (\( \{\{\emptyset\}\} \neq \{\emptyset\} \)) | Yes | No |
\[ B \cap D = \{\emptyset\} = A \]
Note: It turns out \( B \cap D = A \), the original set. This happens because the only element shared by \( B \) and \( D \) is \( \emptyset \) (which always belongs to every power set), and recall that \( \{\emptyset\} = A \).
Exercise 19
In the general diagram of four sets \( A, B, C, D \) there are 16 numbered regions. Given \( A \subset C \), \( B \supset D \), and \( (B \cup C) – (B \cap C) = B \cup C \), which regions are guaranteed to be nonempty?
Solution:
Step 1 — Interpret the hypotheses.
We have three conditions:
- \( A \subset C \): every element of \( A \) belongs to \( C \).
- \( D \subset B \): every element of \( D \) belongs to \( B \).
- \( (B \cup C) – (B \cap C) = B \cup C \): the symmetric difference \( B \triangle C \) equals \( B \cup C \).
The third condition deserves special attention. If removing \( B \cap C \) from \( B \cup C \) returns \( B \cup C \) unchanged, then nothing was removed — meaning:
\[ B \cap C = \emptyset \]
The sets \( B \) and \( C \) are disjoint.
Step 2 — Determine which membership combinations are possible.
Each region of the diagram corresponds to a combination of belonging or not belonging to each of the 4 sets. There are \( 2^4 = 16 \) combinations in total. The conditions rule out many of them:
| Condition | Restriction | Regions eliminated |
|---|---|---|
| \( A \subset C \) | If \( x \in A \), then \( x \in C \). No \( x \in A \) with \( x \notin C \). | Regions where \( A = \text{yes} \) and \( C = \text{no} \) |
| \( D \subset B \) | If \( x \in D \), then \( x \in B \). No \( x \in D \) with \( x \notin B \). | Regions where \( D = \text{yes} \) and \( B = \text{no} \) |
| \( B \cap C = \emptyset \) | No \( x \) can belong to both \( B \) and \( C \). | Regions where \( B = \text{yes} \) and \( C = \text{yes} \) |
Step 3 — Filter all 16 combinations.
| \( A \) | \( B \) | \( C \) | \( D \) | \( A \subset C \) | \( D \subset B \) | \( B \cap C = \emptyset \) | Valid? |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ✓ | ✓ | ✓ | Yes |
| 0 | 0 | 0 | 1 | ✓ | ✗ | ✓ | No |
| 0 | 0 | 1 | 0 | ✓ | ✓ | ✓ | Yes |
| 0 | 0 | 1 | 1 | ✓ | ✗ | ✓ | No |
| 0 | 1 | 0 | 0 | ✓ | ✓ | ✓ | Yes |
| 0 | 1 | 0 | 1 | ✓ | ✓ | ✓ | Yes |
| 0 | 1 | 1 | 0 | ✓ | ✓ | ✗ | No |
| 0 | 1 | 1 | 1 | ✓ | ✓ | ✗ | No |
| 1 | 0 | 0 | 0 | ✗ | ✓ | ✓ | No |
| 1 | 0 | 0 | 1 | ✗ | ✗ | ✓ | No |
| 1 | 0 | 1 | 0 | ✓ | ✓ | ✓ | Yes |
| 1 | 0 | 1 | 1 | ✓ | ✗ | ✓ | No |
| 1 | 1 | 0 | 0 | ✗ | ✓ | ✓ | No |
| 1 | 1 | 0 | 1 | ✗ | ✓ | ✓ | No |
| 1 | 1 | 1 | 0 | ✓ | ✓ | ✗ | No |
| 1 | 1 | 1 | 1 | ✓ | ✓ | ✗ | No |
Of the 16 combinations, only 5 are valid:
| Valid combination | Description | Region |
|---|---|---|
| \( (0,0,0,0) \) | Outside all four sets | 1 |
| \( (0,1,0,0) \) | Only in \( B \) | 2 |
| \( (0,0,1,0) \) | Only in \( C \) | 4 |
| \( (1,0,1,0) \) | In \( A \) and \( C \), outside \( B \) and \( D \) | 6 and 12 |
| \( (0,1,0,1) \) | In \( B \) and \( D \), outside \( A \) and \( C \) | (see diagram) |
Result:
The regions guaranteed to be nonempty are: 1, 2, 4, 6, and 12.
The remaining 11 regions (3, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16) are necessarily empty.
Note: The key insight is that \( (B \cup C) – (B \cap C) = B \cup C \) forces \( B \cap C = \emptyset \), which together with the two inclusion conditions cuts the possible regions from 16 down to just 5.
Exercise 20
It is known that \( X \) is a set such that \( X \in \mathcal{P}(A) \) for every \( A \). Determine which of the following statements are true:
- (a) \( X \cap X = X \)
- (b) \( X – A = X \) for every \( A \)
- (c) \( (A – X) \cup (X – A) = A \) for every \( A \)
Solution:
Step 1 — Identify \( X \).
The condition \( X \in \mathcal{P}(A) \) for every \( A \) means \( X \subset A \) for every set \( A \).
The only set with this property is the empty set: \( X = \emptyset \).
This is because \( \emptyset \subset A \) holds for every set \( A \) — including \( A = \emptyset \) itself, since \( \emptyset \subset \emptyset \) is true by definition.
Step 2 — Evaluate each statement with \( X = \emptyset \).
(a) \( X \cap X = X \)
\[ \emptyset \cap \emptyset = \emptyset = X \]
This is just the idempotent law for intersection: \( S \cap S = S \) for every set \( S \).
True. ✓
(b) \( X – A = X \) for every \( A \)
\[ \emptyset – A = \emptyset = X \quad \text{for every } A \]
Starting from the empty set and removing elements of \( A \), there’s nothing to remove. The result stays \( \emptyset \).
True. ✓
(c) \( (A – X) \cup (X – A) = A \) for every \( A \)
\[ (A – \emptyset) \cup (\emptyset – A) = A \cup \emptyset = A \]
This is the symmetric difference identity \( A \triangle \emptyset = A \): comparing any set with the empty set gives the set itself.
True. ✓
Summary: All three statements are true. The key is recognizing that \( X \in \mathcal{P}(A) \) for every \( A \) uniquely forces \( X = \emptyset \), which is the identity element for union and symmetric difference, and the absorbing element for intersection.
Exercise 21
Of the following statements about sets, determine which are true:
- (a) \( F – (F – G) = F \cap G \)
- (b) \( (A – B) – C = A – (B – C) \)
- (c) \( A – (B \cup C) = (A – B) \cup (A – C) \)
Solution:
(a) \( F – (F – G) = F \cap G \)
We expand the left-hand side using the definition of difference:
\[ x \in F – (F – G) \] \[ \equiv x \in F \wedge x \notin (F – G) \] \[ \equiv x \in F \wedge \neg(x \in F \wedge x \notin G) \]
Applying De Morgan to the negation:
\[ \equiv x \in F \wedge (x \notin F \vee x \in G) \]
Distributing the conjunction:
\[ \equiv (x \in F \wedge x \notin F) \vee (x \in F \wedge x \in G) \] \[ \equiv \emptyset \vee (x \in F \cap G) \] \[ \equiv x \in F \cap G \]
True. ✓
(b) \( (A – B) – C = A – (B – C) \)
Let’s simplify each side separately.
Left-hand side:
\[ (A – B) – C = (A \cap B’) \cap C’ = A \cap B’ \cap C’ = A \cap (B \cup C)’ \]
Right-hand side:
\[ A – (B – C) = A \cap (B – C)’ = A \cap (B \cap C’)’ = A \cap (B’ \cup C) \]
These are not equal in general, since \( A \cap (B \cup C)’ \neq A \cap (B’ \cup C) \).
Counterexample: Let \( A = \{1, 2, 3\} \), \( B = \{2\} \), \( C = \{3\} \):
- Left: \( (A – B) – C = \{1, 3\} – \{3\} = \{1\} \)
- Right: \( A – (B – C) = \{1, 2, 3\} – \{2\} = \{1, 3\} \)
\( \{1\} \neq \{1, 3\} \). False. ✗
Note: Set difference is not associative. The correct identity is \( (A – B) – C = A – (B \cup C) \), not \( A – (B – C) \).
(c) \( A – (B \cup C) = (A – B) \cup (A – C) \)
Left-hand side:
\[ A – (B \cup C) = A \cap (B \cup C)’ = A \cap B’ \cap C’ \]
Right-hand side:
\[ (A – B) \cup (A – C) = (A \cap B’) \cup (A \cap C’) = A \cap (B’ \cup C’) = A \cap (B \cap C)’ \]
These are not equal in general, since \( A \cap B’ \cap C’ \neq A \cap (B \cap C)’ \).
Counterexample: Let \( A = \{1, 2, 3\} \), \( B = \{1\} \), \( C = \{2\} \):
- Left: \( A – (B \cup C) = \{1, 2, 3\} – \{1, 2\} = \{3\} \)
- Right: \( (A – B) \cup (A – C) = \{2, 3\} \cup \{1, 3\} = \{1, 2, 3\} \)
\( \{3\} \neq \{1, 2, 3\} \). False. ✗
Note: The correct identity uses intersection, not union: \( A – (B \cup C) = (A – B) \cap (A – C) \). This is one of De Morgan’s Laws for differences.
Summary:
| Part | Result | Note |
|---|---|---|
| (a) | True | \( F – (F – G) = F \cap G \) always holds |
| (b) | False | Set difference is not associative |
| (c) | False | The correct identity uses \( \cap \), not \( \cup \) |
Exercise 22
Let \( A \), \( B \), and \( C \) be nonempty sets such that \( A \) and \( C \) are disjoint and \( A \cup C = B \). Simplify \( A \triangle B \triangle A \triangle C \).
Solution:
Step 1 — Use the algebraic properties of symmetric difference.
Symmetric difference is associative and commutative, so we can regroup freely:
\[ A \triangle B \triangle A \triangle C = (A \triangle A) \triangle (B \triangle C) \]
Step 2 — Simplify \( A \triangle A \).
The symmetric difference of any set with itself is empty — every element appears in both, so none remain:
\[ A \triangle A = \emptyset \]
Therefore:
\[ \emptyset \triangle (B \triangle C) = B \triangle C \]
since \( \emptyset \) is the identity element for symmetric difference.
Step 3 — Compute \( B \triangle C \).
By definition:
\[ B \triangle C = (B – C) \cup (C – B) \]
Now we use the hypotheses: \( A \cap C = \emptyset \) and \( A \cup C = B \).
Compute \( B – C \): the elements of \( B \) not in \( C \).
\[ B – C = (A \cup C) – C = A \]
This holds because \( A \) and \( C \) are disjoint: removing \( C \) from \( A \cup C \) leaves exactly \( A \).
Compute \( C – B \): the elements of \( C \) not in \( B \).
\[ C – B = C – (A \cup C) = \emptyset \]
Since \( C \subset A \cup C = B \), every element of \( C \) already belongs to \( B \), so nothing remains.
Step 4 — Final result.
\[ B \triangle C = A \cup \emptyset = A \]
Therefore:
\[ A \triangle B \triangle A \triangle C = A \]
Key properties used:
- \( X \triangle X = \emptyset \) (self-inverse)
- \( \emptyset \triangle X = X \) (identity element)
- Associativity and commutativity of \( \triangle \)
∎
Exercise 23
Simplify:
\[ P = [(A \cap B) \cup (C’ \cup D’ \cup E’)] \cap [(A \cap B) \cup (C \cap D \cap E)] \]
Solution:
Step 1 — Apply De Morgan.
Notice that \( C’ \cup D’ \cup E’ \) is the complement of an intersection:
\[ C’ \cup D’ \cup E’ = (C \cap D \cap E)’ \]
Setting \( X = A \cap B \) and \( Y = C \cap D \cap E \) to expose the structure:
\[ P = (X \cup Y’) \cap (X \cup Y) \]
Step 2 — Apply the distributive law.
Union distributes over intersection:
\[ (X \cup Y’) \cap (X \cup Y) = X \cup (Y’ \cap Y) \]
Step 3 — Simplify \( Y’ \cap Y \).
A set intersected with its complement is always empty:
\[ Y’ \cap Y = \emptyset \]
Step 4 — Conclude.
\[ P = X \cup \emptyset = X = A \cap B \]
Result:
\[ P = A \cap B \]
Despite involving five sets, the expression collapses to \( A \cap B \) because the structure \( (X \cup Y’) \cap (X \cup Y) \) always simplifies to \( X \), regardless of what \( Y \) is. ∎
Exercise 24
Determine whether each expression is true or false, with justification:
- (a) If \( B \subset A \), then \( (A – B) \in \mathcal{P}(A – B) \) and \( (B – A) \in \mathcal{P}(A – B) \).
- (b) Let \( A = \{a\} \) and \( B = \{b\} \). Then \( \mathcal{P}(A – B) = \mathcal{P}(A) \).
Solution:
(a) We must verify both claims under the hypothesis \( B \subset A \).
First: \( (A – B) \in \mathcal{P}(A – B) \).
Recall that \( X \in \mathcal{P}(Y) \iff X \subset Y \). Since every set is a subset of itself:
\[ A – B \subset A – B \]
always holds, so \( (A – B) \in \mathcal{P}(A – B) \). ✓
Second: \( (B – A) \in \mathcal{P}(A – B) \).
We need \( B – A \subset A – B \). Since \( B \subset A \), every element of \( B \) is already in \( A \), so:
\[ B – A = \emptyset \]
And since the empty set is a subset of every set:
\[ \emptyset \subset A – B \implies \emptyset \in \mathcal{P}(A – B) \]
Therefore \( (B – A) \in \mathcal{P}(A – B) \). ✓
The statement is true. ✓
(b) \( A = \{a\} \), \( B = \{b\} \). Is \( \mathcal{P}(A – B) = \mathcal{P}(A) \)?
The answer depends on whether \( a \) and \( b \) are the same object.
Case 1: \( a \neq b \).
\[ A – B = \{a\} – \{b\} = \{a\} \]
(The element \( a \) is not in \( B \), so it stays.)
\[ \mathcal{P}(A – B) = \mathcal{P}(\{a\}) = \{\emptyset, \{a\}\} \] \[ \mathcal{P}(A) = \mathcal{P}(\{a\}) = \{\emptyset, \{a\}\} \]
Equal. ✓
Case 2: \( a = b \).
Then \( A = B = \{a\} \), so:
\[ A – B = \{a\} – \{a\} = \emptyset \] \[ \mathcal{P}(A – B) = \mathcal{P}(\emptyset) = \{\emptyset\} \]
But \( \mathcal{P}(A) = \{\emptyset, \{a\}\} \), which has 2 elements.
\[ \{\emptyset\} \neq \{\emptyset, \{a\}\} \]
Not equal. ✗
The statement is false in general, since the problem does not guarantee \( a \neq b \). It would only be true with the additional condition \( a \neq b \) explicitly stated.
Exercise 25
Prove that for any three sets \( A \), \( B \), and \( C \):
\[ (A \cap C) \triangle (B \cap C) = (A \triangle B) \cap C \]
Proof:
Recall that \( X \triangle Y = (X \cup Y) – (X \cap Y) \).
Step 1 — Apply the definition of \( \triangle \) to the left-hand side.
\[ (A \cap C) \triangle (B \cap C) = [(A \cap C) \cup (B \cap C)] – [(A \cap C) \cap (B \cap C)] \]
Step 2 — Simplify each part using the distributive law.
The union factors:
\[ (A \cap C) \cup (B \cap C) = (A \cup B) \cap C \]
The intersection also factors:
\[ (A \cap C) \cap (B \cap C) = (A \cap B) \cap C \]
Substituting:
\[ = [(A \cup B) \cap C] – [(A \cap B) \cap C] \]
Step 3 — Factor out \( C \) from the difference.
We use the property: \( (X \cap C) – (Y \cap C) = (X – Y) \cap C \). Indeed:
\[ x \in (X \cap C) – (Y \cap C) \iff x \in X \wedge x \in C \wedge x \notin Y \wedge x \in C \] \[ \iff x \in X \wedge x \in C \wedge (x \notin Y \vee x \notin C) \] \[ \iff x \in X \wedge x \in C \wedge x \notin Y \] \[ \iff x \in (X – Y) \cap C \]
(The option \( x \notin C \) is ruled out since we already have \( x \in C \).)
Applying this:
\[ [(A \cup B) \cap C] – [(A \cap B) \cap C] = [(A \cup B) – (A \cap B)] \cap C \]
Step 4 — Recognize the symmetric difference.
\[ (A \cup B) – (A \cap B) = A \triangle B \]
Therefore:
\[ (A \cap C) \triangle (B \cap C) = (A \triangle B) \cap C \]
∎
Interpretation: Symmetric difference distributes over intersection. Comparing \( A \) and \( B \) within \( C \) gives the same result as first comparing \( A \) and \( B \), then restricting to \( C \).
Exercise 26
Prove that: \( B’ \cap (A \cup B) = A \iff A \cap B = \emptyset \)
Proof:
Step 1 — Simplify the left-hand side of the equation.
Applying the distributive law:
\[ B’ \cap (A \cup B) = (B’ \cap A) \cup (B’ \cap B) \]
Since \( B’ \cap B = \emptyset \) (a set and its complement share no elements):
\[ = (A \cap B’) \cup \emptyset = A \cap B’ = A – B \]
So the original equation is equivalent to:
\[ A – B = A \]
Step 2 — Prove the biconditional \( A – B = A \iff A \cap B = \emptyset \).
\( (\Rightarrow) \) Suppose \( A – B = A \).
If there were some \( x \in A \cap B \), then \( x \in A \) and \( x \in B \). But \( x \in B \) means \( x \notin A – B \). Since \( A – B = A \), this would give \( x \notin A \), contradicting \( x \in A \). So no such \( x \) exists, and \( A \cap B = \emptyset \). ✓
\( (\Leftarrow) \) Suppose \( A \cap B = \emptyset \).
Since \( A \) and \( B \) share no elements, no element of \( A \) belongs to \( B \), so computing \( A – B \) removes nothing:
\[ A – B = A \quad ✓ \]
Conclusion:
Combining both steps:
\[ B’ \cap (A \cup B) = A – B = A \iff A \cap B = \emptyset \]
∎
The takeaway: The expression \( B’ \cap (A \cup B) \) always simplifies to \( A – B \), regardless of the relationship between \( A \) and \( B \). The condition \( A \cap B = \emptyset \) is exactly what forces \( A – B = A \).
Exercise 27
Using set properties, prove that:
\[ [A’ – (B’ \cap C’)]’ \cap (C’ – B)’ = A \cap (B \cup C) \]
Proof:
We simplify the left-hand side step by step.
Step 1 — Simplify \( A’ – (B’ \cap C’) \).
Using \( X – Y = X \cap Y’ \):
\[ A’ – (B’ \cap C’) = A’ \cap (B’ \cap C’)’ \]
By De Morgan, \( (B’ \cap C’)’ = B \cup C \):
\[ = A’ \cap (B \cup C) \]
Step 2 — Take the complement.
\[ [A’ \cap (B \cup C)]’ \]
Applying De Morgan:
\[ = A \cup (B \cup C)’ \]
Step 3 — Simplify \( (C’ – B)’ \).
\[ C’ – B = C’ \cap B’ \]
Taking the complement and applying De Morgan:
\[ (C’ \cap B’)’ = C \cup B = B \cup C \]
Step 4 — Combine both parts.
\[ [A \cup (B \cup C)’] \cap (B \cup C) \]
Setting \( X = B \cup C \) and applying the distributive law:
\[ = (A \cap X) \cup (X’ \cap X) = (A \cap X) \cup \emptyset = A \cap X \]
Result:
\[ [A’ – (B’ \cap C’)]’ \cap (C’ – B)’ = A \cap (B \cup C) \]
∎
Technique: Eliminate difference operators using \( X – Y = X \cap Y’ \), apply De Morgan repeatedly to peel away nested complements, then use \( X’ \cap X = \emptyset \) to collapse the expression.
Exercise 28
Let \( A \), \( B \), and \( C \) be sets. Prove that if \( B \cap C = \emptyset \), then:
\[ [A – (B \cup C)] \cup (A \cap B) \cup (A \cap C) = A \]
Proof:
Step 1 — Group the last two terms.
By the distributive law of \( \cap \) over \( \cup \):
\[ (A \cap B) \cup (A \cap C) = A \cap (B \cup C) \]
Step 2 — Rewrite the difference.
Using \( X – Y = X \cap Y’ \):
\[ A – (B \cup C) = A \cap (B \cup C)’ \]
Step 3 — Substitute into the original expression.
\[ [A \cap (B \cup C)’] \cup [A \cap (B \cup C)] \]
Step 4 — Factor out \( A \).
Applying the distributive law in reverse:
\[ = A \cap [(B \cup C)’ \cup (B \cup C)] \]
Step 5 — Apply the complement law.
A set united with its complement is the universal set:
\[ (B \cup C)’ \cup (B \cup C) = U \]
Therefore:
\[ = A \cap U = A \]
∎
Note: The hypothesis \( B \cap C = \emptyset \) is not actually used in the proof — the identity holds for any sets \( A \), \( B \), and \( C \). Intuitively, the three terms partition \( A \) into what lies outside \( B \cup C \), what lies in \( B \), and what lies in \( C \) — and their union always reconstructs all of \( A \).
Exercise 29
Prove using element-wise definitions that:
\[ (A \cap B) – (A \cap C)’ = A \cap (B – C’) \]
Proof:
The key is the equivalence \( x \notin X’ \iff x \in X \) — not belonging to the complement is the same as belonging to the set.
(1) Let \( x \in (A \cap B) – (A \cap C)’ \).
(2) By definition of difference:
\[ x \in (A \cap B) \wedge x \notin (A \cap C)’ \]
(3) Applying \( x \notin X’ \iff x \in X \):
\[ x \in (A \cap B) \wedge x \in (A \cap C) \]
(4) Expanding both intersections:
\[ (x \in A \wedge x \in B) \wedge (x \in A \wedge x \in C) \]
(5) By idempotence (\( x \in A \wedge x \in A \equiv x \in A \)) and associativity:
\[ x \in A \wedge x \in B \wedge x \in C \]
(6) Since \( x \in C \iff x \notin C’ \), we can write \( x \in B \wedge x \in C \) as \( x \in B \wedge x \notin C’ \):
\[ x \in A \wedge (x \in B \wedge x \notin C’) \]
(7) The expression \( x \in B \wedge x \notin C’ \) is the definition of \( x \in B – C’ \):
\[ x \in A \wedge x \in (B – C’) \]
(8) Which is the definition of \( x \in A \cap (B – C’) \):
\[ x \in A \cap (B – C’) \]
Since every step is an equivalence (\( \iff \)), the membership of \( x \) in the left-hand side is equivalent to membership in the right-hand side, so:
\[ (A \cap B) – (A \cap C)’ = A \cap (B – C’) \]
∎
Exercise 30
Prove using element-wise arguments:
- (a) \( B \subset [A \cup (B – A)] \)
- (b) \( \mathcal{P}[(A \cap B) \cup C] = \mathcal{P}(A \cup C) \cap \mathcal{P}(B \cup C) \)
Proof of (a):
We must show that if \( x \in B \), then \( x \in A \cup (B – A) \).
Let \( x \in B \). There are two cases:
Case 1: \( x \in A \). Then \( x \in A \cup (B – A) \) directly, since \( x \) belongs to the first term of the union. ✓
Case 2: \( x \notin A \). Since \( x \in B \) and \( x \notin A \), we have \( x \in B – A \) by definition of difference. Then \( x \in A \cup (B – A) \), since \( x \) belongs to the second term of the union. ✓
In both cases \( x \in A \cup (B – A) \), so \( B \subset A \cup (B – A) \). ∎
Note: In fact \( A \cup (B – A) = A \cup B \), so the result simply says \( B \subset A \cup B \), which is immediate. The equality \( A \cup (B – A) = A \cup B \) holds because adding back the part of \( B \) outside \( A \) recovers all of \( A \cup B \).
Proof of (b):
We show \( \mathcal{P}[(A \cap B) \cup C] = \mathcal{P}(A \cup C) \cap \mathcal{P}(B \cup C) \) by establishing a chain of equivalences.
Let \( X \) be an arbitrary set.
(1) \( X \in \mathcal{P}[(A \cap B) \cup C] \)
(2) \( \iff X \subset (A \cap B) \cup C \) (definition of power set)
(3) \( \iff X \subset (A \cup C) \cap (B \cup C) \) (distributive law: \( (A \cap B) \cup C = (A \cup C) \cap (B \cup C) \))
(4) \( \iff X \subset (A \cup C) \wedge X \subset (B \cup C) \) (since \( X \subset Y \cap Z \iff X \subset Y \wedge X \subset Z \))
(5) \( \iff X \in \mathcal{P}(A \cup C) \wedge X \in \mathcal{P}(B \cup C) \) (definition of power set)
(6) \( \iff X \in \mathcal{P}(A \cup C) \cap \mathcal{P}(B \cup C) \) (definition of intersection)
Since (1) and (6) are equivalent, the two sets are equal. ∎
Exercise 31
Using set properties, prove that for sets \( A \), \( B \), and \( C \):
\[ (A \triangle B) \cup (B \triangle C) = (A \cup B \cup C) – (A \cap B \cap C) \]
Proof:
Step 1 — Expand the symmetric differences.
\[ A \triangle B = (A \cap B’) \cup (A’ \cap B) \] \[ B \triangle C = (B \cap C’) \cup (B’ \cap C) \]
So:
\[ (A \triangle B) \cup (B \triangle C) = (A \cap B’) \cup (A’ \cap B) \cup (B \cap C’) \cup (B’ \cap C) \]
Step 2 — Regroup by membership in \( B \).
Separating the terms containing \( B’ \) from those containing \( B \):
\[ = [(A \cap B’) \cup (B’ \cap C)] \cup [(A’ \cap B) \cup (B \cap C’)] \]
Factoring \( B’ \) from the first group and \( B \) from the second:
\[ = [B’ \cap (A \cup C)] \cup [B \cap (A’ \cup C’)] \]
Applying De Morgan to the second factor, \( A’ \cup C’ = (A \cap C)’ \):
\[ = [B’ \cap (A \cup C)] \cup [B \cap (A \cap C)’] \quad \cdots (\ast) \]
Step 3 — Simplify the right-hand side.
\[ (A \cup B \cup C) – (A \cap B \cap C) = (A \cup B \cup C) \cap (A \cap B \cap C)’ \]
Applying De Morgan, \( (A \cap B \cap C)’ = A’ \cup B’ \cup C’ \):
\[ = (A \cup B \cup C) \cap (A’ \cup B’ \cup C’) \quad \cdots (\ast\ast) \]
Step 4 — Show that \( (\ast) = (\ast\ast) \).
We analyze by cases according to membership in \( B \):
Case \( x \notin B \): An element \( x \) belongs to \( (\ast) \) if and only if \( x \in A \cup C \) (via the first term \( B’ \cap (A \cup C) \)). For \( (\ast\ast) \): since \( x \notin B \), the condition \( x \in A \cup B \cup C \) reduces to \( x \in A \cup C \), and \( x \in A’ \cup B’ \cup C’ \) is automatic since \( x \in B’ \). Both conditions are identical.
Case \( x \in B \): An element \( x \) belongs to \( (\ast) \) if and only if \( x \notin A \) or \( x \notin C \) (via the second term \( B \cap (A \cap C)’ \)). For \( (\ast\ast) \): \( x \in A \cup B \cup C \) holds automatically since \( x \in B \), and \( x \in A’ \cup B’ \cup C’ \) requires \( x \notin A \) or \( x \notin C \) (since \( x \in B \) rules out \( x \in B’ \)). Both conditions are identical.
In both cases \( (\ast) \iff (\ast\ast) \), therefore:
\[ (A \triangle B) \cup (B \triangle C) = (A \cup B \cup C) – (A \cap B \cap C) \]
∎
Interpretation: The right-hand side says “in at least one of \( A, B, C \) but not in all three at once.” The left-hand side says “differ from \( B \) with respect to \( A \), or differ from \( B \) with respect to \( C \).” Both conditions exclude exactly the same case: belonging to all three sets simultaneously.
Exercise 32
Let \( U = \{x \in \mathbb{N} \mid 0 < x \leq 10\} \) and the subsets \( A = \{x \in U \mid x \text{ is prime}\} \), \( B = \{x \in U \mid x \text{ is a perfect square}\} \), \( C = \{x \in U \mid x \text{ is odd}\} \). Find:
- (a) \( (A \cup B)’ – C \)
- (b) \( (A – C)’ \cap B \)
- (c) \( (A \triangle B) – (A \triangle C) \)
- (d) \( (A \cap C)’ – (B \cup C)’ \)
Solution:
Step 1 — Determine the sets.
\[ U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} \]
| Set | Condition | Elements |
|---|---|---|
| \( A \) | Prime | \( \{2, 3, 5, 7\} \) |
| \( B \) | Perfect square (\( 1^2, 2^2, 3^2 \)) | \( \{1, 4, 9\} \) |
| \( C \) | Odd | \( \{1, 3, 5, 7, 9\} \) |
Complements with respect to \( U \):
| Set | Elements |
|---|---|
| \( A’ \) | \( \{1, 4, 6, 8, 9, 10\} \) |
| \( B’ \) | \( \{2, 3, 5, 6, 7, 8, 10\} \) |
| \( C’ \) | \( \{2, 4, 6, 8, 10\} \) |
Step 2 — Compute each part.
(a) \( (A \cup B)’ – C \)
- \( A \cup B = \{1, 2, 3, 4, 5, 7, 9\} \)
- \( (A \cup B)’ = \{6, 8, 10\} \)
- \( (A \cup B)’ – C = \{6, 8, 10\} – \{1, 3, 5, 7, 9\} = \{6, 8, 10\} \)
None of the elements of \( (A \cup B)’ \) are odd, so nothing is removed.
\[ (A \cup B)’ – C = \{6, 8, 10\} \]
(b) \( (A – C)’ \cap B \)
- \( A – C = \{2\} \) (the only even prime)
- \( (A – C)’ = U – \{2\} = \{1, 3, 4, 5, 6, 7, 8, 9, 10\} \)
- \( (A – C)’ \cap B = \{1, 4, 9\} \)
Since \( 2 \notin B \), the complement of \( \{2\} \) contains all of \( B \).
\[ (A – C)’ \cap B = \{1, 4, 9\} = B \]
(c) \( (A \triangle B) – (A \triangle C) \)
Computing both symmetric differences:
- \( A \triangle B = (A – B) \cup (B – A) = \{2, 3, 5, 7\} \cup \{1, 4, 9\} = \{1, 2, 3, 4, 5, 7, 9\} \)
(\( A \) and \( B \) are disjoint, so \( A \triangle B = A \cup B \).)
- \( A \triangle C = (A – C) \cup (C – A) = \{2\} \cup \{1, 9\} = \{1, 2, 9\} \)
Finally:
\[ (A \triangle B) – (A \triangle C) = \{1, 2, 3, 4, 5, 7, 9\} – \{1, 2, 9\} = \{3, 4, 5, 7\} \]
(d) \( (A \cap C)’ – (B \cup C)’ \)
- \( A \cap C = \{3, 5, 7\} \) (the odd primes in \( U \))
- \( (A \cap C)’ = \{1, 2, 4, 6, 8, 9, 10\} \)
- \( B \cup C = \{1, 3, 4, 5, 7, 9\} \)
- \( (B \cup C)’ = \{2, 6, 8, 10\} \)
- \( (A \cap C)’ – (B \cup C)’ = \{1, 2, 4, 6, 8, 9, 10\} – \{2, 6, 8, 10\} = \{1, 4, 9\} \)
\[ (A \cap C)’ – (B \cup C)’ = \{1, 4, 9\} = B \]
Summary:
| Part | Result | Note |
|---|---|---|
| (a) | \( \{6, 8, 10\} \) | The even composites of \( U \) |
| (b) | \( \{1, 4, 9\} = B \) | Equals \( B \) |
| (c) | \( \{3, 4, 5, 7\} \) | |
| (d) | \( \{1, 4, 9\} = B \) | Also equals \( B \) |
Exercise 33
Let:
- \( A = \{x \in \mathbb{Z} \mid \neg[x \leq -2 \vee x > 3]\} \)
- \( B = \{x \in \mathbb{N} \mid \neg(-1 < x \leq 3 \to x = 5)\} \)
- \( C = \{x \in \mathbb{Z} \mid (x \leq -2 \vee x \geq 2) \to x^2 > 1\} \)
Find \( (B \cap C) \triangle (A \cap B) \).
Solution:
Finding \( A \):
We negate the condition using De Morgan:
\[ \neg[x \leq -2 \vee x > 3] \equiv x > -2 \wedge x \leq 3 \]
That is, \( -2 < x \leq 3 \). The integers satisfying this are:
\[ A = \{-1, 0, 1, 2, 3\} \]
Finding \( B \):
We negate the conditional using \( \neg(p \to q) \equiv p \wedge \neg q \):
\[ \neg(-1 < x \leq 3 \to x = 5) \equiv (-1 < x \leq 3) \wedge (x \neq 5) \]
For \( x \in \mathbb{N} \): the condition \( -1 < x \leq 3 \) gives \( x \in \{1, 2, 3\} \), none of which equal 5.
\[ B = \{1, 2, 3\} \]
Finding \( C \):
The condition is \( (x \leq -2 \vee x \geq 2) \to x^2 > 1 \). Using \( p \to q \equiv \neg p \vee q \):
\[ (-2 < x < 2) \vee (x^2 > 1) \]
Checking by cases:
| Range of \( x \) | \( -2 < x < 2 \) | \( x^2 > 1 \) | Disjunction | \( x \in C \)? |
|---|---|---|---|---|
| \( x \leq -2 \) | No | Yes (\( x^2 \geq 4 \)) | T | Yes ✓ |
| \( x \in \{-1, 0, 1\} \) | Yes | — | T | Yes ✓ |
| \( x \geq 2 \) | No | Yes (\( x^2 \geq 4 \)) | T | Yes ✓ |
The condition holds for every integer.
\[ C = \mathbb{Z} \]
Note: The conditional \( (x \leq -2 \vee x \geq 2) \to x^2 > 1 \) is universally true in \( \mathbb{Z} \): when the hypothesis is false (\( -2 < x < 2 \)), the implication holds vacuously; when it is true, \( x^2 \geq 4 > 1 \).
Final computation:
Since \( C = \mathbb{Z} \):
\[ B \cap C = \{1, 2, 3\} \cap \mathbb{Z} = \{1, 2, 3\} = B \]
Since \( B \subset A \) (\( \{1, 2, 3\} \subset \{-1, 0, 1, 2, 3\} \)):
\[ A \cap B = \{1, 2, 3\} = B \]
Both operands of the symmetric difference are the same set:
\[ (B \cap C) \triangle (A \cap B) = B \triangle B = \emptyset \]
Result:
\[ (B \cap C) \triangle (A \cap B) = \emptyset \]
Note: All the logical work to find \( A \), \( B \), and \( C \) leads to an elegantly simple result: since \( B \subset A \) and \( B \subset C \), both intersections equal \( B \), and \( B \triangle B = \emptyset \).
Exercise 34
Let \( E = \{\emptyset, a, \{a\}, \{a, \emptyset\}\} \) with subsets:
- \( B = \{x \in E \mid x \neq \emptyset \wedge x \neq \{a, \emptyset\}\} \)
- \( C = \{x \in E \mid x \neq a \vee x \neq \{a, \emptyset\}\} \)
- \( D = \{x \in E \mid x \text{ is a letter of the alphabet}\} \)
Find: (a) \( \mathcal{P}(B – C) \), (b) \( (C \cap D) – B’ \), (c) \( (C – B)’ \cup (B \cap D’) \).
Solution:
Step 1 — Identify the elements of \( E \).
\( E \) has 4 elements, each of a different nature:
| Element | Type |
|---|---|
| \( \emptyset \) | Empty set |
| \( a \) | A letter (not a set) |
| \( \{a\} \) | A set with one element |
| \( \{a, \emptyset\} \) | A set with two elements |
Step 2 — Find \( B \), \( C \), and \( D \).
For \( B \): \( x \neq \emptyset \) and \( x \neq \{a, \emptyset\} \) (conjunction — both must fail for exclusion).
| \( x \) | \( x \neq \emptyset \) | \( x \neq \{a, \emptyset\} \) | \( p \wedge q \) | \( x \in B \)? |
|---|---|---|---|---|
| \( \emptyset \) | No | Yes | F | No |
| \( a \) | Yes | Yes | T | Yes ✓ |
| \( \{a\} \) | Yes | Yes | T | Yes ✓ |
| \( \{a, \emptyset\} \) | Yes | No | F | No |
\[ B = \{a, \{a\}\} \]
For \( C \): \( x \neq a \) or \( x \neq \{a, \emptyset\} \) (disjunction).
A disjunction \( p \vee q \) is false only when both are false — that would require \( x = a \) and \( x = \{a, \emptyset\} \) simultaneously, which is impossible. So the condition is always true.
\[ C = E = \{\emptyset, a, \{a\}, \{a, \emptyset\}\} \]
For \( D \): Only \( a \) is a letter of the alphabet; the rest are sets.
\[ D = \{a\} \]
Complements with respect to \( E \):
\[ B’ = \{\emptyset, \{a, \emptyset\}\}, \quad C’ = \emptyset, \quad D’ = \{\emptyset, \{a\}, \{a, \emptyset\}\} \]
Step 3 — Compute each part.
(a) \( \mathcal{P}(B – C) \)
Since \( C = E \), every element of \( B \) is in \( C \):
\[ B – C = \{a, \{a\}\} – E = \emptyset \]
\[ \mathcal{P}(B – C) = \mathcal{P}(\emptyset) = \{\emptyset\} \]
(b) \( (C \cap D) – B’ \)
- \( C \cap D = E \cap \{a\} = \{a\} \)
- \( (C \cap D) – B’ = \{a\} – \{\emptyset, \{a, \emptyset\}\} = \{a\} \)
(The element \( a \) is not in \( B’ \), so it stays.)
\[ (C \cap D) – B’ = \{a\} \]
(c) \( (C – B)’ \cup (B \cap D’) \)
- \( C – B = E – \{a, \{a\}\} = \{\emptyset, \{a, \emptyset\}\} \)
- \( (C – B)’ = E – \{\emptyset, \{a, \emptyset\}\} = \{a, \{a\}\} \)
- \( B \cap D’ = \{a, \{a\}\} \cap \{\emptyset, \{a\}, \{a, \emptyset\}\} = \{\{a\}\} \)
- \( (C – B)’ \cup (B \cap D’) = \{a, \{a\}\} \cup \{\{a\}\} = \{a, \{a\}\} \)
\[ (C – B)’ \cup (B \cap D’) = \{a, \{a\}\} = B \]
Summary:
| Part | Result |
|---|---|
| (a) | \( \{\emptyset\} \) |
| (b) | \( \{a\} = D \) |
| (c) | \( \{a, \{a\}\} = B \) |
Exercise 35
Let:
- \( A = \{x \in \mathbb{N} \mid 7 – x = 3 \vee x < 3\} \)
- \( B = \{x \in \mathbb{N} \mid 5 – x > 2 \wedge \frac{1}{5}(6x – 2) \geq 2\} \)
- \( C = \{x \in \mathbb{N} \mid x \text{ is a perfect square}, x \leq 10\} \)
Find: (a) \( (A \cup B) \cap (C – A) \), (b) \( (A – B) \cup (B \cap C) \), (c) \( (A \cap B) – (A – C) \), (d) \( (A \triangle B) \cap (B \cap C) \).
Solution:
Step 1 — Determine each set.
For \( A \): \( 7 – x = 3 \vee x < 3 \)
- \( 7 – x = 3 \implies x = 4 \)
- \( x < 3 \implies x \in \{1, 2\} \)
\[ A = \{1, 2, 4\} \]
For \( B \): \( 5 – x > 2 \wedge \frac{1}{5}(6x – 2) \geq 2 \)
Solving each inequality:
- \( 5 – x > 2 \implies x < 3 \), so \( x \in \{1, 2\} \)
- \( \frac{1}{5}(6x – 2) \geq 2 \implies 6x – 2 \geq 10 \implies x \geq 2 \)
The conjunction \( x < 3 \wedge x \geq 2 \) gives \( x = 2 \).
\[ B = \{2\} \]
For \( C \): Perfect squares in \( \mathbb{N} \) with \( x \leq 10 \): \( 1, 4, 9 \).
\[ C = \{1, 4, 9\} \]
Step 2 — Useful observations.
- \( B \subset A \) (\( \{2\} \subset \{1, 2, 4\} \))
- \( B \cap C = \emptyset \) (2 is not a perfect square)
Step 3 — Compute each part.
(a) \( (A \cup B) \cap (C – A) \)
- \( A \cup B = \{1, 2, 4\} \) (since \( B \subset A \), nothing is added)
- \( C – A = \{9\} \)
- \( \{1, 2, 4\} \cap \{9\} = \emptyset \)
\[ (A \cup B) \cap (C – A) = \emptyset \]
(b) \( (A – B) \cup (B \cap C) \)
- \( A – B = \{1, 4\} \)
- \( B \cap C = \emptyset \)
- \( \{1, 4\} \cup \emptyset = \{1, 4\} \)
\[ (A – B) \cup (B \cap C) = \{1, 4\} \]
(c) \( (A \cap B) – (A – C) \)
- \( A \cap B = \{2\} \)
- \( A – C = \{2\} \) (only 2 is not a perfect square)
- \( \{2\} – \{2\} = \emptyset \)
\[ (A \cap B) – (A – C) = \emptyset \]
(d) \( (A \triangle B) \cap (B \cap C) \)
- \( A \triangle B = \{1, 4\} \) (since \( B \subset A \), \( B – A = \emptyset \))
- \( B \cap C = \emptyset \)
\[ (A \triangle B) \cap (B \cap C) = \emptyset \]
Summary:
| Part | Result | Key reason |
|---|---|---|
| (a) | \( \emptyset \) | \( A \cup B = A \) doesn’t contain 9 |
| (b) | \( \{1, 4\} \) | The perfect squares of \( A \) (excluding 2) |
| (c) | \( \emptyset \) | \( A \cap B = \{2\} = A – C \), they cancel |
| (d) | \( \emptyset \) | \( B \cap C = \emptyset \) kills everything |
Exercise 36
Let \( A = \{x \in \mathbb{N} \mid 3 < x \leq 4\} \), \( B = \{z \mid z = n^2,\ n \in \mathbb{N},\ n \leq 5\} \), \( C = \{x \in \mathbb{N} \mid x \text{ divides } 30\} \). Find the sum of the elements of \( (A \cap B) \cup (B \cup C) \).
Solution:
Step 1 — Determine each set.
For \( A \): \( 3 < x \leq 4 \) with \( x \in \mathbb{N} \). The only natural number in that interval is \( x = 4 \).
\[ A = \{4\} \]
For \( B \): The squares of the first 5 natural numbers:
| \( n \) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \( n^2 \) | 1 | 4 | 9 | 16 | 25 |
\[ B = \{1, 4, 9, 16, 25\} \]
For \( C \): The natural divisors of \( 30 = 2 \times 3 \times 5 \):
\[ C = \{1, 2, 3, 5, 6, 10, 15, 30\} \]
Step 2 — Compute \( (A \cap B) \cup (B \cup C) \).
\[ A \cap B = \{4\} \cap \{1, 4, 9, 16, 25\} = \{4\} \]
\[ B \cup C = \{1, 2, 3, 4, 5, 6, 9, 10, 15, 16, 25, 30\} \]
Since \( A \cap B = \{4\} \subset B \subset B \cup C \), by the absorption law:
\[ (A \cap B) \cup (B \cup C) = B \cup C = \{1, 2, 3, 4, 5, 6, 9, 10, 15, 16, 25, 30\} \]
Step 3 — Sum the elements.
\[ 1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 15 + 16 + 25 + 30 \]
Grouping conveniently:
\[ (1 + 9) + (2 + 3 + 5) + (4 + 6) + (10 + 30) + (15 + 16 + 25) = 10 + 10 + 10 + 40 + 56 = 126 \]
Result: The sum of the elements is 126.
Note: The operation \( (A \cap B) \cup (B \cup C) \) simplifies to \( B \cup C \) by absorption, since \( A \cap B \subset B \subset B \cup C \). In general, \( X \cup Y = Y \) whenever \( X \subset Y \).
Exercise 37
Which of the following statements are true?
- (a) \( A \cap (A \cup B’) = A \)
- (b) \( (B \cap C) – A = B \cap (C – A) \)
- (c) \( A \cap (B \cup C \cup D) = (A \cap B) \cup (A \cap C) \cup (A \cap D) \)
Solution:
(a) \( A \cap (A \cup B’) = A \)
By the absorption law: \( A \cap (A \cup X) = A \) for any set \( X \).
This is because every element of \( A \) already belongs to \( A \cup X \), so the intersection removes nothing from \( A \). And no element outside \( A \) can survive the intersection with \( A \).
True. ✓
(b) \( (B \cap C) – A = B \cap (C – A) \)
Expanding both sides:
- Left: \( (B \cap C) – A = B \cap C \cap A’ \)
- Right: \( B \cap (C – A) = B \cap C \cap A’ \)
Both reduce to \( B \cap C \cap A’ \) — a consequence of the associativity of \( \cap \).
True. ✓
(c) \( A \cap (B \cup C \cup D) = (A \cap B) \cup (A \cap C) \cup (A \cap D) \)
This is the generalized distributive law of \( \cap \) over \( \cup \). Applying the distributive law twice:
\[ A \cap (B \cup C \cup D) = A \cap [(B \cup C) \cup D] = [A \cap (B \cup C)] \cup (A \cap D) \] \[ = [(A \cap B) \cup (A \cap C)] \cup (A \cap D) = (A \cap B) \cup (A \cap C) \cup (A \cap D) \]
True. ✓
Summary: All three statements are true.
| Part | Law used |
|---|---|
| (a) | Absorption: \( A \cap (A \cup X) = A \) |
| (b) | Associativity of \( \cap \) |
| (c) | Generalized distributive law |
Exercise 38
Given \( A \subset B \) and \( C \cap A = \emptyset \), simplify:
\[ [A \cup (B – C)] \cap [B \cup (C – A)] \]
Solution:
Step 1 — Derive consequences of the hypotheses.
From \( A \subset B \):
- \( A \cup B = B \)
- \( A \cap B = A \)
From \( C \cap A = \emptyset \):
- \( C – A = C \) (nothing to remove)
- \( A \subset C’ \) (every element of \( A \) lies outside \( C \))
Combining: \( A \subset B \) and \( A \subset C’ \), so \( A \subset B \cap C’ = B – C \).
Step 2 — Simplify \( A \cup (B – C) \).
Since \( A \subset B – C \), by absorption:
\[ A \cup (B – C) = B – C \]
Step 3 — Simplify \( B \cup (C – A) \).
Since \( C – A = C \):
\[ B \cup (C – A) = B \cup C \]
Step 4 — Compute the intersection.
\[ (B – C) \cap (B \cup C) \]
Writing \( B – C = B \cap C’ \):
\[ (B \cap C’) \cap (B \cup C) \]
By absorption, \( B \cap (B \cup C) = B \), so:
\[ = B \cap C’ \cap (B \cup C) = (B \cap (B \cup C)) \cap C’ = B \cap C’ = B – C \]
Result:
\[ [A \cup (B – C)] \cap [B \cup (C – A)] = B – C \]
∎
Exercise 39
How many of the following statements are true?
- (a) \( (A \cap A’) \cup A = A \)
- (b) \( (A \cup B)’ = A’ \cap B’ \)
- (c) \( A – B = A \cap B’ \)
- (d) \( A \subset B \iff A’ \subset B’ \)
- (e) \( A \cap (B \cup C) = (A \cup C) \cap (B \cup C) \)
- (f) \( (A \cup B) – (B \cap A) = (A – B) \cup (B – A) \)
Solution:
(a) \( (A \cap A’) \cup A = A \)
\( A \cap A’ = \emptyset \), so \( \emptyset \cup A = A \). True. ✓
(b) \( (A \cup B)’ = A’ \cap B’ \)
De Morgan’s Law. True. ✓
(c) \( A – B = A \cap B’ \)
The definition of set difference. True. ✓
(d) \( A \subset B \iff A’ \subset B’ \)
Counterexample: Let \( U = \{1, 2, 3\} \), \( A = \{1\} \), \( B = \{1, 2\} \).
- \( A \subset B \): \( \{1\} \subset \{1, 2\} \). True. ✓
- \( A’ \subset B’ \): \( \{2, 3\} \subset \{3\} \)? False (\( 2 \notin \{3\} \)). ✗
The correct relation is \( A \subset B \iff B’ \subset A’ \) (contrapositive — the sets swap). False. ✗
(e) \( A \cap (B \cup C) = (A \cup C) \cap (B \cup C) \)
The right-hand side factors: \( (A \cup C) \cap (B \cup C) = (A \cap B) \cup C \).
The left-hand side: \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \).
These are not equal in general.
Counterexample: \( A = \{1\} \), \( B = \{2\} \), \( C = \{3\} \):
- Left: \( \{1\} \cap \{2, 3\} = \emptyset \)
- Right: \( \{1, 3\} \cap \{2, 3\} = \{3\} \)
False. ✗
(f) \( (A \cup B) – (B \cap A) = (A – B) \cup (B – A) \)
Both sides are the symmetric difference \( A \triangle B \):
- Left: \( (A \cup B) – (A \cap B) = A \triangle B \) (by definition)
- Right: \( (A – B) \cup (B – A) = A \triangle B \) (equivalent definition)
True. ✓
Answer: 4 of the 6 statements are true: (a), (b), (c), and (f).
Exercise 40
Let \( U = \{x \in \mathbb{N} \mid 0 < x < 11\} \), \( A = \{1, 2, 3, 4, 5\} \), \( B = \{x \in U \mid x = 2k,\ k \in U\} \). Which of the following statements are false?
- (a) \( (A’ \cap B’) \neq U – \{9\} \)
- (b) \( (A \cup B)’ = \{x \in U \mid x^2 – 16x + 63 = 0\} \)
- (c) \( (A – B)’ \neq A’ \cup (A \cap B) \)
- (d) \( B – A \neq \{8, 10\} \)
Solution:
Step 1 — Determine the sets.
\[ U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} \] \[ A = \{1, 2, 3, 4, 5\}, \quad A’ = \{6, 7, 8, 9, 10\} \]
For \( B \): \( x = 2k \) with \( k \in U \) — the even elements of \( U \):
\[ B = \{2, 4, 6, 8, 10\}, \quad B’ = \{1, 3, 5, 7, 9\} \]
Step 2 — Evaluate each statement.
(a) \( (A’ \cap B’) \neq U – \{9\} \)
By De Morgan: \( A’ \cap B’ = (A \cup B)’ \).
\[ A \cup B = \{1, 2, 3, 4, 5, 6, 8, 10\} \implies (A \cup B)’ = \{7, 9\} \] \[ U – \{9\} = \{1, 2, 3, 4, 5, 6, 7, 8, 10\} \]
\( \{7, 9\} \neq \{1, 2, 3, 4, 5, 6, 7, 8, 10\} \). The inequality holds. The statement is true. ✓
(b) \( (A \cup B)’ = \{x \in U \mid x^2 – 16x + 63 = 0\} \)
We already know \( (A \cup B)’ = \{7, 9\} \). Solving the equation:
\[ x^2 – 16x + 63 = 0 \implies x = \frac{16 \pm \sqrt{256 – 252}}{2} = \frac{16 \pm 2}{2} \implies x = 9 \text{ or } x = 7 \]
\( \{7, 9\} = \{7, 9\} \). The statement is true. ✓
(c) \( (A – B)’ \neq A’ \cup (A \cap B) \)
Computing both sides:
- \( A – B = \{1, 3, 5\} \implies (A – B)’ = \{2, 4, 6, 7, 8, 9, 10\} \)
- \( A \cap B = \{2, 4\} \)
- \( A’ \cup (A \cap B) = \{6, 7, 8, 9, 10\} \cup \{2, 4\} = \{2, 4, 6, 7, 8, 9, 10\} \)
The two sides are equal, but the statement claims they are different. The statement is false. ✗
Why they match: This is a general identity: \( (A – B)’ = A’ \cup B \) (De Morgan). And \( A’ \cup B = A’ \cup (A \cap B) \), because \( B = (A \cap B) \cup (B \cap A’) \), and the term \( B \cap A’ \) is absorbed into \( A’ \) upon union.
(d) \( B – A \neq \{8, 10\} \)
\[ B – A = \{2, 4, 6, 8, 10\} – \{1, 2, 3, 4, 5\} = \{6, 8, 10\} \]
\( \{6, 8, 10\} \neq \{8, 10\} \). The inequality holds. The statement is true. ✓
Answer: Only statement (c) is false.
Exercise 41
Let:
- \( A = \left\{x \in \mathbb{N} \mid x = \frac{1}{2}(k^2 – 1),\ k \in \mathbb{N}\right\} \)
- \( B = \{x \in \mathbb{N} \mid x^2 = 8x\} \)
- \( C = \{x \in \mathbb{N} \mid x^2 – 32x + 192 < 0\} \)
Find \( (B – A) \cap C \).
Solution:
Finding \( A \):
We evaluate \( x = \frac{1}{2}(k^2 – 1) \) for \( k \in \mathbb{N} \) and check when \( x \) is a natural number:
| \( k \) | \( k^2 – 1 \) | \( x = \frac{1}{2}(k^2 – 1) \) | \( x \in \mathbb{N} \)? |
|---|---|---|---|
| 1 | 0 | 0 | — |
| 2 | 3 | 3/2 | No |
| 3 | 8 | 4 | Yes ✓ |
| 4 | 15 | 15/2 | No |
| 5 | 24 | 12 | Yes ✓ |
| 6 | 35 | 35/2 | No |
| 7 | 48 | 24 | Yes ✓ |
| 9 | 80 | 40 | Yes ✓ |
Pattern: Only odd values of \( k \) yield natural numbers. Setting \( k = 2m + 1 \):
\[ x = \frac{(2m+1)^2 – 1}{2} = \frac{4m^2 + 4m}{2} = 2m(m+1) \]
\[ A = \{4, 12, 24, 40, 60, \ldots\} \]
Finding \( B \):
\[ x^2 = 8x \implies x(x – 8) = 0 \implies x = 0 \text{ or } x = 8 \]
Taking \( x \in \mathbb{N} \):
\[ B = \{8\} \]
Finding \( C \):
We solve \( x^2 – 32x + 192 < 0 \). The roots are:
\[ x = \frac{32 \pm \sqrt{1024 – 768}}{2} = \frac{32 \pm 16}{2} \implies x = 8 \text{ or } x = 24 \]
The parabola is negative strictly between the roots:
\[ C = \{9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23\} \]
Final computation:
- \( B – A = \{8\} \) (since \( 8 \notin A \)) ✓
- \( (B – A) \cap C = \{8\} \cap \{9, 10, \ldots, 23\} = \emptyset \)
The value 8 is a root of \( x^2 – 32x + 192 = 0 \), so the strict inequality fails there: \( 8^2 – 32(8) + 192 = 0 \not< 0 \). Therefore \( 8 \notin C \).
\[ (B – A) \cap C = \emptyset \]
Exercise 42
Let \( A = \{a, \emptyset, \{a\}\} \) and \( B = \{\{a\}, \{\{a\}\}\} \). Which of the following statements are true?
- (a) \( (A \cup B) – (A \cap B) = \{a, \emptyset, \{\{a\}\}\} \)
- (b) The number of elements of \( \mathcal{P}(A) \) is 8
- (c) \( \mathcal{P}(A) \cap \mathcal{P}(B) = \{\{\{a\}\}, \emptyset\} \)
Solution:
Identifying the elements:
| Set | Elements | Count |
|---|---|---|
| \( A \) | \( a \), \( \emptyset \), \( \{a\} \) | 3 |
| \( B \) | \( \{a\} \), \( \{\{a\}\} \) | 2 |
The only common element is \( \{a\} \):
\[ A \cap B = \{\{a\}\}, \qquad A \cup B = \{a, \emptyset, \{a\}, \{\{a\}\}\} \]
(a) \( (A \cup B) – (A \cap B) = A \triangle B \)
\[ A \triangle B = \{a, \emptyset, \{a\}, \{\{a\}\}\} – \{\{a\}\} = \{a, \emptyset, \{\{a\}\}\} \]
This matches the claim. True. ✓
(b) \( |\mathcal{P}(A)| = 8 \)
\( A \) has 3 elements, so \( |\mathcal{P}(A)| = 2^3 = 8 \). True. ✓
The 8 subsets of \( A = \{a, \emptyset, \{a\}\} \) are:
\[ \mathcal{P}(A) = \{\emptyset, \{a\}, \{\emptyset\}, \{\{a\}\}, \{a, \emptyset\}, \{a, \{a\}\}, \{\emptyset, \{a\}\}, \{a, \emptyset, \{a\}\}\} \]
(c) \( \mathcal{P}(A) \cap \mathcal{P}(B) = \{\{\{a\}\}, \emptyset\} \)
\( \mathcal{P}(A) \cap \mathcal{P}(B) \) contains the sets that are subsets of both \( A \) and \( B \).
\[ \mathcal{P}(B) = \{\emptyset, \{\{a\}\}, \{\{\{a\}\}\}, \{\{a\}, \{\{a\}\}\}\} \]
Checking which are also in \( \mathcal{P}(A) \):
| \( X \in \mathcal{P}(B) \) | \( X \subset A \)? | \( X \in \mathcal{P}(A) \cap \mathcal{P}(B) \)? |
|---|---|---|
| \( \emptyset \) | Yes (always) | Yes ✓ |
| \( \{\{a\}\} \) | Yes (\( \{a\} \in A \)) | Yes ✓ |
| \( \{\{\{a\}\}\} \) | No (\( \{\{a\}\} \notin A \)) | No |
| \( \{\{a\}, \{\{a\}\}\} \) | No (\( \{\{a\}\} \notin A \)) | No |
\[ \mathcal{P}(A) \cap \mathcal{P}(B) = \{\emptyset, \{\{a\}\}\} \]
This matches the claim. True. ✓
Answer: All three statements are true.
Exercise 43
How many of the following statements are true?
- (a) \( (A – B) – C = A – (B \cup C) \)
- (b) \( ((A’)’)’ = U – A \)
- (c) \( (A \cap B’) \cup A = A \)
- (d) \( (A’ \cup B’) \cap A = B \)
- (e) \( (A’ \cup B) – C = (A \cup C)’ \cup (B – C) \)
Solution:
(a) \( (A – B) – C = A – (B \cup C) \)
- Left: \( (A \cap B’) \cap C’ = A \cap B’ \cap C’ \)
- Right: \( A \cap (B \cup C)’ = A \cap B’ \cap C’ \) (De Morgan)
Both equal \( A \cap B’ \cap C’ \). True. ✓
(b) \( ((A’)’)’ = U – A \)
Applying complement three times: \( A’ \to A \to A’ \):
\[ ((A’)’)’ = (A)’ = A’ = U – A \]
True. ✓
(c) \( (A \cap B’) \cup A = A \)
Since \( A \cap B’ \subset A \), by the absorption law (\( X \cup A = A \) when \( X \subset A \)):
True. ✓
(d) \( (A’ \cup B’) \cap A = B \)
Distributing the intersection:
\[ (A’ \cup B’) \cap A = (A’ \cap A) \cup (B’ \cap A) = \emptyset \cup (A \cap B’) = A – B \]
The expression simplifies to \( A – B \), not \( B \).
Counterexample: \( A = \{1, 2\} \), \( B = \{2, 3\} \):
\[ (A’ \cup B’) \cap A = A – B = \{1\} \neq \{2, 3\} = B \]
False. ✗
(e) \( (A’ \cup B) – C = (A \cup C)’ \cup (B – C) \)
- Left: \( (A’ \cup B) \cap C’ = (A’ \cap C’) \cup (B \cap C’) \) (distributive law)
- Right: \( (A \cup C)’ \cup (B – C) = (A’ \cap C’) \cup (B \cap C’) \) (De Morgan)
Both reduce to \( (A’ \cap C’) \cup (B \cap C’) \). True. ✓
Answer: 4 of the 5 statements are true: (a), (b), (c), and (e). Only (d) is false.
Exercise 44
Given the proposition: \( (x \notin A \wedge x \in B) \vee x \in C \). Which of the following are equivalent to its negation?
- (a) \( x \in (A \cup B’) \cap C’ \)
- (b) \( x \in (A – C) \cup (B \cup C)’ \)
- (c) \( (x \in A \wedge x \in C) \wedge x \notin (B \cup C) \)
Solution:
Step 1 — Negate the original proposition.
\[ \neg[(x \notin A \wedge x \in B) \vee x \in C] \]
Applying De Morgan to the disjunction:
\[ = \neg(x \notin A \wedge x \in B) \wedge \neg(x \in C) \]
Applying De Morgan to the conjunction:
\[ = (x \in A \vee x \notin B) \wedge x \notin C \]
Translating into set notation:
\[ = x \in (A \cup B’) \wedge x \in C’ = x \in (A \cup B’) \cap C’ \quad \cdots (\ast) \]
Step 2 — Check each option.
(a) \( x \in (A \cup B’) \cap C’ \)
Matches \( (\ast) \) exactly. True. ✓
(b) \( x \in (A – C) \cup (B \cup C)’ \)
Simplifying:
\[ (A – C) \cup (B \cup C)’ = (A \cap C’) \cup (B’ \cap C’) = (A \cup B’) \cap C’ \]
Matches \( (\ast) \). True. ✓
(c) \( (x \in A \wedge x \in C) \wedge x \notin (B \cup C) \)
Translating:
\[ x \in A \cap C \cap (B \cup C)’ = x \in A \cap C \cap B’ \cap C’ \]
But \( C \cap C’ = \emptyset \), so this reduces to \( x \in \emptyset \), which is always false — it cannot be equivalent to the negation, which is satisfiable in general.
False. ✗
Answer: Options (a) and (b) are equivalent to the negation. Option (c) contains an internal contradiction (\( C \cap C’ = \emptyset \)) that makes it always false.
Exercise 45
Which of the following statements are true?
- (1) \( A \cap (C – B)’ \) is the same as \( A \cap (B \cup C)’ \).
- (2) \( A = \{x \in \mathbb{Q} \mid 10x^2 = 13x + 3\} \) is a singleton, or \( B = \{x \in \mathbb{R} – \{0\} \mid -x = x^{-1}\} \) is empty.
- (3) If \( x \in \mathbb{R} \) and \( A = \{a \in \mathbb{R} \mid 4x^2 – 2ax + 3 + a \text{ is a perfect square trinomial}\} \), then \( A \subset \{a \in \mathbb{Z} \mid a^3 + 24 = 6a^2 + 4a\} \).
Solution:
(1) We compare algebraically:
\[ (C – B)’ = (C \cap B’)’ = C’ \cup B \quad \text{(De Morgan)} \] \[ A \cap (C – B)’ = A \cap (C’ \cup B) \]
While:
\[ A \cap (B \cup C)’ = A \cap B’ \cap C’ \]
These are not equal in general.
Counterexample: \( A = \{1, 2, 3\} \), \( B = \{2\} \), \( C = \{3\} \):
- \( A \cap (C – B)’ = \{1, 2, 3\} \cap \{3\}’ = \{1, 2\} \)
- \( A \cap (B \cup C)’ = \{1, 2, 3\} \cap \{2, 3\}’ = \{1\} \)
\( \{1, 2\} \neq \{1\} \). False. ✗
(2) We evaluate each part of the disjunction.
For \( A \): \( 10x^2 – 13x – 3 = 0 \)
\[ x = \frac{13 \pm \sqrt{169 + 120}}{20} = \frac{13 \pm 17}{20} \implies x_1 = \frac{3}{2},\quad x_2 = -\frac{1}{5} \]
Both are rational, so \( A = \{3/2, -1/5\} \) has 2 elements — not a singleton. ✗
For \( B \): \( -x = x^{-1} \implies -x^2 = 1 \implies x^2 = -1 \)
No real solution, so \( B = \emptyset \). ✓
The disjunction: (False) \( \vee \) (True) = True. ✓
(3) For \( 4x^2 – 2ax + (3 + a) \) to be a perfect square trinomial, its discriminant must be zero:
\[ \Delta = 4a^2 – 16(3 + a) = 4a^2 – 16a – 48 = 0 \implies a^2 – 4a – 12 = 0 \]
\[ a = \frac{4 \pm 8}{2} \implies a_1 = 6,\quad a_2 = -2 \]
\[ A = \{-2, 6\} \]
Now we check whether \( A \subset \{a \in \mathbb{Z} \mid a^3 + 24 = 6a^2 + 4a\} \):
\[ a^3 – 6a^2 – 4a + 24 = 0 \implies a^2(a – 6) – 4(a – 6) = 0 \implies (a^2 – 4)(a – 6) = 0 \] \[ (a-2)(a+2)(a-6) = 0 \implies a \in \{-2, 2, 6\} \]
Since \( A = \{-2, 6\} \subset \{-2, 2, 6\} \). ✓
True. ✓
Answer: Statements (2) and (3) are true. Only (1) is false.
Exercise 46
Prove that each of the following statements is true:
- (a) \( A \subset C \implies A \cup (B \cap C) = (A \cup B) \cap C \)
- (b) \( A \cup (B \cap A) = A \cap (B \cup A) = A \)
- (c) \( B = A’ \iff A \cup B = U \wedge A \cap B = \emptyset \)
- (d) \( A \cup [B \cap (A \cup C)] = A \cup (B \cap C) \)
Proofs:
(a) \( A \subset C \implies A \cup (B \cap C) = (A \cup B) \cap C \)
Applying the distributive law to the left-hand side:
\[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \]
Now using the hypothesis \( A \subset C \), which implies \( A \cup C = C \):
\[ = (A \cup B) \cap C \]
∎
(b) \( A \cup (B \cap A) = A \cap (B \cup A) = A \)
First equality: Since \( B \cap A \subset A \), by the absorption law: \[ A \cup (B \cap A) = A \]
Second equality: Since \( A \subset B \cup A \), by the absorption law: \[ A \cap (B \cup A) = A \]
Both are instances of the absorption laws: \( X \cup (Y \cap X) = X \) and \( X \cap (Y \cup X) = X \). ∎
(c) \( B = A’ \iff A \cup B = U \wedge A \cap B = \emptyset \)
\( (\Rightarrow) \) If \( B = A’ \):
\[ A \cup A’ = U \quad ✓ \qquad A \cap A’ = \emptyset \quad ✓ \]
\( (\Leftarrow) \) If \( A \cup B = U \) and \( A \cap B = \emptyset \):
From \( A \cap B = \emptyset \): no element of \( B \) is in \( A \), so \( B \subset A’ \).
From \( A \cup B = U \): every element of \( U \) is in \( A \) or \( B \). If \( x \notin A \), then \( x \in B \), so \( A’ \subset B \).
From \( B \subset A’ \) and \( A’ \subset B \) we conclude \( B = A’ \). ∎
Interpretation: The complement of \( A \) is the only set that is simultaneously disjoint from \( A \) and covers all of \( U \) together with \( A \).
(d) \( A \cup [B \cap (A \cup C)] = A \cup (B \cap C) \)
Distributing \( B \) inside the parentheses:
\[ B \cap (A \cup C) = (B \cap A) \cup (B \cap C) \]
Substituting:
\[ A \cup [(B \cap A) \cup (B \cap C)] = A \cup (B \cap A) \cup (B \cap C) \]
Since \( B \cap A \subset A \), it is absorbed:
\[ = A \cup (B \cap C) \]
∎
Exercise 47
Which of the following propositions about sets are always true?
- (a) \( A \subset B \iff A \cup B = B \)
- (b) \( A \subset B’ \iff B \subset A’ \)
- (c) \( A \cap B = \emptyset \to A \subset B’ \)
- (d) \( (A \cup B’)’ = B – A \)
Solution:
(a) \( A \subset B \iff A \cup B = B \)
\( (\Rightarrow) \) If \( A \subset B \): every element of \( A \) is already in \( B \), so \( A \cup B = B \). ✓
\( (\Leftarrow) \) If \( A \cup B = B \): since \( A \subset A \cup B \), we get \( A \subset B \). ✓
Always true. ✓
(b) \( A \subset B’ \iff B \subset A’ \)
Both conditions are equivalent to \( A \cap B = \emptyset \):
- \( A \subset B’ \): every element of \( A \) lies outside \( B \), i.e., \( A \cap B = \emptyset \).
- \( B \subset A’ \): every element of \( B \) lies outside \( A \), i.e., \( B \cap A = \emptyset \).
Since \( A \cap B = B \cap A \), the two are equivalent. Always true. ✓
(c) \( A \cap B = \emptyset \to A \subset B’ \)
If \( A \cap B = \emptyset \), no element of \( A \) belongs to \( B \). By definition of complement, every element of \( A \) is in \( B’ \), so \( A \subset B’ \).
Always true. ✓
Note: The converse is also true (as seen in (b)), so the implication in (c) is actually a biconditional: \( A \cap B = \emptyset \iff A \subset B’ \).
(d) \( (A \cup B’)’ = B – A \)
Applying De Morgan:
\[ (A \cup B’)’ = A’ \cap (B’)’ = A’ \cap B = B \cap A’ = B – A \]
Always true. ✓
Answer: All four propositions are always true.
Exercise 48
Given \( U = \{a, b, c, d, e\} \), \( A \cup B = \{a, b, c, d\} \), \( A \cap B = \{a, c\} \), and \( A – B = \{b\} \). Find \( A \) and \( B \).
Solution:
Step 1 — Reconstruct \( A \).
Every element of \( A \) is either in \( A \cap B \) (shared with \( B \)) or in \( A – B \) (exclusive to \( A \)):
\[ A = (A \cap B) \cup (A – B) = \{a, c\} \cup \{b\} = \{a, b, c\} \]
Step 2 — Find \( B – A \).
The elements exclusive to \( B \) are those in \( A \cup B \) but not in \( A \):
\[ B – A = (A \cup B) – A = \{a, b, c, d\} – \{a, b, c\} = \{d\} \]
Step 3 — Reconstruct \( B \).
By the same logic as Step 1:
\[ B = (A \cap B) \cup (B – A) = \{a, c\} \cup \{d\} = \{a, c, d\} \]
Verification:
| Operation | Computed | Expected | ✓ |
|---|---|---|---|
| \( A \cup B \) | \( \{a, b, c, d\} \) | \( \{a, b, c, d\} \) | ✓ |
| \( A \cap B \) | \( \{a, c\} \) | \( \{a, c\} \) | ✓ |
| \( A – B \) | \( \{b\} \) | \( \{b\} \) | ✓ |
Result:
\[ A = \{a, b, c\}, \qquad B = \{a, c, d\} \]
General method: Any set decomposes into its shared part and its exclusive part: \( X = (X \cap Y) \cup (X – Y) \). Given \( A \cap B \), \( A – B \), and \( A \cup B \), both \( A \) and \( B \) can be uniquely reconstructed.
Exercise 49
Prove that the proposition \( p: x \in [A – (C – B)]’ \) is equivalent to \( q: x \notin [A \cap (C’ \cup B)] \).
Proof:
Step 1 — Interpret \( p \).
\[ x \in [A – (C – B)]’ \iff x \notin A – (C – B) \]
Belonging to the complement of a set is the same as not belonging to that set.
Step 2 — Simplify \( A – (C – B) \).
First, the inner parenthesis:
\[ C – B = C \cap B’ \]
Then the outer difference:
\[ A – (C \cap B’) = A \cap (C \cap B’)’ \]
Applying De Morgan:
\[ (C \cap B’)’ = C’ \cup B \]
Therefore:
\[ A – (C – B) = A \cap (C’ \cup B) \]
Step 3 — Substitute.
\[ p: x \in [A – (C – B)]’ \iff x \notin [A – (C – B)] \iff x \notin [A \cap (C’ \cup B)] \]
This is exactly \( q \). Therefore \( p \iff q \). ∎
In brief: The equivalence reduces to the single algebraic identity \( A – (C – B) = A \cap (C’ \cup B) \). Proposition \( p \) says “not in that set” (by the complement), which is precisely what \( q \) says.
Exercise 50
Let:
- \( M = \{-3,\ -2/3,\ 0,\ 1/2,\ 2,\ \sqrt{2},\ 3+\sqrt{2},\ 2i\} \)
- \( A = \{x \in M \mid x \notin M \to x \notin \mathbb{Z}\} \)
- \( B = \{x \in M \mid x \in \mathbb{R} \iff x \in \mathbb{I}\} \)
- \( D = \{x \in M \mid x \in \mathbb{C} \wedge x \notin \mathbb{Q}\} \)
Find \( (A \cap \mathbb{C}) \cup (B – A) \).
Solution:
Classifying the elements of \( M \):
| Element | \( \mathbb{Z} \) | \( \mathbb{Q} \) | \( \mathbb{I} \) | \( \mathbb{R} \) | \( \mathbb{C} \) |
|---|---|---|---|---|---|
| \( -3 \) | ✓ | ✓ | ✓ | ✓ | |
| \( -2/3 \) | ✓ | ✓ | ✓ | ||
| \( 0 \) | ✓ | ✓ | ✓ | ✓ | |
| \( 1/2 \) | ✓ | ✓ | ✓ | ||
| \( 2 \) | ✓ | ✓ | ✓ | ✓ | |
| \( \sqrt{2} \) | ✓ | ✓ | ✓ | ||
| \( 3+\sqrt{2} \) | ✓ | ✓ | ✓ | ||
| \( 2i \) | ✓ |
Finding \( A \):
The condition is \( x \notin M \to x \notin \mathbb{Z} \). Since every \( x \) under consideration already belongs to \( M \) (by the clause \( x \in M \)), the hypothesis \( x \notin M \) is always false.
An implication with a false hypothesis is vacuously true: \( \text{F} \to q \equiv \text{T} \) for any \( q \).
\[ A = M \]
Finding \( B \):
The condition is \( x \in \mathbb{R} \iff x \in \mathbb{I} \) (real if and only if irrational):
| Element | \( x \in \mathbb{R} \) | \( x \in \mathbb{I} \) | \( \mathbb{R} \iff \mathbb{I} \) | \( \in B \)? |
|---|---|---|---|---|
| \( -3 \) | T | F | F | No |
| \( -2/3 \) | T | F | F | No |
| \( 0 \) | T | F | F | No |
| \( 1/2 \) | T | F | F | No |
| \( 2 \) | T | F | F | No |
| \( \sqrt{2} \) | T | T | T | Yes ✓ |
| \( 3+\sqrt{2} \) | T | T | T | Yes ✓ |
| \( 2i \) | F | F | T | Yes ✓ |
\[ B = \{\sqrt{2},\ 3 + \sqrt{2},\ 2i\} \]
Note on \( 2i \): it satisfies \( \text{F} \iff \text{F} = \text{T} \). It is neither real nor irrational, so the biconditional holds.
Finding \( D \):
Since \( x \in \mathbb{C} \) holds for every element of \( M \), the condition reduces to \( x \notin \mathbb{Q} \):
\[ D = \{\sqrt{2},\ 3 + \sqrt{2},\ 2i\} = B \]
Note: \( B \) and \( D \) have different definitions but produce the same set.
Final computation:
- \( A \cap \mathbb{C} = M \cap \mathbb{C} = M \) (every element of \( M \) is a complex number)
- \( B – A = B – M = \emptyset \) (since \( B \subset M = A \))
\[ (A \cap \mathbb{C}) \cup (B – A) = M \cup \emptyset = M \]
Result:
\[ (A \cap \mathbb{C}) \cup (B – A) = \{-3,\ -2/3,\ 0,\ 1/2,\ 2,\ \sqrt{2},\ 3+\sqrt{2},\ 2i\} = M \]
Key takeaways from this exercise:
- Vacuous truth (\( \text{F} \to q = \text{T} \)) forces \( A = M \), which dominates the final result.
- The biconditional in \( B \) includes \( 2i \) via \( \text{F} \iff \text{F} = \text{T} \) — a non-obvious case.
- The sets \( B \) and \( D \), defined very differently, turn out to be identical.
Exercise 52
Given the custom logical operators \( p * q \equiv p \to \neg q \) and \( p \diamond q \equiv \neg p \to \neg q \), and the sets:
- \( A = \{-9, -\sqrt{2}, 0.\overline{3}, \pi, 6, 3i\} \)
- \( B = \{x \in A \mid x \in \mathbb{Z} \to x \notin \mathbb{R}\} \)
- \( D = \{x \in A \mid x \in \mathbb{Q}\ *\ x \in \mathbb{I}\} \)
- \( E = \{x \in A \mid x \in \mathbb{C}\ \diamond\ x \in \mathbb{N}\} \)
Find \( (A \cup B) \cap (D – E) \).
Solution:
Step 1 — Classify the elements of \( A \).
| Element | \( \mathbb{N} \) | \( \mathbb{Z} \) | \( \mathbb{Q} \) | \( \mathbb{I} \) | \( \mathbb{R} \) | \( \mathbb{C} \) |
|---|---|---|---|---|---|---|
| \( -9 \) | ✓ | ✓ | ✓ | ✓ | ||
| \( -\sqrt{2} \) | ✓ | ✓ | ✓ | |||
| \( 0.\overline{3} \) | ✓ | ✓ | ✓ | |||
| \( \pi \) | ✓ | ✓ | ✓ | |||
| \( 6 \) | ✓ | ✓ | ✓ | ✓ | ✓ | |
| \( 3i \) | ✓ |
Step 2 — Find \( B \): condition \( x \in \mathbb{Z} \to x \notin \mathbb{R} \).
| Element | \( x \in \mathbb{Z} \) | \( x \notin \mathbb{R} \) | \( p \to q \) | \( \in B \)? |
|---|---|---|---|---|
| \( -9 \) | T | F | F | No ✗ |
| \( -\sqrt{2} \) | F | F | T | Yes ✓ |
| \( 0.\overline{3} \) | F | F | T | Yes ✓ |
| \( \pi \) | F | F | T | Yes ✓ |
| \( 6 \) | T | F | F | No ✗ |
| \( 3i \) | F | T | T | Yes ✓ |
\[ B = \{-\sqrt{2}, 0.\overline{3}, \pi, 3i\} \]
*Step 3 — Find \( D \): condition \( x \in \mathbb{Q}\ \ x \in \mathbb{I} \).
Decoding: \( p * q \equiv p \to \neg q \), so the condition is:
\[ x \in \mathbb{Q} \to \neg(x \in \mathbb{I}) \equiv x \in \mathbb{Q} \to x \notin \mathbb{I} \]
This is always true: \( \mathbb{Q} \) and \( \mathbb{I} \) are disjoint — no number is both rational and irrational.
\[ D = A \]
Step 4 — Find \( E \): condition \( x \in \mathbb{C}\ \diamond\ x \in \mathbb{N} \).
Decoding: \( p \diamond q \equiv \neg p \to \neg q \), so the condition is:
\[ x \notin \mathbb{C} \to x \notin \mathbb{N} \]
Its contrapositive is \( x \in \mathbb{N} \to x \in \mathbb{C} \), which is always true since \( \mathbb{N} \subset \mathbb{C} \).
\[ E = A \]
Step 5 — Final computation.
\[ D – E = A – A = \emptyset \]
\[ (A \cup B) \cap (D – E) = (A \cup B) \cap \emptyset = \emptyset \]
\[ (A \cup B) \cap (D – E) = \emptyset \]
Key observations:
- The operator \( * \) applied to \( \mathbb{Q} \) and \( \mathbb{I} \) yields a universal mathematical truth (rationals and irrationals are disjoint), making \( D = A \).
- The operator \( \diamond \) applied to \( \mathbb{C} \) and \( \mathbb{N} \) also yields a universal truth (\( \mathbb{N} \subset \mathbb{C} \)), making \( E = A \).
- \( D = E = A \) implies \( D – E = \emptyset \), which nullifies the entire expression.
Exercise 53
Which of the following propositions are equivalent to the negation of \( x \in [C \cup (B – A)] \)?
- (a) \( x \in [(B – A)’ – C] \)
- (b) \( x \in [(A – C) \cup (B \cup C)’] \)
- (c) \( x \in [A \cup (B \cup C)’] \)
Solution:
Step 1 — Compute the negation.
\[ \neg(x \in [C \cup (B – A)]) \iff x \in [C \cup (B – A)]’ \]
Applying De Morgan:
\[ [C \cup (B – A)]’ = C’ \cap (B – A)’ \]
Since \( (B – A)’ = (B \cap A’)’ = B’ \cup A \):
\[ = C’ \cap (B’ \cup A) = (C’ \cap B’) \cup (C’ \cap A) = (B \cup C)’ \cup (A \cap C’) \]
That is:
\[ = (A – C) \cup (B \cup C)’ \quad \cdots (\ast) \]
Step 2 — Check each option.
(a) \( (B – A)’ – C = (B – A)’ \cap C’ \)
\[ = (B’ \cup A) \cap C’ = (B’ \cap C’) \cup (A \cap C’) = (B \cup C)’ \cup (A – C) \]
Matches \( (\ast) \). Equivalent. ✓
(b) \( (A – C) \cup (B \cup C)’ \)
\[ = (A \cap C’) \cup (B’ \cap C’) \]
Matches \( (\ast) \) directly. Equivalent. ✓
(c) \( A \cup (B \cup C)’ \)
Here \( A \) appears instead of \( A – C = A \cap C’ \). The difference: \( A \) includes elements of \( C \), while \( A – C \) excludes them.
Counterexample: \( U = \{1, 2, 3, 4\} \), \( A = \{1, 2\} \), \( B = \{3\} \), \( C = \{2\} \):
- \( (\ast) = (A – C) \cup (B \cup C)’ = \{1\} \cup \{1, 4\} = \{1, 4\} \)
- Option (c): \( A \cup (B \cup C)’ = \{1, 2\} \cup \{1, 4\} = \{1, 2, 4\} \)
\( \{1, 4\} \neq \{1, 2, 4\} \). Not equivalent. ✗
Answer: Options (a) and (b) are equivalent to the negation. Option (c) fails by not excluding elements of \( C \) from \( A \).
Exercise 54
Let \( A * B = (A – B’) \cup B \). Prove that:
- (a) \( A * B = B * A \implies A = B \)
- (b) \( (A * B) * C = A * (B * C) \)
- (c) \( A * (B \cup C) = (A * B) \cup (A * C) \)
Solution:
Key step — Simplify \( A * B \).
Before tackling each part, let’s simplify the operation:
\[ A * B = (A – B’) \cup B \]
Rewriting \( A – B’ = A \cap (B’)’ = A \cap B \):
\[ A * B = (A \cap B) \cup B \]
Since \( A \cap B \subset B \), by the absorption law:
\[ A * B = B \]
The operation \( * \) simply returns its second argument. The entire exercise reduces to this observation.
Proof of (a): \( A * B = B * A \implies A = B \)
\[ A * B = B \qquad \text{and} \qquad B * A = A \]
If \( A * B = B * A \), then \( B = A \). ∎
Proof of (b): \( (A * B) * C = A * (B * C) \)
- Left: \( (A * B) * C = B * C = C \)
- Right: \( A * (B * C) = A * C = C \)
Both sides equal \( C \). ∎
Proof of (c): \( A * (B \cup C) = (A * B) \cup (A * C) \)
- Left: \( A * (B \cup C) = B \cup C \)
- Right: \( (A * B) \cup (A * C) = B \cup C \)
Both sides equal \( B \cup C \). ∎
Note: The operation \( * \) is a projection onto its second argument. This makes it trivially associative (b) and distributive over \( \cup \) (c). It commutes only when \( A = B \) (a), showing that commutativity is not automatic.
Exercise 55
Let \( A = \{1, 2, 3\} \), \( B = \{x \in \mathbb{Z} \mid x^2 – x – 6 = 0\} \), \( C = \{x \in \mathbb{N} \mid 2 < x < 6\} \), \( D = C – (A \cap B) \). How many elements does \( \mathcal{P}[\mathcal{P}(D)] \) have?
Solution:
Step 1 — Find \( B \).
\[ x^2 – x – 6 = 0 \implies (x – 3)(x + 2) = 0 \implies x = 3 \text{ or } x = -2 \]
\[ B = \{-2, 3\} \]
Step 2 — Find \( C \).
\[ C = \{x \in \mathbb{N} \mid 2 < x < 6\} = \{3, 4, 5\} \]
Step 3 — Compute \( D \).
\[ A \cap B = \{1, 2, 3\} \cap \{-2, 3\} = \{3\} \]
\[ D = C – (A \cap B) = \{3, 4, 5\} – \{3\} = \{4, 5\} \]
Step 4 — Compute \( \mathcal{P}(D) \).
\( |D| = 2 \), so \( |\mathcal{P}(D)| = 2^2 = 4 \):
\[ \mathcal{P}(D) = \{\emptyset, \{4\}, \{5\}, \{4, 5\}\} \]
Step 5 — Compute \( |\mathcal{P}[\mathcal{P}(D)]| \).
\( |\mathcal{P}(D)| = 4 \), so:
\[ |\mathcal{P}[\mathcal{P}(D)]| = 2^4 = 16 \]
Result: \( \mathcal{P}[\mathcal{P}(D)] \) has 16 elements.
Chain of cardinalities: \( |D| = 2 \xrightarrow{2^n} |\mathcal{P}(D)| = 4 \xrightarrow{2^n} |\mathcal{P}[\mathcal{P}(D)]| = 16 \). Each application of the power set operation squares the previous count.
Exercise 56
Given sets \( A \), \( B \), \( C \) with \( C \subset A’ \), prove that:
\[ \{[(C \cup B) \cap A] \cup C’\} \cap B = B \cap C’ \]
Proof:
Step 1 — Consequence of the hypothesis.
\( C \subset A’ \) means every element of \( C \) lies outside \( A \), so:
\[ C \cap A = \emptyset \qquad \text{and equivalently} \qquad A \subset C’ \]
(If \( x \in A \), then \( x \notin C \): were \( x \in C \subset A’ \), we’d have \( x \in A’ \), a contradiction.)
Step 2 — Simplify \( (C \cup B) \cap A \).
Distributing:
\[ (C \cup B) \cap A = (C \cap A) \cup (B \cap A) = \emptyset \cup (A \cap B) = A \cap B \]
Step 3 — Substitute and distribute.
\[ [(A \cap B) \cup C’] \cap B \]
Distributing \( \cap B \):
\[ = (A \cap B \cap B) \cup (C’ \cap B) = (A \cap B) \cup (B \cap C’) \]
Step 4 — Apply absorption.
Since \( A \subset C’ \) (Step 1), we have \( A \cap B \subset C’ \cap B = B \cap C’ \).
By absorption (\( X \cup Y = Y \) when \( X \subset Y \)):
\[ (A \cap B) \cup (B \cap C’) = B \cap C’ \]
∎
Summary: \( C \subset A’ \implies C \cap A = \emptyset \) wipes out a term in Step 2, and \( A \subset C’ \) absorbs \( A \cap B \) in Step 4. Both consequences flow from the single hypothesis.
Exercise 57
Given sets \( A \) and \( B \). Which of the following statements are true?
- (a) \( A \cup B = (A \triangle B) \triangle (A \cap B) \)
- (b) \( A \cap B = A \triangle (A \cup B) \)
- (c) \( A \cap B = (A \cup B) – (A \triangle B) \)
Solution:
(a) \( A \cup B = (A \triangle B) \triangle (A \cap B) \)
Let \( X = A \triangle B = (A \cup B) – (A \cap B) \) and \( Y = A \cap B \). Computing \( X \triangle Y \):
- \( X \cup Y = [(A \cup B) – (A \cap B)] \cup (A \cap B) = A \cup B \) (reuniting what was excluded recovers the whole)
- \( X \cap Y = [(A \cup B) – (A \cap B)] \cap (A \cap B) = \emptyset \) (the symmetric difference and the intersection are disjoint by construction)
\[ X \triangle Y = (X \cup Y) – (X \cap Y) = (A \cup B) – \emptyset = A \cup B \]
True. ✓
Interpretation: \( A \triangle B \) and \( A \cap B \) form a partition of \( A \cup B \). Their symmetric difference (which equals their union since they’re disjoint) reconstructs \( A \cup B \).
(b) \( A \cap B = A \triangle (A \cup B) \)
\[ A \triangle (A \cup B) = [A – (A \cup B)] \cup [(A \cup B) – A] \]
- \( A – (A \cup B) = \emptyset \) (since \( A \subset A \cup B \))
- \( (A \cup B) – A = B – A \)
\[ A \triangle (A \cup B) = B – A \]
Counterexample: \( A = \{1, 2\} \), \( B = \{2, 3\} \):
\[ A \triangle (A \cup B) = \{3\} = B – A \neq \{2\} = A \cap B \]
False. ✗
(c) \( A \cap B = (A \cup B) – (A \triangle B) \)
Using \( A \triangle B = (A \cup B) – (A \cap B) \):
\[ (A \cup B) – (A \triangle B) = (A \cup B) – [(A \cup B) – (A \cap B)] \]
Applying the identity \( X – (X – Y) = X \cap Y \):
\[ = (A \cup B) \cap (A \cap B) = A \cap B \]
(The last equality holds because \( A \cap B \subset A \cup B \).)
True. ✓
Answer: Statements (a) and (c) are true. Only (b) is false — it gives \( B – A \) rather than \( A \cap B \).
Summary of symmetric difference identities:
Expression Simplifies to \( (A \triangle B) \triangle (A \cap B) \) \( A \cup B \) \( A \triangle (A \cup B) \) \( B – A \) (not \( A \cap B \)) \( (A \cup B) – (A \triangle B) \) \( A \cap B \)
Exercise 58
Given sets \( A \), \( B \), and \( C \), simplify:
- (a) \( [(A \cap B) \cup C’]’ \cup (B \cup C) \)
- (b) \( \{[C \cup (B – A’)] \cap [B – (C \cup A)’]’\} \cup B \)
Solution of (a):
Step 1 — Applying De Morgan to the complement:
\[ [(A \cap B) \cup C’]’ = (A \cap B)’ \cap (C’)’ = (A’ \cup B’) \cap C \]
Step 2 — Substituting:
\[ [(A’ \cup B’) \cap C] \cup (B \cup C) \]
Step 3 — Since \( (A’ \cup B’) \cap C \subset C \subset B \cup C \), by absorption:
\[ = B \cup C \]
∎
Solution of (b):
Step 1 — Simplify the inner parts.
\[ B – A’ = B \cap (A’)’ = B \cap A = A \cap B \]
\[ (C \cup A)’ = C’ \cap A’ \quad \text{(De Morgan)} \]
\[ B – (C \cup A)’ = B \cap [(C \cup A)’]’ = B \cap (C \cup A) \]
\[ [B – (C \cup A)’]’ = [B \cap (C \cup A)]’ \quad \text{(taking the complement)} \]
Step 2 — The expression inside \( \{\} \) becomes:
\[ [C \cup (A \cap B)] \cap [B \cap (C \cup A)]’ \]
Step 3 — Analyze by membership in \( B \).
Let \( R = \{[C \cup (A \cap B)] \cap [B \cap (C \cup A)]’\} \cup B \). Since the full expression ends with \( \cup B \), every element of \( B \) belongs to \( R \). We only need to check which elements outside \( B \) are added.
For \( x \notin B \):
- \( x \in C \cup (A \cap B) \): since \( x \notin B \), the term \( A \cap B \) contributes nothing. This reduces to \( x \in C \).
- \( x \in [B \cap (C \cup A)]’ \): since \( x \notin B \), automatically \( x \notin B \cap (C \cup A) \), so \( x \) belongs to the complement. Always true. ✓
Conclusion: An element outside \( B \) belongs to \( R \) if and only if \( x \in C \).
Combining both cases:
\[ R = B \cup C \]
∎
Note: Both parts, despite their apparent complexity, simplify to the same result: \( B \cup C \). The case-analysis technique in (b) (splitting on \( x \in B \) vs. \( x \notin B \)) avoids long algebraic manipulation when the expression ends with \( \cup B \).
Exercise 59
Given sets \( A \), \( B \), and \( C \) in \( U \), simplify:
\[ [A \triangle (B \triangle C)] \triangle [C \triangle B’] \]
Solution:
We use the algebraic properties of \( \triangle \):
| Property | Statement |
|---|---|
| Associativity | \( (X \triangle Y) \triangle Z = X \triangle Y \triangle Z \) |
| Commutativity | \( X \triangle Y = Y \triangle X \) |
| Self-inverse | \( X \triangle X = \emptyset \) |
| Identity | \( X \triangle \emptyset = X \) |
| Complement | \( X \triangle X’ = U \) |
| Universal | \( X \triangle U = X’ \) |
Step 1 — Drop parentheses by associativity.
\[ A \triangle (B \triangle C) \triangle (C \triangle B’) = A \triangle B \triangle C \triangle C \triangle B’ \]
Step 2 — Cancel \( C \triangle C \).
\[ = A \triangle B \triangle \emptyset \triangle B’ = A \triangle B \triangle B’ \]
Step 3 — Apply \( B \triangle B’ = U \).
\[ = A \triangle U \]
Step 4 — Apply \( X \triangle U = X’ \).
\[ = A’ \]
Result:
\[ [A \triangle (B \triangle C)] \triangle [C \triangle B’] = A’ \]
∎
Verification of \( X \triangle U = X’ \): \( X \triangle U = (X \cup U) – (X \cap U) = U – X = X’ \).
Verification of \( X \triangle X’ = U \): \( X \triangle X’ = (X \cup X’) – (X \cap X’) = U – \emptyset = U \).
Exercise 60
Given \( A \subset B \), simplify:
\[ A \cap \{[(B \cup A) \cap C \cap B’] \cup A’ \cup B’\} \]
Solution:
Step 1 — Since \( A \subset B \), we have \( B \cup A = B \):
\[ (B \cup A) \cap C \cap B’ = B \cap C \cap B’ \]
Step 2 — Since \( B \cap B’ = \emptyset \):
\[ B \cap C \cap B’ = \emptyset \]
Step 3 — The expression inside \( \{\} \) becomes:
\[ \emptyset \cup A’ \cup B’ = A’ \cup B’ \]
Step 4 — Since \( A \subset B \), we have \( B’ \subset A’ \), so by absorption \( A’ \cup B’ = A’ \):
\[ A’ \cup B’ = A’ \]
Step 5 — Final result:
\[ A \cap A’ = \emptyset \]
∎
Exercise 61
Let \( A = \{3, \emptyset\} \), \( B = \{\{3\}, \emptyset, \{3, \emptyset\}\} \), and \( C = \{\{\emptyset\}, \{3\}\} \). Find \( \mathcal{P}(A) – [B \cap \mathcal{P}(C)] \).
Solution:
Step 1 — Compute \( \mathcal{P}(A) \).
\( A = \{3, \emptyset\} \) has 2 elements, so \( |\mathcal{P}(A)| = 4 \):
\[ \mathcal{P}(A) = \{\emptyset, \{3\}, \{\emptyset\}, \{3, \emptyset\}\} \]
Step 2 — Compute \( \mathcal{P}(C) \).
\( C = \{\{\emptyset\}, \{3\}\} \) has 2 elements, so \( |\mathcal{P}(C)| = 4 \):
\[ \mathcal{P}(C) = \{\emptyset, \{\{\emptyset\}\}, \{\{3\}\}, \{\{\emptyset\}, \{3\}\}\} \]
Step 3 — Compute \( B \cap \mathcal{P}(C) \).
We check which elements of \( B = \{\{3\}, \emptyset, \{3, \emptyset\}\} \) also belong to \( \mathcal{P}(C) \):
| Element of \( B \) | \( \in \mathcal{P}(C) \)? | Reason |
|---|---|---|
| \( \{3\} \) | No ✗ | \( \{3\} \neq \{\{3\}\} \): contains the number 3, not the set \( \{3\} \) |
| \( \emptyset \) | Yes ✓ | \( \emptyset \in \mathcal{P}(X) \) for every \( X \) |
| \( \{3, \emptyset\} \) | No ✗ | \( \{3, \emptyset\} \neq \{\{\emptyset\}, \{3\}\} \): different elements |
\[ B \cap \mathcal{P}(C) = \{\emptyset\} \]
Key distinction: \( \{3\} \) (the set containing the number 3) is different from \( \{\{3\}\} \) (the set containing the set \( \{3\} \)). Similarly, \( \{3, \emptyset\} \) contains 3 and \( \emptyset \), while \( \{\{\emptyset\}, \{3\}\} \) contains \( \{\emptyset\} \) and \( \{3\} \) — one level deeper.
Step 4 — Compute \( \mathcal{P}(A) – [B \cap \mathcal{P}(C)] \).
\[ \{\emptyset, \{3\}, \{\emptyset\}, \{3, \emptyset\}\} – \{\emptyset\} = \{\{3\}, \{\emptyset\}, \{3, \emptyset\}\} \]
Result:
\[ \mathcal{P}(A) – [B \cap \mathcal{P}(C)] = \{\{3\}, \{\emptyset\}, \{3, \emptyset\}\} \]
Exercise 62
Simplify:
\[ [(A \cup B) – (C – A)] \cap [(A \cap B) – (A \cap C)] \]
Solution:
Step 1 — Simplify the first factor.
\[ (A \cup B) – (C – A) = (A \cup B) \cap (C – A)’ \]
Since \( (C – A)’ = (C \cap A’)’ = C’ \cup A \):
\[ = (A \cup B) \cap (A \cup C’) \]
By the distributive law:
\[ = A \cup (B \cap C’) \]
Step 2 — Simplify the second factor.
\[ (A \cap B) – (A \cap C) = (A \cap B) \cap (A \cap C)’ \]
Applying De Morgan, \( (A \cap C)’ = A’ \cup C’ \):
\[ = (A \cap B) \cap (A’ \cup C’) = \underbrace{(A \cap B \cap A’)}_{\emptyset} \cup (A \cap B \cap C’) = A \cap B \cap C’ \]
Step 3 — Compute the intersection.
\[ [A \cup (B \cap C’)] \cap [A \cap B \cap C’] \]
Since \( A \cap B \cap C’ \subset A \) and \( A \cap B \cap C’ \subset B \cap C’ \), we have:
\[ A \cap B \cap C’ \subset A \cup (B \cap C’) \]
The intersection of a set with a larger set that contains it equals the smaller one:
\[ = A \cap B \cap C’ \]
Result:
\[ [(A \cup B) – (C – A)] \cap [(A \cap B) – (A \cap C)] = A \cap B \cap C’ = (A \cap B) – C \]
∎
Exercise 63
Given sets \( A \), \( B \), \( C \), \( D \) with \( C \subset A’ \), \( A \subset B’ \), and \( C \cup D = D \). Simplify:
\[ [(A’ \cup B’) \cap (C’ \cup D’)] \cup \{[(C \cup B) \cap A] \cup C’\} \cap B \]
Solution:
Step 1 — Extract consequences of the hypotheses.
| Hypothesis | Consequences |
|---|---|
| \( C \subset A’ \) | \( C \cap A = \emptyset \) and \( A \subset C’ \) |
| \( A \subset B’ \) | \( A \cap B = \emptyset \) and \( B \subset A’ \) |
| \( C \cup D = D \) | \( C \subset D \), hence \( C \cap D = C \) |
Step 2 — Simplify the first part: \( (A’ \cup B’) \cap (C’ \cup D’) \).
By De Morgan: \( A’ \cup B’ = (A \cap B)’ \) and \( C’ \cup D’ = (C \cap D)’ \).
- \( A \cap B = \emptyset \) (from \( A \subset B’ \)), so \( (A \cap B)’ = U \)
- \( C \cap D = C \) (from \( C \subset D \)), so \( (C \cap D)’ = C’ \)
\[ (A’ \cup B’) \cap (C’ \cup D’) = U \cap C’ = C’ \]
Step 3 — Simplify the second part: \( \{[(C \cup B) \cap A] \cup C’\} \cap B \).
Distributing \( (C \cup B) \cap A \):
\[ (C \cap A) \cup (B \cap A) = \emptyset \cup \emptyset = \emptyset \]
(Both are empty by the hypotheses.) So:
\[ \{\emptyset \cup C’\} \cap B = C’ \cap B \]
Step 4 — Combine both parts.
\[ C’ \cup (C’ \cap B) \]
Since \( C’ \cap B \subset C’ \), by absorption:
\[ = C’ \]
Result:
\[ [(A’ \cup B’) \cap (C’ \cup D’)] \cup \{[(C \cup B) \cap A] \cup C’\} \cap B = C’ \]
∎
Exercise 64
Given \( A \subset B \) and \( C \cap A = \emptyset \), simplify:
\[ \{[A \cup (B – C)] \cap [B \cup (C – A)]\} \cup \{(A – B) \triangle C\} \]
Solution:
Consequences of the hypotheses:
- \( A \subset B \implies A – B = \emptyset \) and \( A \cup B = B \)
- \( C \cap A = \emptyset \implies C – A = C \) and \( A \subset C’ \), hence \( A \subset B \cap C’ = B – C \)
Simplifying the first part: \( [A \cup (B – C)] \cap [B \cup (C – A)] \)
Since \( A \subset B – C \): \( A \cup (B – C) = B – C \) (absorption).
Since \( C – A = C \): \( B \cup (C – A) = B \cup C \).
\[ (B – C) \cap (B \cup C) \]
Writing \( B – C = B \cap C’ \) and applying absorption (\( B \cap (B \cup C) = B \)):
\[ (B \cap C’) \cap (B \cup C) = B \cap C’ = B – C \]
Simplifying the second part: \( (A – B) \triangle C \)
Since \( A \subset B \): \( A – B = \emptyset \). Therefore:
\[ \emptyset \triangle C = C \]
Combining both parts:
\[ (B – C) \cup C \]
Applying \( (X – Y) \cup Y = X \cup Y \):
\[ = B \cup C \]
Result:
\[ \{[A \cup (B – C)] \cap [B \cup (C – A)]\} \cup \{(A – B) \triangle C\} = B \cup C \]
∎
Note: The first part (already simplified in Exercise 38) gives \( B – C \), and the second gives \( C \). Their union \( (B – C) \cup C = B \cup C \) recovers the full union of \( B \) and \( C \), regardless of \( A \).
Exercise 65
Given \( A \cap B \cap C = \emptyset \), simplify:
\[ (A – B) \cup (B – C) \cup (C – A) \]
Solution:
Step 1 — Identify what gets excluded.
An element \( x \) does not belong to \( (A – B) \cup (B – C) \cup (C – A) \) if and only if:
\[ x \notin A – B \wedge x \notin B – C \wedge x \notin C – A \]
This is equivalent to:
\[ (x \notin A \vee x \in B) \wedge (x \notin B \vee x \in C) \wedge (x \notin C \vee x \in A) \]
That is: \( A \to B \), \( B \to C \), \( C \to A \). This circular chain is satisfied only when \( x \) belongs to all three or to none:
\[ x \in (A \cap B \cap C) \cup (A \cup B \cup C)’ \]
Step 2 — Take the complement to get the union.
Therefore:
\[ (A – B) \cup (B – C) \cup (C – A) = (A \cup B \cup C) – (A \cap B \cap C) \]
Step 3 — Apply the hypothesis \( A \cap B \cap C = \emptyset \).
\[ = (A \cup B \cup C) – \emptyset = A \cup B \cup C \]
Result:
\[ (A – B) \cup (B – C) \cup (C – A) = A \cup B \cup C \]
∎
General identity: Without the hypothesis, the expression always equals \( (A \cup B \cup C) – (A \cap B \cap C) \). The condition \( A \cap B \cap C = \emptyset \) simply removes the only thing being subtracted, leaving the full union.
Verification: \( A = \{1,2\} \), \( B = \{2,3\} \), \( C = \{3,1\} \). \( A \cap B \cap C = \emptyset \) ✓. \( (A-B) \cup (B-C) \cup (C-A) = \{1\} \cup \{2\} \cup \{3\} = \{1,2,3\} = A \cup B \cup C \) ✓.
Exercise 66
Let \( A \), \( B \), \( C \) be nonempty sets with \( B \cap C \neq \emptyset \) and \( (B \cup C) – A = \emptyset \). Find:
\[ Z = (A \triangle B) \cup (A \triangle C) \cup (B \triangle C) \]
Solution:
Step 1 — Interpret the hypotheses.
\( (B \cup C) – A = \emptyset \) means \( B \cup C \subset A \), which implies:
\[ B \subset A \qquad \text{and} \qquad C \subset A \]
Step 2 — Simplify each symmetric difference.
Since \( B \subset A \): \( A \triangle B = (A – B) \cup \underbrace{(B – A)}_{\emptyset} = A – B \)
Since \( C \subset A \): \( A \triangle C = (A – C) \cup \underbrace{(C – A)}_{\emptyset} = A – C \)
Step 3 — Combine the first two terms.
\[ (A – B) \cup (A – C) = (A \cap B’) \cup (A \cap C’) = A \cap (B’ \cup C’) = A \cap (B \cap C)’ = A – (B \cap C) \]
Step 4 — Incorporate the third term.
\[ Z = [A – (B \cap C)] \cup (B \triangle C) \]
Since \( B \subset A \) and \( C \subset A \), we have \( B \cup C \subset A \), so:
\[ B \triangle C = (B \cup C) – (B \cap C) \subset A – (B \cap C) \]
By absorption (\( B \triangle C \) is already contained in \( A – (B \cap C) \)):
\[ Z = A – (B \cap C) \]
Result:
\[ Z = (A \triangle B) \cup (A \triangle C) \cup (B \triangle C) = A – (B \cap C) \]
∎
Verification: \( A = \{1,2,3,4,5\} \), \( B = \{1,2,3\} \), \( C = \{2,3,4\} \).
- \( B \cup C = \{1,2,3,4\} \subset A \) ✓, \( B \cap C = \{2,3\} \neq \emptyset \) ✓
- \( A \triangle B = \{4,5\} \), \( A \triangle C = \{1,5\} \), \( B \triangle C = \{1,4\} \)
- \( Z = \{1,4,5\} = A – \{2,3\} = A – (B \cap C) \) ✓
Exercise 67
Using set properties, find \( R \cup S \), where:
\[ R = [A – (B – D)]’ \cap [A’ \triangle (B – D)] \] \[ S = [(B – A) \cup (D – A)] \cup [A \cup (B \triangle D)] \]
Solution:
Simplifying \( R \):
Let \( X = B – D = B \cap D’ \) to keep the notation manageable.
First factor: \( [A – X]’ = (A \cap X’)’ = A’ \cup X \)
Second factor: \( A’ \triangle X = (A’ \cap X’) \cup (A \cap X) \)
Taking the intersection:
\[ R = (A’ \cup X) \cap [(A’ \cap X’) \cup (A \cap X)] \]
Distributing:
- \( (A’ \cup X) \cap (A’ \cap X’) = A’ \cap X’ \) (since \( A’ \cap X’ \subset A’ \subset A’ \cup X \))
- \( (A’ \cup X) \cap (A \cap X) = A \cap X \) (since \( A \cap X \subset X \subset A’ \cup X \))
\[ R = (A’ \cap X’) \cup (A \cap X) \]
This is the set-theoretic biconditional “\( x \in A \iff x \in X \)”, i.e.:
\[ R = (A \triangle X)’ = [A \triangle (B – D)]’ \]
Simplifying \( S \):
First group:
\[ (B – A) \cup (D – A) = (B \cap A’) \cup (D \cap A’) = (B \cup D) \cap A’ = (B \cup D) – A \]
Second group: \( A \cup (B \triangle D) \). Since \( B \triangle D \subset B \cup D \):
Putting both groups together:
\[ S = [(B \cup D) – A] \cup A \cup (B \triangle D) \]
Applying \( (Y – A) \cup A = Y \cup A \):
\[ = (B \cup D) \cup A \cup (B \triangle D) = A \cup B \cup D \]
(\( B \triangle D \) is absorbed into \( B \cup D \).)
Computing \( R \cup S \):
\[ R \cup S = [A \triangle (B – D)]’ \cup (A \cup B \cup D) \]
For any \( x \) outside \( A \cup B \cup D \): since \( x \notin A \) and \( x \notin B \), we have \( x \notin B – D \). So \( x \) belongs to neither \( A \) nor \( B – D \), meaning \( x \notin A \triangle (B – D) \), hence \( x \in [A \triangle (B – D)]’ = R \).
That is: \( (A \cup B \cup D)’ \subset R \).
Combining:
\[ R \cup S \supset R \cup (A \cup B \cup D) \supset (A \cup B \cup D)’ \cup (A \cup B \cup D) = U \]
Result:
\[ R \cup S = U \]
∎
Exercise 68
Given sets \( A \) and \( B \), prove that if \( (A \cup B) \subset [B’ – (A – B)] \), then \( A = \emptyset \wedge B = \emptyset \).
Proof:
Step 1 — Simplify \( B’ – (A – B) \).
\[ A – B = A \cap B’ \]
\[ B’ – (A \cap B’) = B’ \cap (A \cap B’)’ = B’ \cap (A’ \cup B) \]
Distributing:
\[ = (B’ \cap A’) \cup (B’ \cap B) = (A’ \cap B’) \cup \emptyset = A’ \cap B’ \]
By De Morgan:
\[ B’ – (A – B) = (A \cup B)’ \]
Step 2 — Interpret the hypothesis.
The hypothesis \( (A \cup B) \subset [B’ – (A – B)] \) becomes:
\[ A \cup B \subset (A \cup B)’ \]
That is: a set is contained in its own complement.
Step 3 — Conclude.
If \( X \subset X’ \), then for every \( x \in X \) we have \( x \in X’ \), meaning \( x \notin X \) — a contradiction. So \( X \) can have no elements:
\[ X = \emptyset \]
Applying this with \( X = A \cup B \):
\[ A \cup B = \emptyset \]
Since \( A \subset A \cup B \) and \( B \subset A \cup B \):
\[ A = \emptyset \wedge B = \emptyset \]
∎
In brief: The entire proof hinges on one identity: \( B’ – (A – B) = (A \cup B)’ \). The hypothesis then says \( X \subset X’ \), which forces \( X = \emptyset \).
Exercise 69
Given sets \( A \) and \( B \) with \( n(A \cup B) = 30 \), \( n(A – B) = 12 \), and \( n(B – A) = 10 \). Find \( n(A) + n(B) \).
Solution:
Step 1 — Find \( n(A \cap B) \).
The union \( A \cup B \) decomposes into three disjoint parts:
\[ A \cup B = (A – B) \cup (A \cap B) \cup (B – A) \]
Therefore:
\[ n(A \cup B) = n(A – B) + n(A \cap B) + n(B – A) \] \[ 30 = 12 + n(A \cap B) + 10 \] \[ n(A \cap B) = 8 \]
Step 2 — Reconstruct \( n(A) \) and \( n(B) \).
Each set decomposes into its exclusive part plus the intersection:
\[ n(A) = n(A – B) + n(A \cap B) = 12 + 8 = 20 \] \[ n(B) = n(B – A) + n(A \cap B) = 10 + 8 = 18 \]
Result:
\[ n(A) + n(B) = 20 + 18 = 38 \]
Verification: \( n(A) + n(B) – n(A \cap B) = 20 + 18 – 8 = 30 = n(A \cup B) \) ✓
Exercise 70
Given \( n[\mathcal{P}(A)] = 128 \), \( n[\mathcal{P}(B)] = 16 \), and \( n[\mathcal{P}(A \cap B)] = 8 \). Find \( n[\mathcal{P}(A \cup B)] \).
Solution:
Step 1 — Extract the cardinalities of the sets.
Since \( n[\mathcal{P}(X)] = 2^{n(X)} \), we solve for each:
| Given | Equation | Result |
|---|---|---|
| \( n[\mathcal{P}(A)] = 128 \) | \( 2^{n(A)} = 2^7 \) | \( n(A) = 7 \) |
| \( n[\mathcal{P}(B)] = 16 \) | \( 2^{n(B)} = 2^4 \) | \( n(B) = 4 \) |
| \( n[\mathcal{P}(A \cap B)] = 8 \) | \( 2^{n(A \cap B)} = 2^3 \) | \( n(A \cap B) = 3 \) |
Step 2 — Compute \( n(A \cup B) \).
\[ n(A \cup B) = n(A) + n(B) – n(A \cap B) = 7 + 4 – 3 = 8 \]
Step 3 — Compute \( n[\mathcal{P}(A \cup B)] \).
\[ n[\mathcal{P}(A \cup B)] = 2^{n(A \cup B)} = 2^8 = 256 \]
Result:
\[ n[\mathcal{P}(A \cup B)] = 256 \]
Chain: \( 128, 16, 8 \xrightarrow{\log_2} 7, 4, 3 \xrightarrow{+,-} 8 \xrightarrow{2^n} 256 \)
Exercise 71
In a group of 100 students, 49 do not take Sociology and 53 do not take Philosophy. If 27 students take neither course, how many students take exactly one of these courses?
Solution:
Step 1 — Define the sets and extract the data.
Let \( S \) = students taking Sociology, \( F \) = students taking Philosophy, with \( n(U) = 100 \).
| Given | Translation | Value |
|---|---|---|
| 49 do not take Sociology | \( n(S’) = 49 \) | \( n(S) = 51 \) |
| 53 do not take Philosophy | \( n(F’) = 53 \) | \( n(F) = 47 \) |
| 27 take neither | \( n(S \cup F)’ = 27 \) | \( n(S \cup F) = 73 \) |
Step 2 — Find \( n(S \cap F) \).
By inclusion-exclusion:
\[ 73 = 51 + 47 – n(S \cap F) \implies n(S \cap F) = 25 \]
Step 3 — Count those taking exactly one course.
Students taking exactly one course form the symmetric difference \( S \triangle F \):
\[ n(S \triangle F) = n(S \cup F) – n(S \cap F) = 73 – 25 = 48 \]
Breakdown:
| Region | Formula | Students |
|---|---|---|
| Sociology only | \( n(S) – n(S \cap F) \) | \( 51 – 25 = 26 \) |
| Philosophy only | \( n(F) – n(S \cap F) \) | \( 47 – 25 = 22 \) |
| Both courses | \( n(S \cap F) \) | 25 |
| Neither | \( n(S \cup F)’ \) | 27 |
| Total | 100 ✓ |
Result:
\[ \text{Students taking exactly one course} = 26 + 22 = 48 \]
Exercise 72
Given \( n(U) = 360 \), \( n(A) = 120 \), \( n(B) = 150 \), \( n(C) = 100 \), \( n(A \cap C) = 20 \), \( n(A \cap B) = 30 \), \( n(B \cap C) = 25 \), \( n(A \cap B \cap C) = 10 \). Find \( n(L \cap S) \), where:
\[ L = \{x \in U \mid x \in A \iff x \in B\}, \qquad S = \{x \in U \mid x \in A \to x \in C\} \]
Solution:
Step 1 — Compute the cardinality of each Venn diagram region.
Working outward from the triple intersection:
| Region | Description | Computation | Value |
|---|---|---|---|
| \( e \) | \( A \cap B \cap C \) | Given | 10 |
| \( f \) | \( A \cap C \) without \( B \) | \( 20 – 10 \) | 10 |
| \( d \) | \( B \cap C \) without \( A \) | \( 25 – 10 \) | 15 |
| \( b \) | \( A \cap B \) without \( C \) | \( 30 – 10 \) | 20 |
| \( a \) | Only \( A \) | \( 120 – 20 – 10 – 10 \) | 80 |
| \( c \) | Only \( B \) | \( 150 – 20 – 15 – 10 \) | 105 |
| \( g \) | Only \( C \) | \( 100 – 15 – 10 – 10 \) | 65 |
| \( h \) | Outside all three | \( 360 – 305 \) | 55 |
Verification: \( 80 + 20 + 105 + 15 + 10 + 10 + 65 + 55 = 360 \) ✓
Step 2 — Determine which regions belong to \( L \) and \( S \).
| Region | \( x \in A \) | \( x \in B \) | \( x \in C \) | \( A \iff B \) (\( L \)) | \( A \to C \) (\( S \)) |
|---|---|---|---|---|---|
| \( a \) | T | F | F | F ✗ | F ✗ |
| \( b \) | T | T | F | T ✓ | F ✗ |
| \( c \) | F | T | F | F ✗ | T ✓ |
| \( d \) | F | T | T | F ✗ | T ✓ |
| \( e \) | T | T | T | T ✓ | T ✓ |
| \( f \) | T | F | T | F ✗ | T ✓ |
| \( g \) | F | F | T | T ✓ | T ✓ |
| \( h \) | F | F | F | T ✓ | T ✓ |
Summary:
- \( L \) = regions \( b, e, g, h \) (where \( A \) and \( B \) agree: both in or both out)
- \( S \) = regions \( c, d, e, f, g, h \) (where being in \( A \) implies being in \( C \))
Step 3 — Compute \( n(L \cap S) \).
\( L \cap S \) = regions in both: \( e, g, h \).
\[ n(L \cap S) = n(e) + n(g) + n(h) = 10 + 65 + 55 = 130 \]
Result:
\[ n(L \cap S) = 130 \]
Interpretation: The 130 elements of \( L \cap S \) are those that simultaneously (1) stand in the same relation to both \( A \) and \( B \) (biconditional), and (2) whenever they’re in \( A \) they’re also in \( C \) (conditional). Only three regions satisfy both conditions: the triple intersection (\( e \)), those only in \( C \) (\( g \)), and those outside everything (\( h \)).
Exercise 73
Three sets \( A \), \( B \), and \( C \) have \( n \), \( 3n \), and \( n – 1 \) elements respectively, with \( n(A \cap B) = n/2 \), \( n(A \cap C) = n/4 \), \( n(B \cap C) = 2 \), and \( n(A \cap B \cap C) = 1 \). Find the number of elements of \( K = [(A \cup B) – (A \cap B)] – C \).
Solution:
Step 1 — Recognize that \( K = (A \triangle B) – C \).
\[ K = (A \cup B) – (A \cap B) – C = (A \triangle B) – C \]
That is, the elements belonging to exactly one of \( A \) or \( B \), but not to \( C \).
Step 2 — Compute each exclusive region of the Venn diagram.
Using \( \alpha \) (only \( A \)), \( \beta \) (\( A \cap B \) without \( C \)), \( \gamma \) (only \( B \)), \( \delta = A \cap B \cap C = 1 \), \( \varepsilon \) (\( A \cap C \) without \( B \)), \( \zeta \) (\( B \cap C \) without \( A \)), \( \eta \) (only \( C \)):
| Intersection | Equation | Exclusive region |
|---|---|---|
| \( n(A \cap B) = n/2 \) | \( \beta + 1 = n/2 \) | \( \beta = n/2 – 1 \) |
| \( n(A \cap C) = n/4 \) | \( \varepsilon + 1 = n/4 \) | \( \varepsilon = n/4 – 1 \) |
| \( n(B \cap C) = 2 \) | \( \zeta + 1 = 2 \) | \( \zeta = 1 \) |
| Set | Equation | Only-region |
|---|---|---|
| \( n(A) = n \) | \( \alpha + (n/2-1) + 1 + (n/4-1) = n \) | \( \alpha = n/4 + 1 \) |
| \( n(B) = 3n \) | \( \gamma + (n/2-1) + 1 + 1 = 3n \) | \( \gamma = 5n/2 – 1 \) |
| \( n(C) = n-1 \) | \( \eta + (n/4-1) + 1 + 1 = n-1 \) | \( \eta = 3n/4 – 2 \) |
Step 3 — Identify the regions of \( K \).
\( A \triangle B \) covers regions \( \alpha, \varepsilon, \gamma, \zeta \). Removing \( C \) eliminates \( \varepsilon \) and \( \zeta \) (which lie inside \( C \)):
\[ K = \{\text{regions } \alpha, \gamma\} \]
Step 4 — Compute \( n(K) \).
\[ n(K) = \alpha + \gamma = \left(\frac{n}{4} + 1\right) + \left(\frac{5n}{2} – 1\right) = \frac{n + 10n}{4} = \frac{11n}{4} \]
Result:
\[ n(K) = \frac{11n}{4} \]
Note: For the problem to make sense, \( n \) must be a multiple of 4 (so all cardinalities are positive integers). The minimum case is \( n = 4 \), giving \( n(K) = 11 \).
Exercise 74
The number of people who drink beverage \( A \) is 190, beverage \( B \) is 110, and beverage \( C \) is 150. The number who drink only \( C \) is half those who drink only \( B \) and one third of those who drink only \( A \). The number who drink only \( B \) and \( C \) (not \( A \)) is half those who drink only \( A \) and \( B \) (not \( C \)). The number who drink all three is one third of those who drink only \( A \) and \( C \) (not \( B \)). How many people drink exactly one beverage?
Solution:
Step 1 — Express all regions in terms of three variables.
Let \( x \) = only \( C \), \( y \) = only \( B \cap C \) (not \( A \)), \( z = n(A \cap B \cap C) \).
| Condition | Translation | Region |
|---|---|---|
| Only \( C \) = \( \frac{1}{2} \)(only \( B \)) | Only \( B = 2x \) | \( 2x \) |
| Only \( C \) = \( \frac{1}{3} \)(only \( A \)) | Only \( A = 3x \) | \( 3x \) |
| Only \( B \cap C \) = \( \frac{1}{2} \)(only \( A \cap B \)) | Only \( A \cap B = 2y \) | \( 2y \) |
| \( n(ABC) \) = \( \frac{1}{3} \)(only \( A \cap C \)) | Only \( A \cap C = 3z \) | \( 3z \) |
Venn diagram — the 7 regions:
| Region | Variable |
|---|---|
| Only \( A \) | \( 3x \) |
| Only \( A \cap B \) (not \( C \)) | \( 2y \) |
| Only \( B \) | \( 2x \) |
| \( A \cap B \cap C \) | \( z \) |
| Only \( A \cap C \) (not \( B \)) | \( 3z \) |
| Only \( B \cap C \) (not \( A \)) | \( y \) |
| Only \( C \) | \( x \) |
Step 2 — Set up the system of equations.
Summing the regions for each set:
\[ n(A) = 3x + 2y + z + 3z = 3x + 2y + 4z = 190 \quad \cdots (1) \] \[ n(B) = 2x + 2y + z + y = 2x + 3y + z = 110 \quad \cdots (2) \] \[ n(C) = x + 3z + z + y = x + y + 4z = 150 \quad \cdots (3) \]
Step 3 — Solve the system.
Subtracting (1) \( – \) (3): \( 2x + y = 40 \cdots (4) \)
From (4): \( y = 40 – 2x \). Substituting into (3):
\[ x + (40 – 2x) + 4z = 150 \implies 4z = 110 + x \implies z = \frac{110 + x}{4} \]
Substituting \( y \) and \( z \) into (2):
\[ 2x + 3(40 – 2x) + \frac{110 + x}{4} = 110 \implies -4x + 120 + \frac{110 + x}{4} = 110 \]
Multiplying by 4:
\[ -16x + 480 + 110 + x = 440 \implies -15x = -150 \implies x = 10 \]
So \( y = 20 \) and \( z = 30 \).
Step 4 — Verification.
| Region | Value | Set | Sum | Expected | ✓ | |
|---|---|---|---|---|---|---|
| Only \( A \) | 30 | \( n(A) \) | \( 30+40+30+90 \) | 190 | ✓ | |
| Only \( A \cap B \) | 40 | \( n(B) \) | \( 20+40+30+20 \) | 110 | ✓ | |
| Only \( B \) | 20 | \( n(C) \) | \( 10+90+30+20 \) | 150 | ✓ | |
| \( A \cap B \cap C \) | 30 | |||||
| Only \( A \cap C \) | 90 | |||||
| Only \( B \cap C \) | 20 | |||||
| Only \( C \) | 10 |
Result:
\[ \text{People drinking exactly one beverage} = 3x + 2x + x = 6x = 6(10) = \mathbf{60} \]
Exercise 75
Given sets \( A \) and \( B \) with \( n(A \cup B) = 24 \), \( n(A – B) = 10 \), and \( n(B – A) = 6 \). Find \( 5n(A) – 4n(B) \).
Solution:
Step 1 — Find \( n(A \cap B) \).
\[ 24 = 10 + n(A \cap B) + 6 \implies n(A \cap B) = 8 \]
Step 2 — Reconstruct the cardinalities.
\[ n(A) = 10 + 8 = 18, \qquad n(B) = 6 + 8 = 14 \]
Step 3 — Compute.
\[ 5n(A) – 4n(B) = 5(18) – 4(14) = 90 – 56 = 34 \]
Result:
\[ 5n(A) – 4n(B) = 34 \]
Exercise 76
Given \( n(A) = 4 \), \( n(B) = 3 \), and \( n(A \cap B) = 2 \). Find:
\[ n[\mathcal{P}(A) \cup \mathcal{P}(B)] + n[\mathcal{P}(A \cup B)] \]
Solution:
Step 1 — Basic cardinalities.
\[ n(A \cup B) = 4 + 3 – 2 = 5 \]
| Set | Cardinality | \( n[\mathcal{P}(\cdot)] = 2^n \) |
|---|---|---|
| \( A \) | 4 | 16 |
| \( B \) | 3 | 8 |
| \( A \cap B \) | 2 | 4 |
| \( A \cup B \) | 5 | 32 |
Step 2 — Compute \( n[\mathcal{P}(A) \cup \mathcal{P}(B)] \).
By inclusion-exclusion:
\[ n[\mathcal{P}(A) \cup \mathcal{P}(B)] = n[\mathcal{P}(A)] + n[\mathcal{P}(B)] – n[\mathcal{P}(A) \cap \mathcal{P}(B)] \]
Key property: \( \mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B) \), since a set is a subset of both \( A \) and \( B \) if and only if it is a subset of \( A \cap B \).
\[ n[\mathcal{P}(A) \cup \mathcal{P}(B)] = 16 + 8 – 4 = 20 \]
Step 3 — Add.
\[ n[\mathcal{P}(A) \cup \mathcal{P}(B)] + n[\mathcal{P}(A \cup B)] = 20 + 32 = 52 \]
Result:
\[ n[\mathcal{P}(A) \cup \mathcal{P}(B)] + n[\mathcal{P}(A \cup B)] = 52 \]
Key identity: \( \mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B) \) is a fundamental result linking the intersection of power sets to the power set of the intersection — it’s what allows inclusion-exclusion to be applied to power sets directly.
Exercise 77
Given \( n(U) = 44 \), \( n(A) = 21 \), \( n(B) = 17 \), \( n(A \cap C) = 14 \), \( n(B \cap C) = 12 \), \( n(A \cap B \cap C’) = 3 \), \( n(A \cap B \cap C) = 5 \), and \( n(A \cup B \cup C)’ = 6 \). Find \( n(C) \).
Note: The original problem states \( n(A \cap B) = 14 \), which contradicts the data \( n(A \cap B \cap C’) = 3 \) and \( n(A \cap B \cap C) = 5 \), since \( n(A \cap B) = 3 + 5 = 8 \neq 14 \). The correct datum is \( n(A \cap C) = 14 \), which makes the system consistent.
Solution:
Step 1 — Compute each Venn diagram region.
Using \( \alpha \) (only \( A \)), \( \beta \) (\( A \cap B \) without \( C \)), \( \gamma \) (only \( B \)), \( \delta \) (\( B \cap C \) without \( A \)), \( \varepsilon = A \cap B \cap C = 5 \), \( \varphi \) (\( A \cap C \) without \( B \)), \( \eta \) (only \( C \)):
| Given | Equation | Result |
|---|---|---|
| \( n(A \cap B \cap C’) = 3 \) | \( \beta = 3 \) | \( \beta = 3 \) |
| \( n(A \cap C) = 14 \) | \( \varphi + 5 = 14 \) | \( \varphi = 9 \) |
| \( n(B \cap C) = 12 \) | \( \delta + 5 = 12 \) | \( \delta = 7 \) |
| \( n(A) = 21 \) | \( \alpha + 3 + 5 + 9 = 21 \) | \( \alpha = 4 \) |
| \( n(B) = 17 \) | \( \gamma + 3 + 5 + 7 = 17 \) | \( \gamma = 2 \) |
| \( n(A \cup B \cup C) = 38 \) | \( 4+3+2+7+5+9+\eta = 38 \) | \( \eta = 8 \) |
Step 2 — Verification.
| \( \alpha \) | \( \beta \) | \( \gamma \) | \( \delta \) | \( \varepsilon \) | \( \varphi \) | \( \eta \) | outside |
|---|---|---|---|---|---|---|---|
| 4 | 3 | 2 | 7 | 5 | 9 | 8 | 6 |
- \( n(A) = 4 + 3 + 5 + 9 = 21 \) ✓
- \( n(B) = 2 + 3 + 5 + 7 = 17 \) ✓
- \( n(A \cap C) = 9 + 5 = 14 \) ✓
- \( n(B \cap C) = 7 + 5 = 12 \) ✓
- Total \( = 4+3+2+7+5+9+8+6 = 44 \) ✓
Step 3 — Compute \( n(C) \).
\[ n(C) = \varphi + \varepsilon + \delta + \eta = 9 + 5 + 7 + 8 = 29 \]
Result:
\[ n(C) = 29 \]
Exercise 78
Given \( n(A) = 8 \), \( n(B) = 8 \), \( n(C) = 5 \), \( n(D) = 5 \). The maximum number of elements of \( A \cup C \) is \( k \), and the maximum number of elements of \( B \cap D \) is \( h \). Find \( h \cdot k \).
Solution:
Finding \( k \) — maximum of \( n(A \cup C) \).
\[ n(A \cup C) = n(A) + n(C) – n(A \cap C) \]
\( n(A \cup C) \) is maximized when \( n(A \cap C) \) is minimized, i.e., when \( A \cap C = \emptyset \):
\[ k = 8 + 5 – 0 = 13 \]
Finding \( h \) — maximum of \( n(B \cap D) \).
\( n(B \cap D) \) is maximized when the smaller set is completely contained in the larger, i.e., \( D \subset B \):
\[ h = \min(n(B), n(D)) = \min(8, 5) = 5 \]
Result:
\[ h \cdot k = 5 \times 13 = 65 \]
General principles:
- \( n(X \cup Y)_{\max} = n(X) + n(Y) \) (when \( X \cap Y = \emptyset \))
- \( n(X \cap Y)_{\max} = \min(n(X), n(Y)) \) (when one contains the other)
Exercise 79
Given finite sets \( A \), \( B \), and \( C \), prove that:
\[ n[(A \triangle B) \cup C] = n(A) + n(B) + n(C) – 2n(A \cap B) – n(A \cap C) – n(B \cap C) + 2n(A \cap B \cap C) \]
Proof:
Step 1 — Apply inclusion-exclusion to \( (A \triangle B) \cup C \).
\[ n[(A \triangle B) \cup C] = n(A \triangle B) + n(C) – n[(A \triangle B) \cap C] \]
Step 2 — Compute \( n(A \triangle B) \).
\[ n(A \triangle B) = n(A \cup B) – n(A \cap B) = [n(A) + n(B) – n(A \cap B)] – n(A \cap B) \] \[ = n(A) + n(B) – 2n(A \cap B) \quad \cdots (\ast) \]
Step 3 — Compute \( n[(A \triangle B) \cap C] \).
\[ (A \triangle B) \cap C = [(A \cap B’) \cup (B \cap A’)] \cap C = (A \cap B’ \cap C) \cup (B \cap A’ \cap C) \]
These two parts are disjoint (no element can be in both \( B’ \) and \( B \)):
\[ n[(A \triangle B) \cap C] = n(A \cap B’ \cap C) + n(B \cap A’ \cap C) \]
Expressing each term using known intersections:
\[ n(A \cap B’ \cap C) = n(A \cap C) – n(A \cap B \cap C) \] \[ n(B \cap A’ \cap C) = n(B \cap C) – n(A \cap B \cap C) \]
Therefore:
\[ n[(A \triangle B) \cap C] = n(A \cap C) + n(B \cap C) – 2n(A \cap B \cap C) \quad \cdots (\ast\ast) \]
Step 4 — Substitute \( (\ast) \) and \( (\ast\ast) \).
\[ n[(A \triangle B) \cup C] = [n(A) + n(B) – 2n(A \cap B)] + n(C) – [n(A \cap C) + n(B \cap C) – 2n(A \cap B \cap C)] \]
\[ = n(A) + n(B) + n(C) – 2n(A \cap B) – n(A \cap C) – n(B \cap C) + 2n(A \cap B \cap C) \]
∎
Comparison with classical inclusion-exclusion: In \( n(A \cup B \cup C) \), the coefficients are \( +1, +1, +1, -1, -1, -1, +1 \). Here, replacing \( A \cup B \) with \( A \triangle B \) changes the coefficient of \( n(A \cap B) \) from \( -1 \) to \( -2 \) and that of \( n(A \cap B \cap C) \) from \( +1 \) to \( +2 \). Symmetric difference doubly penalizes the intersection.
Exercise 80
Given finite sets \( A \), \( B \), and \( C \) that are pairwise non-disjoint, prove that:
\[ n[(A \triangle B) \triangle C] = n(A) + n(B) + n(C) – 2n(A \cap B) – 2n(A \cap C) – 2n(B \cap C) + 4n(A \cap B \cap C) \]
Proof:
Step 1 — Apply the cardinality formula for \( \triangle \).
For any sets \( X \) and \( Y \):
\[ n(X \triangle Y) = n(X) + n(Y) – 2n(X \cap Y) \]
Applying this with \( X = A \triangle B \) and \( Y = C \):
\[ n[(A \triangle B) \triangle C] = n(A \triangle B) + n(C) – 2n[(A \triangle B) \cap C] \quad \cdots (I) \]
Step 2 — Substitute \( n(A \triangle B) \) (proved in Exercise 79):
\[ n(A \triangle B) = n(A) + n(B) – 2n(A \cap B) \quad \cdots (\ast) \]
Step 3 — Substitute \( n[(A \triangle B) \cap C] \) (proved in Exercise 79):
\[ n[(A \triangle B) \cap C] = n(A \cap C) + n(B \cap C) – 2n(A \cap B \cap C) \quad \cdots (\ast\ast) \]
Step 4 — Substitute \( (\ast) \) and \( (\ast\ast) \) into \( (I) \).
\[ n[(A \triangle B) \triangle C] = [n(A) + n(B) – 2n(A \cap B)] + n(C) – 2[n(A \cap C) + n(B \cap C) – 2n(A \cap B \cap C)] \]
\[ = n(A) + n(B) + n(C) – 2n(A \cap B) – 2n(A \cap C) – 2n(B \cap C) + 4n(A \cap B \cap C) \]
∎
Comparing coefficients across three formulas:
Formula \( A \) \( B \) \( C \) \( A \cap B \) \( A \cap C \) \( B \cap C \) \( A \cap B \cap C \) \( n(A \cup B \cup C) \) +1 +1 +1 \( -1 \) \( -1 \) \( -1 \) \( +1 \) \( n[(A \triangle B) \cup C] \) +1 +1 +1 \( -2 \) \( -1 \) \( -1 \) \( +2 \) \( n[(A \triangle B) \triangle C] \) +1 +1 +1 \( -2 \) \( -2 \) \( -2 \) \( +4 \) Each application of \( \triangle \) doubles the penalty on the pairwise intersections and quadruples the compensation at the triple intersection.
Exercise 81
A sports club has 78 members. Of these, 50 play football, 32 play basketball, and 23 play volleyball. In addition, 6 play all three sports and 10 play none. If \( x \) is the total number of members who play exactly one sport and \( y \) the total who play exactly two, find \( x – y \).
Solution:
Step 1 — Set up the regions.
Let \( F \) = football, \( B \) = basketball, \( V \) = volleyball. The 7 Venn diagram regions are:
- \( a \) = only \( F \), \( b \) = only \( F \cap B \), \( c \) = only \( B \), \( d \) = only \( B \cap V \), \( e = F \cap B \cap V = 6 \), \( f \) = only \( F \cap V \), \( g \) = only \( V \).
\[ n(F \cup B \cup V) = 78 – 10 = 68 \]
Step 2 — Write equations for each set.
Subtracting \( e = 6 \) from each total:
| Set | Equation | Simplified |
|---|---|---|
| \( n(F) = 50 \) | \( a + b + 6 + f = 50 \) | \( a + b + f = 44 \) |
| \( n(B) = 32 \) | \( c + b + 6 + d = 32 \) | \( c + b + d = 26 \) |
| \( n(V) = 23 \) | \( g + d + 6 + f = 23 \) | \( g + d + f = 17 \) |
Step 3 — Solve using strategic sums.
Define:
- \( x = a + c + g \) (exactly one sport)
- \( y = b + d + f \) (exactly two sports)
From the union: \( x + y + 6 = 68 \), so:
\[ x + y = 62 \quad \cdots (I) \]
Adding the three simplified equations:
\[ (a + b + f) + (c + b + d) + (g + d + f) = 44 + 26 + 17 = 87 \] \[ (a + c + g) + 2(b + d + f) = 87 \] \[ x + 2y = 87 \quad \cdots (II) \]
Subtracting \( (II) – (I) \):
\[ y = 25, \quad x = 37 \]
Verification:
| Group | Members |
|---|---|
| Exactly one sport (\( x \)) | 37 |
| Exactly two sports (\( y \)) | 25 |
| All three sports | 6 |
| None | 10 |
| Total | 78 ✓ |
Result:
\[ x – y = 37 – 25 = 12 \]
Exercise 82
Every morning in January (31 days), Juan has either eggs or bacon for breakfast. If he has bacon on 25 mornings and eggs on 18 mornings, on how many mornings does he have eggs only?
Solution:
Let \( T \) = days with bacon, \( H \) = days with eggs.
Key fact: He has eggs or bacon every morning without exception, so \( n(H \cup T) = 31 \).
Step 1 — Find \( n(H \cap T) \) (days with both):
\[ 31 = 18 + 25 – n(H \cap T) \implies n(H \cap T) = 12 \]
Step 2 — Days with eggs only:
\[ n(H – T) = n(H) – n(H \cap T) = 18 – 12 = 6 \]
Verification:
| Eggs only | Both | Bacon only | Total |
|---|---|---|---|
| 6 | 12 | 13 | 31 ✓ |
Result: Juan has eggs only on 6 mornings.
Exercise 83
Suppose Juan has either eggs or bacon for breakfast every morning in January (31 days). If he has bacon on 25 mornings and eggs on 18 mornings, how many mornings does he have eggs only?
Solution:
Define the sets:
- \( H \) = mornings on which Juan has eggs
- \( T \) = mornings on which Juan has bacon
Given:
- \( n(H) = 18 \)
- \( n(T) = 25 \)
- He has eggs or bacon every morning without exception, so \( n(H \cup T) = 31 \).
Step 1 — Find the days he has both.
Applying inclusion-exclusion:
\[ n(H \cup T) = n(H) + n(T) – n(H \cap T) \] \[ 31 = 18 + 25 – n(H \cap T) \implies n(H \cap T) = 12 \]
Juan has both on 12 mornings.
Step 2 — Find the days he has eggs only.
Mornings with eggs only are those in \( H \) but not in \( T \), i.e., \( H – T \):
\[ n(H – T) = n(H) – n(H \cap T) = 18 – 12 = 6 \]
Verification:
| Mornings | Count |
|---|---|
| Eggs only \( (H – T) \) | 6 |
| Eggs and bacon \( (H \cap T) \) | 12 |
| Bacon only \( (T – H) \) | 13 |
| Total | 31 ✓ |
Result: Juan has eggs only on 6 mornings.
Exercise 84
From 120 students at a university, the following information was gathered:
- 72 are enrolled in course \( A \)
- 64 are enrolled in course \( B \)
- 36 are enrolled in course \( C \)
- 12 are enrolled in all three
How many students are enrolled in exactly two courses?
Solution.
We assume all 120 students are enrolled in at least one course:
\[ n(A \cup B \cup C) = 120 \]
Step 1 — Set up the 7 Venn diagram regions.
| Region | Variable |
|---|---|
| Only \( A \) | \( a \) |
| Only \( B \) | \( b \) |
| Only \( C \) | \( c \) |
| Only \( A \) and \( B \) (not \( C \)) | \( d \) |
| Only \( A \) and \( C \) (not \( B \)) | \( e \) |
| Only \( B \) and \( C \) (not \( A \)) | \( f \) |
| All three | \( g = 12 \) |
The students enrolled in exactly two courses are those in regions \( d \), \( e \), and \( f \). We need \( d + e + f \).
Step 2 — Write equations for each set.
\[ n(A) = a + d + e + g = 72 \implies a + d + e = 60 \quad \cdots (1) \] \[ n(B) = b + d + f + g = 64 \implies b + d + f = 52 \quad \cdots (2) \] \[ n(C) = c + e + f + g = 36 \implies c + e + f = 24 \quad \cdots (3) \]
Step 3 — Add the three equations.
\[ (a+d+e) + (b+d+f) + (c+e+f) = 136 \] \[ (a+b+c) + 2(d+e+f) = 136 \quad \cdots (4) \]
Step 4 — Use the total.
Since the 7 regions sum to 120 and \( g = 12 \):
\[ a + b + c + d + e + f = 108 \quad \cdots (5) \]
Subtracting (5) from (4):
\[ d + e + f = 136 – 108 = 28 \]
Cross-check with inclusion-exclusion:
\[ 120 = 72 + 64 + 36 – n(A \cap B) – n(A \cap C) – n(B \cap C) + 12 \] \[ n(A \cap B) + n(A \cap C) + n(B \cap C) = 64 \]
Since each pairwise intersection includes the triple:
\[ d + e + f = 64 – 3(12) = 28 ; ✓ \]
Result: Exactly 28 students are enrolled in exactly two courses.
Exercise 85
A sports club has 79 members, of whom 52 play football, 36 play basketball, 49 play volleyball, and 63 play football or basketball. If 15 play only football and basketball (not volleyball) and 16 play only volleyball:
- (a) How many members play all three sports?
- (b) How many members play at least two of the three sports?
Solution.
Define \( F \) (football), \( B \) (basketball), \( V \) (volleyball) with 7 Venn regions:
| Region | Value |
|---|---|
| Only \( F \) | \( a \) |
| Only \( B \) | \( b \) |
| Only \( V \) | \( c = 16 \) |
| Only \( F \cap B \) (not \( V \)) | \( d = 15 \) |
| Only \( F \cap V \) (not \( B \)) | \( e \) |
| Only \( B \cap V \) (not \( F \)) | \( f \) |
| All three | \( g \) |
Part (a) — Find \( g \).
From \( n(F \cup B) = 63 \), by inclusion-exclusion:
\[ 63 = 52 + 36 – n(F \cap B) \implies n(F \cap B) = 25 \]
Since \( n(F \cap B) = d + g \):
\[ 15 + g = 25 \implies \boxed{g = 10} \]
10 members play all three sports.
Part (b) — Members playing at least two sports.
“At least two” = exactly two + all three = \( d + e + f + g \).
From \( n(V) = 49 \):
\[ c + e + f + g = 49 \implies 16 + e + f + 10 = 49 \implies e + f = 23 \]
\[ d + e + f + g = 15 + 23 + 10 = 48 \]
Verification:
From \( n(F) = 52 \): \( a + e = 27 \). From \( n(B) = 36 \): \( b + f = 11 \). Total without \( c, d, g \): \( a+b+e+f = 79 – 16 – 15 – 10 = 38 = 27 + 11 \) ✓
Note: The individual values of \( e \) and \( f \) cannot be determined from the given data, but their sum \( e + f = 23 \) is enough to answer the question.
At least two sports: 48 members.
Exercise 86
A survey of university students yielded the following results:
- 55% passed Basic Chemistry (\( Q \))
- 30% passed Basic Mathematics (\( M \))
- 50% passed Language (\( L \))
- 10% passed all three
- 40% of those who passed \( Q \) passed no other course
- 20% of those who passed \( Q \) also passed \( M \) but not \( L \)
- 14% passed none of the three
- 256 respondents passed both \( M \) and \( L \)
Find: (a) How many passed all three courses? (b) How many passed \( M \) or \( L \) but not \( Q \)?
Solution.
Let \( N \) be the total number of respondents. The 7 Venn regions in terms of \( N \):
| Region | Description | In terms of \( N \) |
|---|---|---|
| \( a \) | Only \( Q \) | \( 0.22N \) |
| \( b \) | Only \( M \) | ? |
| \( c \) | Only \( L \) | ? |
| \( d \) | Only \( Q \cap M \) (not \( L \)) | \( 0.11N \) |
| \( e \) | Only \( Q \cap L \) (not \( M \)) | ? |
| \( f \) | Only \( M \cap L \) (not \( Q \)) | ? |
| \( g \) | All three | \( 0.10N \) |
Step 1 — Extract the direct data.
The percentages relative to \( Q \) convert to percentages of \( N \):
- “40% of those who passed \( Q \) passed no other course” → only \( Q \): \( a = 0.40 \times 0.55N = 0.22N \)
- “20% of those who passed \( Q \) also passed \( M \) but not \( L \)” → only \( Q \cap M \): \( d = 0.20 \times 0.55N = 0.11N \)
Step 2 — Find \( e \) from \( n(Q) \).
\[ 0.22N + 0.11N + e + 0.10N = 0.55N \implies e = 0.12N \]
Step 3 — Set up equations using \( n(M) \), \( n(L) \), and the total.
From the 14% who passed none: \( n(Q \cup M \cup L) = 0.86N \), giving:
\[ b + c + f = 0.31N \quad \cdots (I) \]
From \( n(M) = 0.30N \): \( b + f = 0.09N \quad \cdots (II) \)
From \( n(L) = 0.50N \): \( c + f = 0.28N \quad \cdots (III) \)
Step 4 — Find \( f \) and \( N \).
Adding (II) and (III): \( b + c + 2f = 0.37N \). Subtracting (I): \( f = 0.06N \).
Since \( n(M \cap L) = f + g = 256 \):
\[ 0.06N + 0.10N = 256 \implies N = 1600 \]
Part (a) — Those who passed all three.
\[ g = 0.10 \times 1600 = \mathbf{160} \text{ students} \]
Part (b) — Those who passed \( M \) or \( L \) but not \( Q \).
With \( N = 1600 \): \( f = 96 \), \( b = 48 \), \( c = 352 \).
\[ b + c + f = 48 + 352 + 96 = \mathbf{496} \text{ students} \]
Full verification:
| Region | Students |
|---|---|
| Only \( Q \) | 352 |
| Only \( M \) | 48 |
| Only \( L \) | 352 |
| Only \( Q \cap M \) | 176 |
| Only \( Q \cap L \) | 192 |
| Only \( M \cap L \) | 96 |
| All three | 160 |
| None | 224 |
| Total | 1600 ✓ |
Exercise 87
A survey of professionals found: 72% are mathematicians, 52% physicists, 37% chemists, 32% physicist-mathematicians, 12% physicist-chemists, 22% mathematician-chemists, and 2% physicist-mathematician-chemists. Find:
- (a) The percentage who follow exactly one field.
- (b) The percentage who follow other fields.
Solution.
Define \( M \) (mathematicians), \( F \) (physicists), and \( Q \) (chemists). All data are percentages of the total surveyed.
Note: Percentages like \( n(F \cap M) = 32% \) refer to “physicist-mathematicians” in general — including those who are also chemists. The same applies to the other pairwise intersections.
Step 1 — Compute \( n(M \cup F \cup Q) \) by inclusion-exclusion.
\[ n(M \cup F \cup Q) = 72 + 52 + 37 – 32 – 12 – 22 + 2 = \mathbf{97%} \]
Part (b) — Those in other fields.
\[ 100% – 97% = \boxed{3%} \]
Part (a) — Those following exactly one field.
Using the formula: only \( X \) = \( n(X) – n(X \cap Y) – n(X \cap Z) + n(X \cap Y \cap Z) \)
\[ \text{Only } M: \quad 72 – 32 – 22 + 2 = 20% \] \[ \text{Only } F: \quad 52 – 32 – 12 + 2 = 10% \] \[ \text{Only } Q: \quad 37 – 12 – 22 + 2 = 5% \]
\[ \text{Exactly one field} = 20 + 10 + 5 = \boxed{35%} \]
Verification — the 7 regions must sum to 97%:
| Region | Percentage |
|---|---|
| Only \( M \) | 20% |
| Only \( F \) | 10% |
| Only \( Q \) | 5% |
| Only \( F \cap M \) (not \( Q \)) | 30% |
| Only \( F \cap Q \) (not \( M \)) | 10% |
| Only \( M \cap Q \) (not \( F \)) | 20% |
| All three | 2% |
| Total | 97% ✓ |
(a) 35% follow exactly one field. (b) 3% follow other fields.
Exercise 88
University records for a group of 300 first-year students show: 155 are enrolled in course \( A \), 170 in course \( B \), and 110 in course \( C \). Also: 85 are in both \( A \) and \( B \), 70 in both \( B \) and \( C \), 50 in both \( A \) and \( C \), and 35 in all three. Find:
- (a) The number enrolled in \( A \) but not \( C \).
- (b) The number enrolled in none of the three courses.
Solution.
Part (a) — Enrolled in \( A \) but not \( C \).
This is exactly \( A – C \):
\[ n(A – C) = n(A) – n(A \cap C) = 155 – 50 = \boxed{105} \]
Note: This formula subtracts from \( A \) everyone who is also in \( C \), regardless of whether they are in \( B \). No need to break down internal sub-regions.
Part (b) — Enrolled in none of the three.
By inclusion-exclusion:
\[ n(A \cup B \cup C) = 155 + 170 + 110 – 85 – 70 – 50 + 35 = 265 \]
\[ \text{None} = 300 – 265 = \boxed{35} \]
Full verification:
| Region | Computation | Students |
|---|---|---|
| Only \( A \) | \( 155 – 85 – 50 + 35 \) | 55 |
| Only \( B \) | \( 170 – 85 – 70 + 35 \) | 50 |
| Only \( C \) | \( 110 – 70 – 50 + 35 \) | 25 |
| Only \( A \cap B \) (not \( C \)) | \( 85 – 35 \) | 50 |
| Only \( B \cap C \) (not \( A \)) | \( 70 – 35 \) | 35 |
| Only \( A \cap C \) (not \( B \)) | \( 50 – 35 \) | 15 |
| All three | — | 35 |
| None | — | 35 |
| Total | 300 ✓ |
Check for part (a): “only \( A \)” + “only \( A \cap B \)” = \( 55 + 50 = 105 \) ✓
(a) 105 students are enrolled in \( A \) but not \( C \). (b) 35 students are enrolled in none.
Exercise 89
Of 150 people surveyed about the sports they play: 82 play football, 54 play basketball, 50 play only football, and 30 play only basketball. Also:
- The number who play only basketball and tennis is half those who play only football and tennis.
- The number who play only football and basketball is three times those who play all three sports.
- Those who play no sport equals those who play only tennis.
Find: (a) How many play exactly two sports? (b) How many play no sport?
Solution.
Define \( F \) (football), \( B \) (basketball), \( T \) (tennis) with 7 regions:
| Region | Description | Value |
|---|---|---|
| \( a \) | Only \( F \) | 50 |
| \( b \) | Only \( B \) | 30 |
| \( c \) | Only \( T \) | ? |
| \( d \) | Only \( F \cap B \) (not \( T \)) | ? |
| \( e \) | Only \( F \cap T \) (not \( B \)) | ? |
| \( f \) | Only \( B \cap T \) (not \( F \)) | ? |
| \( g \) | All three | ? |
The conditions translate to: \( f = e/2 \), \( d = 3g \), none \( = c \).
Step 1 — Equations from \( n(F) \) and \( n(B) \).
\[ d + e + g = 32 \quad \cdots (1) \] \[ d + f + g = 24 \quad \cdots (2) \]
Step 2 — Find \( e \) and \( f \).
Subtracting: \( e – f = 8 \). With \( f = e/2 \):
\[ \frac{e}{2} = 8 \implies e = 16, \quad f = 8 \]
Step 3 — Find \( d \) and \( g \).
From (1): \( d + g = 16 \). With \( d = 3g \): \( g = 4 \), \( d = 12 \).
Step 4 — Find \( c \) from the total.
\[ 50 + 30 + c + 12 + 16 + 8 + 4 + c = 150 \implies 2c = 30 \implies c = 15 \]
Complete table:
| Region | Description | People |
|---|---|---|
| \( a \) | Only \( F \) | 50 |
| \( b \) | Only \( B \) | 30 |
| \( c \) | Only \( T \) | 15 |
| \( d \) | Only \( F \cap B \) | 12 |
| \( e \) | Only \( F \cap T \) | 16 |
| \( f \) | Only \( B \cap T \) | 8 |
| \( g \) | All three | 4 |
| None | — | 15 |
| Total | 150 ✓ |
(a) Exactly two sports: \( d + e + f = 12 + 16 + 8 = \boxed{36} \)
(b) No sport: none \( = c = \boxed{15} \)
Exercise 90
A survey at a supermarket asked 400 housewives about their consumption of three products \( A \), \( B \), and \( C \). The number consuming all three is:
- \( \tfrac{1}{4} \) of those consuming only \( A \)
- \( \tfrac{1}{5} \) of those consuming only \( B \)
- \( \tfrac{1}{3} \) of those consuming only \( C \)
- \( \tfrac{1}{2} \) of those consuming \( A \) and \( B \) (with or without \( C \))
- \( \tfrac{1}{3} \) of those consuming \( B \) and \( C \) (with or without \( A \))
- \( \tfrac{1}{3} \) of those consuming \( A \) and \( C \) (with or without \( B \))
If 40 housewives consume none of the three products, find: (a) How many consume only one product? (b) How many consume at least two?
Solution.
Let \( g \) = those consuming all three. All other regions are expressed in terms of \( g \):
| Region | Description | In terms of \( g \) |
|---|---|---|
| \( a \) | Only \( A \) | \( 4g \) |
| \( b \) | Only \( B \) | \( 5g \) |
| \( c \) | Only \( C \) | \( 3g \) |
| \( d \) | Only \( A \cap B \) (not \( C \)) | \( g \) |
| \( e \) | Only \( B \cap C \) (not \( A \)) | \( 2g \) |
| \( f \) | Only \( A \cap C \) (not \( B \)) | \( 2g \) |
| \( g \) | All three | \( g \) |
Step 1 — Derive the relations.
The three single-product conditions give \( a = 4g \), \( b = 5g \), \( c = 3g \).
For the double intersections (applied to the full \( A \cap B = d + g \)):
\[ g = \frac{d+g}{2} \implies d = g \qquad g = \frac{e+g}{3} \implies e = 2g \qquad g = \frac{f+g}{3} \implies f = 2g \]
Step 2 — Find \( g \) from the total.
\[ 4g + 5g + 3g + g + 2g + 2g + g + 40 = 400 \implies 18g = 360 \implies \boxed{g = 20} \]
Complete table:
| Region | Description | People |
|---|---|---|
| \( a \) | Only \( A \) | 80 |
| \( b \) | Only \( B \) | 100 |
| \( c \) | Only \( C \) | 60 |
| \( d \) | Only \( A \cap B \) | 20 |
| \( e \) | Only \( B \cap C \) | 40 |
| \( f \) | Only \( A \cap C \) | 40 |
| \( g \) | All three | 20 |
| None | — | 40 |
| Total | 400 ✓ |
(a) Only one product: \( a + b + c = 80 + 100 + 60 = \boxed{240} \)
(b) At least two products: \( d + e + f + g = 20 + 40 + 40 + 20 = \boxed{120} \)
Exercise 91
A language institute survey found: 60 people study English, 48 German, and 28 French. Also:
- Those studying only French = \( \tfrac{1}{3} \) of those studying only English = \( \tfrac{1}{2} \) of those studying only German.
- Those studying all three languages = \( \tfrac{1}{2} \) of those studying only English and French.
- Those studying only German and French = \( \tfrac{1}{3} \) of those studying only English and German.
Find: (a) How many study exactly one language? (b) How many study exactly two?
Solution.
Define \( I \) (English), \( A \) (German), \( F \) (French) with 7 regions expressed in terms of \( c \) (only \( F \)) and \( g \) (all three):
| Region | Description | In terms of \( c \) and \( g \) |
|---|---|---|
| \( a \) | Only \( I \) | \( 3c \) |
| \( b \) | Only \( A \) | \( 2c \) |
| \( c \) | Only \( F \) | \( c \) |
| \( d \) | Only \( I \cap A \) (not \( F \)) | \( d \) |
| \( e \) | Only \( I \cap F \) (not \( A \)) | \( 2g \) |
| \( f \) | Only \( A \cap F \) (not \( I \)) | \( d/3 \) |
| \( g \) | All three | \( g \) |
Step 1 — Set up equations from the set sizes.
\[ n(I) = 3c + d + 3g = 60 \quad \cdots (1) \] \[ n(A) = 2c + \tfrac{4d}{3} + g = 48 \quad \cdots (2) \] \[ n(F) = c + \tfrac{d}{3} + 3g = 28 \quad \cdots (3) \]
Step 2 — Solve.
Subtracting (3) from (1): \( c + \tfrac{d}{3} = 16 \quad \cdots (4) \)
Substituting (4) into (3): \( g = 4 \).
From (2): \( c + \tfrac{2d}{3} = 22 \quad \cdots (5) \). Subtracting (4) from (5): \( d = 18 \), then \( c = 10 \).
Remaining regions: \( a = 30 \), \( b = 20 \), \( e = 8 \), \( f = 6 \).
Complete table:
| Region | Description | People |
|---|---|---|
| \( a \) | Only \( I \) | 30 |
| \( b \) | Only \( A \) | 20 |
| \( c \) | Only \( F \) | 10 |
| \( d \) | Only \( I \cap A \) | 18 |
| \( e \) | Only \( I \cap F \) | 8 |
| \( f \) | Only \( A \cap F \) | 6 |
| \( g \) | All three | 4 |
| Total | 96 |
Verification: \( n(I) = 30+18+8+4 = 60 \) ✓, \( n(A) = 20+18+6+4 = 48 \) ✓, \( n(F) = 10+8+6+4 = 28 \) ✓
(a) Exactly one language: \( a + b + c = 30 + 20 + 10 = \boxed{60} \)
(b) Exactly two languages: \( d + e + f = 18 + 8 + 6 = \boxed{32} \)
Note: The total surveyed is \( 60 + 32 + 4 = 96 \). The problem does not specify the sample size or mention anyone studying no language, so we assume everyone studies at least one.
Exercise 92
In an apartment building: 20% of families live on the first floor (half have a refrigerator), 40% on the second floor (half have a refrigerator), 30% on the third floor (one third have a refrigerator), and 10% on the fourth floor (none have a refrigerator). Of the families with a refrigerator, what percentage live on the second floor?
Solution:
Step 1 — Assume 100 families total (to work directly in percentages).
| Floor | Families | Fraction with refrigerator | Families with refrigerator |
|---|---|---|---|
| 1st | 20 | 1/2 | 10 |
| 2nd | 40 | 1/2 | 20 |
| 3rd | 30 | 1/3 | 10 |
| 4th | 10 | 0 | 0 |
| Total | 100 | 40 |
Step 2 — Compute the requested percentage.
Let \( R \) = families with a refrigerator, \( P_2 \) = families on the second floor.
\[ \frac{n(R \cap P_2)}{n(R)} = \frac{20}{40} = \frac{1}{2} = 50% \]
Result: 50% of the families with a refrigerator live on the second floor.
Note: Although the second floor has 40% of all families, it accounts for 50% of all refrigerators. This is because the fourth floor contributes none, shifting the relative weight toward the floors that do.
What’s next?
With set theory under our belt, we’re ready for the next chapter: Relations and Functions, where we’ll explore:
- ✅ Cartesian product \( A \times B \): the set of all ordered pairs \( (a, b) \) with \( a \in A \) and \( b \in B \)
- ✅ Binary relations: subsets of \( A \times B \) that connect elements between sets
- ✅ Properties of relations: reflexivity, symmetry, transitivity, and antisymmetry
- ✅ Equivalence relations and partitions: how a relation can divide a set into classes
- ✅ Functions: relations where each element of the domain corresponds to exactly one element of the codomain
- ✅ Types of functions: injective, surjective, and bijective
- ✅ Composition and inverse of functions
The sets we studied here are the raw material for all of these structures: the domain and codomain of a function are sets, its graph is a subset of the Cartesian product, and the properties we proved — inclusion, equality, operations — will be everyday tools when studying relations and functions. Without that language, no formal definition of a function could be stated with precision.