4.1 Functions, Composition, and Inverses

Chapter 3 taught us to read definitions literally and to prove that every required condition holds. We now apply that habit to a structure you have already met informally: an input goes into a process and an output comes out.

A calculator button, a program that converts a username to an account ID, and a rule that assigns each student a graduation year all behave like functions. The word “function,” however, has a precise meaning. We will build it from the sets and ordered pairs introduced in Chapter 1.

From ordered pairs to functions

Let $A$ and $B$ be sets. Recall that the Cartesian product

A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}

contains every ordered pair whose first entry comes from $A$ and whose second entry comes from $B$ .

A relation from $A$ to $B$ is any subset of $A\times B$ . A function from $A$ to $B$ is a special relation that satisfies two rules:

1. every element of $A$ appears as the first entry of an ordered pair;

2. each element of $A$ is paired with exactly one element of $B$ .

We write

f:A\to B

and read it as “ $f$ is a function from $A$ to $B$ .” The set $A$ is the domain and the set $B$ is the codomain. If $(a,b)$ belongs to the function, we usually write

f(a)=b.

The values that actually occur as outputs form the range:

\operatorname{range}(f)=\{f(a)\mid a\in A\}.

The range is always a subset of the codomain, but it need not equal the codomain.

A finite example

Let

A=\{1,2,3\},\qquad B=\{p,q,r,s\},

and define

f=\{(1,q),(2,q),(3,s)\}.

Every member of $A$ has one output, so $f$ is a function. Its domain is $A$ , its codomain is $B$ , and

\operatorname{range}(f)=\{q,s\}.

The unused codomain values $p$ and $r$ remain part of $B$ even though they are not in the range.

Now compare two broken relations:

R_1=\{(1,p),(2,q)\}

is not a function from $A$ to $B$ because input $3$ has no output, while

R_2=\{(1,p),(1,q),(2,r),(3,s)\}

is not a function because input $1$ has two outputs. Several inputs may share one output; one input may not split into several outputs.

Injective, surjective, and bijective functions

After checking that a mapping is a function, we can ask how its outputs cover the codomain.

A function $f:A\to B$ is injective (one-to-one) when different inputs always have different outputs:

\forall x_1,x_2\in A,\quad f(x_1)=f(x_2)\Rightarrow x_1=x_2.

The contrapositive form is often easier to visualize:

x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2).

An arrow diagram for an injective function never sends two domain elements into the same codomain element.

A function is surjective (onto) when every codomain element is reached:

\forall y\in B,\quad \exists x\in A\text{ such that }f(x)=y.

Equivalently,

\operatorname{range}(f)=B.

A function is bijective when it is both injective and surjective. Every codomain element then receives exactly one arrow.

For a finite function, use this audit:

Question	If yes
Does every domain element have exactly one outgoing arrow?	it is a function
Do distinct domain elements avoid sharing an output?	it is injective
Does every codomain element receive an arrow?	it is surjective
Are both of the previous two property checks true?	it is bijective

Be careful: injective and surjective depend on the stated domain and codomain. The rule $f(x)=x^2$ is not injective as a function $\mathbb Z\to\mathbb Z$ because $f(2)=f(-2)$ . Restricting the domain to the nonnegative integers removes that collision.

Loading interactive lab...

Route packages through a mapping conveyor. You may redirect outputs, leave an input disconnected, or create a split. Live inspectors separate the basic function rule from injectivity, surjectivity, and bijectivity, so changing one arrow reveals exactly which definition changes.

Loading concept check...

Loading practice...

Composition connects two functions

Suppose

f:A\to B \qquad\text{and}\qquad g:B\to C.

Because the output of $f$ belongs to $B$ , it can become an input to $g$ . Their composition is the function

g\circ f:A\to C

defined by

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

The rightmost function acts first. This order is not a typographical choice: an input must pass through $f$ before the result can enter $g$ .

Following one value through a pipeline

Let

f(x)=2x+1,\qquad g(y)=y^2.

For $x=3$ ,

3\xrightarrow{f}7\xrightarrow{g}49,

(g\circ f)(3)=g(f(3))=g(7)=49.

As formulas,

(g\circ f)(x)=g(2x+1)=(2x+1)^2.

Reversing the machines produces a different function:

