Function

Intuition [Beginner]

A function is a dependable rule. Give it an allowed input, and it gives back one output.

Think of a vending machine with labeled buttons. Press button 2, and the machine gives the snack assigned to button 2. A good function does not hesitate between two snacks for the same button.

Functions matter because mathematics constantly compares things by sending one kind of object to another: a number to its square, a point to its height, a vector to its length, or a symmetry move to where it sends a corner.

Visual [Beginner]

Each input has exactly one outgoing arrow. Different inputs may land on the same output.

The rule may miss some outputs. It may also send several inputs to the same output.

Worked example [Beginner]

Use the rule "double the number and add 1."

Input 0 gives output 1.

Input 3 gives output 7.

Input 10 gives output 21.

The same input always gives the same output. That is the important point. The rule is not "maybe 7, maybe 8" when the input is 3.

What this tells us: a function is a controlled assignment from inputs to outputs.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $A$ and $B$ be sets. A function $f:A\to B$ assigns to every element $a\in A$ a unique element $f(a)\in B$. The set $A$ is the domain, and $B$ is the codomain. The image of $f$ is

$$\mathrm{im}(f)=\{b\in B\mid b=f(a)\text{ for some }a\in A\}.$$

Equivalently, a function $A\to B$ is a subset ${\Gamma }_f\subseteq A\times B$ such that each $a\in A$ occurs in exactly one pair $(a,b)\in {\Gamma }_f$ ^{[Halmos §8]}. This subset is the graph of $f$.

The function is injective if $f(a)=f(a^{\prime })$ implies $a=a^{\prime }$. It is surjective if $\mathrm{im}(f)=B$. It is bijective if it is both injective and surjective.

Key theorem with proof [Intermediate+]

Theorem (inverse criterion). A function $f:A\to B$ is bijective if and only if there exists a function $g:B\to A$ such that

$$g\circ f={\mathrm{id}}_A,f\circ g={\mathrm{id}}_B.$$

Proof. Assume first that $f$ is bijective. For each $b\in B$, surjectivity gives at least one $a\in A$ with $f(a)=b$. Injectivity makes that $a$ unique. Define $g(b)$ to be this unique element. Then $g(f(a))=a$ for every $a\in A$, and $f(g(b))=b$ for every $b\in B$.

Conversely, assume such a function $g$ exists. If $f(a)=f(a^{\prime })$, then applying $g$ gives

$$a=g(f(a))=g(f(a^{\prime }))=a^{\prime },$$

so $f$ is injective. For any $b\in B$, the identity $f(g(b))=b$ shows that $b$ lies in the image of $f$, so $f$ is surjective. Thus $f$ is bijective. $\square$

Bridge. The construction here builds toward 01.01.03 (vector space), where the same data is upgraded, and the symmetry side is taken up in 01.02.01 (group). The defining pattern appears again in those units in a sharpened form, where the local data is glued or quotiented. Putting these together, the foundational insight is that the data of this unit gives the structural signature that the rest of the strand reads off.

Exercises [Intermediate+]

Lean formalization [Intermediate+]

[object Promise]

Advanced results [Master]

The category Set has sets as objects and functions as morphisms. Composition is ordinary composition, and the identity morphism on $A$ is ${\mathrm{id}}_A$. The associativity and identity laws are equations of functions, checked by evaluating both sides at an element ^{[Bourbaki Ch. II]}.

A function $f:A\to B$ is a monomorphism in Set precisely when it is injective, and an epimorphism precisely when it is surjective. For monomorphisms, the proof is cancellation against maps from a one-point test set. For epimorphisms, cancellation against all maps $B\to C$ forces every point of $B$ to lie in the image of $f$.

The graph description embeds functions into relations. In that language, functions are exactly the total single-valued relations. This viewpoint is used in set-theoretic foundations, while algebra and geometry usually use the arrow notation $A\to B$.

Synthesis. This construction generalises the linear baseline of earlier strands, with the rigid pairing replaced by its structured analogue. Read in the opposite direction, the construction is dual to the metric story: complements and orthogonality are taken with respect to the bilinear datum of this unit, not a metric, and the resulting category of subobjects is the one the rest of the strand classifies. The central insight is that this datum identifies algebra with geometry: functions become vector fields, subspaces become quotients, and invariants become cohomology classes — and that identification is the engine driving every theorem downstream.

Full proof set [Master]

Proposition. In Set, monomorphisms are injective functions.

If $f:A\to B$ is injective and $u,v:X\to A$ satisfy $f\circ u=f\circ v$, then $f(u(x))=f(v(x))$ for each $x\in X$, so $u(x)=v(x)$ and hence $u=v$.

Conversely, assume $f$ is a monomorphism. If $f(a)=f(a^{\prime })$, let $1=\{\ast \}$ and define $u(\ast )=a$, $v(\ast )=a^{\prime }$. Then $f\circ u=f\circ v$, so $u=v$, hence $a=a^{\prime }$. Thus $f$ is injective.

Proposition. In Set, epimorphisms are surjective functions.

If $f$ is surjective and $h,k:B\to C$ satisfy $h\circ f=k\circ f$, then for every $b\in B$ choose $a\in A$ with $f(a)=b$. The equality gives $h(b)=k(b)$, so $h=k$.

Conversely, if $f$ is not surjective, choose an element $b_0\in B$ not in its image. Let $C=\{0,1\}$. Define $h:B\to C$ by $h(b)=0$ for all $b$, and define $k:B\to C$ by $k(b_0)=1$ and $k(b)=0$ for $b\ne b_0$. Then $h\ne k$ but $h\circ f=k\circ f$, so $f$ is not an epimorphism.

Connections [Master]

• Functions are the input language for vector spaces 01.01.03, where addition and scalar multiplication are functions satisfying axioms.

• Groups 01.02.01 are sets with multiplication, identity, and inverse functions satisfying algebraic identities.

• Group actions 03.03.02 are functions $G\times X\to X$ encoding how symmetries move points.

• Continuous maps 02.01.02 are functions that preserve topological closeness.

Historical & philosophical context [Master]

Dedekind, Frege, Peano, and Cantor helped shift nineteenth-century mathematics toward mappings and sets as primitive organizing language. Bourbaki later standardized the terminology of mappings, products, graphs, injections, surjections, and bijections in a set-theoretic framework ^{[Bourbaki Ch. II]}.

Halmos's Naive Set Theory presents functions as set-theoretic graphs with the single-valued condition, a formulation that remains compatible with modern model-theoretic and category-theoretic treatments ^{[Halmos §8]}.

Bibliography [Master]

[object Promise]