Sets and Relations: The Language of Mathematical Structure
Introduction to Set Theory
Set theory provides the fundamental language for describing collections of objects and their relationships. It forms the foundation for virtually all areas of mathematics and computer science, from number systems and functions to databases and algorithms.
A set is simply a collection of distinct objects, called elements or members. Set theory gives us precise tools for working with these collections and understanding their properties and relationships.
Set Theory Foundations
═════════════════════
What is a Set?
• Collection of distinct objects
• Objects called elements or members
• Order doesn't matter: {1, 2, 3} = {3, 1, 2}
• No repetition: {1, 1, 2} = {1, 2}
• Can contain any type of objects
Examples:
• {1, 2, 3, 4, 5} - set of integers
• {red, blue, green} - set of colors
• {∅} - set containing the empty set
• ℕ = {1, 2, 3, ...} - set of natural numbers
• ℝ - set of real numbers
Applications:
• Database design (relations as sets of tuples)
• Programming (data structures, collections)
• Probability (sample spaces and events)
• Logic (domains of discourse)
• Computer graphics (sets of pixels, vertices)Basic Set Concepts
Set Notation and Membership
Set Notation
═══════════
Element Membership:
• a ∈ A: "a is an element of A" or "a belongs to A"
• a ∉ A: "a is not an element of A"
Examples:
• 3 ∈ {1, 2, 3, 4}
• 5 ∉ {1, 2, 3, 4}
• apple ∈ {apple, banana, orange}
Set Specification Methods:
1. Roster Method (List Elements):
A = {1, 2, 3, 4, 5}
B = {red, blue, green}
C = {2, 4, 6, 8, 10, ...}
2. Set-Builder Notation:
A = {x | P(x)} - "set of all x such that P(x) is true"
A = {x ∈ S | P(x)} - "set of all x in S such that P(x) is true"
Examples:
• {x | x is an even integer} = {... -4, -2, 0, 2, 4, ...}
• {x ∈ ℕ | x < 10} = {1, 2, 3, 4, 5, 6, 7, 8, 9}
• {x ∈ ℝ | x² = 4} = {-2, 2}
• {x ∈ ℤ | x is prime} = {2, 3, 5, 7, 11, 13, ...}
3. Interval Notation (for real numbers):
• [a, b] = {x ∈ ℝ | a ≤ x ≤ b} (closed interval)
• (a, b) = {x ∈ ℝ | a < x < b} (open interval)
• [a, b) = {x ∈ ℝ | a ≤ x < b} (half-open interval)
Special Sets:
• ∅ or {} - empty set (contains no elements)
• ℕ = {1, 2, 3, ...} - natural numbers
• ℤ = {..., -2, -1, 0, 1, 2, ...} - integers
• ℚ - rational numbers
• ℝ - real numbers
• ℂ - complex numbersSet Equality and Subsets
Set Relationships
════════════════
Set Equality:
A = B if and only if A and B have exactly the same elements
Formally: A = B ⟺ ∀x (x ∈ A ⟺ x ∈ B)
Examples:
• {1, 2, 3} = {3, 1, 2} (order doesn't matter)
• {1, 2, 2, 3} = {1, 2, 3} (repetition doesn't matter)
• {a, b} ≠ {a, b, c}
Subset:
A ⊆ B if every element of A is also an element of B
Formally: A ⊆ B ⟺ ∀x (x ∈ A → x ∈ B)
Examples:
• {1, 2} ⊆ {1, 2, 3, 4}
• ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ
• ∅ ⊆ A for any set A
• A ⊆ A for any set A
Proper Subset:
A ⊂ B if A ⊆ B and A ≠ B
A is a proper subset of B
Examples:
• {1, 2} ⊂ {1, 2, 3}
• ℕ ⊂ ℤ
• ∅ ⊂ {1, 2, 3} (unless A = ∅)
Superset:
A ⊇ B if B ⊆ A
A ⊃ B if B ⊂ A
Properties:
• Reflexive: A ⊆ A
• Antisymmetric: (A ⊆ B ∧ B ⊆ A) → A = B
• Transitive: (A ⊆ B ∧ B ⊆ C) → A ⊆ CSet Operations
Basic Set Operations
Fundamental Set Operations
═════════════════════════
Union (A ∪ B):
Set of elements that are in A or B (or both)
A ∪ B = {x | x ∈ A ∨ x ∈ B}
Examples:
• {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}
• {a, b} ∪ {c, d} = {a, b, c, d}
• A ∪ ∅ = A
Intersection (A ∩ B):
Set of elements that are in both A and B
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Examples:
• {1, 2, 3} ∩ {3, 4, 5} = {3}
• {a, b, c} ∩ {b, c, d} = {b, c}
• A ∩ ∅ = ∅
Difference (A - B or A \ B):
Set of elements that are in A but not in B
A - B = {x | x ∈ A ∧ x ∉ B}
Examples:
• {1, 2, 3, 4} - {3, 4, 5} = {1, 2}
• {a, b, c} - {b, d} = {a, c}
• A - ∅ = A
• A - A = ∅
Complement (A' or Ā):
Set of elements in universal set U that are not in A
A' = U - A = {x ∈ U | x ∉ A}
Examples (with U = {1, 2, 3, 4, 5}):
• If A = {1, 3, 5}, then A' = {2, 4}
• If A = {2, 4}, then A' = {1, 3, 5}
• ∅' = U
• U' = ∅
Symmetric Difference (A ⊕ B):
Set of elements that are in A or B but not in both
A ⊕ B = (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B)
Examples:
• {1, 2, 3} ⊕ {3, 4, 5} = {1, 2, 4, 5}
• {a, b} ⊕ {b, c} = {a, c}Properties of Set Operations
Set Operation Properties
══════════════════════
Identity Laws:
• A ∪ ∅ = A
• A ∩ U = A
Domination Laws:
• A ∪ U = U
• A ∩ ∅ = ∅
Idempotent Laws:
• A ∪ A = A
• A ∩ A = A
Complement Laws:
• A ∪ A' = U
• 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)
De Morgan's Laws:
• (A ∪ B)' = A' ∩ B'
• (A ∩ B)' = A' ∪ B'
Absorption Laws:
• A ∪ (A ∩ B) = A
• A ∩ (A ∪ B) = A
Example Application:
Simplify: (A ∪ B) ∩ (A ∪ B')
Using distributive law:
(A ∪ B) ∩ (A ∪ B') = A ∪ (B ∩ B')
= A ∪ ∅ (complement law)
= A (identity law)Venn Diagrams
Visual Representation of Sets
════════════════════════════
Venn Diagrams:
Visual tool for representing sets and their relationships
Rectangles represent universal set
Circles represent individual sets
Overlapping regions show intersections
Two-Set Venn Diagram:
┌─────────────────────────────┐
│ U │
│ ┌─────────┐ ┌─────────┐ │
│ │ A │ │ B │ │
│ │ ┌──┴───┴──┐ │ │
│ │ │ A ∩ B │ │ │
│ │ └──┬───┬──┘ │ │
│ │ │ │ │ │
│ └─────────┘ └─────────┘ │
│ │
└─────────────────────────────┘
Regions:
• A only: A - B
• B only: B - A
• Both A and B: A ∩ B
• Neither A nor B: (A ∪ B)'
Three-Set Venn Diagram:
Shows all possible intersections of three sets A, B, C
8 distinct regions total
Applications:
• Visualizing set operations
• Solving word problems
• Understanding logical relationships
• Database query design
• Probability problems
Example Problem:
In a class of 30 students:
• 18 study math
• 15 study physics
• 10 study both math and physics
• How many study neither?
Solution using Venn diagram:
• Math only: 18 - 10 = 8
• Physics only: 15 - 10 = 5
• Both: 10
• Total studying at least one: 8 + 5 + 10 = 23
• Neither: 30 - 23 = 7Cartesian Products and Relations
Cartesian Products
Cartesian Product Definition
══════════════════════════
Ordered Pair:
(a, b) where order matters: (a, b) ≠ (b, a) unless a = b
Cartesian Product:
A × B = {(a, b) | a ∈ A ∧ b ∈ B}
Set of all ordered pairs where first element from A, second from B
Examples:
• {1, 2} × {a, b} = {(1, a), (1, b), (2, a), (2, b)}
• {x, y} × {1, 2, 3} = {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)}
• ∅ × A = ∅
• A × ∅ = ∅
Properties:
• Generally not commutative: A × B ≠ B × A
• |A × B| = |A| × |B| (cardinality)
• A × (B ∪ C) = (A × B) ∪ (A × C)
• A × (B ∩ C) = (A × B) ∩ (A × C)
Higher-Order Products:
A × B × C = {(a, b, c) | a ∈ A, b ∈ B, c ∈ C}
Aⁿ = A × A × ... × A (n times)
Examples:
• ℝ² = ℝ × ℝ (coordinate plane)
• ℝ³ = ℝ × ℝ × ℝ (3D space)
• {0, 1}³ = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}
Applications:
• Coordinate systems
• Database tables (tuples)
• Function domains and codomains
• State spaces in computer science
• Probability sample spacesBinary Relations
Relations Between Sets
═════════════════════
Binary Relation:
R ⊆ A × B is a relation from A to B
If (a, b) ∈ R, we write aRb or R(a, b)
Examples:
• "Less than" relation on integers: R = {(a, b) | a < b}
• "Divides" relation: R = {(a, b) | a divides b}
• "Is parent of" relation on people
• "Is enrolled in" relation from students to courses
Relation on a Set:
R ⊆ A × A is a relation on set A
Examples:
• Equality: R = {(a, a) | a ∈ A}
• "Less than or equal": R = {(a, b) | a ≤ b}
• "Is sibling of" on set of people
Domain and Range:
• Domain: dom(R) = {a ∈ A | ∃b ∈ B, (a, b) ∈ R}
• Range: range(R) = {b ∈ B | ∃a ∈ A, (a, b) ∈ R}
Example:
R = {(1, a), (2, b), (2, c), (3, a)}
• dom(R) = {1, 2, 3}
• range(R) = {a, b, c}
Inverse Relation:
R⁻¹ = {(b, a) | (a, b) ∈ R}
Example:
If R = {(1, 2), (3, 4), (5, 6)}
Then R⁻¹ = {(2, 1), (4, 3), (6, 5)}
Composition of Relations:
If R ⊆ A × B and S ⊆ B × C, then
S ∘ R = {(a, c) | ∃b ∈ B, (a, b) ∈ R ∧ (b, c) ∈ S}
Example:
R = {(1, 2), (3, 4)} (from A to B)
S = {(2, x), (4, y)} (from B to C)
S ∘ R = {(1, x), (3, y)}Properties of Relations
Relation Properties
══════════════════
Let R be a relation on set A:
Reflexive:
∀a ∈ A, (a, a) ∈ R
Every element is related to itself
Examples:
• ≤ on real numbers (reflexive: a ≤ a)
• = on any set
• "Is subset of" on sets
Irreflexive:
∀a ∈ A, (a, a) ∉ R
No element is related to itself
Examples:
• < on real numbers
• "Is proper subset of" on sets
• "Is parent of" on people
Symmetric:
∀a, b ∈ A, (a, b) ∈ R → (b, a) ∈ R
If a is related to b, then b is related to a
Examples:
• = on any set
• "Is sibling of" on people
• "Is married to" on people
Antisymmetric:
∀a, b ∈ A, ((a, b) ∈ R ∧ (b, a) ∈ R) → a = b
If a is related to b and b is related to a, then a = b
Examples:
• ≤ on real numbers
• ⊆ on sets
• "Divides" on positive integers
Asymmetric:
∀a, b ∈ A, (a, b) ∈ R → (b, a) ∉ R
If a is related to b, then b is not related to a
Examples:
• < on real numbers
• "Is parent of" on people
Transitive:
∀a, b, c ∈ A, ((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R
If a is related to b and b is related to c, then a is related to c
Examples:
• < and ≤ on real numbers
• ⊆ on sets
• "Is ancestor of" on people
• "Divides" on integers
Property Combinations:
• Equivalence relation: reflexive, symmetric, transitive
• Partial order: reflexive, antisymmetric, transitive
• Strict partial order: irreflexive, asymmetric, transitiveEquivalence Relations and Partitions
Equivalence Relations
Equivalence Relations
════════════════════
Definition:
A relation R on set A is an equivalence relation if it is:
1. Reflexive: ∀a ∈ A, aRa
2. Symmetric: ∀a, b ∈ A, aRb → bRa
3. Transitive: ∀a, b, c ∈ A, (aRb ∧ bRc) → aRc
Examples:
• Equality (=) on any set
• Congruence modulo n: a ≡ b (mod n) iff n|(a-b)
• "Has same birthday as" on people
• "Is similar to" on triangles
• "Has same cardinality as" on sets
Equivalence Class:
For equivalence relation R on A and element a ∈ A:
[a] = {x ∈ A | xRa}
Set of all elements equivalent to a
Examples:
Congruence modulo 3 on integers:
• [0] = {..., -6, -3, 0, 3, 6, 9, ...}
• [1] = {..., -5, -2, 1, 4, 7, 10, ...}
• [2] = {..., -4, -1, 2, 5, 8, 11, ...}
Properties of Equivalence Classes:
• Every element belongs to exactly one equivalence class
• [a] = [b] if and only if aRb
• [a] ∩ [b] = ∅ or [a] = [b]
• ⋃{[a] | a ∈ A} = A
Quotient Set:
A/R = {[a] | a ∈ A}
Set of all equivalence classes
Example:
ℤ/(≡ mod 3) = {[0], [1], [2]}Partitions
Partitions of Sets
═════════════════
Definition:
A partition of set A is a collection of non-empty, pairwise disjoint subsets whose union is A
Formally: P = {A₁, A₂, ..., Aₙ} is a partition of A if:
1. Aᵢ ≠ ∅ for all i
2. Aᵢ ∩ Aⱼ = ∅ for i ≠ j
3. ⋃ᵢ Aᵢ = A
Examples:
• {{1, 3}, {2, 4}, {5}} is a partition of {1, 2, 3, 4, 5}
• {Even integers, Odd integers} partitions ℤ
• {Freshmen, Sophomores, Juniors, Seniors} partitions students
Fundamental Theorem:
There is a one-to-one correspondence between:
• Equivalence relations on A
• Partitions of A
Given equivalence relation R:
→ Partition: {[a] | a ∈ A}
Given partition P = {A₁, A₂, ..., Aₙ}:
→ Equivalence relation: aRb iff a and b are in same Aᵢ
Applications:
• Classification systems
• Database normalization
• Clustering algorithms
• Modular arithmetic
• Abstract algebra (quotient structures)
Example: Student Classification
Students = {Alice, Bob, Carol, Dave, Eve}
Partition by class year:
• Freshmen: {Alice, Carol}
• Sophomores: {Bob, Eve}
• Juniors: {Dave}
Corresponding equivalence relation:
"Has same class year as"
Alice ~ Carol, Bob ~ Eve, etc.Functions as Relations
Functions Defined as Relations
Functions as Special Relations
════════════════════════════
Function Definition:
A function f: A → B is a relation f ⊆ A × B such that:
∀a ∈ A, ∃!b ∈ B, (a, b) ∈ f
In other words: each element in A is related to exactly one element in B
Notation:
• f(a) = b means (a, b) ∈ f
• A is the domain
• B is the codomain
• range(f) = {f(a) | a ∈ A} ⊆ B
Examples:
• f: ℝ → ℝ, f(x) = x²
• g: {1, 2, 3} → {a, b}, g = {(1, a), (2, b), (3, a)}
• h: ℕ → ℕ, h(n) = 2n
Not Functions:
• R = {(1, a), (1, b), (2, c)} (1 maps to two values)
• S = {(1, a), (3, b)} on domain {1, 2, 3} (2 has no image)
Types of Functions:
Injective (One-to-One):
∀a₁, a₂ ∈ A, f(a₁) = f(a₂) → a₁ = a₂
Different inputs give different outputs
Examples:
• f(x) = 2x on ℝ
• f(x) = x³ on ℝ
Surjective (Onto):
∀b ∈ B, ∃a ∈ A, f(a) = b
Every element in codomain is an output
Examples:
• f: ℝ → ℝ, f(x) = x³
• g: ℝ → [0, ∞), g(x) = x²
Bijective (One-to-One and Onto):
Function that is both injective and surjective
Establishes one-to-one correspondence between A and B
Examples:
• f: ℝ → ℝ, f(x) = 2x + 1
• g: (0, 1) → ℝ, g(x) = tan(π(x - 1/2))
Function Composition:
If f: A → B and g: B → C, then g ∘ f: A → C
(g ∘ f)(a) = g(f(a))
Inverse Function:
If f: A → B is bijective, then f⁻¹: B → A exists
f⁻¹(b) = a iff f(a) = bApplications in Computer Science
Database Relations
Relational Database Model
════════════════════════
Tables as Relations:
Database table is a relation (subset of Cartesian product)
Rows are tuples, columns are attributes
Example: Students table
Students ⊆ ID × Name × Major × GPA
{(123, "Alice", "CS", 3.8), (456, "Bob", "Math", 3.5), ...}
Relational Operations:
Selection (σ):
Choose rows satisfying condition
σ_{GPA > 3.5}(Students) = students with GPA > 3.5
Projection (π):
Choose specific columns
π_{Name, Major}(Students) = names and majors only
Join (⋈):
Combine tables based on common attributes
Students ⋈ Enrollments = student info with course data
Union, Intersection, Difference:
Standard set operations on compatible relations
Keys and Constraints:
• Primary key: uniquely identifies each tuple
• Foreign key: references primary key in another relation
• Functional dependencies: determine relationships between attributes
Normalization:
Use set theory and functional dependencies to:
• Eliminate redundancy
• Prevent update anomalies
• Ensure data integrity
Example:
Instead of: Students(ID, Name, CourseID, CourseName, Grade)
Use: Students(ID, Name), Courses(CourseID, CourseName), Enrollments(ID, CourseID, Grade)Data Structures and Algorithms
Sets in Programming
══════════════════
Set Data Structures:
• Hash sets: O(1) average insertion, deletion, lookup
• Tree sets: O(log n) operations, maintain order
• Bit sets: efficient for small universes
Set Operations in Code:
```python
# Python set operations
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
union = A | B # {1, 2, 3, 4, 5, 6}
intersection = A & B # {3, 4}
difference = A - B # {1, 2}
symmetric_diff = A ^ B # {1, 2, 5, 6}Applications: • Removing duplicates from data • Membership testing • Set-based algorithms (graph algorithms) • Database query optimization • Caching and memoization
Graph Theory: Graphs as relations on vertex sets • Adjacency relation: R ⊆ V × V • Path relation: transitive closure of adjacency • Equivalence classes: connected components
Algorithm Design: • Union-Find data structure (disjoint sets) • Set cover and hitting set problems • Bloom filters (probabilistic set membership) • Set intersection algorithms
## Summary and Key Concepts
Sets and relations provide the fundamental language for describing mathematical structures and relationships, forming the foundation for advanced mathematics and computer science.
Chapter Summary ══════════════
Essential Skills Mastered: ✓ Set notation, membership, and basic operations ✓ Set properties and algebraic laws ✓ Cartesian products and ordered pairs ✓ Binary relations and their properties ✓ Equivalence relations and partitions ✓ Functions as special relations ✓ Applications in databases and programming
Key Concepts: • Sets as collections of distinct objects • Set operations: union, intersection, complement, difference • Relations as subsets of Cartesian products • Equivalence relations and their connection to partitions • Functions as single-valued relations • Database tables as relations
Fundamental Operations: • Union (∪): elements in either set • Intersection (∩): elements in both sets • Complement (’): elements not in set • Cartesian product (×): ordered pairs • Relation composition: chaining relationships
Problem-Solving Tools: • Venn diagrams for visualization • Set algebra for simplification • Equivalence classes for classification • Function properties for analysis • Relational operations for data manipulation
Applications Covered: • Database design and relational algebra • Programming data structures • Mathematical foundations • Classification and equivalence • Graph theory and networks
Next Steps: Set and relation concepts prepare you for: - Functions and their properties - Graph theory and network analysis - Database design and query optimization - Abstract algebra and mathematical structures - Algorithm design and data structures ```
Sets and relations represent the fundamental building blocks of mathematical reasoning and computer science applications. The concepts developed in this chapter - set operations, relation properties, equivalence classes, and functions - provide essential tools for organizing information, modeling relationships, and solving complex problems across mathematics, computer science, and engineering.
Understanding sets and relations enables you to think precisely about collections of objects and their relationships, whether you’re designing databases, analyzing algorithms, or exploring abstract mathematical structures. These foundational concepts will serve you throughout your mathematical and computational journey, providing the language and tools needed for advanced study and practical applications.