(f\circ g)(x)=f(x^2)=2x^2+1.

For example,

(g\circ f)(1)=9 \qquad\text{but}\qquad (f\circ g)(1)=3.

Therefore composition is generally not commutative:

g\circ f\ne f\circ g.

It may even be impossible to reverse the order when the output set of $g$ does not fit the input set of $f$ .

Identity and inverse functions

The identity function on a set $A$ returns each element unchanged:

\operatorname{id}_A:A\to A,\qquad \operatorname{id}_A(x)=x.

It acts like a do-nothing machine:

f\circ\operatorname{id}_A=f \qquad\text{and}\qquad \operatorname{id}_B\circ f=f

for every $f:A\to B$ .

An inverse function reverses a function. If $f:A\to B$ has an inverse, it is written

f^{-1}:B\to A

and must satisfy both

f^{-1}\circ f=\operatorname{id}_A \qquad\text{and}\qquad f\circ f^{-1}=\operatorname{id}_B.

Thus, for every $x\in A$ and $y\in B$ ,

f^{-1}(f(x))=x, \qquad f(f^{-1}(y))=y.

The notation $f^{-1}(x)$ does not mean the reciprocal $1/f(x)$ . The superscript $-1$ says “undo the mapping.”

Why bijections are exactly the invertible functions

If $f$ is not injective, two inputs collide at one output. A reverse machine receiving that output cannot know which original input to return.

If $f$ is not surjective, some $y\in B$ was never produced. A reverse function with domain $B$ would have no valid original input to assign to that $y$ .

A bijection has neither problem: each $y\in B$ corresponds to exactly one $x\in A$ . Therefore:

f\text{ has an inverse function} \quad\Longleftrightarrow\quad f\text{ is bijective}.

For example, define $f:\mathbb R\to\mathbb R$ by

f(x)=3x-2.

To find the inverse, set $y=3x-2$ and solve for $x$ :

x=\frac{y+2}{3}.

Replacing the temporary input letter $y$ by $x$ gives

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

Check both directions:

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

and

f(f^{-1}(x)) =3\left(\frac{x+2}{3}\right)-2 =x.

Loading interactive lab...

Send a token through two animated machines, swap their order, and then attempt a reverse journey. The lab makes intermediate values visible and deliberately introduces collisions or unreachable outputs so you can diagnose why an inverse fails.

Loading concept check...

Loading practice...

Note

Before composing functions, check that the first output belongs to the second function’s domain. Before claiming an inverse, check both injectivity and surjectivity relative to the stated sets.

Section bridge

A function is a relation with a strict “exactly one output per input” rule. The next section removes that restriction and studies general binary relations. Instead of asking only whether arrows define a function, we will inspect patterns such as loops, paired arrows, and multi-step paths.

4.1 Functions, Composition, and Inverses

From ordered pairs to functions

Let $A$ and $B$ be sets. Recall that the Cartesian product

A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}

contains every ordered pair whose first entry comes from $A$ and whose second entry comes from $B$ .

A relation from $A$ to $B$ is any subset of $A\times B$ . A function from $A$ to $B$ is a special relation that satisfies two rules:

1. every element of $A$ appears as the first entry of an ordered pair;

2. each element of $A$ is paired with exactly one element of $B$ .

We write

f:A\to B

and read it as “ $f$ is a function from $A$ to $B$ .” The set $A$ is the domain and the set $B$ is the codomain. If $(a,b)$ belongs to the function, we usually write

f(a)=b.

The values that actually occur as outputs form the range:

\operatorname{range}(f)=\{f(a)\mid a\in A\}.

The range is always a subset of the codomain, but it need not equal the codomain.

A finite example

Let

A=\{1,2,3\},\qquad B=\{p,q,r,s\},

and define

f=\{(1,q),(2,q),(3,s)\}.

Every member of $A$ has one output, so $f$ is a function. Its domain is $A$ , its codomain is $B$ , and

\operatorname{range}(f)=\{q,s\}.

The unused codomain values $p$ and $r$ remain part of $B$ even though they are not in the range.

Now compare two broken relations:

R_1=\{(1,p),(2,q)\}

is not a function from $A$ to $B$ because input $3$ has no output, while

R_2=\{(1,p),(1,q),(2,r),(3,s)\}

