3.1.1 Foundational Prerequisite: Cartesian Products & Ordered Pairs


Before defining a mathematical relation, we must establish the formal algebraic structure of the Cartesian Product upon which all relational mappings are built.

  • Ordered Pair: An ordered pair (a, b) is a compound mathematical structure containing two objects a and b in a strictly prescribed order, where a is designated as the first coordinate and b is the second coordinate. Unlike an unordered set where sequence is irrelevant (i.e., {a, b} = {b, a}), two ordered pairs are equivalent if and only if their corresponding coordinates match precisely:
  • (a, b) = (c, d)  ⟺  (a = c) ∧ (b = d)
  • Cartesian Product: Let A and B be sets. The Cartesian product (or cross product) of A and B, denoted by A × B, is defined as the comprehensive set of all possible ordered pairs (a, b) where the first element is selected from A and the second element is selected from B:
  • A × B = { (a, b) | a ∈ A ∧ b ∈ B }
  • Cardinality Rule: If set A contains exactly m distinct elements (|A| = m) and set B contains exactly n distinct elements (|B| = n), the total number of ordered pairs in the resulting product space equals the numerical product of their individual cardinalities:
  • |A × B| = |A| × |B| = m × n


3.1.2 Definition of a Binary Relation, Domain, and Range

The most direct and structured way to express a relationship between elements of two sets is to utilize ordered pairs consisting of related elements.


1. Binary Relation Definition

Let A and B be sets. A binary relation R from set A to set B is formally defined as a subset of the Cartesian product A × B:

R ⊆ A × B

  • Membership Notation: If an ordered pair (a, b) belongs to the relation R, we write (a, b) ∈ R or utilize the standard infix notation a R b (read as: "a is related to b by R").
  • Non-Membership: If (a, b) does not belong to R, we write (a, b) ∉ R or a ⌉R b (read as: "a is not related to b by R").
  • Relation on a Set: When set A is identical to set B (i.e., A = B), a binary relation from A to A is formally termed a relation on A, which is simply a subset of the Cartesian space A × A.


2. Domain and Range Extractions

Given a binary relation R ⊆ A × B, we define two fundamental sub-collections:

  • Domain (Dom(R)): The set of all first coordinates of the ordered pairs that actively belong to R. It represents the subset of A containing elements that are related to at least one element in B:
  • Dom(R) = { a ∈ A | ∃b ∈ B, (a, b) ∈ R } ⊆ A
  • Range (Ran(R) or Im(R)): The set of all second coordinates of the ordered pairs that actively belong to R. It represents the subset of B containing elements to which at least one element in A is mapped:
  • Ran(R) = { b ∈ B | ∃a ∈ A, (a, b) ∈ R } ⊆ B


Concrete Mathematical Example:

Let A = {1, 2, 3, 4} and B = {x, y, z}. Consider the relation R from A to B defined explicitly as:

R = { (1, x), (2, x), (2, z), (4, y) }

• Domain Calculation: By extracting the unique first coordinates, we obtain Dom(R) = {1, 2, 4}. (Note: The element 3 ∉ Dom(R) because 3 never appears as a starting coordinate in any ordered pair of R).

• Range Calculation: By extracting the unique second coordinates, we obtain Ran(R) = {x, y, z} = B.