4. ¿What is a mathematical correspondence?

In previous posts we explored binary relations — as in saying one number “is less than” another — and equivalence relations — as in grouping people who “are the same age.” Both concepts generally operate within a single set, comparing elements of the same kind. Now we take the next step toward a broader and more powerful idea: the mathematical correspondence.

What makes it special? Mathematics does not only compare elements with one another. It also needs to link elements of completely different kinds: assigning a temperature to each city, associating a price with each product, or pairing each student with a grade. When a relation acts as a bridge between two different sets, we are dealing with this kind of formal connection.

The correspondence is the concept that ties everything we already know about binary relations to the idea of a function — arguably the most important tool in all of mathematics. In this post we will build that bridge step by step: from the most general definition to the special types of correspondence that give rise to functions, injections, surjections, and bijections.

Quick recap: binary relations and the Cartesian product

Before moving on, a brief review of ordered pairs, the Cartesian product, and binary relations:

Ordered pair. An ordered pair \( (a, b) \) is a pairing of two elements where position counts. Two pairs are equal if and only if their corresponding components match:

\[ (a, b) = (c, d) \iff a = c \wedge b = d \]

Cartesian product. Given two sets \( A \) and \( B \), the Cartesian product \( A \times B \) is the set of all possible ordered pairs:

\[ A \times B = \{(a, b) \mid a \in A \wedge b \in B\} \]

Binary relation. A binary relation \( R \) from \( A \) to \( B \) is any subset of the Cartesian product:

\[ R \subseteq A \times B \]

In the study of binary relations we focused mainly on homogeneous relations — those where both sets are the same (\( R \subseteq A \times A \)) — and explored properties such as reflexivity, symmetry, and transitivity.

Now we take the next step: what happens when \( A \) and \( B \) are different?

Homogeneous vs. heterogeneous relations

Type	Definition	Example
Homogeneous	\( R \subseteq A \times A \) — both sets are the same	“\( x \) divides \( y \)” on \( \mathbb{N} \)
Heterogeneous	\( R \subseteq A \times B \) with \( A \neq B \) — distinct sets	“student \( x \) received grade \( y \)”

In plain terms: A homogeneous relation compares elements of the same type. A heterogeneous relation connects elements from two different worlds — and those connections are what we call correspondences.

In the figure on the left, the “divides” relation acts within a single set of numbers: each arrow indicates that the origin divides the destination. For example, the arrow from \( 1 \) to \( 2 \) means \( 1 \) divides \( 2 \), the arrow from \( 3 \) to \( 6 \) means \( 3 \) divides \( 6 \), and so on. On the right, the correspondence connects two sets of a different nature: students with their grades.

Note. A homogeneous relation \( R \subseteq A \times A \) can also be treated as heterogeneous if we analyze it from the correspondence perspective — it suffices to consider the source set and target set as conceptually distinct copies of \( A \).

Correspondence: definition and components

Formal definition

A correspondence is a heterogeneous binary relation between two sets \( A \) and \( B \) that links elements of one set to elements of the other according to a specific rule or condition.

Formally, given a relation \( R \) from \( A \) to \( B \):

\[ R = \{(x, y) \in A \times B \mid P(x, y)\} \]

where \( P(x, y) \) is a proposition — the correspondence rule — that determines which pairs belong to the relation.

Intuition. Out of all possible combinations in \( A \times B \), the correspondence keeps only those satisfying the condition \( P(x, y) \). Think of it as a filter: of all imaginable arrows between the two sets, it retains only those that make sense under the given rule.

Example. Let \( A = \{2, 3, 5\} \) and \( B = \{4, 6, 9, 10, 25\} \). Define the correspondence:

\[ R = \{(x, y) \in A \times B \mid y = x^2\} \]

Here \( P(x, y) \) is the proposition “\( y \) is the square of \( x \).” Evaluating:

\( x \in A \)	\( x^2 \)	\( x^2 \in B \)?	Pair in \( R \)
2	4	Yes	\( (2, 4) \)
3	9	Yes	\( (3, 9) \)
5	25	Yes	\( (5, 25) \)

So \( R = \{(2, 4),\ (3, 9),\ (5, 25)\} \).

Notation

To indicate that \( R \) is a correspondence from \( A \) to \( B \), instead of writing \( R \subseteq A \times B \), we use:

\[ R: A \rightarrow B \]

Read as “\( R \) is a correspondence from \( A \) to \( B \).” If \( (x, y) \in R \), we say:

• \( y \) is an image of \( x \) under \( R \)
• \( x \) is an origin (or preimage) of \( y \) under \( R \)

Notation examples:

Notation	Equivalent	Read as	Meaning
\( R: \mathbb{R} \rightarrow \mathbb{N} \)	\( R \subseteq \mathbb{R} \times \mathbb{N} \)	“\( R \) from the reals to the naturals”	Takes elements of \( \mathbb{R} \) and associates them with elements of \( \mathbb{N} \)
\( R: \mathbb{N} \rightarrow \mathbb{N} \)	\( R \subseteq \mathbb{N} \times \mathbb{N} \)	“\( R \) from the naturals to the naturals”	Operates within the naturals
\( R: \mathbb{N} \rightarrow \mathbb{R} \)	\( R \subseteq \mathbb{N} \times \mathbb{R} \)	“\( R \) from the naturals to the reals”	Takes naturals and associates them with reals
\( R: \mathbb{Q} \rightarrow \mathbb{R} \)	\( R \subseteq \mathbb{Q} \times \mathbb{R} \)	“\( R \) from the rationals to the reals”	Takes rationals and associates them with reals

Note. Order matters: \( R: \mathbb{N} \rightarrow \mathbb{R} \) and \( R: \mathbb{R} \rightarrow \mathbb{N} \) are different correspondences even though they involve the same sets, because the direction of association is different.

Domain and range of a correspondence

Given a correspondence \( R: A \rightarrow B \):

\[ \text{Dom}(R) = \{x \in A \mid \exists y \in B,\ (x, y) \in R\} \]

\[ \text{Ran}(R) = \{y \in B \mid \exists x \in A,\ (x, y) \in R\} \]

The domain is the set of all elements of \( A \) that have at least one image in \( B \). The range is the set of all elements of \( B \) that are the image of at least one element of \( A \).

Components of a correspondence

Component	Notation	Definition	Description
Source set	\( A \)	\( x \in A \)	All elements that could have an image
Target set	\( B \)	\( y \in B \)	All elements that could be an image
Domain	\( \text{Dom}(R) \)	\( \{x \in A \mid \exists y \in B,\ (x,y) \in R\} \)	Elements of \( A \) that actually have an image
Range	\( \text{Ran}(R) \)	\( \{y \in B \mid \exists x \in A,\ (x,y) \in R\} \)	Elements of \( B \) that actually are an image

In plain terms: The source set is the “universe of candidates” for having an image. The domain is the subset of candidates that actually participate in the correspondence. The same applies on the right: the target set is the universe, and the range is what actually receives an arrow.

It always holds that:

\[ \text{Dom}(R) \subseteq A \qquad \text{and} \qquad \text{Ran}(R) \subseteq B \]

