Lesson 5: 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

1. Relation as a Table — Mark each ordered pair with 1 (true) or 0 (false).
2. Arrow Diagram — Draw arrows from each domain element to its range elements.
3. 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.