A relation $R$ between sets $A$ and $B$ is any subset of the Cartesian product:
$R \subseteq A \times B$
Each ordered pair $(a, b) \in R$ means "$a$ is related to $b$" (often written $aRb$).
Python — relation as a set of tuplesA = {1, 2, 3}
B = {"x", "y", "z"}
R = {(1, "x"), (1, "y"), (2, "y"), (2, "z"), (3, "x")}
# Is R a relation from A to B?
print(R.issubset({(a, b) for a in A for b in B})) # True
Python — relation as a dict (multi-valued)from collections import defaultdict
R_dict = defaultdict(set)
for a, b in R:
R_dict[a].add(b)
print(dict(R_dict))
# {1: {'x','y'}, 2: {'y','z'}, 3: {'x'}}
3 / 14
Graphing
Relations can be visualized as the links between the input set and the output set — a bipartite graph.
Bipartite graph for $R = \{(1,x),(1,y),(2,y),(2,z),(3,x)\}$
Python — networkx bipartite drawing# pip install networkx matplotlib
import networkx as nx, matplotlib.pyplot as plt
R = [(1,"x"),(1,"y"),(2,"y"),(2,"z"),(3,"x")]
G = nx.DiGraph(); G.add_edges_from(R)
left = {1, 2, 3}
pos = {**{n: (0, -i) for i, n in enumerate(sorted(left))},
**{n: (1, -i) for i, n in enumerate(["x","y","z"])}}
nx.draw(G, pos, with_labels=True, node_color="#fff", edgecolors="#2c3e50",
edge_color="#3a6fb3", arrows=True)
plt.show()
4 / 14
Functions
A relation $R \subseteq A \times B$ is called many-to-one iff each $a \in A$ has a unique $b \in B$ with $(a,b) \in R$. We then write $f(a) = b$.
A function is defined as a many-to-one relation.
Python — test whether a relation is a functiondef is_function(R, A):
"""Each a in A must have exactly one image in R."""
counts = {a: 0 for a in A}
for a, b in R:
counts[a] += 1
return all(c == 1 for c in counts.values())
R1 = {(1,"x"),(2,"y"),(3,"x")} # function
R2 = {(1,"x"),(1,"y"),(2,"z")} # not a function (1 has two images)
print(is_function(R1, {1,2,3})) # True
print(is_function(R2, {1,2})) # False
Python — functions as codedef f(x): # named function
return x ** 2 + 1
g = lambda x: 2*x + 3 # anonymous (lambda)
print(f(3), g(3)) # 10, 9
5 / 14
Valid function?
For a graph to be a valid function, every element of the domain must have exactly one outgoing arrow.
✓ Valid function — each of 1..6 has one image
✗ Not a function — 3 maps to two images
Vertical line test (for real-valued graphs): a curve is a function iff every vertical line intersects it at most once. A spiral fails this test; the upper half of a circle passes it.
6 / 14
Domain and Range
Consider a function $f : A \to B$.
The domain (preimage) is the set of values $A$ for which $f(x)$ is defined.
The range (image, codomain) is the set of values $B$ produced by $f(x)$ for $x \in A$.
Python — common quick facts| Function | Injective | Surjective | Bijective |
|-------------------|-----------|------------|-----------|
| f(x) = 3x + 1 | yes | yes | yes |
| f(x) = x² on ℝ | no | no | no |
| f(x) = x² on ℝ⁺ | yes | yes | yes |
| f(x) = eˣ | yes | no | no |
9 / 14
Bijection & Invertibility
A function $f$ is bijective (one-to-one correspondence) iff it is both injective and surjective.
A bijective function is invertible. For an invertible $f(x)$, the inverse function is denoted $f^{-1}(x)$, and satisfies
$\;f^{-1}(f(x)) = x = f(f^{-1}(x))$.
Python — invert a finite bijectiondef invert(f_dict):
if len(set(f_dict.values())) != len(f_dict):
raise ValueError("not injective — no inverse")
return {v: k for k, v in f_dict.items()}
f = {1:"x", 2:"y", 3:"z"}
print(invert(f)) # {'x':1, 'y':2, 'z':3}
SymPy — symbolic inversefrom sympy import symbols, log, exp, solve, Eq
x, y = symbols('x y', real=True)
# Invert log(x): y = log(x) → x = e^y
sol = solve(Eq(y, log(x)), x)
print(sol) # [exp(y)]
10 / 14
Example — invertible?
Is $f(x) = x^2$ invertible on $\mathbb{R}$? No — it is not injective (e.g. $f(-2) = f(2) = 4$). The horizontal line $y = 2$ crosses the parabola twice.
Is $f(x) = x^3$ invertible on $\mathbb{R}$? Yes — strictly increasing, so injective and surjective on $\mathbb{R}$. Its inverse is $f^{-1}(x) = x^{1/3}$.
Python — numerical horizontal-line testimport numpy as np
def horiz_line_test(f, xs, c):
"""Count intersections of y=c with f over xs (by sign changes)."""
ys = np.array([f(x) - c for x in xs])
return int(np.sum(np.sign(ys[:-1]) != np.sign(ys[1:])))
xs = np.linspace(-2, 2, 1001)
print(horiz_line_test(lambda x: x**2, xs, 2.0)) # 2 → not injective
print(horiz_line_test(lambda x: x**3, xs, 2.0)) # 1 → injective