In this example, \( \text{Dom}(R) = \{2, 3, 5\} \) (all participate, since all have a square in \( B \)), while \( 7 \in A \) falls outside the domain (\( 7^2 = 49 \notin B \)). On the \( B \) side, the range is \( \{4, 9, 25\} \), while \( 6 \) and \( 10 \) are the image of no element of \( A \).

Representation tools

A correspondence can look abstract at first. To make it more approachable, there are three standard ways to represent one.

Arrow diagram

The arrow diagram (or sagittal diagram) is the most intuitive visual tool. It draws arrows between elements to make the links concrete.

Construction:

1. Draw two ovals: one for the source set \( A \) and one for the target set \( B \)
2. Place the elements inside each oval
3. For each pair \( (x, y) \in R \), draw an arrow from \( x \) to \( y \)

Example. Let \( A = \{a, b, c, d\} \), \( B = \{1, 2, 3\} \), and the correspondence:

\[ R = \{(a, 1),\ (b, 2),\ (b, 3),\ (d, 2)\} \]

Notice that:

• Element \( c \) sends no arrows — it does not belong to the domain
• Element \( b \) sends two arrows — it has two distinct images
• Elements \( b \) and \( d \) share the image \( 2 \) — element \( 2 \) has two origins

The arrow diagram’s strength is that a single glance reveals the full behavior of the correspondence: who has an image, who doesn’t, who has several, who is the image of multiple origins.

Cartesian diagram

For correspondences between numerical sets, the Cartesian diagram maps the relation to a two-dimensional plane:

• Elements of \( A \) are placed on the horizontal axis
• Elements of \( B \) are placed on the vertical axis
• Each pair \( (x, y) \in R \) is marked as a point in the plane

Example. Let \( A = \{1, 2, 3, 4\} \), \( B = \{2, 4, 6, 8\} \), and the correspondence \( R: A \rightarrow B \) defined by \( y = 2x \):

This representation is especially useful when working with continuous functions, since it lets you see trends, symmetries, and graphical behavior at a glance.

Note. For correspondences over continuous numerical sets (like \( \mathbb{R} \)), the isolated points become curves. When studying real functions, the Cartesian plane makes the vertical line test available: a correspondence is a function if every vertical line meets the graph in at most one point.

Matrix representation

When both sets are finite, any correspondence can be encoded as a Boolean matrix (or adjacency matrix):

• Rows represent the elements of the source set \( A \)
• Columns represent the elements of the target set \( B \)
• Each cell holds T (true) if the pair belongs to \( R \), or F (false) if not

Example. Let \( A = \{1, 2, 3\} \), \( B = \{1, 2, 3\} \), and the correspondence “\( x \) is strictly less than \( y \)” (\( x < y \)):

\[ R = \{(1, 2),\ (1, 3),\ (2, 3)\} \]

\( A \downarrow \setminus B \rightarrow \)	1	2	3
1	F	T	T
2	F	F	T
3	F	F	F

Reading the matrix directly:

• Row 1 has two T’s → 1 is related to 2 and 3 (since \( 1 < 2 \) and \( 1 < 3 \))
• Row 3 has only F’s → 3 is not less than any element of \( B \)
• The main diagonal has only F’s → no element is less than itself (the relation is irreflexive)

Intuition. The matrix representation eliminates the visual clutter that can appear in arrow diagrams with many crossing arrows. It also enables computer systems to process relations via algebraic operations on Boolean matrices.

Another example. Let \( A = \{2, 3, 6\} \), \( B = \{2, 3, 6\} \), and “\( x \) divides \( y \)”:

\( A \downarrow \setminus B \rightarrow \)	2	3	6
2	T	F	T
3	F	T	T
6	F	F	T

The main diagonal has only T’s (every number divides itself), and the row of \( 6 \) has just one T in the column of \( 6 \), since \( 6 \) does not divide \( 2 \) or \( 3 \).

The four fundamental conditions

Given a correspondence \( R: A \rightarrow B \), its behavior is completely described by four independent conditions. Each one evaluates a different aspect of how elements are connected across the two sets.

These conditions are the key to classifying correspondences — and to understanding what makes a function special.

Condition 1: Existence of image (e.i.)

The condition of existence of image guarantees that every element of the source set \( A \) has at least one image in \( B \). No element of \( A \) is left dangling.

\[ \forall a \in A,\ \exists b \in B : (a, b) \in R \]

In plain terms: “Everyone on the left sends at least one arrow.” No element of \( A \) is stranded.

When this condition holds, the domain equals the entire source set:

\[ \text{Dom}(R) = A \]

Condition 2: Uniqueness of image (u.i.)

The condition of uniqueness of image guarantees that elements of \( A \) that have an image have only one. No element may “branch” to multiple destinations.

\[ \big((a, b_1) \in R \wedge (a, b_2) \in R\big) \implies b_1 = b_2 \]

In plain terms: “No element on the left sends more than one arrow.” Some may send none, but none may send two.

Condition 3: Existence of origin (e.o.)

The condition of existence of origin guarantees that every element of the target set \( B \) is the image of at least one element of \( A \). No element of \( B \) is left without receiving an arrow.

\[ \forall b \in B,\ \exists a \in A : (a, b) \in R \]

In plain terms: “Everyone on the right receives at least one arrow.” The range equals the entire target set:

\[ \text{Ran}(R) = B \]

Condition 4: Uniqueness of origin (u.o.)

The condition of uniqueness of origin guarantees that elements of \( B \) that are images come from exactly one element of \( A \). No two elements of \( A \) may both point to the same destination.

\[ \big((a_1, b) \in R \wedge (a_2, b) \in R\big) \implies a_1 = a_2 \]

In plain terms: “No element on the right receives more than one arrow.” Some may receive none, but none may receive two.

Summary of the four conditions

Condition	Abbreviation	What it checks	Formula
Existence of image	e.i.	Does every element of \( A \) have an image?	\( \forall a \in A,\ \exists b \in B : (a,b) \in R \)
Uniqueness of image	u.i.	Does every element that has an image have only one?	\( (a,b_1) \in R \wedge (a,b_2) \in R \implies b_1 = b_2 \)
Existence of origin	e.o.	Does every element of \( B \) have an origin?	\( \forall b \in B,\ \exists a \in A : (a,b) \in R \)
Uniqueness of origin	u.o.	Does every element that has an origin have only one?	\( (a_1,b) \in R \wedge (a_2,b) \in R \implies a_1 = a_2 \)

The key insight. The four conditions are independent: satisfying one does not imply satisfying another. This generates \( 2^4 = 16 \) possible combinations. The most important ones have special names, which we study next.

Notice the symmetry: the first two conditions (e.i. and u.i.) concern the source set \( A \), while the last two (e.o. and u.o.) concern the target set \( B \). Furthermore, “existence” means “at least one” and “uniqueness” means “at most one.”

When both conditions on the same side hold simultaneously, we get “exactly one”:

Combination	Result
e.i. + u.i.	Every element of \( A \) has exactly one image
e.o. + u.o.	Every element of \( B \) has exactly one origin

Classification of correspondences

The four fundamental conditions allow us to classify correspondences into specific types according to which ones are satisfied. Each type has a name and a precise meaning.

Multi-valued correspondence

A correspondence is multi-valued when it does not satisfy uniqueness of image: at least one element of \( A \) has two or more distinct images.

