1.1 Introduction to Sets
A set is a well-defined collection of distinct objects, called elements or members of the set.
Basic Notation:
- A = {1, 2, 3, 4} - Roster notation
- B = {x | x is an even integer} - Set-builder notation
- x ∈ A - x is an element of set A
- y ∉ A - y is not an element of set A
Important Number Sets:
- Natural Numbers: ℕ = {0, 1, 2, 3, ...}
- Integers: ℤ = {..., -2, -1, 0, 1, 2, ...}
- Positive Integers: ℤ⁺ = {1, 2, 3, ...}
- Rational Numbers: ℚ
- Real Numbers: ℝ
- Complex Numbers: ℂ
1.2 Subsets and Power Sets
Subset Relationships
- Subset: A ⊆ B if every element of A is also in B
- Proper Subset: A ⊂ B if A ⊆ B and A ≠ B
- Set Equality: A = B if A ⊆ B and B ⊆ A
Power Sets
The power set P(A) is the set of all subsets of A.
If |A| = n, then |P(A)| = 2^n.
Example: If A = {1, 2}, then
P(A) = {∅, {1}, {2}, {1,2}}
1.3 Set Operations
Basic Operations
- Union: A ∪ B = {x | x ∈ A or x ∈ B}
- Intersection: A ∩ B = {x | x ∈ A and x ∈ B}
- Complement: A^c = {x ∈ U | x ∉ A}
- Difference: A - B = {x | x ∈ A and x ∉ B}
- Symmetric Difference: A ⊖ B = (A ∪ B) - (A ∩ B)
Inclusion-Exclusion Principle
- |A ∪ B| = |A| + |B| - |A ∩ B|
- |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
1.4 Laws of Set Algebra
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)
De Morgan's Laws
(A ∪ B)^c = A^c ∩ B^c
(A ∩ B)^c = A^c ∪ B^c
1.5 Cartesian Products and Functions
Cartesian Product
The Cartesian product of sets A and B is:
A × B = {(a, b) | a ∈ A and b ∈ B}
Example: If A = {1, 2} and B = {x, y}, then
A × B = {(1,x), (1,y), (2,x), (2,y)}
Note: |A × B| = |A| × |B|
Functions
A function f: X → Y is a rule that assigns to each element in X exactly one element in Y.
- Domain: The set X (input set)
- Codomain: The set Y (possible output set)
- Range/Image: f(X) = {f(x) | x ∈ X} (actual outputs)
Function Properties
- Injective (One-to-one): If f(x₁) = f(x₂), then x₁ = x₂
- Surjective (Onto): For every y ∈ Y, there exists x ∈ X such that f(x) = y
- Bijective: Both injective and surjective
Practice Problems
Problem 1: Set Operations
Given: A = {1, 2, 3, 4} and B = {3, 4, 5, 6}
Find: A ∪ B, A ∩ B, and A - B
Solution:
- A ∪ B = {1, 2, 3, 4, 5, 6}
- A ∩ B = {3, 4}
- A - B = {1, 2}
Problem 2: Cartesian Product
Given: A = {a, b} and B = {1, 2, 3}
Find: A × B and |A × B|
Solution:
- A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}
- |A × B| = |A| × |B| = 2 × 3 = 6