Back to: Mathematics – Freshman Courses
0
Chapter 1: Propositional Logic and Set Theory
1.4 Set Theory
Set theory is the foundation of modern mathematics. It provides the language and tools to describe collections of objects, define functions, and reason about infinity, logic, and structure. In this section, we explore the basic concepts of sets, their representations, relationships, and operations.
1.4.1 The Concept of a Set
Definition: A set is a well-defined collection of distinct objects, called elements or members.
“Well-defined” means that for any object, we can definitively say whether it belongs to the set or not.
- The set of vowels in English:
{a, e, i, o, u} - The set of prime numbers less than 10:
{2, 3, 5, 7} - Not a set: “The set of all large numbers” — not well-defined.
Notation:
- If \( x \) is an element of set \( A \), we write \( x \in A \).
- If \( x \) is not in \( A \), we write \( x \notin A \).
- Sets are usually denoted by capital letters: \( A, B, C, \dots \)
- Elements are denoted by lowercase letters: \( a, b, c, \dots \)
1.4.2 Description of Sets
There are four main ways to describe a set:
1. Verbal Method
Describe the set in words.
“The set of all even integers between 1 and 10.”
2. Roster (Complete Listing) Method
List all elements within curly braces, without repetition.
\( A = \{2, 4, 6, 8, 10\} \)
Important:
- Order doesn’t matter: \( \{1,2\} = \{2,1\} \)
- No duplicates: \( \{a,a,b\} = \{a,b\} \)
3. Partial Listing (Pattern) Method
Used when the set is too large (or infinite). Show a pattern with ellipses (\(…\)).
- Natural numbers: \( \mathbb{N} = \{1, 2, 3, \dots\} \)
- Integers: \( \mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\} \)
4. Set-Builder Method
Define a set by a property that all elements satisfy.
\( A = \{ x \mid P(x) \} \) or \( A = \{ x : P(x) \} \)
Read as: “The set of all \(x\) such that \(P(x)\) is true.”
Read as: “The set of all \(x\) such that \(P(x)\) is true.”
- \( A = \{ x \in \mathbb{Z} \mid x \text{ is even} \} \)
- \( B = \{ x \in \mathbb{R} \mid x^2 – 4 = 0 \} = \{-2, 2\} \)
1.4.3 Special Sets
Empty Set (Null Set): A set with no elements, denoted \( \varnothing \) or \( \{\} \).
\( \{ x \in \mathbb{R} \mid x^2 + 1 = 0 \} = \varnothing \)
Universal Set (\(U\)): The set that contains all objects under discussion in a given context.
1.4.4 Relationships Between Sets
Subset: \( B \subseteq A \) if every element of \( B \) is also in \( A \).
Formally: \( (\forall x)(x \in B \Rightarrow x \in A) \)
Formally: \( (\forall x)(x \in B \Rightarrow x \in A) \)
Proper Subset: \( B \subset A \) if \( B \subseteq A \) and \( B \ne A \).
Let \( A = \{1, 2, 3\} \), \( B = \{1, 2\} \), \( C = \{1, 2, 3\} \).
Then:
Then:
- \( B \subseteq A \) and \( B \subset A \)
- \( C \subseteq A \) but \( C \not\subset A \) (since they’re equal)
Important facts:
- \( \varnothing \subseteq A \) for any set \( A \)
- \( A \subseteq A \) (reflexivity)
- If \( A \subseteq B \) and \( B \subseteq C \), then \( A \subseteq C \) (transitivity)
Set Equality: \( A = B \) iff \( A \subseteq B \) and \( B \subseteq A \).
1.4.5 Power Set
The power set of \( A \), denoted \( \mathcal{P}(A) \), is the set of all subsets of \( A \).
If \( A = \{x, y\} \), then:
\( \mathcal{P}(A) = \big\{ \varnothing, \{x\}, \{y\}, \{x, y\} \big\} \)
\( \mathcal{P}(A) = \big\{ \varnothing, \{x\}, \{y\}, \{x, y\} \big\} \)
If \( A \) has \( n \) elements, then \( \mathcal{P}(A) \) has \( 2^n \) elements.
Example: For \( A = \{a, b, c\} \),
\( \mathcal{P}(A) = \big\{ \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \big\} \)
1.4.6 Set Operations
Union: \( A \cup B = \{ x \mid x \in A \lor x \in B \} \)
Intersection: \( A \cap B = \{ x \mid x \in A \land x \in B \} \)
Disjoint Sets: If \( A \cap B = \varnothing \), then \( A \) and \( B \) are disjoint.
Set Difference: \( A – B = A \setminus B = \{ x \mid x \in A \land x \notin B \} \)
Complement: If \( U \) is the universal set, then the complement of \( A \) is:
\( A’ = A^c = U – A = \{ x \in U \mid x \notin A \} \)
\( A’ = A^c = U – A = \{ x \in U \mid x \notin A \} \)
Let \( U = \{1,2,3,4,5\} \), \( A = \{1,2\} \), \( B = \{2,3,4\} \). Then:
- \( A \cup B = \{1,2,3,4\} \)
- \( A \cap B = \{2\} \)
- \( A – B = \{1\} \)
- \( A’ = \{3,4,5\} \)
De Morgan’s Laws for Sets
- \( (A \cup B)’ = A’ \cap B’ \)
- \( (A \cap B)’ = A’ \cup B’ \)
1.4.7 Symmetric Difference
The symmetric difference of \( A \) and \( B \) is:
\( A \triangle B = (A – B) \cup (B – A) \)
\( A \triangle B = (A – B) \cup (B – A) \)
If \( A = \{1,2,3\} \), \( B = \{3,4\} \), then:
\( A \triangle B = \{1,2,4\} \)
\( A \triangle B = \{1,2,4\} \)
1.4.8 Fundamental Set Identities
| Law | Identity |
|---|---|
| Commutative | \( A \cup B = B \cup A \), \( A \cap B = B \cap A \) |
| Associative | \( A \cup (B \cup C) = (A \cup B) \cup C \) \( A \cap (B \cap C) = (A \cap B) \cap C \) |
| Distributive | \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \) \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) |
| Identity | \( A \cup \varnothing = A \), \( A \cap U = A \) |
| Complement | \( A \cup A’ = U \), \( A \cap A’ = \varnothing \) |
| Double Complement | \( (A’)’ = A \) |
| Idempotent | \( A \cup A = A \), \( A \cap A = A \) |
1.4.9 Venn Diagrams (Conceptual)
Although we can’t embed graphics here, Venn diagrams represent sets as circles inside a rectangle (the universal set \( U \)).
- Union \( A \cup B \): shaded region covering both circles.
- Intersection \( A \cap B \): overlapping region only.
- Complement \( A’ \): everything outside circle \( A \) but inside \( U \).
- Disjoint sets: non-overlapping circles.
1.4.10 Summary of Key Ideas
- A set is a well-defined collection of distinct objects.
- Sets can be described verbally, by listing, or using set-builder notation.
- \( \varnothing \) is a subset of every set.
- Power set \( \mathcal{P}(A) \) has \( 2^n \) elements if \( |A| = n \).
- Set operations mirror logical connectives: union ↔ OR, intersection ↔ AND.
- De Morgan’s Laws apply to both logic and sets.
End of Section 1.4 – Set Theory
Section 1.4: Set Theory – Exercises with Full Solutions
Exercise 1. Which of the following are sets?
a. 1,2,3
b. {1,2},3
c. {{1},2},3
d. {1,{2},3}
e. {1,2,a,b}
a. 1,2,3
b. {1,2},3
c. {{1},2},3
d. {1,{2},3}
e. {1,2,a,b}
Solution:
A set must be a well-defined collection enclosed in braces.
A set must be a well-defined collection enclosed in braces.
- a. Not a set — missing braces.
- b. Not a set — only part “{1,2}” is a set; trailing “,3” makes whole expression invalid.
- c. Not a set — same issue as (b).
- d. Yes — valid set with elements 1, {2}, and 3.
- e. Yes — valid set with elements 1, 2, a, b.
Exercise 2. Which of the following sets can be described in complete listing, partial listing, and/or set-builder methods? Describe each by at least one method.
a. First 10 letters of English alphabet.
b. All countries in the world.
c. Students of Addis Ababa University in 2018/2019.
d. Positive multiples of 5.
e. All horses with six legs.
a. First 10 letters of English alphabet.
b. All countries in the world.
c. Students of Addis Ababa University in 2018/2019.
d. Positive multiples of 5.
e. All horses with six legs.
Solution:
- a. Complete listing: {a, b, c, d, e, f, g, h, i, j}
- b. Set-builder: {x | x is a sovereign country}
- c. Set-builder: {x | x was a registered student at AAU in 2018/19}
- d. Partial listing: {5, 10, 15, 20, …} or set-builder: {x ∈ ℕ | x is divisible by 5}
- e. Empty set: ∅ — since no six-legged horses exist. Complete listing: {}
Exercise 3. Write each set by listing its elements.
a. \( A = \{x \in \mathbb{Z} : -4 < x \leq 4\} \)
b. \( B = \{x \in \mathbb{Z} : x^2 < 5\} \)
c. \( C = \{x \in \mathbb{N} : x^3 < 5\} \)
d. \( D = \{x \in \mathbb{R} : x^2 – x = 0\} \)
e. \( E = \{x \in \mathbb{R} : x^2 + 1 = 0\} \)
a. \( A = \{x \in \mathbb{Z} : -4 < x \leq 4\} \)
b. \( B = \{x \in \mathbb{Z} : x^2 < 5\} \)
c. \( C = \{x \in \mathbb{N} : x^3 < 5\} \)
d. \( D = \{x \in \mathbb{R} : x^2 – x = 0\} \)
e. \( E = \{x \in \mathbb{R} : x^2 + 1 = 0\} \)
Solution:
- a. \( A = \{-3, -2, -1, 0, 1, 2, 3, 4\} \)
- b. \( x^2 < 5 \Rightarrow x \in \{-2, -1, 0, 1, 2\} \) → \( B = \{-2, -1, 0, 1, 2\} \)
- c. \( x \in \mathbb{N} = \{1,2,3,\dots\} \). \( 1^3 = 1 < 5 \), \( 2^3 = 8 > 5 \) → \( C = \{1\} \)
- d. \( x(x – 1) = 0 \Rightarrow x = 0 \text{ or } 1 \) → \( D = \{0, 1\} \)
- e. No real solution → \( E = \varnothing \)
Exercise 4. Let \( A = \{ \text{positive even integers} < 15 \} = \{2,4,6,8,10,12,14\} \). Determine truth value:
a. \( 15 \in A \)
b. \( -16 \in A \)
c. \( \varnothing \in A \)
d. \( 12 \subset A \)
e. \( \{2,8,14\} \in A \)
f. \( \{2,3,4\} \subseteq A \)
g. \( \{2,4\} \in A \)
h. \( \varnothing \subset A \)
i. \( \{246\} \subseteq A \)
a. \( 15 \in A \)
b. \( -16 \in A \)
c. \( \varnothing \in A \)
d. \( 12 \subset A \)
e. \( \{2,8,14\} \in A \)
f. \( \{2,3,4\} \subseteq A \)
g. \( \{2,4\} \in A \)
h. \( \varnothing \subset A \)
i. \( \{246\} \subseteq A \)
Solution:
- a. False — 15 is odd
- b. False — negative not positive
- c. False — ∅ is not an element of A
- d. False — 12 is a number, not a set; ⊂ applies to sets
- e. False — {2,8,14} is a subset, not an element
- f. False — 3 ∉ A
- g. False — {2,4} is not an element of A
- h. True — ∅ is subset of every nonempty set
- i. False — 246 ∉ A, so {246} ⊈ A
Exercise 5. Find truth value and justify:
a. \( \varnothing \subseteq \varnothing \)
b. \( \{1,2\} \subseteq \{1,2\} \)
c. \( \varnothing \in A \) for any set A
d. \( \{\varnothing\} \subseteq A \) for any set A
e. \( 5,7 \subseteq \{5,6,7,8\} \)
f. \( \varnothing \in \{\{\varnothing\}\} \)
g. For any set A, \( A \subset A \)
h. \( \{\varnothing\} = \varnothing \)
a. \( \varnothing \subseteq \varnothing \)
b. \( \{1,2\} \subseteq \{1,2\} \)
c. \( \varnothing \in A \) for any set A
d. \( \{\varnothing\} \subseteq A \) for any set A
e. \( 5,7 \subseteq \{5,6,7,8\} \)
f. \( \varnothing \in \{\{\varnothing\}\} \)
g. For any set A, \( A \subset A \)
h. \( \{\varnothing\} = \varnothing \)
Solution:
- a. True — empty set is subset of every set, including itself.
- b. True — every set is a subset of itself.
- c. False — e.g., A = {1}, ∅ ∉ A.
- d. False — only if ∅ ∈ A; not true for A = {1}.
- e. Nonsense — “5,7” is not a set; if meant {5,7}, then True.
- f. False — only element is {∅}, not ∅.
- g. False — proper subset requires A ≠ A.
- h. False — {∅} has one element; ∅ has none.
Exercise 6. Find power set of:
a. {ab}
b. {1, 1.5}
c. {a, b}
d. {a, 0.5, x}
a. {ab}
b. {1, 1.5}
c. {a, b}
d. {a, 0.5, x}
Solution:
- a. \( \mathcal{P} = \{ \varnothing, \{ab\} \} \)
- b. \( \mathcal{P} = \{ \varnothing, \{1\}, \{1.5\}, \{1, 1.5\} \} \)
- c. \( \mathcal{P} = \{ \varnothing, \{a\}, \{b\}, \{a,b\} \} \)
- d. \( \mathcal{P} = \{ \varnothing, \{a\}, \{0.5\}, \{x\}, \{a,0.5\}, \{a,x\}, \{0.5,x\}, \{a,0.5,x\} \} \)
Exercise 7 & 8. How many subsets and proper subsets for sets with 1,2,3,4,8,10,20 elements? Find formula.
Solution:
If \( |A| = n \), then:
If \( |A| = n \), then:
- Number of subsets = \( 2^n \)
- Number of proper subsets = \( 2^n – 1 \)
- n=1: 2 subsets, 1 proper
- n=2: 4 subsets, 3 proper
- n=3: 8 subsets, 7 proper
- n=4: 16 subsets, 15 proper
- n=8: 256 subsets, 255 proper
- n=10: 1024 subsets, 1023 proper
- n=20: 1,048,576 subsets, 1,048,575 proper
Exercise 9. Is there a set A with exactly:
a. Only one subset?
b. Only one proper subset?
c. Exactly 3 proper subsets?
d. Exactly 4 subsets?
a. Only one subset?
b. Only one proper subset?
c. Exactly 3 proper subsets?
d. Exactly 4 subsets?
Solution:
- a. Yes — A = ∅. Subsets: {∅} → 1 subset.
- b. Yes — |A| = 2 → 3 subsets total → 2 proper? Wait: proper subsets = \( 2^n – 1 \). Set = 1 ⇒ \( 2^n – 1 = 1 \Rightarrow n = 1 \). A = {x} → proper subsets: {∅} → exactly 1. ✅
- c. Proper subsets = 3 ⇒ \( 2^n – 1 = 3 \Rightarrow 2^n = 4 \Rightarrow n = 2 \). Yes: A = {a,b} → proper subsets: ∅, {a}, {b}.
- d. Subsets = 4 ⇒ \( 2^n = 4 \Rightarrow n = 2 \). Yes: e.g., {a,b}.
Exercise 10. How many elements if A has:
a. 64 subsets?
b. 31 proper subsets?
c. No proper subset?
d. 255 proper subsets?
a. 64 subsets?
b. 31 proper subsets?
c. No proper subset?
d. 255 proper subsets?
Solution:
- a. \( 2^n = 64 \Rightarrow n = 6 \)
- b. \( 2^n – 1 = 31 \Rightarrow 2^n = 32 \Rightarrow n = 5 \)
- c. Only if A = ∅ → n = 0
- d. \( 2^n – 1 = 255 \Rightarrow 2^n = 256 \Rightarrow n = 8 \)
Exercise 11. Truth value:
a. \( \varnothing \in \mathcal{P}(\varnothing) \)
b. For any A, \( \varnothing \subseteq \mathcal{P}(A) \)
c. For any A, \( A \in \mathcal{P}(A) \)
d. For any A, \( A \subset \mathcal{P}(A) \)
a. \( \varnothing \in \mathcal{P}(\varnothing) \)
b. For any A, \( \varnothing \subseteq \mathcal{P}(A) \)
c. For any A, \( A \in \mathcal{P}(A) \)
d. For any A, \( A \subset \mathcal{P}(A) \)
Solution:
- a. \( \mathcal{P}(\varnothing) = \{\varnothing\} \). So ∅ ∈ {∅} → True
- b. ∅ is subset of every set → True
- c. A ⊆ A ⇒ A ∈ 𝒫(A) → True
- d. False — e.g., A = {1}. Then 𝒫(A) = {∅, {1}}. But 1 ∉ 𝒫(A), so A ⊈ 𝒫(A).
Exercise 12. Prove:
a. If \( A \subseteq B \) and \( B \subseteq C \), then \( A \subseteq C \).
b. If \( A \subset B \) and \( B \subset C \), then \( A \subset C \).
a. If \( A \subseteq B \) and \( B \subseteq C \), then \( A \subseteq C \).
b. If \( A \subset B \) and \( B \subset C \), then \( A \subset C \).
Solution:
a. Let \( x \in A \). Since \( A \subseteq B \), \( x \in B \). Since \( B \subseteq C \), \( x \in C \). So every \( x \in A \Rightarrow x \in C \) → \( A \subseteq C \).
b. From (a), \( A \subseteq C \). Also, \( A \ne B \) and \( B \ne C \). Suppose \( A = C \). Then \( A = C \supset B \supset A \), contradiction. So \( A \ne C \). Hence \( A \subset C \).
a. Let \( x \in A \). Since \( A \subseteq B \), \( x \in B \). Since \( B \subseteq C \), \( x \in C \). So every \( x \in A \Rightarrow x \in C \) → \( A \subseteq C \).
b. From (a), \( A \subseteq C \). Also, \( A \ne B \) and \( B \ne C \). Suppose \( A = C \). Then \( A = C \supset B \supset A \), contradiction. So \( A \ne C \). Hence \( A \subset C \).
All exercises from Section 1.4: Set Theory with full solutions.