\[ \exists a \in A : a \text{ has two or more distinct images in } B \]

Example. \( A = \{1, 2\} \), \( B = \{a, b, c\} \), \( R = \{(1, a),\ (1, b),\ (2, c)\} \).

Element \( 1 \) has two images: \( a \) and \( b \). The correspondence is multi-valued.

Single-valued correspondence

A correspondence is single-valued when it satisfies uniqueness of image (u.i.). Elements that have an image have exactly one.

Condition	Status
u.i.	✓

Example. \( A = \{1, 2, 3\} \), \( B = \{a, b, c\} \), \( R = \{(1, a),\ (3, b)\} \).

Element \( 1 \) has a single image (\( a \)) and element \( 3 \) has a single image (\( b \)). Element \( 2 \) has no image — but that is allowed, since u.i. only requires that those with an image have no more than one.

Note. The single-valued correspondence is the foundation on which the concept of function is built. Every function is, at minimum, a single-valued correspondence.

One-to-one correspondence

A correspondence is one-to-one when it satisfies both uniqueness of image (u.i.) and uniqueness of origin (u.o.).

Condition	Status
u.i.	✓
u.o.	✓

The connections are strictly “one to one”: each element that has an image has exactly one, and each element that is an image has exactly one origin.

Example. \( A = \{1, 2, 3, 4\} \), \( B = \{a, b, c, d\} \), \( R = \{(1, c),\ (3, a)\} \).

Partial function (u.i. without e.i.)

Some authors use the term “function” to designate a correspondence that satisfies only uniqueness of image (u.i.) — without requiring every element of \( A \) to have an image.

In modern terminology, this is called a partial function: a rule that assigns a unique image to each element in its domain, but whose domain may be a proper subset of \( A \).

Condition	Status
u.i.	✓
e.i.	✗ (may fail)

\[ f \subseteq A \times B \qquad \text{with} \qquad (x,y) \in f \wedge (x,z) \in f \implies y = z \]

In plain terms: A partial function is a single-valued correspondence where not all elements of \( A \) necessarily participate.

Example. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{a, b, c\} \). The relation \( f = \{(1, a),\ (2, c),\ (4, b)\} \) satisfies u.i. (each element with an image has exactly one), but not e.i. because \( 3 \in A \) has no image. So \( f \) is a partial function.

Function (u.i. + e.i.)

A correspondence \( f: A \rightarrow B \) is called a function (or total function, or mapping) when every element of \( A \) is assigned a unique image in \( B \). This requires both uniqueness and existence of image to hold simultaneously.

Condition	Status
u.i.	✓
e.i.	✓

Formally:

\[ \forall x \in A,\ \exists ! y \in B : y = f(x) \]

read as “for every \( x \) in \( A \), there exists a unique \( y \) in \( B \) such that \( y = f(x) \).”

In plain terms: A function is a correspondence where every element of \( A \) sends exactly one arrow.

The standard notation is:

\[ f: A \rightarrow B \quad \text{defined by} \quad y = f(x) \]

where \( x \) is called the independent variable (or argument), \( y \) the dependent variable (or value), and \( f(x) \) denotes “the image of \( x \) under \( f \).”

Example. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{2, 4, 6, 8, 10\} \) with \( f(x) = 2x \):

\[ f = \{(1, 2),\ (2, 4),\ (3, 6),\ (4, 8)\} \]

Every element of \( A \) has exactly one image → \( f \) is a function. Note that \( 10 \in B \) is nobody’s image, but that does not prevent \( f \) from being a function (e.o. is not required).

Terminological note. In many textbooks the terms “function” and “mapping” are used interchangeably. When \( A \) and \( B \) are numerical sets, “function” is preferred. When they are abstract (sets of points, vector spaces, etc.), “map” or “mapping” is more common. In this post we use both terms freely.

Injective function (u.i. + e.i. + u.o.)

A function is injective (one-to-one) when, in addition to being a function, it satisfies uniqueness of origin: distinct elements of \( A \) produce distinct images in \( B \).

Condition	Status
u.i.	✓
e.i.	✓
u.o.	✓

Formally:

\[ f(x_1) = f(x_2) \implies x_1 = x_2 \]

or equivalently (by contrapositive):

\[ x_1 \neq x_2 \implies f(x_1) \neq f(x_2) \]

In plain terms: “Distinct origins always lead to distinct destinations.” No two arrows arrive at the same point.

Example 1. Let \( f: \mathbb{N} \rightarrow \mathbb{N} \) be defined by \( f(x) = 2x + 3 \).

Proof of injectivity: Let \( x_1, x_2 \in \mathbb{N} \) with \( f(x_1) = f(x_2) \):

\[ 2x_1 + 3 = 2x_2 + 3 \implies 2x_1 = 2x_2 \implies x_1 = x_2 \]

Therefore \( f \) is injective. ✓

Example 2. Let \( g: \mathbb{Z} \rightarrow \mathbb{N} \) be defined by \( g(x) = x^2 – 1 \).

If \( g(x_1) = g(x_2) \), then \( x_1^2 = x_2^2 \), meaning \( x_1 = x_2 \) or \( x_1 = -x_2 \). Since we cannot conclude \( x_1 = x_2 \) in all cases, \( g \) is not injective. ✗

Graphical note. In the Cartesian plane, a function is injective if and only if every horizontal line meets the graph in at most one point.

Surjective function (u.i. + e.i. + e.o.)

A function is surjective (onto) when it satisfies existence of origin: every element of \( B \) is the image of at least one element of \( A \).

Condition	Status
u.i.	✓
e.i.	✓
e.o.	✓

Formally:

\[ \forall y \in B,\ \exists x \in A : f(x) = y \qquad \text{i.e.} \qquad \text{Ran}(f) = B \]

In plain terms: “Everyone on the right receives at least one arrow.” No element of \( B \) is left out.

Example 1. Let \( A = \{1, 2, 3, 4\} \), \( B = \{1, 3, 5, 7\} \), and \( g = \{(1, 3),\ (2, 1),\ (3, 5),\ (4, 7)\} \).

\( \text{Ran}(g) = \{1, 3, 5, 7\} = B \). Every element of \( B \) is an image → \( g \) is surjective. ✓

Example 2. Let \( f: \mathbb{N} \rightarrow \mathbb{N} \) be defined by \( f(x) = 2x \).

\( \text{Ran}(f) = \{2, 4, 6, \ldots\} \neq \mathbb{N} \) (odd numbers are nobody’s image). So \( f \) is not surjective. ✗

Bijective function (all 4 conditions)

A function is bijective (a bijection) when it is simultaneously injective and surjective — satisfying all four fundamental conditions.

Condition	Status
u.i.	✓
e.i.	✓
u.o.	✓
e.o.	✓

In plain terms: Every element of \( A \) has exactly one image, and every element of \( B \) has exactly one origin. A perfect “one-to-one and onto” pairing.

For finite sets, a bijection is only possible when \( A \) and \( B \) have the same number of elements (the same cardinality).

Example. Let \( B = \{y \mid y = 2n,\ n \in \mathbb{N}\} \) (the even natural numbers) and \( f: \mathbb{N} \rightarrow B \) defined by \( f(x) = 2x \).

