MTH 331 – Sheet 7
Introduction
Definition 32 (Set). A set is a well-defined (i.e. it is always possible to determine if an
object is in the set or not) collection of distinct objects. The objects in the set are called
elements. If a set has no elements it is called the empty set and denote it by ∅.
Notation 33 (Set-builder notation). Let P (x) be a statement about a variable x. The set
of all elements x which satisfy P (x) is denoted by {x : P (x)}.
For instance, the set of even integers can be denoted {n ∈ Z : 2 divides n}.
Definition 34 (Equality of sets). Let A and B be sets. We say that A is equal to B if
they have exactly the same elements (i.e. for all x, x ∈ A if and only if x ∈ B).
Definition 35 (Subset). Let A and B be sets. We say that A is a subset of B, denoted
A ⊆ B, if every element of A is an element of B. Symbolically, A ⊆ B ≡ ∀x, x ∈ A⇒ x ∈
B.
Note: A 6⊆ B means ¬(A ⊆ B) ≡ ¬(∀x, x ∈ A⇒ x ∈ B) ≡ ∃x, x ∈ A ∧ x 6∈ B.
Definition 36 (Intersection). Let A and B be sets. The intersection of A and B, denoted
A ∩ B, is the set of all elements which are contained in both A and B. Symbolically,
A ∩B = {x : x ∈ A ∧ x ∈ B}.
Definition 37 (Union). Let A and B be sets. The union of A and B, denoted A ∪ B, is
the set of all elements which are contained in A or B. Symbolically, A ∪ B = {x : x ∈
A ∨ x ∈ B}.
Definition 38 (Set difference). Let A and B be sets. The difference of A and B, denoted A\
B, is the set of all elements which are contained in A but not contained in B. Symbolically,
A \B = {x : x ∈ A ∧ x /∈ B}.
Definition 39 (Complement). Let A be a subset of a set U . The complement of A (with
respect to U), denoted A, is the set U \A.
Note: x ∈ A means x 6∈ A.
Definition 40 (Disjoint). Let A and B be sets. We say A and B are disjoint if A∩B = ∅.
Fact 41. Let A and B be sets. A = B if and only if A ⊆ B and B ⊆ A.
Fact 42. For all sets A, ∅ ⊆ A.
Fact 43. For all sets A, (A) = A.
21
Proposition 44. For all sets A,B,C,
(i) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C),
(ii) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C).
Proof. (i)
x ∈ A ∩ (B ∪ C) ≡ x ∈ A ∧ (x ∈ B ∪ C)
≡ x ∈ A ∧ (x ∈ B ∨ x ∈ C)
∗≡ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)
≡ (x ∈ A ∩B) ∨ (x ∈ A ∩ C)
≡ x ∈ (A ∩B) ∪ (A ∩ C)
(where * holds by the distributive law from Appendix B)
Since x ∈ A∩(B∪C) is equivalent to x ∈ (A∩B)∪(A∩C), we have that A∩(B∪C) =
(A ∩B) ∪ (A ∩ C).
Proposition 45. Let A and B be sets.
(i) A ∩B = A ∪B,
(ii) A ∪B = A ∩B.
Proof. (i)
x ∈ A ∩B ≡ x 6∈ A ∩B
≡ ¬(x ∈ A ∩B)
≡ ¬(x ∈ A ∧ x ∈ B)
∗≡ (x 6∈ A ∨ x 6∈ B)
≡ x ∈ A ∨ x ∈ B
≡ x ∈ A ∪B
(where * holds by the DeMorgan’s Laws)
Since x ∈ A ∩B is equivalent to x ∈ A ∪B, we have that A ∩B = A ∪B.
Fact 46. Let A, B, and C be sets. If A ⊆ B and B ⊆ C, then A ⊆ C.
Proof. Suppose A ⊆ B and B ⊆ C. Let x ∈ A. Since x ∈ A and A ⊆ B, then x ∈ B. Since
x ∈ B and B ⊆ C, then x ∈ C.
MTH 331 – Sheet 7
Extra practice
Statement 50. A ⊆ B ∩ C if and only if A ⊆ B and A ⊆ C.
Question 51. What are the distributive laws for set difference with respect to intersection
and union? (Only using intersection, union, and set difference). Prove your answers.
(i) A \ (B ∩ C) =?
(ii) A \ (B ∪ C) =?
(iii) (A ∩B) \ C =?
(iv) (A ∪B) \ C =?
(v) A ∩ (B \ C) =?
(vi) A ∪ (B \ C) =?
For presentation
Statement 52. Let A,B,C be sets.
(i) Prove or disprove: C ⊆ A ∪B if and only if C ⊆ A or C ⊆ B
(ii) Prove or disprove: If A ⊆ B and A ⊆ C, then B ⊆ C.
Statement 53. Let A,B,C,D be sets. If A \B ⊆ C \D, then A ∩D ⊆ B.
Statement 54. For all n ∈ Z+ and sets A1, A2, . . . , An,
(i) A1 ∩A2 ∩ · · · ∩An = A1 ∪A2 ∪ · · · ∪An.
(ii) A1 ∪A2 ∪ · · · ∪An = A1 ∩A2 ∩ · · · ∩An.
(Hint: First use induction to prove ¬(P1∧· · ·∧Pn) = ¬P1∨· · ·∨¬Pn and ¬(P1∨· · ·∨Pn) =
¬P1 ∧ · · · ∧ ¬Pn.)
Statement 55. {n ∈ Z : 15|n} ∩ {n ∈ Z : 2|n} ⊆ {n ∈ Z : 10|n}
Statement 56. For all sets A,B, A = (A \B) ∪ (A ∩B).
Statement 57. Let A and B be sets. A ⊆ B if and only if for all sets C, C \B ⊆ C \A.
For typing (Due Monday Oct 5)
Statement 58. Let A,B,C be sets. If C ⊆ A ∪B and B ∩ C = ∅, then C ⊆ A \B.
Statement 59. Let A and B be sets.
(i) A ⊆ B if and only if A ∪B = B.
(ii) A ⊆ B if and only if A ∩B = A.
(iii) A ⊆ B if and only if A \B = ∅.

欢迎咨询51作业君