Relations and Functions

Introduction

Relations and functions are foundational concepts in mathematics, especially in set theory and algebra. They help describe how elements from one set are associated with elements of another set, providing a framework for mathematical analysis and real-world modeling.

2.1 Cartesian Product of Sets

The Cartesian product of two sets, say A and B, is the set of all possible ordered pairs where the first element comes from A and the second from B. It is denoted as A × B:

A × B = { (a, b) : a ∈ A, b ∈ B }
    

• The order in the pair matters: (a, b) ≠ (b, a) unless a = b.
• If A has m elements and B has n elements, then A × B has m × n elements.
• If either set is empty, the Cartesian product is also empty.
• The operation is not commutative: A × B ≠ B × A in general.

Example:
If A = {1, 2}, B = {x, y}:
A × B = { (1, x), (1, y), (2, x), (2, y) }

2.2 Relations

A relation from set A to set B is any subset of the Cartesian product A × B. That is, a relation is a set of ordered pairs where the first element is from A and the second is from B.

• Reflexive: Every element is related to itself.
• Symmetric: If (a, b) is in the relation, so is (b, a).
• Transitive: If (a, b) and (b, c) are in the relation, so is (a, c).

Example:
Let A = {1, 2}, B = {x, y}, and R = { (1, x), (2, y) } is a relation from A to B.

2.3 Functions

A function is a special type of relation where each element in the domain (first set) is associated with exactly one element in the codomain (second set). Formally, a function f from A to B is a subset of A × B such that for every a ∈ A, there exists a unique b ∈ B with (a, b) ∈ f.

• Every function is a relation, but not every relation is a function.
• The domain is the set of all possible inputs.
• The codomain is the set of possible outputs.
• The range is the set of actual outputs.

Example:
If A = {1, 2, 3}, B = {x, y}, a function f could be f = { (1, x), (2, y), (3, x) }.

2.4 Summary Table

Concept	Definition	Example
Cartesian Product	Set of all ordered pairs from two sets	{ (1, x), (1, y), (2, x), (2, y) }
Relation	Subset of Cartesian product; any association between elements	{ (1, x), (2, y) }
Function	Relation where each input has exactly one output	{ (1, x), (2, y), (3, x) }