Mathematical Relationships

Mathematics (and life, in fact) is meaningless without relationships: between basic objects and between whole fields of exploration. While the latter will take a lifetime to even surface, we aim to highlight the former in formal objects known as relations.

Definition 1. Let $K,L$ be sets. A relation from $K$ to $L$ is a subset of

$K \times L := \{(x,y) : x \in K, y \in L\},$

i.e. the cartesian product of $K$ and $L$ .

Example 1. Let $K$ be a set. The identity relation $\mathrm{id}_K$ on $K$ is defined by

$\mathrm{id}_K := \{(x,x) \subseteq K \times K : x \in K\}.$

We need relations to define a centrally crucial notion in mathematics known as a function, which is a relation that satisfies extra properties:

Definition 2. A relation $f \subseteq K \times L$ is a function if it satisfies the following two properties:

For any $x \in K$ , there exists $y \in L$ such that $(x,y) \in f$ .
For any $x \in K, y_1,y_2 \in L$ , $(x,y_1)\in f \wedge (x,y_2) \in f$ implies $y_1 = y_2$ .

In this case, we denote $f : K \to L$ , and $y = f(x)$ .

Example 2. For any set $K$ , $\mathrm{id}_K$ is a function.

Intuitively, these quantified propositions capture the idea that functions $f$ take in input values $x$ , and returns one (the first condition) and only one (the second condition) output value $f(x)$ for each input $x$ .

Many properties of functions follows from relations. Hence, we first study relations to obtain general transferrable features of functions.

Often, we need to chain relations together. This is where the notion of composite relations arises.

Definition 3. Let $K,L,M$ be sets, $R \subseteq K \times L$ , $S \subseteq L \times M$ be relations. Define the composite relation $S \circ R \subseteq K \times M$ by

$S \circ R := \{(x, z) \subseteq K \times M: (\exists y \in L: (x,y) \in R \wedge (y,z) \in S)\}.$

We can check that composing functions yields another function.

Theorem 1. Let $K, L, M$ be sets, $f : K \to L$ , $g : L \to M$ be functions. Then $g \circ f \subseteq K \times M$ is a function. Furthermore,

$(g \circ f)(x) = g(f(x)).$

Proof. We need to check that for any $x \in K$ , there exists one and only one $z \in M$ such that $(x,z) \in M$ .

Fix $x \in K$ . Since $f$ is a function, there exists one and only one $y \in L$ such that $y = f(x)$ , i.e. $(x,y) \in f$ . Since $g$ is a function, there exists one and only one $z \in L$ such that $z = g(y)$ , i.e. $(y, z) \in g$ .

Combining $(x, y)$ and $(y, z)$ , we have $(x, z) \in g \circ f$ . Furthermore,

$(g \circ f)(x) = z = g(y) = g(f(x)).$

The key property shared by relations and functions is the fact that they are associative under composition.

Theorem 2. Let $K,L,M,N$ be sets and $R \subseteq K \times L$ , $S \subseteq L \times M$ , $T \subseteq M \times N$ be relations. Then

$T \circ (S \circ R) = (T \circ S) \circ R.$

Proof. We will prove $T \circ (S \circ R) \subseteq (T \circ S) \circ R$ and leave $(\supseteq)$ as an exercise. Fix $(x,w) \in T \circ (S \circ R) \subseteq K \times N$ .

By definition, there exists $z \in M$ such that $(x,z) \in S \circ R$ and $(z,w) \in T$ . Similarly, there exists $y \in L$ such that $(x,y) \in R$ and $(y,z) \in S$ .

Combining $(y,z)$ and $(z,w)$ , we have $(y, w) \in T \circ S$ . Combining $(x,y)$ and $(y, w)$ , we have $(x,w) \in (T \circ S) \circ R$ , as required.

Corollary 1. Let $K,L,M,N$ be sets and $f : K \to L$ , $g : L \to M$ , $h : M \to N$ be functions. Then

$h \circ (g \circ f) = (h \circ g) \circ f.$

Likewise, it is often useful to invert relations. This motivates the study of inverse relations.

Definition 4. Let $K,L$ be sets and $R \subseteq K \times L$ be a relation. Define the inverse relation of $R$ by

$R^{-1} := \{(y,x) \in L \times K : (x,y) \in K \times L\}.$

Unlike function composition, the inverse of a function may not itself be a function! When then do we obtain an inverse for a function?

Theorem 3. Let $K,L$ be sets and $f : K \to L$ be a function. Then the relation $f^{-1}$ is a function if and only if $f$ satisfies the following two properties:

Surjectivity: For any $y \in L$ , there exists $x \in K$ such that $y = f(x)$ .
Injectivity: For any $x_1,x_2 \in K$ , $f(x_1) = f(x_2)$ implies $x_1 = x_2$ .

In this case, we say that $f$ is a bijection. Furthermore, $f^{-1}$ is a bijection. Furthermore, this corresponds intuitively to the horizontal line test that students may have learned prior to a discrete mathematics course.

Proof. The proof becomes obvious once we write

$y = f(x) \iff (x,y) \in f \iff (y,x) \in f^{-1}.$

We will speak more on the invertibility of functions in a future post, since there is much to discuss therein. The utility of defining functions in this manner is so that we can now properly define the natural numbers using the von Neumann construction, in the next post.