1. Injectivity: If \( f(x_1) = f(x_2) \), then \( 2x_1 = 2x_2 \), so \( x_1 = x_2 \). ✓
2. Surjectivity: Given \( y \in B \), since \( y \) is even, there exists \( x = y/2 \in \mathbb{N} \) such that \( f(x) = y \). ✓

Being both injective and surjective, \( f \) is bijective. ✓

Note. This example shows that the natural numbers and the even natural numbers have the same cardinality! It seems paradoxical (the evens look like “half” of the naturals), but the bijection confirms it. This is one of the surprises of infinite sets, discovered by Cantor — and in fact, it was precisely this study of different “sizes” of infinity that led Cantor to create set theory, the foundation of all modern mathematics.

Classification summary table

Type of correspondence	u.i.	e.i.	u.o.	e.o.	Description
General correspondence	—	—	—	—	No restrictions
Multi-valued	✗	—	—	—	At least one element has multiple images
Single-valued	✓	—	—	—	Each participating origin has exactly one image
One-to-one	✓	—	✓	—	One-to-one without requiring totality
Partial function	✓	✗	—	—	Single-valued but not all elements participate
Function (mapping)	✓	✓	—	—	All participate with a unique image
Injective function	✓	✓	✓	—	Function + distinct origins → distinct images
Surjective function	✓	✓	—	✓	Function + every element of \( B \) is an image
Bijective function	✓	✓	✓	✓	Perfect pairing

Note. The four conditions generate \( 2^4 = 16 \) possible combinations. The table above lists only those that receive standard names in mathematics. The remaining combinations are perfectly valid correspondences, but they typically don’t get special names because the primary interest is in correspondences that involve uniqueness of image (u.i.), since those lead to the concept of a function.

Composition of correspondences

Correspondences are not static structures: they can be chained together to produce new connections. The operation that makes this possible is called composition.

Definition

Let \( R_1: A \rightarrow B \) and \( R_2: B \rightarrow C \) be two correspondences. The composition of \( R_1 \) with \( R_2 \), written \( R_2 \circ R_1 \), is the correspondence from \( A \) to \( C \) defined by:

\[ R_2 \circ R_1 = \{(x, z) \in A \times C \mid \exists y \in B : (x, y) \in R_1 \wedge (y, z) \in R_2\} \]

In plain terms: Composition is a “logical shortcut.” Instead of going from \( A \) to \( B \) and then from \( B \) to \( C \), you connect \( A \) directly to \( C \) by chaining both rules. If \( x \) relates to \( y \) via \( R_1 \), and \( y \) relates to \( z \) via \( R_2 \), then \( x \) relates to \( z \) via \( R_2 \circ R_1 \).

When both correspondences are functions (satisfying e.i. + u.i.), the composition simplifies to the familiar notation:

\[ (g \circ f)(x) = g\big[f(x)\big] \]

and the result is also a function.

Important note on reading. In the notation \( g \circ f \), we read it as “\( g \) composed with \( f \)” or “\( g \) after \( f \).” Evaluation proceeds right to left: \( f \) is applied first, then \( g \) is applied to the result.

Compatibility requirement

For the composition \( R_2 \circ R_1 \) to be nonempty, the range of \( R_1 \) must have a nonempty intersection with the domain of \( R_2 \):

\[ \text{Ran}(R_1) \cap \text{Dom}(R_2) \neq \emptyset \]

If \( R_1: A \rightarrow B \) and \( R_2: B \rightarrow C \), this requirement is automatically satisfied because the output of \( R_1 \) lands in \( B \), which is precisely the input set of \( R_2 \).

Example with ordered pairs

Let the correspondences be:

\[ R_1 = \{(-2, 0),\ (-1, -4),\ (3, 1),\ (5, 2)\} \] \[ R_2 = \{(-2, -1),\ (0, 3),\ (1, 4),\ (2, 0),\ (4, 5)\} \]

To find \( R_2 \circ R_1 \), we chain: for each pair \( (x, y) \in R_1 \), we look for \( (y, z) \in R_2 \) and form \( (x, z) \).

\( x \)	\( y \) in \( R_1 \)	\( z \) in \( R_2 \)	Pair in \( R_2 \circ R_1 \)
\( -2 \)	\( 0 \)	\( (0, 3) \in R_2 \Rightarrow 3 \)	\( (-2, 3) \)
\( 3 \)	\( 1 \)	\( (1, 4) \in R_2 \Rightarrow 4 \)	\( (3, 4) \)
\( 5 \)	\( 2 \)	\( (2, 0) \in R_2 \Rightarrow 0 \)	\( (5, 0) \)

Note: \( (-1, -4) \in R_1 \), but there is no pair \( (-4, z) \in R_2 \), so \( -1 \) does not belong to the domain of \( R_2 \circ R_1 \).

\[ R_2 \circ R_1 = \{(-2, 3),\ (3, 4),\ (5, 0)\} \]

Example with formulas (the case of functions)

When the correspondences are functions, composition can be computed by direct substitution.

Let \( f: \mathbb{Q} \rightarrow \mathbb{Q} \) with \( f(x) = x + 3 \) and \( g: \mathbb{Q} \rightarrow \mathbb{Q} \) with \( g(x) = 2x \).

The notation \( f: \mathbb{Q} \rightarrow \mathbb{Q} \) means \( f \) takes rationals and maps them to rationals — equivalent to writing \( f \subseteq \mathbb{Q} \times \mathbb{Q} \).

Notation reminder. The expression \( (g \circ f)(x) \) is read “\( g \) composed with \( f \) evaluated at \( x \).” Evaluation goes right to left: apply \( f \) first, then \( g \).

\[ (g \circ f)(x) = g\big[f(x)\big] \]

Finding \( g \circ f \):

Step 1: Apply \( f \) to \( x \):

\[ f(x) = x + 3 \]

Step 2: Apply \( g \) to the result:

\[ g\big[f(x)\big] = g(x + 3) = 2(x + 3) = 2x + 6 \]

\[ (g \circ f)(x) = 2x + 6 \]

Finding \( f \circ g \):

Step 1: Apply \( g \) to \( x \):

\[ g(x) = 2x \]

Step 2: Apply \( f \) to the result:

\[ f\big[g(x)\big] = f(2x) = 2x + 3 \]

\[ (f \circ g)(x) = 2x + 3 \]

Comparison:

	Result
\( (g \circ f)(x) \)	\( 2x + 6 \)
\( (f \circ g)(x) \)	\( 2x + 3 \)

Since \( 2x + 6 \neq 2x + 3 \), we have \( g \circ f \neq f \circ g \).

Key observation. In general, composition of correspondences is not commutative — the order in which they are applied changes the result.

Properties of composition

Property	Statement	Description
Associativity	\( (R_3 \circ R_2) \circ R_1 = R_3 \circ (R_2 \circ R_1) \)	The grouping does not change the result
Non-commutativity	\( R_2 \circ R_1 \neq R_1 \circ R_2 \) (in general)	Order matters
Identity element	\( R \circ I_A = R \) and \( I_B \circ R = R \)	The identity changes nothing

where \( I_A: A \rightarrow A \) is the identity correspondence, defined by \( I_A = \{(x, x) \mid x \in A\} \).

