Chapter 1: Sets and Operations of Sets, Relations and Functions
1. Sets
Definition
A set is a well-defined collection of distinct objects, called elements. Well-defined means that for any object, it must be unambiguous whether it belongs to the set or not.
Example
- A = {2, 4, 6, 8} is a set
- B = {good students} is not a set (not well-defined)
Representation of Sets
(a) Roster (Tabular) Form
Elements are listed explicitly.
Example: A = {1, 3, 5, 7}
(b) Set-Builder Form
Elements are described using a property.
Example: A = {x | x ∈ ℕ, x is odd and x < 10}
Common Sets Used in CS
- ℕ – Natural numbers
- ℤ – Integers
- ℚ – Rational numbers
- ℝ – Real numbers
Types of Sets
Empty Set (∅)
A set with no elements.
Example: A = {x ∈ ℕ | x < 0} = ∅
Finite and Infinite Sets
- Finite: {a, b, c}
- Infinite: ℕ = {1, 2, 3, ...}
Subset
A ⊆ B if every element of A is also an element of B.
Example: A = {1, 2}, B = {1, 2, 3, 4} ⇒ A ⊆ B
Proper Subset
A ⊂ B if A ⊆ B and A ≠ B
Cardinality of a Set
The number of elements in a set A is denoted by |A|.
Example: A = {a, b, c, d} ⇒ |A| = 4
2. Operations on Sets
Let A and B be subsets of a universal set U.
Union (A ∪ B)
Set of all elements that belong to A or B or both.
[ A ∪ B = {x | x ∈ A \lor x ∈ B} ]
Example A = {1, 2, 3}, B = {3, 4, 5} A ∪ B = {1, 2, 3, 4, 5}
Intersection (A ∩ B)
Set of elements common to both A and B.
[ A ∩ B = {x | x ∈ A \land x ∈ B} ]
Example A ∩ B = {3}
Difference (A − B)
Elements in A but not in B.
[ A − B = {x | x ∈ A \land x ∉ B} ]
Example A − B = {1, 2}
Complement
Elements in the universal set that are not in A.
[ A' = U − A ]
Symmetric Difference
Elements in either A or B but not in both.
[ A Δ B = (A − B) ∪ (B − A) ]
3. Laws of Set Algebra
These laws are fundamental for proofs, simplifications, and CS logic.
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) ]
De Morgan’s Laws
Very important for Boolean algebra and digital logic.
[ (A ∪ B)' = A' ∩ B' ] [ (A ∩ B)' = A' ∪ B' ]
4. Cartesian Product
If A and B are sets, the Cartesian product A × B is:
[ A × B = {(a, b) | a ∈ A, b ∈ B} ]
Example A = {1, 2}, B = {x, y}
[ A × B = {(1,x),(1,y),(2,x),(2,y)} ]
Important Note
- |A × B| = |A| × |B|
- A × B ≠ B × A (generally)
5. Relations
Definition
A relation R from set A to set B is any subset of A × B.
[ R ⊆ A × B ]
Example
A = {1, 2, 3} B = {a, b}
R = {(1, a), (2, b)}
Domain and Range
- Domain: {1, 2}
- Range: {a, b}
Types of Relations
Reflexive Relation
[ (a, a) ∈ R \quad \forall a ∈ A ]
Example: R = {(1,1),(2,2),(3,3)}
Symmetric Relation
[ (a,b) ∈ R ⇒ (b,a) ∈ R ]
Transitive Relation
[ (a,b),(b,c) ∈ R ⇒ (a,c) ∈ R ]
Antisymmetric Relation
[ (a,b),(b,a) ∈ R ⇒ a = b ]
Equivalence Relation
A relation that is:
- Reflexive
- Symmetric
- Transitive
CS Application: Partitioning data into equivalence classes.
6. Functions
Definition
A function f from A to B is a relation where each element of A is mapped to exactly one element of B.
[ f : A → B ]
Example
f(x) = x², where A = ℕ and B = ℕ
Domain, Codomain, Range
- Domain = A
- Codomain = B
- Range = {x² | x ∈ ℕ}
Types of Functions
Injective (One-to-One)
[ f(x_1) = f(x_2) ⇒ x_1 = x_2 ]
Surjective (Onto)
Every element of B has a preimage in A.
Bijective
Both injective and surjective. Only bijective functions have inverses.
Many-to-One Function
Multiple elements in domain map to the same element in codomain.
Example: f(x) = x² over integers
7. Composition of Functions
If f : A → B g : B → C
Then: [ (g ∘ f)(x) = g(f(x)) ]
8. Inverse of a Function
A function f has an inverse if and only if it is bijective.
[ f^{-1}(y) = x \text{ where } f(x) = y ]