Relations Definition

Set Theory · Axiom Academy

Formalizing relationships between sets using ordered pairs 1. Relation as Subset of A × B A relation R from set A to set B is any subset of the Cartesian product A × B. This means R is a collection of ordered pairs (a, b) where a ∈ A and b ∈ B. The relation R describes which elements of A are related to which elements of B. 2. Domain, Codomain, and Range For a relation R ⊆ A × B, we define three important sets: Domain: dom(R) = a ∈ A : ∃b ∈ B, (a,b) ∈ R Range: ran(R) = b ∈ B : ∃a ∈ A, (a,b) ∈ R The domain contains all first elements that appear in R. The range contains all second elements that appear in R. Note: ran(R) ⊆ B. We have multiple equivalent ways to express that a and b are related: The infix notation aRb is particularly intuitive for familiar relations like a < b or a = b. When the domain and codomain are the same set A, we say R is a relation on A : This is the case for many important relations: equality on numbers, divisibility on integers, "subset of" on sets, and "less than" on real numbers. Important relations on sets of numbers: Less than: < on ℝ where a < b means a is less than b Divisibility: | on ℤ⁺ where a | b means a divides b Equality: = on any set A where a = b iff they're the same Congruence: ≡ₙ on ℤ where a ≡ₙ b means n | (a - b) Each of these is a subset of the appropriate Cartesian product.

This is the written version of the interactive lesson above. See the full Set Theory course.