For now, let’s prove a rather interesting result that will help us detail more about inverse functions.

Theorem 4. Let $K,L$ be sets and $f : K \to L$ be a function. The following hold:

$f^{-1} \circ f =\mathrm{id}_K$ if and only if $f$ is injective.
If $f \circ f^{-1} \subseteq \mathrm{id}_L$ , then $f$ is injective.
If $\mathrm{id}_L \subseteq f \circ f^{-1}$ , then $f$ is surjective.

Proof. For the first claim, fix $(x,x) \in \mathrm{id}_K$ . Since $f$ is a function, there exists $f(x) \in L$ . Hence

$(x,f(x))\in f \wedge (f(x),x) \in f^{-1}\quad\Rightarrow \quad (x,x) \in f^{-1} \circ f.$

Thus, $\mathrm{id}_K \subseteq f^{-1} \circ f$ unconditionally. Thus, we prove that $f^{-1} \circ f \subseteq \mathrm{id}_K$ if and only if $f$ is injective.

For the direction $(\Rightarrow)$ , fix $x_1,x_2 \in K$ such that $f(x_1)=f(x_2)$ . Then

$(x_1,f(x_1)) \in f \wedge (x_2, f(x_1)) \in f \Rightarrow (x_1,x_2) \in f^{-1} \circ f \subseteq \mathrm{id}_K.$

Hence, $x_1 = x_2$ , as required.

For the direction $(\Leftarrow)$ , fix $(x,x') \in f^{-1} \circ f$ . By definition of a composite relation, there exists $y \in L$ such that

$(x,y) \in f \wedge (y,x') \in f^{-1} \quad \iff \quad f(x)=y=f(x').$

Since $f$ is injective,

$x=x' \quad \Rightarrow\quad (x,x') = (x,x) \in \mathrm{id}_K.$

For the second claim, fix $x_1,x_2 \in K$ with $f(x_1) = f(x_2)$ .Therefore,

$(x_2, f(x_1)) \in f \quad \iff \quad (f(x_1),x_2) \in f^{-1}.$

On the other hand, $(x_1, f(x_1)) \in f$ as well. Hence, $(x_1,x_2) \in f \circ f^{-1} \subseteq \mathrm{id}_L$ , which implies $x_1 = x_2$ , as required.

For the third claim, fix $y \in L$ so that $(y,y) \in \mathrm{id}_L$ . Then there exists $x \in K$ such that

$(y,x) \in f^{-1} \wedge (x,y) \in f \quad \iff \quad y = f(x).$

Functions help us define natural numbers. Probably the most crucial component in mathematics.

—Joel Kindiak, 3 Dec 24, 1229H

Responses

Demystifying the Square Root – KindiakMath

December 5, 2024 at 7:48 pm

[…] If such a function exists, we say that is the inverse of the squaring function . In fact, we have discussed such an idea before. […]

LikeLike

The True Religion of Relationship – KindiakWrites

September 18, 2025 at 8:34 pm

[…] One partial solution is that the positive interactions ought to outweigh the negative ones. There is certainly some tangible short-term merit to this notion. However, the Bible offers a far more sustainable long-term solution to the problem of human sin, and sin in the more specific sense of relational hurt. The reason why relational hurt is the most painful of all hurts is because before the world began, relationship existed between the Father and the Son and the Spirit. The Father loved the Son before creation (John 17:24), and all things were created through the Son, for the Son (Colossians 1:16). It is therefore unsurprising, therefore, that relationships are fundamental to creation, especially in mathematics! […]

LikeLike

Tying Up Loose Pairs – KindiakMath

December 28, 2025 at 12:35 am

[…] This turns out to help us define relations, and in turn, functions—the most pervasive object in mathematics. We will discuss them in further detail next time. […]

LikeLike

The Origin of Numbers – KindiakMath

December 28, 2025 at 12:38 am

[…] will now use sets and functions to define the primary star of mathematics—the natural […]

LikeLike

Creating the Integers – KindiakMath

December 28, 2025 at 12:57 am

[…] that’s not the only way to discuss inclusion—we have injections on our […]

LikeLike

Surjections as Sets – KindiakMath

December 28, 2025 at 1:02 am

[…] discussing relations, we leaned more on logic than sets. It turns out that there are ways to discuss relations more […]

LikeLike

The Indicator Function – KindiakMath

January 5, 2026 at 6:27 pm

[…] 1. Let be any set. For any , define the indicator function on […]

LikeLike

The Broad Basics of Vectors – KindiakMath

January 6, 2026 at 2:39 pm

[…] the most important instances of vector spaces would be the function spaces. These spaces don’t always share all of the same properties as , but when they do, […]

LikeLike

Entering the Matrix – KindiakMath

January 6, 2026 at 3:10 pm

[…] That is well-defined follows from being a function. For surjectivity, fix . Define and extend it to a linear transformation by linearity. […]

LikeLike

Theoretic Gaussian Elimination – KindiakMath

January 6, 2026 at 3:19 pm

[…] we call a group under function composition, called the symmetric group over . Furthermore, if is a vector space over , then the general […]

LikeLike

Mathematical Relationships

Share this:

Responses

Leave a reply to The Indicator Function – KindiakMath Cancel reply