Ch 4. Relations
4.1 Sets, Their Properties, and Applications
A set is a well-defined collection of distinct (different) objects. The objects in a set are called elements or members.
Example 4.1
Let [latex]A = \{ 2, 4, 6, 8 \}[/latex]. This is a set of even numbers less than 10.
Set-builder notation describes a set by stating the properties that its members must satisfy.
Example 4.2
The set of all even numbers less than 10 can be written as
[latex]A = \{ x \text{ is an integer} \mid x \text{ is even and } x < 10 \}[/latex]
The following table contains common sets of numbers used in discrete mathematics.
| Symbol | Name | Example |
|---|---|---|
| [latex]\mathbb{N}[/latex] | Natural numbers | [latex]\{ 0, 1, 2, \dots \}[/latex] |
| [latex]\mathbb{Z}[/latex] | Integers | [latex]\{ \dots, -2, -1, 0, 1, 2, \dots \}[/latex] |
| [latex]\mathbb{N}^{-}[/latex] | Negative integers | [latex]\{ -1, -2, -3, \dots \}[/latex] |
| [latex]\mathbb{N}^{\text{nonneg}}[/latex] | Non-negative integers | [latex]\{ 0, 1, 2, 3, \dots \}[/latex] |
| [latex]\mathbb{Q}[/latex] | Rational numbers | [latex]\{ \frac{1}{2}, -3, 0.75 \}[/latex] |
| [latex]\mathbb{Q}^{+}[/latex] | Positive rational numbers | [latex]\{ \frac{1}{2}, 3, 0.75 \}[/latex] |
| [latex]\mathbb{R}[/latex] | Real Numbers | [latex]\{ -\sqrt{2}, 0, \pi, 3.5 \}[/latex] |
The cardinality of a set is the number of elements in the set. It is denoted by [latex]|A|[/latex].
Example 4.3
If [latex]A = \{ 2, 4, 6, 8 \}[/latex], then [latex]|A| = 4[/latex].
When it comes to membership notation, we write [latex]a \in A[/latex] to represent “[latex]a[/latex] is an element of [latex]A[/latex]” and [latex]b \notin A[/latex] to represent “[latex]b[/latex] is not an element of [latex]A[/latex]”.
Example 4.2 (revisited)
The set of all even numbers less than 10 can be written as
[latex]A = \{ x \in \mathbb{Z} \mid x \text{ is even and } x < 10 \}[/latex]
Example 4.4
The empty set (also called the null set or void set) is the set with no elements. It is denoted by [latex]\emptyset[/latex] or {}.
Example 4.5
We say that two sets A and B are equal if they contain the same elements. The notation we use for this is [latex]A = B[/latex] if and only if every element of [latex]A[/latex] is in [latex]B[/latex], and every element of [latex]B[/latex] is in [latex]A[/latex].
Example 4.6
To formally prove that two sets are equal, you must show that:
- Every element of [latex]A[/latex] is in [latex]B[/latex]
- Every element of [latex]B[/latex] is in [latex]A[/latex]
If both are true, then [latex]A = B[/latex].
Example 4.7
Claim
[latex]A = \{ x \in \mathbb{R} \mid x^{2} = 1 \}[/latex] and [latex]B = \{ -1, 1 \}[/latex] are equal.
Proof
First, we show that every element of [latex]A[/latex] is in [latex]B[/latex].
Take any [latex]x \in A[/latex]. Then [latex]x^{2} = 1[/latex]. So, [latex]x = 1[/latex] or [latex]x = -1[/latex]. Thus, [latex]x \in B[/latex].
Then, we show that every element of [latex]B[/latex] is in [latex]A[/latex].
Take any [latex]x \in B[/latex]. Then [latex]x = 1[/latex] or [latex]x = -1[/latex]. In both cases, [latex]x^{2} = 1[/latex], so [latex]x \in A[/latex]. Therefore, [latex]x \in A[/latex].
Since both statements hold, we conclude that [latex]A = B.[/latex]
[latex]\square[/latex]
Two sets are not equal if there is at least one element in one set that is not in the other.
Example 4.8
If [latex]A[/latex] and [latex]B[/latex] are sets and every element of [latex]A[/latex] is also an element of [latex]B[/latex], then we say that [latex]A[/latex] is a subset of [latex]B[/latex]. We use the notation [latex]A \subseteq B[/latex] to represent this.
The subset notation gives another way to prove that two sets are equal formally. That is, if [latex]A \subseteq B[/latex] and [latex]B \subseteq A[/latex] are both true, then [latex]A = B[/latex].
Example 4.9
If you want to prove that one set is a subset of another, you need to show that every element in the one set is also an element of the other. This can be achieved using the following steps:
- Assume [latex]x \in A[/latex].
- Show that [latex]x \in B[/latex] using definitions, properties, or logical reasoning.
- Conclude that since [latex]x \in A \Rightarrow x \in B[/latex], then [latex]A \subseteq B[/latex].
Example 4.10
Claim
Let [latex]A = \{ x \in \mathbb{Z} \mid x \text{ is even and } x > 0 \}[/latex] and [latex]B = \{ x \in \mathbb{Z} \mid x \text{ is divisible by 2} \}[/latex]. Then [latex]A \subseteq B[/latex].
Proof
Let [latex]x \in A[/latex]. Then by definition of [latex]A[/latex], [latex]x[/latex] is a positive even integer.
Since [latex]x[/latex] is even, there exists an integer [latex]k[/latex] such that [latex]x = 2k[/latex]. This means [latex]x[/latex] is divisible by [latex]2[/latex]. Therefore, [latex]x \in B[/latex].
Since every [latex]x \in A[/latex] is also in [latex]B[/latex], we conclude [latex]A \subseteq B.[/latex]
[latex]\square[/latex]
If there is at least one element in [latex]A[/latex] that is not in [latex]B[/latex], then [latex]A[/latex] is not a subset of [latex]B[/latex]. We use the notation [latex]A \nsubseteq B[/latex] to represent this.
Example 4.11
Note that for any set [latex]A[/latex], it is always true that [latex]A \subseteq A[/latex]. Also, the empty set [latex]\emptyset[/latex] is a subset of every set.
Example 4.12
It is important to distinguish between being a subset and being an element of a set.
[latex]a \in A[/latex]: “[latex]a[/latex] is an element of [latex]A[/latex]”
[latex]\{ a \} \subseteq A[/latex]: “the set containing [latex]a[/latex] is a subset of [latex]A[/latex]”
Example 4.13
A set [latex]A[/latex] is a proper subset of [latex]B[/latex] if [latex]A \subseteq B[/latex] and [latex]A \neq B[/latex]. We use the notation [latex]A \subset B[/latex] to represent this.
Example 4.14
The power set of a set [latex]A[/latex], denoted [latex]\mathcal{P}(A)[/latex], is the set of all subsets of [latex]A[/latex], including the empty set and [latex]A[/latex] itself.
Example 4.15
We can use mathematical induction (see Section 3.6) to prove an important property of power sets, namely, if a set [latex]A[/latex] has [latex]n[/latex] elements, then its power set [latex]\mathcal{P}(A)[/latex] has [latex]2^{n}[/latex] elements.
Theorem 4.1: Size of the Power Set
For all [latex]n \in \mathbb{N}[/latex], if [latex]|A| = n[/latex], then [latex]|\mathcal{P}(A)| = 2^{n}[/latex].
Proof
Basis Step: Let [latex]A = \emptyset[/latex]. Then [latex]\mathcal{P}(A) = \{ \emptyset \}[/latex], which has [latex]1[/latex] element. Also, [latex]2^0 = 1[/latex]. So, the basis case holds.
Inductive Step: Assume that for some [latex]k \in \mathbb{N}[/latex], if [latex]|A| = k[/latex], then [latex]|\mathcal{P}(A)| = 2^{k}[/latex].
We must show that if [latex]|A| = k + 1[/latex], then [latex]|\mathcal{P}(A)| = 2^{k+1}[/latex].
Let [latex]A[/latex] be a set with [latex]k+1[/latex] elements. Pick an element [latex]a \in A[/latex], and define [latex]B[/latex] to be the set [latex]A[/latex] with the set [latex]\{ a \}[/latex] removed, so [latex]|B| = k[/latex].
Now, every subset of [latex]A[/latex] either contains [latex]a[/latex], or does not contain [latex]a[/latex]. The subsets not containing [latex]a[/latex] are exactly the subsets of [latex]B[/latex]: there are [latex]2^{k}[/latex] of them (by the inductive hypothesis). The subsets containing [latex]a[/latex] can be formed by taking each subset of [latex]B[/latex] and adding [latex]a[/latex]: again, [latex]2^{k}[/latex] of them.
So, the total subsets of [latex]A = 2^{k}[/latex] (without [latex]a[/latex]) + [latex]2^{k}[/latex] (with [latex]a[/latex]) [latex]= 2^{k} + 2^{k} = 2 \cdot 2^{k} = 2^{k+1}. \blacksquare[/latex]
This theorem avoids us having to list all the members of the power set to determine how many there are.
Example 4.16
The union of sets [latex]A[/latex] and [latex]B[/latex] is the set of all elements that are in [latex]A[/latex], in [latex]B[/latex], or in both. We write this as [latex]A \cup B[/latex].
Example 4.17
The intersection of sets [latex]A[/latex] and [latex]B[/latex] is the set of all elements that are in both [latex]A[/latex] and [latex]B[/latex]. We write this as [latex]A \cap B[/latex].
Example 4.18
Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 3, 4, 5 \}[/latex]. Then [latex]A \cap B = \{ 3 \}[/latex].
The difference of sets [latex]A[/latex] and [latex]B[/latex] is the set of elements that are in [latex]A[/latex] but not in [latex]B[/latex]. We write this as [latex]A - B[/latex] or [latex]A \setminus B[/latex]. This is also called the relative complement of [latex]B[/latex] in [latex]A[/latex].
Example 4.19
Note that in the proof of Theorem 4.1, we could have written “define to be the set [latex]A[/latex] with the set [latex]\{ a \}[/latex]removed” as “define [latex]B = A - \{ a \}[/latex]” or “define [latex]B = A \setminus \{ a \}[/latex]”.
A family of sets (also called a collection of sets) is a set whose elements are themselves sets. This concept is useful when working with groups of related sets, such as in topology, probability, or database schemas.
A family of sets is often denoted by a capital script letter, such as [latex]\mathcal{F}[/latex] or [latex]\mathcal{A}[/latex].
Example 4.20
Let [latex]\mathcal{F} = \{ \{ 1, 2 \}, \{ 2, 3 \}, \{ 1, 3 \} \}[/latex]. Here, [latex]\mathcal{F}[/latex] is a family of sets, and each element of [latex]\mathcal{F}[/latex] is itself a set.
You can also define a family of sets using a rule:
[latex]\mathcal{A} = \{ A_{i} \mid A_{i} = \{ i, i+1 \}, i \in \{ 1, 2, 3 \} \}[/latex]
Then [latex]A_{1} = \{ 1, 2 \} , A_{2} = \{ 2, 3 \} , \text{ and } A_{3} = \{ 3, 4 \} .[/latex] So, [latex]\mathcal{A} = \{ \{ 1, 2 \}, \{ 2, 3 \}, \{ 3, 4 \} \}[/latex].
If two sets have no elements in common, then they are said to be disjoint. Formally, we write [latex]A \cap B = \emptyset[/latex].
Example 4.21
Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 3, 4, 5 \}[/latex]. Then [latex]A[/latex] and [latex]B[/latex] are disjoint because [latex]A \cap B = \emptyset[/latex].
A family of sets [latex]\mathcal{F} = \{ A_{1}, A_{2}, \dots, A_{n} \}[/latex] is pairwise disjoint if every pair of distinct sets in the family is disjoint. Formally, we write for all [latex]i \neq j, A_{i} \cap A_{j} = \emptyset[/latex].
Example 4.22
Let [latex]\mathcal{F} = \{ \{ 1 \} , \{ 2 \} , \{ 3 \} \}[/latex]. This family is pairwise disjoint because no two sets share any elements.
Let [latex]\mathcal{G} = \{ \{ 1, 2 \} , \{ 2, 3\} , \{ 3, 4 \}[/latex]. This is not pairwise disjoint because
[latex]\{ 1, 2 \} \cap \{ 2, 3 \} = \{ 2 \} \neq \emptyset[/latex]
[latex]\{ 2, 3 \} \cap \{ 3, 4 \} = \{ 3 \} \neq \emptyset[/latex]
The universal set, often denoted by [latex]U[/latex], is the set that contains all elements under consideration for a particular discussion or problem. All other sets are considered subsets of the universal set.
Example 4.23
If we are discussing integers from [latex]1[/latex] to [latex]10[/latex], then [latex]U = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}[/latex].
Let [latex]A = \{ 2, 4, 6, 8\}[/latex]. Then [latex]A \subseteq U[/latex].
The set of all elements in the universal set [latex]U[/latex] that are not in [latex]A[/latex] is called the complement of a set [latex]A[/latex], and is denoted [latex]A^{c}[/latex] or [latex]\bar{A}[/latex]. Formally, we write [latex]A^{c} = \{ x \in U \mid x \notin A \}[/latex].
Example 4.24
Let [latex]U = \{ 1, 2, 3, 4, 5 \}[/latex] and [latex]A = \{ 2, 4 \}[/latex]. Then [latex]A^{c} = \{ 1, 3, 5 \}[/latex].
A Venn diagram is a visual representation of sets and their relationships using overlapping circles. The circles represent sets, and the overlapping regions show intersections, unions, and differences between sets.
Venn diagrams are especially useful for illustrating membership, subsets, intersections, unions, and complements.
Example 4.25
Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ 3, 4, 5 \}[/latex]. The Venn diagram below shows the circle for [latex]A[/latex] containing [latex]1[/latex], [latex]2[/latex], and [latex]3[/latex], the circle for [latex]B[/latex] containing [latex]3[/latex], [latex]4[/latex], and [latex]5[/latex], and the overlapping region (intersection) containing [latex]3[/latex].
Example 4.26
Let [latex]A[/latex] = people who like coffee and [latex]B[/latex] = people who like tea. The Venn diagram below shows people who like only coffee (in [latex]A[/latex] but not [latex]B[/latex]), people who like only tea (in [latex]B[/latex] but not [latex]A[/latex]), people who like both (in [latex]A \cap B[/latex]), and people who like neither (outside both circles since a universal set is shown).
Now that we have covered the basics of sets and their properties, we state and prove each of the fundamental laws of set theory that will be used for the remainder of this textbook.
Theorem 4.2: Fundamental Laws of Set Theory
Let [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex] be subsets of a universal set [latex]U[/latex]. The following identities hold:
Associative Laws
- [latex]A \cup (B \cup C) = (A \cup B) \cup C[/latex]
- [latex]A \cap (B \cap C) = (A \cap B) \cap C[/latex]
Commutative Laws
- [latex]A \cup B = B \cup A[/latex]
- [latex]A \cap B = B \cap A[/latex]
Distributive Laws
- [latex]A \cap (B \cup C) = (A \cap B) \cup (A \cap C)[/latex]
- [latex]A \cup (B \cap C) = (A \cup B) \cap (A \cup C)[/latex]
Identity Laws
- [latex]A \cup \emptyset = A[/latex]
- [latex]A \cap U = A[/latex]
Complement Laws
- [latex]A \cup A^{c} = U[/latex]
- [latex]A \cap A^{c} = \emptyset[/latex]
Idempotent Laws
- [latex]A \cup A = A[/latex]
- [latex]A \cap A = A[/latex]
Bound Laws
- [latex]A \cup U = U[/latex]
- [latex]A \cap \emptyset = \emptyset[/latex]
Absorption Laws
- [latex]A \cup (A \cap B) = A[/latex]
- [latex]A \cap (A \cup B) = A[/latex]
Involution Law
- [latex](A^{c})^{c} = A[/latex]
0/1 Laws
- [latex]\emptyset^{c} = U[/latex]
- [latex]U^{c} = \emptyset[/latex]
De Morgan’s Laws
- [latex](A \cup B)^{c} = A^{c} \cap B^{c}[/latex]
- [latex](A \cap B)^{c} = A^{c} \cup B^{c}[/latex]
Associative Laws Proof
a. Let [latex]x \in A \cup (B \cup C)[/latex]. Then [latex]x \in A[/latex] or [latex]x \in B \cup C[/latex]. If [latex]x \in A[/latex], then [latex]x \in (A \cup B)[/latex], so [latex]x \in (A \cup B) \cup C[/latex]. If [latex]x \in B \cup C[/latex], then [latex]x \in B[/latex] or [latex]x \in C[/latex]. If [latex]x \in B[/latex], then [latex]x \in (A \cup B)[/latex], so [latex]x \in (A \cup B) \cup C[/latex]. If [latex]x \in C[/latex], then [latex]x \in (A \cup B) \cup C[/latex]. Thus, [latex]A \cup (B \cup C) \subseteq (A \cup B) \cup C[/latex].
Now let [latex]x \in (A \cup B) \cup C[/latex]. Then [latex]x \in A \cup B[/latex] or [latex]x \in C[/latex]. If [latex]x \in A \cup B[/latex], then [latex]x \in A[/latex] or [latex]x \in B[/latex]. If [latex]x \in A[/latex], then [latex]x \in A \cup (B \cup C)[/latex]. If [latex]x \in B[/latex], then [latex]x \in B \cup C[/latex], so [latex]x \in A \cup (B \cup C)[/latex]. Thus, [latex](A \cup B) \cup C \subseteq A \cup (B \cup C)[/latex].
Therefore, both sets are equal, that is, [latex]A \cup (B \cup C) = (A \cup B) \cup C[/latex].
[latex]\square[/latex]
b. Let [latex]x \in A \cap (B \cap C)[/latex]. Then [latex]x \in A[/latex] and [latex]x \in B \cap C[/latex]. So, [latex]x \in B[/latex] and [latex]x \in C[/latex]. Thus, [latex]x \in A \cap B[/latex] and [latex]x \in C[/latex], so [latex]x \in (A \cap B) \cap C[/latex]. Hence, [latex]A \cap (B \cap C) \subseteq (A \cap B) \cap C[/latex].
Now let [latex]x \in (A \cap B) \cap C[/latex]. Then [latex]x \in A \cap B[/latex] and [latex]x \in C[/latex]. So, [latex]x \in A[/latex] and [latex]x \in B[/latex], and [latex]x \in C[/latex]. Thus, [latex]x \in B \cap C[/latex], and [latex]x \in A[/latex], so [latex]x \in A \cap (B \cap C)[/latex]. Hence, [latex](A \cap B) \cap C \subseteq A \cap (B \cap C)[/latex].
Therefore, [latex]A \cap (B \cap C) = (A \cap B) \cap C.[/latex]
[latex]\square[/latex]
Commutative Laws Proof
a. Let [latex]x \in A \cup B[/latex]. Then [latex]x \in A[/latex] or [latex]x \in B[/latex]. This is logically equivalent to saying [latex]x \in B[/latex] or [latex]x \in A[/latex], which means [latex]x \in B \cup A[/latex]. So, [latex]A \cup B \subseteq B \cup A[/latex].
Now let [latex]x \in B \cup A[/latex]. Then [latex]x \in B[/latex] or [latex]x \in A[/latex]. This is logically equivalent to saying [latex]x \in A[/latex] or [latex]x \in B[/latex], which means [latex]x \in A \cup B[/latex]. Thus, [latex]B \cup A \subseteq A \cup B[/latex].
Therefore, [latex]A \cup B = B \cup A.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap B[/latex]. Then [latex]x \in A[/latex] and [latex]x \in B[/latex]. This is logically equivalent to [latex]x \in B[/latex] and [latex]x \in A[/latex], so [latex]x \in B \cap A[/latex]. Hence, [latex]A \cap B \subseteq B \cap A[/latex].
Now let [latex]x \in B \cap A[/latex]. Then [latex]x \in B[/latex] and [latex]x \in A[/latex]. This is logically equivalent to [latex]x \in A[/latex] and [latex]x \in B[/latex], so [latex]x \in A \cap B[/latex]. Hence, [latex]B \cap A \subseteq A \cap B[/latex].
Therefore, [latex]A \cap B = B \cap A.[/latex]
[latex]\square[/latex]
Distributive Laws Proof
a. Let [latex]x \in A \cap (B \cup C)[/latex]. Then [latex]x \in A[/latex] and [latex]x \in B \cup C[/latex]. So, [latex]x \in A[/latex] and [latex]x \in B[/latex] or [latex]x \in C[/latex]. If [latex]x \in B[/latex], then [latex]x \in A \cap B[/latex]. If [latex]x \in C[/latex], then [latex]x \in A \cap C[/latex]. So, [latex]x \in (A \cap B) \cup (A \cap C)[/latex]. Thus, [latex]A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)[/latex].
Now let [latex]x \in (A \cap B) \cup (A \cap C)[/latex]. Then [latex]x \in A \cap B[/latex] or [latex]x \in A \cap C[/latex]. If [latex]x \in A \cap B[/latex], then [latex]x \in A[/latex] and [latex]x \in B[/latex], so [latex]x \in B \cup C[/latex]. If [latex]x \in A[/latex] and [latex]C[/latex], then [latex]x \in A[/latex] and [latex]x \in C[/latex], so [latex]x \in B \cup C[/latex]. In both cases, [latex]x \in A \cap (B \cup C)[/latex]. Thus, [latex](A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)[/latex].
Therefore, [latex]A \cap (B \cup C) = (A \cap B) \cup (A \cap C).[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cup (B \cap C)[/latex]. Then [latex]x \in A[/latex] or [latex]x \in (B \cap C)[/latex]. If [latex]x \in A[/latex], then [latex]x \in A[/latex] or [latex]B[/latex] and [latex]x \in A[/latex] or [latex]C[/latex], so [latex]x \in (A \cup B) \cap (A \cup C)[/latex]. If [latex]x \in B \cap C[/latex], then [latex]x \in B[/latex] and [latex]x \in C[/latex], so [latex]x \in A \cup B[/latex] and [latex]x \in A \cup C[/latex], hence [latex]x \in (A \cup B) \cap (A \cup C)[/latex]. Thus, [latex]A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)[/latex].
Now let [latex]x \in (A \cup B) \cap (A \cup C)[/latex]. Then [latex]x \in A \cup B[/latex] and [latex]x \in A \cup C[/latex]. So, either [latex]x \in A[/latex], or [latex]x \in B[/latex] and [latex]x \in C[/latex]. In either case, [latex]x \in A \cup (B \cap C)[/latex]. Thus, [latex](A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)[/latex].
Therefore, [latex]A \cup (B \cap C) = (A \cup B) \cap (A \cup C).[/latex]
[latex]\square[/latex]
Identity Laws Proof
a. Let [latex]x \in A \cup \emptyset[/latex]. Then [latex]x \in A[/latex] or [latex]x \in \emptyset[/latex]. But [latex]\emptyset[/latex] has no elements, so [latex]x \in \emptyset[/latex] is never true. Therefore, [latex]x \in A[/latex]. So, [latex]A \cup \emptyset \subseteq A[/latex].
Now let [latex]x \in A[/latex]. Then [latex]x \in A \cup \emptyset[/latex]. So, [latex]A \subseteq A \cup \emptyset[/latex].
Therefore, [latex]A \cup \emptyset = A.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap U[/latex]. Then [latex]x \in A[/latex] and [latex]x \in U[/latex]. Since all elements of A are in [latex]U[/latex], this means [latex]x \in A[/latex]. So, [latex]A \cap U \subseteq A[/latex].
Now let [latex]x \in A[/latex]. Since [latex]A \subseteq U[/latex], [latex]x \in U[/latex]. Therefore, [latex]x \in A \cap U[/latex]. So, [latex]A \subseteq A \cap U[/latex].
Therefore, [latex]A \cap U = A.[/latex]
[latex]\square[/latex]
Complement Laws Proof
a. Let [latex]x \in A \cup A^{c}[/latex]. Then [latex]x \in A[/latex] or [latex]x \in A^{c}[/latex]. Of complements, [latex]A^{c} = \{ x \in U | x \notin A \}[/latex]. So, every element of [latex]U[/latex] is either in [latex]A[/latex] or not in [latex]A[/latex], which means [latex]x \in A \cup A^{c}[/latex] for all [latex]x \in U[/latex]. Thus, [latex]A \cup A^{c} = U.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap A^{c}[/latex]. Then [latex]x \in A[/latex] and [latex]x \in A^{c}[/latex]. But [latex]x \in A^{c}[/latex] means [latex]x \notin A[/latex]. So, [latex]x[/latex] cannot be in [latex]A[/latex] and not in [latex]A[/latex] at the same time – a contradiction. Therefore, no such [latex]x[/latex] exists[/latex], and [latex]A \cap A^{c} = \emptyset.[/latex]
[latex]\square[/latex]
Idempotent Laws Proof
a. Let [latex]x \in A \cup A[/latex]. Then [latex]x \in A[/latex] or [latex]x \in A[/latex], which is just [latex]x \in A[/latex]. So, [latex]A \cup A \subseteq A[/latex].
If [latex]x \in A[/latex], then [latex]x \in A \cup A[/latex]. So, [latex]A \subseteq A \cup A[/latex].
Therefore, [latex]A \cup A = A.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap A[/latex]. Then [latex]x \in A[/latex] and [latex]x \in A[/latex], which is just [latex]x \in A[/latex]. So, [latex]A \cap A \subseteq A[/latex].
If [latex]x \in A[/latex], then [latex]x \in A \cap A[/latex]. So, [latex]A \subseteq A \cap A[/latex].
Therefore, [latex]A \cap A = A.[/latex]
[latex]\square[/latex]
Bound Laws Proof
a. Let [latex]x \in A \cup U[/latex]. Then [latex]x \in A[/latex] or [latex]x \in U[/latex]. But since [latex]U[/latex] contains all elements under consideration, [latex]x \in U[/latex] is always true. So, [latex]x \in U[/latex], and thus [latex]A \cup U \subseteq U[/latex].
Now let [latex]x \in U[/latex]. Then [latex]x \in A \cup U[/latex]. So, [latex]U \subseteq A \cup U[/latex].
Therefore, [latex]A \cup U = U.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap \emptyset[/latex]. Then [latex]x \in A[/latex] and [latex]x \in \emptyset[/latex]. But [latex]\emptyset[/latex] has no elements, so this is impossible. Therefore, no such [latex]x[/latex] exists, and [latex]A \cap \emptyset = \emptyset.[/latex]
[latex]\square[/latex]
Absorption Laws Proof
a. Let [latex]x \in A \cup (A \cap B)[/latex]. Then [latex]x \in A[/latex] or [latex]x \in (A \cap B)[/latex]. If [latex]x \in A[/latex], then [latex]x \in A[/latex]. If [latex]x \in A \cap B[/latex], then [latex]x \in A[/latex] and [latex]x \in B[/latex], so [latex]x \in A[/latex]. So, [latex]A \cup (A \cap B) \subseteq A[/latex].
Now let [latex]x \in A[/latex]. Then [latex]x \in A \cup (A \cap B)[/latex]. So, [latex]A \subseteq A \cup (A \cap B)[/latex].
Therefore, [latex]A \cup (A \cap B) = A.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in A \cap (A \cup B)[/latex]. Then [latex]x \in A[/latex] and [latex]x \in (A \cup B)[/latex]. Since [latex]x \in A[/latex], this is already satisfied. So, [latex]A \cap (A \cup B) \subseteq A[/latex].
Now let [latex]x \in A[/latex]. Then [latex]x \in A \cup B[/latex], so [latex]x \in A \cap (A \cup B)[/latex]. Thus, [latex]A \subseteq A \cap (A \cup B)[/latex].
Therefore, [latex]A \cap (A \cup B) = A.[/latex]
[latex]\square[/latex]
Involution Law Proof
Let [latex]x \in (A^{c})^{c}[/latex]. Then [latex]x \notin A^{c}[/latex]. By the definition of complement, [latex]x \notin A^{c}[/latex] means [latex]x \in A[/latex]. So, [latex](A^{c})^{c} \subseteq A[/latex].
Now let [latex]x \in A[/latex]. Then [latex]x \notin A^{c}[/latex], so [latex]x \in (A^{c})^{c}[/latex]. Thus, [latex]A \subseteq (A^{c})^{c}[/latex].
Therefore, [latex](A^{c})^{c} = A.[/latex]
[latex]\square[/latex]
0/1 Laws Proof
a. By the definition of complement, [latex]\emptyset^{c} = \{ x \in U | x \notin \emptyset \}[/latex]. Since [latex]\emptyset[/latex] contains no elements, every element of [latex]U[/latex] is not in [latex]\emptyset[/latex]. Therefore, [latex]\emptyset^{c} = U[/latex].
[latex]\square[/latex]
b. Using the definition of complement, [latex]U^{c} = \{ x \in U | x \notin U \}[/latex]. But no element in [latex]U[/latex] can be not in [latex]U[/latex], so this set contains no elements. Therefore, [latex]U^{c} = \emptyset.[/latex]
[latex]\square[/latex]
De Morgan’s Laws Proof
a. Let [latex]x \in (A \cup B)^{c}[/latex]. Then [latex]x \notin A \cup B[/latex], which means [latex]x \notin A[/latex] and [latex]x \notin B[/latex]. So, [latex]x \in A^{c}[/latex] and [latex]x \in B^{c}[/latex], hence [latex]x \in A^{c} \cap B^{c}[/latex]. Thus, [latex](A \cup B)^{c} \subseteq A^{c} \cap B^{c}[/latex].
Now let [latex]x \in A^{c} \cap B^{c}[/latex]. Then [latex]x \in A^{c}[/latex] and [latex]x \in Bc[/latex], so [latex]x \notin A[/latex] and [latex]x \notin B[/latex]. Therefore, [latex]x \notin A \cup B[/latex], which means [latex]x \in (A \cup B)^{c}[/latex]. Thus, [latex]A^{c} \cap B^{c} \subseteq (A \cup B)^{c}[/latex].
Therefore, [latex](A \cup B)^{c} = A^{c} \cap B^{c}.[/latex]
[latex]\square[/latex]
b. Let [latex]x \in (A \cap B)^{c}[/latex]. Then [latex]x \notin A \cap B[/latex], which means [latex]x \notin A[/latex] or [latex]x \notin B[/latex]. So, [latex]x \in A^{c}[/latex] and [latex]x \in B^{c}[/latex], hence [latex]x \in A^{c} \cap B^{c}[/latex]. Thus, [latex](A \cup B)^{c} \subseteq A^{c} \cap B^{c}[/latex].
Now let [latex]x \in A^{c} \cap B^{c}[/latex]. Then [latex]x \in A^{c}[/latex] and [latex]x \in B^{c}[/latex], so [latex]x \notin A[/latex] and [latex]x \notin B[/latex]. Therefore, [latex]x \notin A \cup B[/latex], which means [latex]x \in (A \cup B)^{c}[/latex]. Thus, [latex]A^{c} \cap B^{c} \subseteq (A \cup B)^{c}[/latex].
Therefore, [latex](A \cup B)^{c} = A^{c} \cap B^{c}.[/latex]
[latex]\square[/latex]
Real-World Example 4.1: Online Streaming Preferences
Imagine a streaming service wants to analyze user preferences to recommend content. Suppose
[latex]A[/latex] = set of users who like action movies = {Aiden, Benjamin, Chloe},
[latex]B[/latex] = set of users who like comedy movies = {Benjamin, Daniel, Eve}, and
[latex]C[/latex] = set of users who like drama movies = {Chloe, Eve, Frank}.
If we want to know which users like action or comedy, then we compute
[latex]A \cup B[/latex] = users who like action or comedy = {Aiden, Benjamin, Chloe, Daniel, Eve}
If we want to know which users like both comedy and drama, then we compute
[latex]B \cap C[/latex] = users who like both comedy and drama = {Eve}
For users who like action but not drama, we compute
[latex]A - C[/latex] = users who like action but not drama = {Aiden, Benjamin}
The users who don’t like action movies would be
[latex]A^{c}[/latex] = {Daniel, Eve, Frank, Gillian}