Intuition. Associativity says that if you have three chained correspondences \( A \xrightarrow{R_1} B \xrightarrow{R_2} C \xrightarrow{R_3} D \), you can compute the result by grouping however you like: first \( R_2 \circ R_1 \) then \( R_3 \), or first \( R_3 \circ R_2 \) then compose with \( R_1 \). The final result is the same.

Proof of associativity. Let \( R_1: A \rightarrow B \), \( R_2: B \rightarrow C \), \( R_3: C \rightarrow D \). For all \( (x, w) \):

\[ (x, w) \in (R_3 \circ R_2) \circ R_1 \iff \exists y \in B : (x, y) \in R_1 \wedge (y, w) \in R_3 \circ R_2 \] \[ \iff \exists y \in B,\ \exists z \in C : (x, y) \in R_1 \wedge (y, z) \in R_2 \wedge (z, w) \in R_3 \]

\[ (x, w) \in R_3 \circ (R_2 \circ R_1) \iff \exists z \in C : (x, z) \in R_2 \circ R_1 \wedge (z, w) \in R_3 \] \[ \iff \exists y \in B,\ \exists z \in C : (x, y) \in R_1 \wedge (y, z) \in R_2 \wedge (z, w) \in R_3 \]

Both expressions yield the same condition, so \( (R_3 \circ R_2) \circ R_1 = R_3 \circ (R_2 \circ R_1) \). ∎

The proofs of the remaining properties follow a similar argument and are left as exercises.

Does composition preserve the type?

A natural question: if we compose two correspondences of the same type, does the result stay that type? Analyzing each condition under composition \( R_2 \circ R_1 \):

Condition	Preserved?	Reason
u.i.	✓ Always	If \( x \) has a unique image \( y \) via \( R_1 \), and \( y \) has a unique image \( z \) via \( R_2 \), then \( x \) has unique image \( z \)
e.i.	✓ Always	If every \( x \in A \) reaches some \( y \in B \), and every \( y \in B \) reaches some \( z \in C \), the chain never breaks
u.o.	✓ Always	If two distinct \( x \)’s reach the same \( z \), by u.o. of \( R_2 \) they passed through the same \( y \), and by u.o. of \( R_1 \) they are the same \( x \)
e.o.	✓ Always	If every \( z \in C \) has an origin \( y \) via \( R_2 \), and that \( y \) has an origin \( x \) via \( R_1 \), then every \( z \) has an origin \( x \)

Takeaway. All four positive conditions (✓) are preserved under composition. This means types defined by positive conditions always stay their type when two such correspondences are composed.

The complete table:

Type	Preserved under composition?
General correspondence	✓ Always (trivially)
Multi-valued	✗ Not always
Single-valued	✓ Always
One-to-one	✓ Always
Partial function	✓ Always
Function	✓ Always
Injective function	✓ Always
Surjective function	✓ Always
Bijective function	✓ Always

Note. The multi-valued type is the only one that does not preserve itself. This happens because it is defined by a negative condition (✗ u.i.), and under composition the “branches” can converge and disappear.

Counterexample for multi-valued. Let \( B = \{a, b, c\} \), \( C = \{x, y\} \):

\[ R_1 = \{(1, a),\ (1, b)\} \quad \text{(multi-valued: 1 has two images)} \] \[ R_2 = \{(a, x),\ (b, x),\ (c, x),\ (c, y)\} \quad \text{(multi-valued: } c \text{ has two images)} \]

Composing: the two routes from \( 1 \) (through \( a \) and \( b \)) both converge to \( x \), and the multi-valued branch of \( R_2 \) (through \( c \)) is never reached:

\[ R_2 \circ R_1 = \{(1, x)\} \quad \text{— single-valued!} \]

Inverse correspondence

The intuition

If a correspondence \( R \) associates \( x \) with \( y \), can we build another correspondence that “undoes” that association and recovers \( x \) from \( y \)? That correspondence is called the inverse.

Graphically, the inverse reverses all arrows: what was an image becomes an origin, and vice versa.

Definition

Given any correspondence \( R \subseteq A \times B \), we can always form its inverse correspondence \( R^{-1} \subseteq B \times A \) by swapping the pairs:

\[ (x, y) \in R \iff (y, x) \in R^{-1} \]

In plain terms: The inverse always exists as a correspondence — simply swap the components of every ordered pair. What was an image becomes an origin, and vice versa.

Notation

Given a correspondence \( R: A \rightarrow B \), its inverse is written:

\[ R^{-1}: B \rightarrow A \]

That is, if the original correspondence goes from \( A \) to \( B \), the inverse goes from \( B \) to \( A \) — equivalent to writing \( R^{-1} \subseteq B \times A \).

Does the inverse of a function remain a function?

Not always. When arrows are reversed, a functional inverse may lose properties the original had. Specifically, the inverse of a function is not always a function. Here is why:

Example. Let \( A = \{-2, -1, 0, 2\} \), \( B = \{0, 1, 2, 4, 5\} \), and \( f(x) = x^2 \):

\[ f = \{(-2, 4),\ (-1, 1),\ (0, 0),\ (2, 4)\} \]

The inverse relation would be:

\[ f^{-1} = \{(4, -2),\ (1, -1),\ (0, 0),\ (4, 2)\} \]

The problem: element \( 4 \) has two images in the inverse — \( -2 \) and \( 2 \). This violates uniqueness of image, so \( f^{-1} \) is not a function.

Additionally, \( 2 \in B \) and \( 5 \in B \) have no image in \( f^{-1} \), so existence of image also fails.

As this example shows, inverting a correspondence does not always preserve its properties. However, under specific conditions, it does. Let’s see what those conditions are.

When is the inverse a function?

If \( f: A \rightarrow B \) is a bijective function, its inverse \( f^{-1}: B \rightarrow A \) is also a function, and satisfies:

\[ y = f(x) \iff x = f^{-1}(y) \]

Moreover, the inverse satisfies:

\[ (f^{-1} \circ f)(x) = x \quad \forall x \in A \qquad \text{and} \qquad (f \circ f^{-1})(y) = y \quad \forall y \in B \]

That is: \( f^{-1} \circ f = I_A \) and \( f \circ f^{-1} = I_B \), where \( I_A \) and \( I_B \) are the identity functions.

In plain terms: Applying \( f \) and then \( f^{-1} \) (or vice versa) returns you to the starting point. The inverse “undoes” what \( f \) did.

Theorem: existence of the inverse function

A function \( f: A \rightarrow B \) has an inverse function \( f^{-1}: B \rightarrow A \) if and only if \( f \) is bijective.

Proof.

\( (\Rightarrow) \) If \( f \) has an inverse, then it is bijective.

Suppose there exists \( g: B \rightarrow A \) such that \( g \circ f = I_A \) and \( f \circ g = I_B \).

a) \( f \) is injective: Let \( x_1, x_2 \in A \) with \( f(x_1) = f(x_2) \). Applying \( g \) to both sides:

\[ g\big[f(x_1)\big] = g\big[f(x_2)\big] \implies (g \circ f)(x_1) = (g \circ f)(x_2) \implies I_A(x_1) = I_A(x_2) \implies x_1 = x_2 \]

b) \( f \) is surjective: Let \( y \in B \). Since \( f \circ g = I_B \):

\[ y = I_B(y) = (f \circ g)(y) = f\big[g(y)\big] \]

