Relations and Their Properties
What Is a Relation?
A relation describes how elements from one set correspond to elements of another (or the same) set. A binary relation is a set of ordered pairs (a, b).
Notation: a R b means (a, b) ∈ R. The domain of a relation is the set of all first elements; the range is the set of all second elements.
Representing Relations
- Relation as a Table — Mark each ordered pair with 1 (true) or 0 (false).
- Arrow Diagram — Draw arrows from each domain element to its range elements.
- Directed Graph (Digraph) — Vertices for elements, arrows for ordered pairs. A pair (a, a) creates a self-loop.
Properties of Relations
Reflexive
Every element is related to itself: ∀a, (a, a) ∈ R.
Common reflexive relations: =, ≥, ≤; Non-reflexive: >, <
Irreflexive: No element is related to itself: ∀a, (a, a) ∉ R.
In a digraph, reflexive relations have a self-loop at every vertex.
Symmetric
If (a, b) ∈ R then (b, a) ∈ R for all a, b.
Asymmetric: If (a, b) ∈ R then (b, a) ∉ R.
Antisymmetric
If both (a, b) ∈ R and (b, a) ∈ R, then a = b.
Transitive
If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
Ordering Relations
Partial Order
A relation R on set A is a partial order if it is reflexive, antisymmetric, and transitive. A set with a partial order is called a poset.
Total Order (Linear Order)
A partial order where every pair of elements is comparable.
Function Notation
A function f from set A to set B maps every element of A to exactly one element of B.
Example 1: Given f(x) = 3x − 5, find f(2).
- f(2) = 3(2) − 5 = 1
Example 2: Find g(4w) when g(x) = x² − 2x + 1.
- g(4w) = (4w)² − 2(4w) + 1 = 16w² − 8w + 1
Operations on Functions
Given functions f and g:
- (f + g)(x) = f(x) + g(x)
- (f − g)(x) = f(x) − g(x)
- (f · g)(x) = f(x) · g(x)
- (f/g)(x) = f(x)/g(x), where g(x) ≠ 0
Composition of Functions
The composition (f ∘ g)(x) = f(g(x)) — apply g first, then feed the result into f.
In general, f ∘ g ≠ g ∘ f.
Example: Let g(x) = 2x and f(x) = x + 1.
- g ∘ f(1) = g(f(1)) = g(2) = 4
- f ∘ g(1) = f(g(1)) = f(2) = 3
Pigeonhole Principle
Statement: If n + 1 or more objects are distributed into n containers, then at least one container holds two or more objects.
Example 1: In a room with more than 366 people, at least two share the same birthday.
Example 2: If a class has 14 boys and 22 girls (36 total), at minimum 15 members guarantees at least one female.