is not a function because input $1$ has two outputs. Several inputs may share one output; one input may not split into several outputs.

Injective, surjective, and bijective functions

After checking that a mapping is a function, we can ask how its outputs cover the codomain.

A function $f:A\to B$ is injective (one-to-one) when different inputs always have different outputs:

\forall x_1,x_2\in A,\quad f(x_1)=f(x_2)\Rightarrow x_1=x_2.

The contrapositive form is often easier to visualize:

x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2).

An arrow diagram for an injective function never sends two domain elements into the same codomain element.

A function is surjective (onto) when every codomain element is reached:

\forall y\in B,\quad \exists x\in A\text{ such that }f(x)=y.

Equivalently,

\operatorname{range}(f)=B.

A function is bijective when it is both injective and surjective. Every codomain element then receives exactly one arrow.

For a finite function, use this audit:

Question	If yes
Does every domain element have exactly one outgoing arrow?	it is a function
Do distinct domain elements avoid sharing an output?	it is injective
Does every codomain element receive an arrow?	it is surjective
Are both of the previous two property checks true?	it is bijective

Loading interactive lab...

Loading concept check...

Loading practice...

Composition connects two functions

Suppose

f:A\to B \qquad\text{and}\qquad g:B\to C.

Because the output of $f$ belongs to $B$ , it can become an input to $g$ . Their composition is the function

g\circ f:A\to C

defined by

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

The rightmost function acts first. This order is not a typographical choice: an input must pass through $f$ before the result can enter $g$ .

Following one value through a pipeline

Let

f(x)=2x+1,\qquad g(y)=y^2.

For $x=3$ ,

3\xrightarrow{f}7\xrightarrow{g}49,

(g\circ f)(3)=g(f(3))=g(7)=49.

As formulas,

(g\circ f)(x)=g(2x+1)=(2x+1)^2.

Reversing the machines produces a different function:

(f\circ g)(x)=f(x^2)=2x^2+1.

For example,

(g\circ f)(1)=9 \qquad\text{but}\qquad (f\circ g)(1)=3.

Therefore composition is generally not commutative:

g\circ f\ne f\circ g.

It may even be impossible to reverse the order when the output set of $g$ does not fit the input set of $f$ .

Identity and inverse functions

The identity function on a set $A$ returns each element unchanged:

\operatorname{id}_A:A\to A,\qquad \operatorname{id}_A(x)=x.

It acts like a do-nothing machine:

f\circ\operatorname{id}_A=f \qquad\text{and}\qquad \operatorname{id}_B\circ f=f

for every $f:A\to B$ .

An inverse function reverses a function. If $f:A\to B$ has an inverse, it is written

f^{-1}:B\to A

and must satisfy both

f^{-1}\circ f=\operatorname{id}_A \qquad\text{and}\qquad f\circ f^{-1}=\operatorname{id}_B.

Thus, for every $x\in A$ and $y\in B$ ,

f^{-1}(f(x))=x, \qquad f(f^{-1}(y))=y.

The notation $f^{-1}(x)$ does not mean the reciprocal $1/f(x)$ . The superscript $-1$ says “undo the mapping.”

Why bijections are exactly the invertible functions

If $f$ is not injective, two inputs collide at one output. A reverse machine receiving that output cannot know which original input to return.

If $f$ is not surjective, some $y\in B$ was never produced. A reverse function with domain $B$ would have no valid original input to assign to that $y$ .

A bijection has neither problem: each $y\in B$ corresponds to exactly one $x\in A$ . Therefore:

f\text{ has an inverse function} \quad\Longleftrightarrow\quad f\text{ is bijective}.

For example, define $f:\mathbb R\to\mathbb R$ by

f(x)=3x-2.

To find the inverse, set $y=3x-2$ and solve for $x$ :

x=\frac{y+2}{3}.

Replacing the temporary input letter $y$ by $x$ gives

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

Check both directions:

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

and

f(f^{-1}(x)) =3\left(\frac{x+2}{3}\right)-2 =x.

Loading interactive lab...

Loading concept check...

Loading practice...

Note

Before composing functions, check that the first output belongs to the second function’s domain. Before claiming an inverse, check both injectivity and surjectivity relative to the stated sets.