Setting \( x = g(y) \in A \), we have \( f(x) = y \). So every \( y \in B \) has a preimage.

Being injective and surjective, \( f \) is bijective. ✓

\( (\Leftarrow) \) If \( f \) is bijective, then it has an inverse.

Since \( f \) is surjective, for every \( y \in B \) there exists \( x \in A \) with \( f(x) = y \). Since \( f \) is injective, that \( x \) is unique. Define:

\[ g: B \rightarrow A \qquad \text{by} \qquad g(y) = x \iff f(x) = y \]

Verification:

• \( (g \circ f)(x) = g\big[f(x)\big] = g(y) = x = I_A(x) \) → \( g \circ f = I_A \) ✓
• \( (f \circ g)(y) = f\big[g(y)\big] = f(x) = y = I_B(y) \) → \( f \circ g = I_B \) ✓

Therefore \( g = f^{-1} \) is the inverse function of \( f \). ∎

How to find the inverse

To find the algebraic expression for \( f^{-1} \), follow this procedure:

1. Write \( y = f(x) \)
2. Solve for \( x \) in terms of \( y \)
3. Swap the variables: the result is \( f^{-1}(x) \)

Example. Let \( f: \mathbb{Q} \rightarrow \mathbb{Q} \) be defined by \( f(x) = 2x – 3 \). Determine whether it is invertible and find the inverse.

Step 1: Verify bijectivity.

• Injectivity: If \( f(x_1) = f(x_2) \), then \( 2x_1 – 3 = 2x_2 – 3 \), so \( x_1 = x_2 \). ✓
• Surjectivity: Given \( y \in \mathbb{Q} \), solve \( y = 2x – 3 \): \( x = \frac{y + 3}{2} \in \mathbb{Q} \). ✓

\( f \) is bijective, so it is invertible.

Step 2: Find the inverse.

From \( y = 2x – 3 \), solve for \( x = \frac{y + 3}{2} \). Swapping variables:

\[ f^{-1}(x) = \frac{x + 3}{2} \]

Verification:

\[ (f \circ f^{-1})(x) = f\left(\frac{x+3}{2}\right) = 2 \cdot \frac{x+3}{2} – 3 = x + 3 – 3 = x \quad ✓ \]

Graphical interpretation

In the Cartesian plane, the graph of \( f^{-1} \) is the reflection of the graph of \( f \) across the line \( y = x \).

This symmetry makes sense: if the point \( (a, b) \) lies on the graph of \( f \) (meaning \( b = f(a) \)), then the point \( (b, a) \) lies on the graph of \( f^{-1} \) — and \( (b, a) \) is exactly the reflection of \( (a, b) \) across the line \( y = x \).

Note. If the original function is not injective, reversing the arrows creates “collisions” — a single input would produce two different outputs — and the inverse fails to be a function. This is why bijectivity is both necessary and sufficient.

Does inverting preserve the type of correspondence?

We know that every correspondence has an inverse — simply swap the components of each ordered pair. But does the inverse stay the same type as the original?

Note. Mathematics textbooks typically prove that the inverse of a function is a function if and only if it is bijective (the theorem above), but they rarely extend that analysis to all other types of correspondence in a systematic way. This section does exactly that, using the property-swapping rule: inverting exchanges image properties with origin properties.

How properties transform under inversion

When a correspondence \( R \) is inverted, the properties on the image side and the origin side swap:

Property in \( R \)	Becomes… in \( R^{-1} \)
\( u.i. \) (uniqueness of image)	\( u.o. \) (uniqueness of origin)
\( e.i. \) (existence of image)	\( e.o. \) (existence of origin)
\( u.o. \) (uniqueness of origin)	\( u.i. \) (uniqueness of image)
\( e.o. \) (existence of origin)	\( e.i. \) (existence of image)

Intuition. Reversing the arrows turns every “image-side” property into an “origin-side” property, and vice versa. With this swapping rule we can mechanically determine what type results from inverting any correspondence.

Analysis by correspondence type

General correspondence — always preserves the type

A general correspondence has no restrictions. Its inverse is also a general correspondence. ✓

One-to-one — always preserves the type

One-to-one requires \( u.i. = \checkmark \) and \( u.o. = \checkmark \). After inverting:

• \( u.i._{R^{-1}} = u.o._R = \checkmark \) ✓
• \( u.o._{R^{-1}} = u.i._R = \checkmark \) ✓

The two properties simply trade places. The inverse of a one-to-one correspondence is always another one-to-one correspondence.

Bijective function — always preserves the type

A bijection has all four properties. After inverting, all four trade places and all still hold. The inverse of a bijective function is always another bijective function. This is precisely what the theorem above demonstrates.

Note. The general correspondence, the one-to-one correspondence, and the bijective function are the three types whose definitions are symmetric with respect to the image/origin swap. They are the only ones that always preserve their type under inversion.

Multi-valued — does not always preserve the type

Multi-valued is defined by \( u.i. = \text{✗} \). For the inverse also to be multi-valued, we need \( u.i._{R^{-1}} = \text{✗} \), which is equivalent to \( u.o._R = \text{✗} \).

Preserves the type only if the original is not injective (\( u.o. = \text{✗} \)).

Counterexample. Let \( A = \{1\} \), \( B = \{a, b\} \), and \( R = \{(1, a), (1, b)\} \). The relation is multi-valued (1 has two images), but \( R^{-1} = \{(a, 1), (b, 1)\} \) is single-valued — each origin has exactly one image. The type was not preserved.

Single-valued — does not always preserve the type

Single-valued requires \( u.i. = \checkmark \). For the inverse also to be single-valued, we need \( u.o._R = \checkmark \).

Preserves the type only if the original is injective. If not, the inverse is multi-valued.

Partial function — does not always preserve the type

Partial function requires \( u.i. = \checkmark \) and \( e.i. = \text{✗} \). For the inverse also to be a partial function:

• \( u.i._{R^{-1}} = u.o._R \) must be \( \checkmark \) → the original must be injective
• \( e.i._{R^{-1}} = e.o._R \) must be \( \text{✗} \) → the original must not be surjective

Preserves the type only if \( u.o. = \checkmark \) and \( e.o. = \text{✗} \).

Function — does not always preserve the type

A function requires \( u.i. = \checkmark \) and \( e.i. = \checkmark \). For the inverse also to be a function:

• \( u.i._{R^{-1}} = u.o._R \) must be \( \checkmark \) → the original must be injective
• \( e.i._{R^{-1}} = e.o._R \) must be \( \checkmark \) → the original must be surjective

Preserves the type only if the original is bijective. This is the theorem of the inverse function we already proved.

Injective function — does not always preserve the type

An injective function requires \( u.i. = \checkmark \), \( e.i. = \checkmark \), and \( u.o. = \checkmark \). For the inverse also to be injective:

• \( u.i._{R^{-1}} = u.o._R = \checkmark \) ✓ (already guaranteed)
• \( e.i._{R^{-1}} = e.o._R \) must be \( \checkmark \) → the original must be surjective
• \( u.o._{R^{-1}} = u.i._R = \checkmark \) ✓ (already guaranteed)

Preserves the type only if \( e.o. = \checkmark \), which makes it bijective.

Surjective function — does not always preserve the type

