Understand binary relations as subsets of Cartesian products
Master the concept of Cartesian products A × B
Analyze relations on numbers with concrete examples
Use set comprehension to define complex relations
Identify key properties of relations (reflexivity, symmetry, transitivity)
Apply relations to real mathematical scenarios
6.1 Definition
🔑 Binary Relation
A relation R on sets A and B is a subset of A × B
Relations connect elements from one set to elements in another set through ordered pairs.
🔑 Cartesian Product
A × B = {(a, b) | a ∈ A, b ∈ B}
The set of all ordered pairs where the first element comes from A and the second from B.
💡 Notation
If (a, b) ∈ R, we often write a R b
Read as: "a is related to b by relation R"
Cartesian Product Example
Let A = {1, 2} and B = {x, y, z}
Then A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}
(1, x)
(1, y)
(1, z)
(2, x)
(2, y)
(2, z)
|A × B| = |A| × |B| = 2 × 3 = 6
6.2 Relations on Numbers
Example 1: Divisibility Relation
R = {(a, b) | a, b ∈ ℕ, a × b = 63}
Elements of R:
(1, 63)
(3, 21)
(7, 9)
(9, 7)
(21, 3)
(63, 1)
Extension to Integers
If extended to ℤ (integers), R would also include negative pairs like (-7, -9), (-21, -3), etc.
Example 2: Prime Powers Relation
R = {(p, n) | p is prime, n = p^m for some m ∈ ℕ}
Examples of elements:
For prime 3: (3, 1), (3, 3), (3, 9), (3, 27), (3, 81), ...
For prime 5: (5, 1), (5, 5), (5, 25), (5, 125), (5, 625), ...
For prime 2: (2, 1), (2, 2), (2, 4), (2, 8), (2, 16), ...
Note: (p, 1) always included
Since p⁰ = 1 for any prime p, every prime is related to 1.
6.3 Using Set Comprehension for Relations
Defining Primes with Sets
P = {p | p ∈ ℕ, p ≠ 1, factors(p) = {1, p}}
A prime has exactly two factors: 1 and itself
1 is explicitly excluded (it only has one factor)
Defining Prime Powers Relation
R = {(p, n) | (p, n) ∈ P × ℕ, n = p^m for some m ∈ ℕ}
Step-by-step breakdown:
P × ℕ: All ordered pairs (prime, natural number)
Condition: The natural number must be a power of the prime
Result: Only pairs where the second element is actually a power of the first
💡 Flexibility in Notation
Can use words like "for some", "there exists"
Can use mathematical symbols: ∃ (exists), ∀ (for all)
As long as meaning is clear and unambiguous
Alternative notation:
R = {(p, n) | p ∈ P, n ∈ ℕ, ∃m ∈ ℕ : n = p^m}
6.4 Properties of Relations
🔄 Reflexivity
Every element relates to itself
For all a ∈ A: (a, a) ∈ R
Example: "equals" (=) is reflexive since a = a
↔️ Symmetry
If a relates to b, then b relates to a
If (a, b) ∈ R, then (b, a) ∈ R
Example: "is sibling of" is symmetric
➡️ Transitivity
If a relates to b and b relates to c, then a relates to c
If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R
Example: "less than" (<) is transitive
🎯 Importance
These properties are particularly important for equivalence relations, which are fundamental in advanced mathematics and computer science.
An equivalence relation must be reflexive, symmetric, AND transitive.
🧮 Practice Problems
Problem 1: Cartesian Products
Given A = {1, 2, 3} and B = {a, b}:
Find A × B
Find B × A
What is |A × B|?
Is A × B = B × A?
Solutions:
A × B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
B × A = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}
|A × B| = |A| × |B| = 3 × 2 = 6
No, A × B ≠ B × A (order matters in ordered pairs)
Problem 2: Defining Relations
Define the following relations using set comprehension:
The "less than" relation on natural numbers
The "divides" relation on natural numbers
The "same remainder when divided by 3" relation on integers
Solutions:
R₁ = {(a, b) | a, b ∈ ℕ, a < b}
R₂ = {(a, b) | a, b ∈ ℕ, a ≠ 0, b = ka for some k ∈ ℕ}
R₃ = {(a, b) | a, b ∈ ℤ, a mod 3 = b mod 3}
Problem 3: Properties Analysis
For each relation on ℕ, determine if it's reflexive, symmetric, or transitive:
R₁ = {(a, b) | a ≤ b}
R₂ = {(a, b) | a + b is even}
R₃ = {(a, b) | |a - b| ≤ 2}
Solutions:
R₁ (≤): • Reflexive: ✓ (a ≤ a always)
• Symmetric: ✗ (if a ≤ b, doesn't mean b ≤ a)
• Transitive: ✓ (if a ≤ b and b ≤ c, then a ≤ c)
R₂ (sum is even): • Reflexive: ✓ (a + a = 2a is always even)
• Symmetric: ✓ (if a + b is even, then b + a is even)
• Transitive: ✓ (both odd or both even preserved)