Relations, Functions, and Morphisms

In the set-theoretic foundation of mathematics, we transition from static collections to dynamic interactions by defining relations and functions. These concepts allow us to compare sets, group elements by shared properties, and transform data while preserving structure.

Binary Relations and Their Properties

A Binary Relation $R$ between sets $A$ and $B$ is formally defined as a subset of the Cartesian product $A \times B$ . If $(a, b) \in R$ , we often write $a R b$ . When $A = B$ , we say $R$ is a relation on $A$ .

The nature of a relation is determined by several key properties:

Reflexivity: $\forall a \in A, a R a$ .
Symmetry: $a R b ⟹ b R a$ .
Antisymmetry: $(a R b \land b R a) ⟹ a = b$ .
Transitivity: $(a R b \land b R c) ⟹ a R c$ .

Equivalence Relations and Partitions

An Equivalence Relation is reflexive, symmetric, and transitive. The most significant feature of an equivalence relation is that it partitions the set $A$ into disjoint Equivalence Classes. For $a \in A$ , the class $[a] = {x \in A ∣ x R a}$ .

Example: Modular arithmetic. The relation $a \equiv b (mod n)$ partitions the integers into $n$ classes.
Quotient Sets: The set of all equivalence classes is denoted $A / R$ . This allows us to “collapse” a set into a simpler structure.

Order Relations

A Partial Order (POSET) is reflexive, antisymmetric, and transitive (e.g., $\subseteq$ or $\leq$ ). If every pair of elements is comparable, it is a Total Order. Partial orders are the basis for Lattice Theory and Domain Theory.

The Formal Definition of a Function

A Function $f : A \to B$ is a relation $f \subseteq A \times B$ with two specific constraints:

Existence: $\forall a \in A, \exists b \in B$ such that $(a, b) \in f$ .
Uniqueness: $(a, b) \in f \land (a, c) \in f ⟹ b = c$ .

This ensures that every input is mapped to exactly one output. We write $f (a) = b$ .

Domain: The set $A$ of all valid inputs.
Codomain: The set $B$ where outputs reside.
Range (Image): The specific subset of $B$ reached by the function, $I m (f) = {f (a) ∣ a \in A}$ .

Classification of Mappings

The behavior of a function relative to its codomain defines its classification:

Injection (One-to-One): Differing inputs yield differing outputs. $\forall x, y \in A, f (x) = f (y) ⟹ x = y$ .
Surjection (Onto): The range is equal to the codomain. $\forall b \in B, \exists a \in A$ such that $f (a) = b$ .
Bijection: Both injective and surjective. A bijection represents a perfect “one-to-one correspondence” between sets. Bijections are invertible: there exists $f^{- 1} : B \to A$ .

Composition and Identity

Given functions $f : A \to B$ and $g : B \to C$ , the Composition $g \circ f : A \to C$ is defined by $(g \circ f) (x) = g (f (x))$ .

Composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$ .
Every set has an Identity Function $i d_{A} (x) = x$ such that $f \circ i d_{A} = f$ and $i d_{B} \circ f = f$ .

Images and Pre-images

For a subset $S \subseteq A$ , the image is $f (S) = {f (x) ∣ x \in S}$ . For a subset $T \subseteq B$ , the Pre-image (or inverse image) is $f^{- 1} (T) = {x \in A ∣ f (x) \in T}$ . Crucially, $f^{- 1} (T)$ exists even if the function $f$ is not invertible as a mapping! Pre-images behave well with set operations:

$f^{- 1} (X \cap Y) = f^{- 1} (X) \cap f^{- 1} (Y)$
$f^{- 1} (X \cup Y) = f^{- 1} (X) \cup f^{- 1} (Y)$

Morphisms: A Categorical Overview

In higher mathematics, we look at functions that preserve structure. These are called Morphisms.

Homomorphism: A function between algebraic structures (like groups) that preserves the operations.
Homeomorphism: A continuous bijection between topological spaces with a continuous inverse.
Isomorphism: A morphism that can be reversed. Two isomorphic structures are “mathematically identical” in their properties, even if their elements are different.

Computational Modeling of Relations

In software, relations are often modeled as Boolean-valued functions or via adjacency structures.

type SetElement = string | number;
type Relation<T extends SetElement> = (a: T, b: T) => boolean;

/**
 * Example: The 'Less than or equal to' relation on numbers.
 * This is a Partial Order (and actually a Total Order on R).
 */
const leq: Relation<number> = (a, b) => a <= b;

/**
 * Example: Modular equivalence (an Equivalence Relation).
 */
const modEquiv = (n: number): Relation<number> => (a, b) => (a - b) % n === 0;

// Functions are simply a subset of relations where each 'a' has one 'b'.
type MathFunction<A, B> = (input: A) => B;

Knowledge Check

Conceptual Check

A relation that is reflexive, symmetric, and transitive is known as what?

While computers handle finite mappings efficiently, the pure mathematical study of functions extends to infinite-dimensional spaces (Functional Analysis), where functions themselves become the “elements” of larger sets. Understanding the properties of mappings is the first step toward understanding the architecture of space and transformation.