A surjective function requires \( u.i. = \checkmark \), \( e.i. = \checkmark \), and \( e.o. = \checkmark \). For the inverse also to be surjective:

• \( u.i._{R^{-1}} = u.o._R \) must be \( \checkmark \) → the original must be injective
• \( e.i._{R^{-1}} = e.o._R = \checkmark \) ✓ (already guaranteed)
• \( e.o._{R^{-1}} = e.i._R = \checkmark \) ✓ (already guaranteed)

Preserves the type only if \( u.o. = \checkmark \), which makes it bijective.

---

Summary table: does the inverse preserve the type?

Type of correspondence	Defining properties	Preserved under inversion?
General correspondence	—	Always ✓
One-to-one	\( u.i.,\ u.o. \)	Always ✓
Bijective function	\( u.i.,\ e.i.,\ u.o.,\ e.o. \)	Always ✓
Multi-valued	\( u.i. = \text{✗} \)	Only if \( u.o. = \text{✗} \)
Single-valued	\( u.i. \)	Only if \( u.o. = \checkmark \)
Partial function	\( u.i.,\ e.i. = \text{✗} \)	Only if \( u.o. = \checkmark \wedge e.o. = \text{✗} \)
Function (mapping)	\( u.i.,\ e.i. \)	Only if bijective
Injective function	\( u.i.,\ e.i.,\ u.o. \)	Only if \( e.o. = \checkmark \) (bijective)
Surjective function	\( u.i.,\ e.i.,\ e.o. \)	Only if \( u.o. = \checkmark \) (bijective)

Observation. The only types that always preserve their classification under inversion are those whose definition is symmetric with respect to the image/origin swap: the general correspondence (no properties), the one-to-one (u.i. and u.o. trade places), and the bijective function (all four properties trade places). All others have asymmetric definitions — they require properties on one side that they don’t require on the other — and can therefore lose their type under inversion.

Restricted functions and extensions

In practice, we sometimes need to shrink or expand the domain of a function to achieve properties it lacks on its full domain — for example, restricting it to make it injective and thus invertible, or extending it to a larger set where it was previously undefined.

Restriction

Let \( f: A \rightarrow B \) be a function and \( E \subseteq A \) a subset of its domain. The restriction of \( f \) to \( E \), written \( f|_E \), is the function:

\[ f|_E : E \rightarrow B \qquad \text{defined by} \qquad f|_E(x) = f(x) \quad \forall x \in E \]

In plain terms: The restriction is the same function, but “trimmed” to a smaller domain. The rule of correspondence does not change; only the set of elements it is applied to changes.

Example 1. Let \( f: \{-2, -1, 0, 1, 2\} \rightarrow \{0, 1, 4\} \) be defined by \( f(x) = x^2 \), and \( E = \{0, 1, 2\} \subseteq A \).

The restriction \( g = f|_E : \{0, 1, 2\} \rightarrow \{0, 1, 4\} \) with \( g(x) = x^2 \) has the same rule, but operates only over \( E \).

Notice that:

• \( f \) is not injective (since \( f(-1) = f(1) = 1 \) and \( f(-2) = f(2) = 4 \))
• \( g = f|_E \) is injective (over \( \{0, 1, 2\} \), no two elements share the same image)

Example 2. Let \( h: [-2, 2] \rightarrow [0, 2] \) be defined by \( h(x) = \sqrt{4 – x^2} \) (the upper semicircle).

The restriction \( g = h|_{[0,2]}: [0, 2] \rightarrow [0, 2] \) takes only the right quarter-circle. While \( h \) is not injective (for example, \( h(-1) = h(1) \)), the restriction \( g \) is.

Note. Restricting functions is essential for obtaining injective functions and inverses. If a function is not injective on its full domain, restricting it to a subset where it is makes inversion possible. This is the principle behind the inverse trigonometric functions (\( \arcsin \), \( \arccos \), \( \arctan \)).

Extension

The reverse operation is the extension: if \( g: E \rightarrow B \) is a function with \( E \subset A \), and there exists a function \( f: A \rightarrow B \) such that \( f(x) = g(x) \) for all \( x \in E \), we say \( f \) is an extension of \( g \) to \( A \).

Intuition. Restricting is “trimming” the domain; extending is “expanding” it. They are inverse operations of each other.

Correspondences in real life

Correspondences are not purely theoretical constructs. They arise naturally across many fields of knowledge and everyday life.

In computing: hash tables

In computer science, a hash table is a data structure that maps a unique key to a block of values. This mapping is a strict single-valued correspondence: each key has exactly one associated value.

When two distinct keys produce the same hash value — a “collision” — we have a violation of uniqueness of origin: the correspondence ceases to be injective. Anticipating and resolving these collisions is one of the core problems of algorithm design.

In transportation: network maps

A subway map establishes a bijection between the geometric nodes printed on the diagram and the physical stations in the city. Each point on the map corresponds to exactly one station, and each station is represented by exactly one point.

In economics: demand functions

The relationship between the price of a good and the quantity a consumer is willing to buy is modeled as a function:

\[ p = f(q) \]

where \( q \) is the quantity and \( p \) the unit price. For example, \( p = 40 – 2q \) with \( 0 \leq q \leq 20 \) defines a decreasing linear demand function: the larger the quantity, the lower the unit price.

In early education: matching

When a teacher shows a set of pencils and a set of notebooks and asks children to draw lines assigning a unique pencil to each notebook, they are intuitively introducing the concept of an injective function. The notebook left without a pencil visually illustrates that the range does not always equal the target set.

In mathematics itself

The simple act of counting objects establishes a bijective correspondence between the objects and the natural numbers \( \{1, 2, 3, \ldots\} \). If you can pair each object with exactly one number and vice versa, you have counted correctly.

Reflection. The mathematical correspondence, stripped of its formal notation, is the universal language of order. Whenever we associate, classify, assign, or pair, we are establishing correspondences — often without realizing it.

Solved exercises

Exercise 1: identifying the components of a correspondence

Problem. Let \( A = \{1, 2, 3, 4, 5\} \), \( B = \{a, b, c, d, e, f\} \), and the correspondence:

\[ R = \{(1, b),\ (2, d),\ (2, e),\ (4, a),\ (5, b)\} \]

Find the domain, the range, and classify the correspondence (single-valued or multi-valued, injective or not).

Solution.

• Domain: \( \text{Dom}(R) = \{1, 2, 4, 5\} \) (elements of \( A \) appearing as first components)
• Range: \( \text{Ran}(R) = \{a, b, d, e\} \) (elements of \( B \) appearing as second components)
• Does e.i. hold? No, because \( 3 \in A \) has no image. ✗
• Does u.i. hold? No, because element \( 2 \) has two images: \( d \) and \( e \). ✗
• Does e.o. hold? No, because \( c, f \in B \) have no origin. ✗
• Does u.o. hold? No, because \( b \) has two origins: \( 1 \) and \( 5 \). ✗

Classification: \( R \) is a multi-valued correspondence (u.i. fails).

---

Exercise 2: determining whether a relation is a function

Problem. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{2, 4, 6, 8, 10\} \). Determine whether each of the following relations is a function from \( A \) to \( B \):

• \( f = \{(1, 2),\ (2, 6),\ (3, 10),\ (4, 4)\} \)
• \( g = \{(1, 2),\ (2, 6),\ (2, 8),\ (3, 10),\ (4, 4)\} \)

