5.S: Set Theory (Summary)
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86127
( \newcommand{\kernel}{\mathrm{null}\,}\)
Important Definitions
- Equal sets, page 55
- Subset, page 55
- Proper subset, page 218
- Power set, page 222
- Cardinality of a finite set, page 223
- Intersection of two sets, page 216
- Union of two sets, page 216
- Set difference, page 216
- Complement of a set, page 216
- Disjoint sets, page 236
- Cartesian product of two sets, pages 256
- Ordered pair, page 256
- Union over a family of sets, page 265
- Intersection over a family of sets, page 265
- Indexing set, page 268
- Indexed family of sets, page 268
- Union over an indexed family of sets, page 269
- Intersection over an indexed family of sets, page 269
- Pairwise disjoint family of sets, page 272
Important Theorems and Results about Sets
- Theorem 5.5. Let n be a nonnegative integer and let A be a subset of some universal set. If A is a finite set with n elements, then A has 2n subsets. That is, if |A|=n, then |P(A)|=2n.
- Theorem 5.18. Let A, B, and C be subsets of some universal set U. Then all of the following equalities hold.
Properties of the Empty Set A∩∅=∅ A∩U=A
and the Universal Set A∪∅=A A∪U=U
Idempotent Laws A∩A=A A∪A=A
Commutative Laws. A∩B=B∩A A∪B=B∪A
Associative Laws (A∩B)∩C=A∩(B∩C)
(A∪B)∪C=A∪(B∪C)
Distributive Laws A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C) - Theorem 5.20. Let A and B be subsets of some universal set U. Then the following are true:
Basic Properties(Ac)c=AA−B=A∩BcEmpty Set, Universal Set A−∅=A and A−U=∅∅c=U and Uc=∅De Morgan's Laws(A∩B)c=Ac∪Bc(A∪B)c=Ac∩BcSubsets and ComplementsA⊆B if and only if Bc⊆Ac. - Theorem 5.25. Let A, B, and C be sets. Then
1. A×(B∩C)=(A×B)∩(A×C)
2. A×(B∪C)=(A×B)∪(A×C)
3. (A∩B)×C=(A×C)∩(B×C)
4. (A∪B)×C=(A×C)∪(B×C)
5. A×(B−C)=(A×B)−(A×C)
6. (A−B)×C=(A×C)−(B×C)
7. If T⊆A, then T×B⊆A×B.
8. If T⊆B, then A×Y⊆A×B. - Theorem 5.30. Let Λ be a nonempty indexing set and let A={Aα | α∈Λ} be an indexed family of sets. Then
1. For each β∈Λ, ⋂α∈ΛAα⊆Aβ.
2. For each β∈Λ, Aβ⊆⋂α∈ΛAα.
3. (⋂α∈ΛAα)c=⋃α∈ΛAcα
4. (⋃α∈ΛAα)c=⋂α∈ΛAcα
Parts(3) and (4) are known as De Morgan's Laws. - Theorem 5.31. Let Λ be a nonempty indexing set, let A={Aα | α∈Λ} be an indexed family of sets, and let B be a set. Then
1. B∩(⋃α∈ΛAα)=⋃α∈Λ(B∩Aα), and
2. B∪(⋂α∈ΛAα)=⋂α∈Λ(B∪Aα),
Important Proof Method
The Choose-an-Element Method
The choose-an-element method is frequently used when we encounter a universal quantifier in a statement in the backward process of a proof. This statement often has the form
For each element with a given property, something happens.
In the forward process of the proof, we then we choose an arbitrary element with the given property.
Whenever we choose an arbitrary element with a given property, we are not selecting a specific element. Rather, the only thing we can assume about the element is the given property.
For more information, see page 232.