Questions
3 questions in typical university papers
Difficulty
Medium
Importance
High yield for core discrete mathematics modules
Overview
Set Theory and Relations form the fundamental language of discrete mathematics, providing the structural basis for database theory, logic, and algorithm design. Mastering these concepts is essential for university exams as they serve as the building blocks for more advanced topics like Graph Theory and Boolean Algebra.
Set Operations
Set operations define how elements are combined or filtered between groups. These are standard foundations for data set manipulations and probability theory.
- Union: A ∪ B = {x | x ∈ A or x ∈ B}
- Intersection: A ∩ B = {x | x ∈ A and x ∈ B}
- Complement: A' = {x | x ∉ A and x ∈ U}
- Difference: A - B = {x | x ∈ A and x ∉ B}
- De Morgan's Laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'
- Principle of Inclusion-Exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
Relations & Equivalence Classes
A relation is a subset of a Cartesian product, defining how elements of sets relate to one another. Equivalence relations are particularly important as they partition a set into disjoint subsets.
- Reflexive: (a, a) ∈ R for all a ∈ A
- Symmetric: (a, b) ∈ R implies (b, a) ∈ R
- Transitive: (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R
- Equivalence Relation: Satisfies reflexivity, symmetry, and transitivity
- Equivalence Class [a]: {x ∈ A | xRa}
- Partition: A collection of disjoint sets whose union is the original set
Functions & Mappings
Functions map elements from a domain to a codomain such that each input relates to exactly one output. Understanding the behavior of surjective, injective, and bijective functions is critical for algorithm complexity analysis.
- Injective (One-to-One): f(a) = f(b) implies a = b
- Surjective (Onto): Range equals Codomain
- Bijective: Both injective and surjective
- Composition of functions: (f ∘ g)(x) = f(g(x))
- Identity function: f(x) = x
- Inverse function: f⁻¹ exists if and only if f is bijective
Formula Sheet
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|
(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'
n(A × B) = n(A) × n(B)
Total relations on set A of size n = 2^(n^2)
Total functions from set A (size m) to set B (size n) = n^m
Exam Tip
When proving an equivalence relation, always write out the formal definitions for reflexivity, symmetry, and transitivity explicitly before applying them to the specific variables given in the problem.
Common Mistakes
- Confusing reflexive relations with symmetric ones or failing to check transitivity across all possible triplets.
- Misapplying De Morgan's laws by forgetting to flip the union/intersection operator.
- Assuming every relation on a set is an equivalence relation without verifying all three required properties.
More Revision Notes
Ready to test yourself?
Play topic-wise Set Theory & Relations questions in Aspirant Arcade — gamified MCQ practice.
Download Free