03 Relations and Functions

Relations as sets of ordered pairs

A relation describes which elements of one set are connected to elements of another set. If $A$ and $B$ are sets, a relation from $A$ to $B$ is a subset of $A\times B$, so each connection is written as an ordered pair $(a,b)$.

For example, let

and let

The domain is $\{1,2\}$, because these are the first coordinates that occur. The range is $\{a,b\}$, because these are the second coordinates that occur. A relation on $A$ is a relation from $A$ to itself, so it is a subset of $A\times A$.

Takeaway: Relations are sets of ordered pairs; their domain and range are determined by the coordinates that actually occur.

Testing relation properties

The properties of a relation describe how its ordered pairs behave.

• Reflexive: Every element is related to itself, so $aRa$ for every $a\in A$.

• Symmetric: Reversing a related pair preserves the relation, so $aRb$ implies $bRa$.

• Antisymmetric: If both directions hold, then the elements must be equal: $(aRb\land bRa)\Rightarrow a=b$.

• Transitive: Two links can be chained: $(aRb\land bRc)\Rightarrow aRc$.

The relation $\leq$ on the integers illustrates several properties at once. It is reflexive because $a\leq a$, antisymmetric because $a\leq b$ and $b\leq a$ imply $a=b$, and transitive because $a\leq b$ and $b\leq c$ imply $a\leq c$. It is not symmetric: for instance, $2\leq 5$ but $5\not\leq 2$.

Takeaway: Test each property separately. Antisymmetric means that opposite relations force equality; it does not mean simply “not symmetric.”

Equivalence and order structures

Two important combinations of relation properties organize sets in different ways.

An equivalence relation is reflexive, symmetric, and transitive. Congruence modulo $n$ is an example on $\mathbb Z$:

For example, modulo $3$,

Equivalence classes group elements that are equivalent under the relation. These classes form a partition: they do not overlap, and every element belongs to exactly one class.

A partial order is reflexive, antisymmetric, and transitive. Subset inclusion $\subseteq$ on $\mathcal P(S)$ is a partial order. Unlike a total order, a partial order does not require every pair to be comparable. In $\mathcal P(\{1,2\})$, neither $\{1\}\subseteq\{2\}$ nor $\{2\}\subseteq\{1\}$ holds.

Takeaway: Equivalence relations produce partitions, while partial orders organize elements without necessarily comparing every pair.

Functions and their parts

A function is a special kind of relation: each input in the domain must have exactly one output in the codomain. Multiple inputs may share an output, but a single input cannot be assigned two different outputs.

For example,

is a function from $\{1,2,3\}$ to $\{a,b\}$. Every input appears exactly once with one output. By contrast,

is not a function because the input $1$ has two different outputs.

For a function $f:A\to B$, distinguish the following sets:

• The domain is $A$, the set of allowed inputs.

• The codomain is $B$, the set in which outputs are required to lie.

• The image or range is $f(A)=\{f(a):a\in A\}$, the set of outputs actually produced.

The image can be smaller than the codomain. This distinction becomes essential when deciding whether a function is surjective.

Takeaway: The defining test for a function is exactly one output for every input.

Injective, surjective, and bijective behavior

Injectivity and surjectivity measure different aspects of how a function connects its domain and codomain.

An injective function never sends two distinct inputs to the same output. A useful test is

For $f(n)=2n+1$ on $\mathbb Z$, if $f(m)=f(n)$, then

so the function is injective. The rule $g(n)=n^2$ is not injective on $\mathbb Z$, since $g(1)=g(-1)=1$.

A surjective function reaches every element of its codomain. For $f:A\to B$, this means

The rule $x^3$ is surjective from $\mathbb R$ to $\mathbb R$, because every real target $y$ has the preimage $x=\sqrt[3]{y}$. The rule $x^2$ is not surjective from $\mathbb R$ to $\mathbb R$, because no real input produces a negative output; it is surjective when the codomain is $[0,\infty)$.

A bijection is both injective and surjective. Therefore, each codomain element has exactly one preimage.

Takeaway: Injectivity prevents repeated outputs from different inputs; surjectivity ensures that no codomain elements are missed.

Inverses and reversible functions

An inverse reverses the input-output assignments of a function. For an inverse function to exist on the entire codomain, the original function must be bijective: injectivity ensures that each output has at most one preimage, and surjectivity ensures that each codomain element has at least one preimage.

Consider

Solve $y=3x-4$ for $x$:

Therefore,

The two composition checks are

and

Do not confuse the inverse function with a reciprocal. If $f(x)=2x$, then

whereas

is a different function.

Takeaway: To find an inverse, solve the equation $y=f(x)$ for $x$, then verify both composition identities when appropriate.

Connecting the concepts

The main ideas form a hierarchy:

1. A relation is any set of ordered pairs.

2. Relation properties such as reflexivity, symmetry, antisymmetry, and transitivity describe structural behavior.

3. Equivalence relations partition sets into equivalence classes.

4. Partial orders organize sets while allowing incomparable elements.

5. A function is a relation with exactly one output for every input.

6. Injectivity concerns repeated outputs, while surjectivity concerns whether the codomain is fully reached.

7. A bijection has both properties and therefore has an inverse function.

When analyzing a new example, first identify the sets and ordered pairs. Then determine the domain, range, and relevant relation properties. If the object is a function, compare its image with its codomain and check whether different inputs can share an output. These steps reveal whether the function is injective, surjective, bijective, or invertible.

Final takeaway: Relations provide the general framework; functions impose a unique-output rule; bijections are exactly the functions whose assignments can be reversed.