Solution.

For \( f \):

• \( \text{Dom}(f) = \{1, 2, 3, 4\} = A \) → e.i. holds ✓
• Each element has exactly one image → u.i. holds ✓

\( f \) is a function from \( A \) to \( B \). ✓

For \( g \):

• The pairs \( (2, 6) \) and \( (2, 8) \) share the same first component, meaning element \( 2 \) has two images: \( 6 \) and \( 8 \).
• u.i. fails. ✗

\( g \) is not a function from \( A \) to \( B \). ✗

---

Exercise 3: classifying a function (injective, surjective, bijective)

Problem. Let \( A = \{1, 2, 5, 7, 8\} \) and \( B = \{2, 3, 4, 5, 6\} \). Classify each function:

• \( f = \{(1, 2),\ (2, 3),\ (5, 4),\ (7, 5),\ (8, 6)\} \)
• \( h = \{(1, 4),\ (2, 2),\ (5, 3),\ (7, 5),\ (8, 3)\} \)

Solution.

For \( f \):

Condition	Verification	Result
e.i.	\( \text{Dom}(f) = \{1,2,5,7,8\} = A \)	✓
u.i.	Each element has a single image	✓
u.o.	Each image comes from a single origin	✓
e.o.	\( \text{Ran}(f) = \{2,3,4,5,6\} = B \)	✓

\( f \) is bijective. ✓

For \( h \):

• \( h(5) = 3 \) and \( h(8) = 3 \), but \( 5 \neq 8 \). u.o. fails. ✗
• \( \text{Ran}(h) = \{2, 3, 4, 5\} \neq B \) (\( 6 \) is missing). e.o. fails. ✗

\( h \) is a function (total mapping), but neither injective nor surjective, and therefore not bijective. ✗

---

Exercise 4: composition of functions

Problem. Let \( f: \mathbb{Q} \rightarrow \mathbb{Q} \) with \( f(x) = 3x + 2 \) and \( g: \mathbb{Q} \rightarrow \mathbb{Q} \) with \( g(x) = 2x + 1 \). Find \( (f \circ g)(x) \), \( (g \circ f)(x) \), and verify whether \( f \circ g = g \circ f \).

Solution.

Finding \( f \circ g \):

\[ (f \circ g)(x) = f\big[g(x)\big] = f(2x + 1) = 3(2x + 1) + 2 = 6x + 5 \]

Finding \( g \circ f \):

\[ (g \circ f)(x) = g\big[f(x)\big] = g(3x + 2) = 2(3x + 2) + 1 = 6x + 5 \]

Observation: In this particular case, \( (f \circ g)(x) = (g \circ f)(x) = 6x + 5 \). The two compositions coincide!

Note. This is exceptional. In general, composition is not commutative. Here they agree because the linear coefficients satisfy a special relation: \( f \circ g = g \circ f \) holds for linear functions \( ax + b \) and \( cx + d \) precisely when \( b(c – 1) = d(a – 1) \) — here \( 2(2 – 1) = 1(3 – 1) \), i.e., \( 2 = 2 \). ✓

---

Exercise 5: finding the inverse function

Problem. Let \( f: \mathbb{Q} \rightarrow \mathbb{Q} \) be defined by \( f(x) = 3x + 2 \). Determine whether \( f \) is invertible. If it is, find \( f^{-1} \) and verify that \( (f \circ f^{-1})(x) = x \).

Solution.

Step 1: Verify bijectivity.

• Injectivity: If \( f(x_1) = f(x_2) \):

\[ 3x_1 + 2 = 3x_2 + 2 \implies x_1 = x_2 \quad ✓ \]

• Surjectivity: Given \( y \in \mathbb{Q} \), solve \( y = 3x + 2 \):

\[ x = \frac{y – 2}{3} \in \mathbb{Q} \quad ✓ \]

\( f \) is bijective → it is invertible.

Step 2: Find the inverse.

From \( y = 3x + 2 \), solve \( x = \frac{y – 2}{3} \). Swapping variables:

\[ f^{-1}(x) = \frac{x – 2}{3} \]

Step 3: Verify.

\[ (f \circ f^{-1})(x) = f\left(\frac{x – 2}{3}\right) = 3 \cdot \frac{x – 2}{3} + 2 = (x – 2) + 2 = x \quad ✓ \]

\[ (f^{-1} \circ f)(x) = f^{-1}(3x + 2) = \frac{(3x + 2) – 2}{3} = x \quad ✓ \]

Both compositions give the identity. \( f^{-1}(x) = \frac{x – 2}{3} \) is the inverse of \( f \). ∎

Summary

This post built the bridge between binary relations and functions. The key concepts:

Concept map

Concept	Core idea
Correspondence	Heterogeneous binary relation \( R \subseteq A \times B \) with an association rule
Domain / Range	The subsets that actually participate in the relation
The 4 conditions	e.i., u.i., e.o., u.o. — independent checks of behavior
Multi-valued	✗ u.i. — at least one origin has multiple images
Single-valued	u.i. — each participating origin has at most one image
One-to-one	u.i. + u.o. — one-to-one, without requiring totality
Partial function	u.i. without e.i. — single-valued but not all elements participate
Function (mapping)	u.i. + e.i. — all elements have exactly one image
Injective	Function + u.o. — distinct origins give distinct images
Surjective	Function + e.o. — every element of \( B \) is an image
Bijective	All 4 conditions — perfect pairing
Composition	Chaining \( R_2 \circ R_1 \) — associative, not commutative; preserves positive conditions
Inverse correspondence	Swap all pairs; always exists as a correspondence
Inverse function	Exists \( \iff \) \( f \) is bijective — “undoes” the transformation
Restriction	Trim the domain to gain properties (e.g., injectivity)

Key takeaways

1. Functions are special correspondences — not all correspondences are functions, but every function is a correspondence satisfying u.i. + e.i.
2. The 4 conditions are independent — you can combine them freely, generating 16 possible types.
3. Composition chains correspondences — but order matters: \( R_2 \circ R_1 \neq R_1 \circ R_2 \) in general.
4. Bijectivity is the key to inversion — only bijective functions have an inverse function.
5. Restricting the domain is a practical tool for “forcing” injectivity when the function does not have it naturally.

What’s coming next

In this post we worked with correspondences and functions in a general setting — the sets \( A \) and \( B \) could be of any nature (numbers, letters, sets, objects).

In the next post we will take a more concrete step and study real-valued functions of a real variable: functions where both the source and target sets are subsets of the real numbers \( \mathbb{R} \).

\[ f: D \subseteq \mathbb{R} \longrightarrow \mathbb{R} \]

There we will explore:

• Natural domain of a real function (for which values of \( x \) does the expression make sense?)
• Graphs in the Cartesian plane — the complete visual representation of a function
• Elementary functions: linear, quadratic, square root, absolute value, piecewise
• Operations on functions: addition, subtraction, product, quotient
• Symmetries: even and odd functions
• Monotonicity: increasing and decreasing functions

Everything we have learned here — the existence and uniqueness conditions, injectivity, surjectivity, composition, and inversion — will be the theoretical foundation on which we build the detailed study of real functions.

See you in the next post!