# Function The function is arguably the most fundamental concept in all of mathematics. Every mathematical structure — group, [topological](/page/Topology) space, measure space — is defined in terms of [sets](/page/Set) and functions. Yet the modern definition, which assigns to each element of a domain exactly one element of a codomain, took centuries to crystallise. Early mathematicians thought of functions as formulas: $y = x^2$, $y = \sin x$, expressions you could write down and compute. It was only through sustained engagement with [Fourier series](/page/Fourier%20Series), pathological constructions, and the foundations of set theory that the mathematical community arrived at the abstract, general definition we use today. This article develops that definition carefully, explores the key properties of injectivity, surjectivity, and bijectivity, and shows how the simple notion of a function ramifies into the structure-preserving maps that animate every branch of mathematics. ## Motivation [motivation] ### From formulas to arbitrary assignments For most of the eighteenth century, a "function" meant a formula — an algebraic expression like $y = x^3 - 7x + 2$ or a trigonometric one like $y = \sin(x)$. Euler's original definition required that a function be given by a single analytic expression. This restriction was natural in an era when calculus was the study of curves, and curves were the graphs of formulas. The decisive break came with Fourier's work on heat conduction in 1807. Fourier claimed that an "arbitrary" function — even one defined piecewise, such as a function that equals $1$ on $[0, 1]$ and $0$ on $(1, 2]$ — could be represented by a trigonometric [series](/page/Series). His contemporaries found this deeply suspect, and the ensuing debate forced mathematicians to confront the question: what, exactly, is a function? Dirichlet's answer, given in 1837, was radical in its generality. A function from a set $X$ to a set $Y$, he proposed, is any rule that assigns to each element of $X$ a single element of $Y$. No formula is required. The assignment can be completely arbitrary — the only constraint is that each input produces exactly one output. This is the definition we formalise below. ### Why domain and codomain matter Consider the formula $f(x) = x^2$. Interpreted as a function $f \colon \mathbb{R} \to \mathbb{R}$, it is neither injective (since $f(-2) = f(2) = 4$) nor surjective (since $-1$ has no preimage). Interpreted as a function $f \colon [0, \infty) \to [0, \infty)$, it is both injective and surjective — a bijection. The formula has not changed, but the function has, because a function is not just a rule; it is a rule together with a specified domain and codomain. As we will see, injectivity, surjectivity, the existence of inverses, and even cardinality arguments all depend critically on the choice of domain and codomain. ### The power of abstraction Once we have the general definition of a function, powerful questions become available. When are two functions "the same"? The answer — when they have the same domain, the same codomain, and the same value at every point — is the principle of extensionality. When does a function have an inverse? Precisely when it is a bijection. And once we can compose functions and take inverses, we can ask which functions preserve mathematical structure. This last question leads to homomorphisms of groups, [continuous](/page/Continuity) maps of topological spaces, and [linear maps](/page/Linear%20Map) of vector spaces — the morphisms that form the backbone of modern mathematics. [/motivation] ## Formal Definition [definition:Function] Let $X$ and $Y$ be sets. A **function** from $X$ to $Y$ is a subset $f \subseteq X \times Y$ satisfying two conditions: 1. **Existence.** For every $x \in X$, there exists a $y \in Y$ such that $(x, y) \in f$. 2. **Uniqueness.** If $(x, y_1) \in f$ and $(x, y_2) \in f$, then $y_1 = y_2$. The set $X$ is the **domain** of $f$, written $\operatorname{dom}(f) = X$. The set $Y$ is the **codomain** of $f$, written $\operatorname{cod}(f) = Y$. We write $f \colon X \to Y$ to indicate that $f$ is a function from $X$ to $Y$, and $f(x) = y$ to mean $(x, y) \in f$. The notation $x \mapsto f(x)$ describes the assignment rule. The **image** (or **range**) of $f$ is the set \begin{align*} \operatorname{im}(f) = \{y \in Y : \text{there exists } x \in X \text{ with } f(x) = y\}. \end{align*} [/definition] The existence condition says that every element of the domain is "accounted for" — the function is defined everywhere on $X$. The uniqueness condition says that every input produces a single, well-defined output. Together, they ensure that the phrase "the value $f(x)$" makes sense for every $x \in X$. It is important to distinguish the codomain from the image. The codomain $Y$ is part of the data of the function — it is declared, not computed. The image $\operatorname{im}(f)$ is the set of values actually attained, and it satisfies $\operatorname{im}(f) \subseteq Y$. The function $f \colon \mathbb{R} \to \mathbb{R}$ defined by $x \mapsto x^2$ has codomain $\mathbb{R}$ but image $[0, \infty)$. A function is surjective precisely when its image equals its codomain. A word on notation: we write $f \colon X \to Y$ for the function itself, and $f(x)$ for the value of $f$ at a particular element $x \in X$. The function is the entire mapping $f$, not the expression $f(x)$. When we write "let $f \colon \mathbb{R} \to \mathbb{R}$ be the function $x \mapsto x^2$," the symbol $f$ names the function and $x \mapsto x^2$ describes its rule of assignment. ## Examples [example:IdentityFunction] **The identity function.** For any set $X$, the **identity function** $\operatorname{id}_X \colon X \to X$ is defined by $\operatorname{id}_X(x) = x$ for all $x \in X$. As a subset of $X \times X$, it is the diagonal $\{(x, x) : x \in X\}$. The identity function is both injective and surjective, hence a bijection. It serves as the neutral element for function composition: $f \circ \operatorname{id}_X = f$ and $\operatorname{id}_Y \circ f = f$ for every function $f \colon X \to Y$. [/example] [example:InclusionMap] **Inclusion maps.** Let $A \subseteq X$ be a subset. The **inclusion map** $\iota \colon A \hookrightarrow X$ is defined by $\iota(a) = a$ for all $a \in A$. This function is always injective: if $\iota(a_1) = \iota(a_2)$, then $a_1 = a_2$. It is surjective if and only if $A = X$. The inclusion map is not the same as the identity function unless $A = X$, because the two functions have different domains (and hence are different subsets of different Cartesian products). [/example] [example:FloorFunction] **The floor function.** Define $\lfloor \cdot \rfloor \colon \mathbb{R} \to \mathbb{Z}$ by $\lfloor x \rfloor = \max\{n \in \mathbb{Z} : n \le x\}$. For instance, $\lfloor 3.7 \rfloor = 3$, $\lfloor -1.2 \rfloor = -2$, and $\lfloor 5 \rfloor = 5$. The floor function is surjective: every integer $n$ is the image of $n$ itself. It is not injective: both $3.1$ and $3.9$ map to $3$. [/example] [example:ProjectionMap] **Projection maps.** Given sets $X$ and $Y$, the **projection maps** $\pi_1 \colon X \times Y \to X$ and $\pi_2 \colon X \times Y \to Y$ are defined by $\pi_1(x, y) = x$ and $\pi_2(x, y) = y$. When both $X$ and $Y$ are non-empty, each projection is surjective. However, neither is injective in general: if $|Y| \ge 2$, then the pairs $(x, y_1)$ and $(x, y_2)$ with $y_1 \ne y_2$ satisfy $\pi_1(x, y_1) = \pi_1(x, y_2) = x$. [/example] ## Injectivity, Surjectivity, and Bijectivity The three most important properties a function can have concern how it relates the elements of its domain to the elements of its codomain. These properties control whether a function can be "reversed," and they play a central role in counting arguments, in the construction of inverse functions, and in the definition of cardinality. [definition:InjectiveFunction] A function $f \colon X \to Y$ is **injective** (or **one-to-one**) if distinct elements of $X$ map to distinct elements of $Y$: \begin{align*} \text{for all } x_1, x_2 \in X, \quad f(x_1) = f(x_2) \implies x_1 = x_2. \end{align*} Equivalently, $f$ is injective if and only if the equation $f(x) = y$ has at most one solution $x \in X$ for every $y \in Y$. [/definition] [definition:SurjectiveFunction] A function $f \colon X \to Y$ is **surjective** (or **onto**) if every element of $Y$ is hit: \begin{align*} \text{for all } y \in Y, \quad \text{there exists } x \in X \text{ such that } f(x) = y. \end{align*} Equivalently, $f$ is surjective if and only if $\operatorname{im}(f) = Y$. [/definition] [definition:BijectiveFunction] A function $f \colon X \to Y$ is **bijective** (or a **bijection**, or a **one-to-one correspondence**) if it is both injective and surjective. Equivalently, $f$ is bijective if and only if for every $y \in Y$, the equation $f(x) = y$ has exactly one solution $x \in X$. [/definition] To test injectivity in practice, one typically assumes $f(x_1) = f(x_2)$ and attempts to deduce $x_1 = x_2$. To test surjectivity, one takes an arbitrary $y \in Y$ and attempts to solve $f(x) = y$ for $x$. Consider the function $f \colon \mathbb{R} \to \mathbb{R}$ defined by $f(x) = 2x + 3$. To check injectivity, suppose $f(x_1) = f(x_2)$, so $2x_1 + 3 = 2x_2 + 3$. Subtracting $3$ and dividing by $2$ gives $x_1 = x_2$, confirming injectivity. To check surjectivity, take any $y \in \mathbb{R}$ and solve $2x + 3 = y$ to get $x = (y - 3)/2 \in \mathbb{R}$, confirming surjectivity. Since $f$ is both injective and surjective, it is a bijection. In contrast, the function $g \colon \mathbb{R} \to \mathbb{R}$ defined by $g(x) = x^2$ fails both conditions. It is not injective because $g(-1) = g(1) = 1$. It is not surjective because $g(x) = x^2 \ge 0$ for all $x \in \mathbb{R}$, so $-1$ has no preimage. However, the restriction $g|_{[0,\infty)} \colon [0, \infty) \to [0, \infty)$ is a bijection — the same formula, but a different function with different properties, because the domain and codomain have changed. ## Composition and Inverses ### Composition [definition:Composition] Let $f \colon X \to Y$ and $g \colon Y \to Z$ be functions. The **composition** of $g$ with $f$ is the function $g \circ f \colon X \to Z$ defined by \begin{align*} (g \circ f)(x) = g(f(x)) \quad \text{for all } x \in X. \end{align*} [/definition] Composition is read right to left: in $g \circ f$, the function $f$ is applied first, and $g$ is applied to the result. This convention, while occasionally confusing, is consistent with the notation $(g \circ f)(x) = g(f(x))$ and is universal in modern mathematics. Composition is associative: if $f \colon X \to Y$, $g \colon Y \to Z$, and $h \colon Z \to W$, then \begin{align*} h \circ (g \circ f) = (h \circ g) \circ f. \end{align*} To verify this, let $x \in X$. Then $(h \circ (g \circ f))(x) = h((g \circ f)(x)) = h(g(f(x)))$, and $((h \circ g) \circ f)(x) = (h \circ g)(f(x)) = h(g(f(x)))$. Both sides equal $h(g(f(x)))$, so the two functions agree at every point, and extensionality gives equality. Composition is not commutative in general. If $f \colon \mathbb{R} \to \mathbb{R}$ is defined by $f(x) = x + 1$ and $g \colon \mathbb{R} \to \mathbb{R}$ by $g(x) = x^2$, then $(g \circ f)(x) = (x+1)^2 = x^2 + 2x + 1$ while $(f \circ g)(x) = x^2 + 1$. These are different functions, since $(g \circ f)(0) = 1$ but $(f \circ g)(0) = 1$ happens to agree at $0$, while $(g \circ f)(1) = 4$ and $(f \circ g)(1) = 2$. Composition interacts well with injectivity and surjectivity: - If $f$ and $g$ are both injective, then $g \circ f$ is injective. Indeed, if $(g \circ f)(x_1) = (g \circ f)(x_2)$, then $g(f(x_1)) = g(f(x_2))$, so injectivity of $g$ gives $f(x_1) = f(x_2)$, and injectivity of $f$ gives $x_1 = x_2$. - If $f$ and $g$ are both surjective, then $g \circ f$ is surjective. Given $z \in Z$, surjectivity of $g$ yields $y \in Y$ with $g(y) = z$, and surjectivity of $f$ yields $x \in X$ with $f(x) = y$. Then $(g \circ f)(x) = g(f(x)) = g(y) = z$. - If $f$ and $g$ are both bijections, then $g \circ f$ is a bijection. This follows from the two points above. This fact is essential in algebra, where it underpins [Theorem 770](/theorems/770) — the composition of group isomorphisms is again an isomorphism. ### Inverse functions [definition:InverseFunction] Let $f \colon X \to Y$ be a bijection. The **inverse function** $f^{-1} \colon Y \to X$ is defined by \begin{align*} f^{-1}(y) = x \quad \text{if and only if} \quad f(x) = y. \end{align*} [/definition] The inverse is well-defined precisely because $f$ is bijective: surjectivity guarantees that for each $y \in Y$ there exists at least one $x$ with $f(x) = y$, and injectivity guarantees that there is at most one such $x$. Together, there is exactly one $x$, so the assignment $y \mapsto x$ defines a function. The inverse satisfies the cancellation properties $f^{-1} \circ f = \operatorname{id}_X$ and $f \circ f^{-1} = \operatorname{id}_Y$. To verify the first, let $x \in X$; then $f^{-1}(f(x)) = x$ because $f(x)$ is the unique element of $Y$ mapping to $x$ under $f^{-1}$. The second identity is verified similarly. The inverse of a bijection is itself a bijection, and $(f^{-1})^{-1} = f$. If $f \colon X \to Y$ and $g \colon Y \to Z$ are both bijections, then $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ — the order reverses, just as when removing two layers of clothing. ### Left and right inverses The full inverse requires bijectivity, but weaker one-sided inverses exist under weaker hypotheses. A function $g \colon Y \to X$ is a **left inverse** (or **retraction**) of $f \colon X \to Y$ if $g \circ f = \operatorname{id}_X$. A function $h \colon Y \to X$ is a **right inverse** (or **section**) of $f$ if $f \circ h = \operatorname{id}_Y$. These one-sided inverses characterise injectivity and surjectivity: - A function $f \colon X \to Y$ (with $X$ non-empty) is injective if and only if $f$ has a left inverse. If $f$ is injective, define $g \colon Y \to X$ by $g(y) = x$ when $y = f(x)$ and $g(y) = x_0$ (a fixed element of $X$) when $y \notin \operatorname{im}(f)$. Then $(g \circ f)(x) = g(f(x)) = x$ for all $x \in X$. Conversely, if $g \circ f = \operatorname{id}_X$ and $f(x_1) = f(x_2)$, then $x_1 = g(f(x_1)) = g(f(x_2)) = x_2$, so $f$ is injective. - A function $f \colon X \to Y$ is surjective if and only if $f$ has a right inverse (assuming the axiom of choice for general sets). If $f$ is surjective, then for each $y \in Y$ the set $f^{-1}(\{y\})$ is non-empty, and we may choose an element $h(y) \in f^{-1}(\{y\})$. Then $f(h(y)) = y$ for all $y$, so $f \circ h = \operatorname{id}_Y$. Conversely, if $f \circ h = \operatorname{id}_Y$, then every $y \in Y$ satisfies $f(h(y)) = y$, so $y \in \operatorname{im}(f)$, confirming surjectivity. When $f$ has both a left inverse $g$ and a right inverse $h$, they must be equal: \begin{align*} g = g \circ \operatorname{id}_Y = g \circ (f \circ h) = (g \circ f) \circ h = \operatorname{id}_X \circ h = h. \end{align*} In this case, $f$ is a bijection and $g = h = f^{-1}$. ## Image and Preimage The image and preimage operations extend a function $f \colon X \to Y$ from acting on elements to acting on subsets. They are the workhorses of set-theoretic arguments throughout analysis, topology, and algebra. [definition:ImageOfASet] Let $f \colon X \to Y$ be a function and let $A \subseteq X$. The **image of $A$ under $f$** is the set \begin{align*} f(A) = \{f(x) : x \in A\} = \{y \in Y : \text{there exists } x \in A \text{ with } f(x) = y\}. \end{align*} [/definition] [definition:PreimageOfASet] Let $f \colon X \to Y$ be a function and let $B \subseteq Y$. The **preimage** (or **inverse image**) of $B$ under $f$ is the set \begin{align*} f^{-1}(B) = \{x \in X : f(x) \in B\}. \end{align*} The notation $f^{-1}(B)$ is used even when $f$ is not bijective. When $f$ is not invertible, the symbol $f^{-1}$ applied to a set denotes the preimage operation, not the application of an inverse function. [/definition] Image and preimage behave differently with respect to set operations, and this asymmetry is one of the most instructive features of elementary set theory. **Preimage preserves all Boolean operations.** For any function $f \colon X \to Y$ and any subsets $B_1, B_2 \subseteq Y$: \begin{align*} f^{-1}(B_1 \cup B_2) &= f^{-1}(B_1) \cup f^{-1}(B_2), \\ f^{-1}(B_1 \cap B_2) &= f^{-1}(B_1) \cap f^{-1}(B_2), \\ f^{-1}(Y \setminus B_1) &= X \setminus f^{-1}(B_1). \end{align*} Each identity follows by direct element-chasing. For the first: $x \in f^{-1}(B_1 \cup B_2)$ if and only if $f(x) \in B_1 \cup B_2$, if and only if $f(x) \in B_1$ or $f(x) \in B_2$, if and only if $x \in f^{-1}(B_1)$ or $x \in f^{-1}(B_2)$, if and only if $x \in f^{-1}(B_1) \cup f^{-1}(B_2)$. The other two identities are verified in the same fashion. **Image preserves unions but not intersections.** For any $A_1, A_2 \subseteq X$: \begin{align*} f(A_1 \cup A_2) &= f(A_1) \cup f(A_2), \\ f(A_1 \cap A_2) &\subseteq f(A_1) \cap f(A_2). \end{align*} The first identity holds because $y \in f(A_1 \cup A_2)$ means $y = f(x)$ for some $x \in A_1 \cup A_2$, which means $x \in A_1$ (so $y \in f(A_1)$) or $x \in A_2$ (so $y \in f(A_2)$). The reverse inclusion follows because $f(A_1) \subseteq f(A_1 \cup A_2)$ and $f(A_2) \subseteq f(A_1 \cup A_2)$. The inclusion $f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)$ can be strict. Take $f \colon \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$, $A_1 = \{-1, 0\}$, and $A_2 = \{0, 1\}$. Then $A_1 \cap A_2 = \{0\}$ and $f(A_1 \cap A_2) = \{0\}$, but $f(A_1) = \{0, 1\}$ and $f(A_2) = \{0, 1\}$, so $f(A_1) \cap f(A_2) = \{0, 1\} \supsetneq \{0\}$. The culprit is the failure of injectivity: the element $1$ in the intersection $f(A_1) \cap f(A_2)$ is produced by $-1 \in A_1$ and by $1 \in A_2$, but no single element of $A_1 \cap A_2$ maps to $1$. This asymmetry — preimage is better behaved than image — is why preimages play the defining role in topology (a continuous function is one for which the preimage of every [open set](/page/Open%20Set) is open) and in measure theory (a measurable function is one for which the preimage of every measurable set is measurable). ## Key Results [theorem:Bijective Iff Invertible] Let $f \colon X \to Y$ be a function with $X$ non-empty. Then $f$ is bijective if and only if there exists a function $g \colon Y \to X$ such that $g \circ f = \operatorname{id}_X$ and $f \circ g = \operatorname{id}_Y$. [/theorem] [proof] **Step 1 (Bijective implies invertible).** Suppose $f$ is bijective. Define $g \colon Y \to X$ by $g(y) = x$, where $x$ is the unique element of $X$ satisfying $f(x) = y$. The element $x$ exists because $f$ is surjective and is unique because $f$ is injective. For any $x \in X$, we have $g(f(x)) = x$ by construction, so $g \circ f = \operatorname{id}_X$. For any $y \in Y$, if $g(y) = x$, then $f(x) = y$ by definition of $g$, so $f(g(y)) = y$, giving $f \circ g = \operatorname{id}_Y$. **Step 2 (Invertible implies bijective).** Suppose $g \colon Y \to X$ satisfies $g \circ f = \operatorname{id}_X$ and $f \circ g = \operatorname{id}_Y$. Then $g$ is a left inverse of $f$, so $f$ is injective (as shown in the discussion of left inverses above: if $f(x_1) = f(x_2)$, then $x_1 = g(f(x_1)) = g(f(x_2)) = x_2$). Also, $g$ is a right inverse of $f$, so $f$ is surjective (for any $y \in Y$, $f(g(y)) = y$, so $y \in \operatorname{im}(f)$). Since $f$ is both injective and surjective, it is bijective. $\blacksquare$ [/proof] This theorem unifies the discussion of inverse functions: a function is bijective if and only if it is invertible, and the inverse is unique (as shown by the left-inverse-equals-right-inverse argument). In algebra, this result combines with [Theorem 770](/theorems/770) to show that the inverse of a group isomorphism is again an isomorphism, and that isomorphism is an equivalence relation on groups. [theorem:Composition Preserves Injectivity And Surjectivity] Let $f \colon X \to Y$ and $g \colon Y \to Z$ be functions. 1. If $g \circ f$ is injective, then $f$ is injective. 2. If $g \circ f$ is surjective, then $g$ is surjective. [/theorem] [proof] **Step 1 (Part 1).** Suppose $g \circ f$ is injective and suppose $f(x_1) = f(x_2)$ for some $x_1, x_2 \in X$. Then $g(f(x_1)) = g(f(x_2))$, i.e., $(g \circ f)(x_1) = (g \circ f)(x_2)$. Since $g \circ f$ is injective, $x_1 = x_2$. Hence $f$ is injective. **Step 2 (Part 2).** Suppose $g \circ f$ is surjective. Let $z \in Z$. Then there exists $x \in X$ with $(g \circ f)(x) = z$, i.e., $g(f(x)) = z$. Setting $y = f(x) \in Y$, we have $g(y) = z$. Since $z$ was arbitrary, $g$ is surjective. $\blacksquare$ [/proof] Part 1 tells us that if a composition is injective, the "first" function applied must be injective — but the second need not be. Part 2 tells us that if a composition is surjective, the "last" function applied must be surjective — but the first need not be. For example, let $X = \{1\}$, $Y = \{a, b\}$, $Z = \{p\}$. Define $f \colon X \to Y$ by $f(1) = a$ and $g \colon Y \to Z$ by $g(a) = g(b) = p$. Then $g \circ f \colon X \to Z$ is the unique function from a one-element set to a one-element set, which is bijective. Here $f$ is injective (as Part 1 guarantees) but not surjective, and $g$ is surjective (as Part 2 guarantees) but not injective. [theorem:Image And Preimage Under Composition] Let $f \colon X \to Y$ and $g \colon Y \to Z$ be functions. Then for any $A \subseteq X$ and $C \subseteq Z$: 1. $(g \circ f)(A) = g(f(A))$. 2. $(g \circ f)^{-1}(C) = f^{-1}(g^{-1}(C))$. [/theorem] [proof] **Step 1 (Part 1).** Let $z \in (g \circ f)(A)$. Then $z = (g \circ f)(x) = g(f(x))$ for some $x \in A$. Since $f(x) \in f(A)$, we have $z = g(f(x)) \in g(f(A))$, so $(g \circ f)(A) \subseteq g(f(A))$. Conversely, let $z \in g(f(A))$. Then $z = g(y)$ for some $y \in f(A)$, so $y = f(x)$ for some $x \in A$. Then $z = g(f(x)) = (g \circ f)(x) \in (g \circ f)(A)$. Hence $g(f(A)) \subseteq (g \circ f)(A)$. **Step 2 (Part 2).** An element $x \in X$ belongs to $(g \circ f)^{-1}(C)$ if and only if $(g \circ f)(x) \in C$, if and only if $g(f(x)) \in C$, if and only if $f(x) \in g^{-1}(C)$, if and only if $x \in f^{-1}(g^{-1}(C))$. Since both sets contain exactly the same elements, they are equal. $\blacksquare$ [/proof] Part 2 is the reason that preimage interacts so cleanly with mathematical structures defined by set-theoretic conditions. If both $f$ and $g$ are continuous, the preimage of an open set under $g \circ f$ is computed by two successive preimage operations, each of which preserves openness. This is the one-line proof that compositions of continuous functions are continuous. ## Functions in Mathematical Structures The raw notion of a function — an arbitrary assignment from one set to another — becomes truly powerful when combined with mathematical structure. The central pattern of modern mathematics is this: given two sets equipped with the same type of structure, the "interesting" functions are those that respect the structure. **Homomorphisms** preserve algebraic structure. If $(G, \cdot)$ and $(H, *)$ are [groups](/page/Group), a function $\varphi \colon G \to H$ is a **group homomorphism** if $\varphi(a \cdot b) = \varphi(a) * \varphi(b)$ for all $a, b \in G$. A bijective homomorphism is an **isomorphism**, and [Theorem 770](/theorems/770) shows that the composition and inversion of isomorphisms are again isomorphisms. This means isomorphism is an [equivalence relation](/page/Equivalence%20Relation) on groups — a fact that allows us to classify groups up to isomorphism. **Linear maps** preserve the structure of vector spaces. A function $T \colon V \to W$ between vector spaces over a field $\mathbb{F}$ is a **linear map** if $T(\alpha v_1 + \beta v_2) = \alpha T(v_1) + \beta T(v_2)$ for all $v_1, v_2 \in V$ and $\alpha, \beta \in \mathbb{F}$. In finite dimensions, [Theorem 386](/theorems/386) reveals a remarkable rigidity: if $\dim V = \dim W$, then a linear map $T \colon V \to W$ is injective if and only if it is surjective if and only if it is an isomorphism. This equivalence fails in infinite dimensions — the right shift operator on $\ell^2(\mathbb{N})$ is injective but not surjective. **Continuous functions** preserve topological structure, in the sense that the preimage of every open set is open. **Measurable functions** preserve measure-theoretic structure, in the sense that the preimage of every measurable set is measurable. In both cases, the defining condition involves preimages rather than images — a reflection of the superior algebraic behaviour of the preimage operation documented above. The pattern extends further: ring homomorphisms preserve both addition and multiplication, smooth maps between manifolds preserve [differentiable](/page/Derivative) structure, and functors between categories are "functions" between mathematical theories themselves. In every case, the starting point is the notion of function developed in this article. ## Cardinality and the Role of Bijections Two sets $A$ and $B$ are said to have the **same cardinality**, written $|A| = |B|$, if there exists a bijection $f \colon A \to B$. This definition, due to Cantor, extends the intuitive notion of "same size" from finite sets to infinite ones. For finite sets, the definition agrees with counting: a set $A$ has $n$ elements precisely when there is a bijection $A \to \{1, 2, \ldots, n\}$. For infinite sets, the definition yields surprises. The function $f \colon \mathbb{N} \to \mathbb{Z}$ defined by \begin{align*} f(n) = \begin{cases} n/2 & \text{if } n \text{ is even}, \\ -(n-1)/2 & \text{if } n \text{ is odd}, \end{cases} \end{align*} giving $f(1) = 0$, $f(2) = 1$, $f(3) = -1$, $f(4) = 2$, $f(5) = -2$, and so on, is a bijection. So $|\mathbb{N}| = |\mathbb{Z}|$: the integers, despite "looking twice as big" as the natural numbers, have the same cardinality. A set is called [countable](/page/Countable%20Set) when it admits an injection into $\mathbb{N}$, and the rationals $\mathbb{Q}$ are countable by an argument that writes $\mathbb{Q}$ as a [countable union of countable sets](/theorems/755). Not all infinite sets are countable. Cantor's diagonal argument ([Theorem 758](/theorems/758)) shows that $\mathbb{R}$ is uncountable: there is no bijection between $\mathbb{N}$ and $\mathbb{R}$. The [Cantor Theorem](/theorems/759) generalises this dramatically: for any set $X$ whatsoever, there is no surjection from $X$ onto its power set $\mathcal{P}(X)$, so $|X| < |\mathcal{P}(X)|$. This shows that there is no largest cardinality — the hierarchy of infinities extends without bound. When mutual injections exist — an injection $f \colon A \to B$ and an injection $g \colon B \to A$ — the [Schroder-Bernstein Theorem](/theorems/760) guarantees the existence of a bijection $h \colon A \to B$. This result, which is non-trivial to prove, allows one to establish equicardinality by constructing two injections rather than a single bijection, which is often much easier in practice. ## Problems [problem] Let $f \colon X \to Y$ and $g \colon Y \to Z$ be functions. Prove that if $g \circ f$ is bijective, then $f$ is injective and $g$ is surjective. Give an example showing that $f$ need not be surjective and $g$ need not be injective. *Difficulty: 1* [/problem] [solution] Since $g \circ f$ is bijective, it is in particular injective, so $f$ is injective by Part 1 of the Composition Preserves Injectivity and Surjectivity theorem. Since $g \circ f$ is surjective, $g$ is surjective by Part 2 of the same theorem. For the counterexample, let $X = \{1\}$, $Y = \{a, b\}$, $Z = \{p\}$. Define $f(1) = a$ and $g(a) = g(b) = p$. Then $(g \circ f)(1) = p$, so $g \circ f$ is a bijection from a one-element set to a one-element set. However, $f$ is not surjective ($b$ has no preimage) and $g$ is not injective ($g(a) = g(b)$ with $a \ne b$). [/solution] [problem] Let $f \colon X \to Y$ be a function. Prove that $f$ is injective if and only if $f(A \cap B) = f(A) \cap f(B)$ for all subsets $A, B \subseteq X$. *Difficulty: 2* [/problem] [solution] **Forward direction.** Suppose $f$ is injective. The inclusion $f(A \cap B) \subseteq f(A) \cap f(B)$ holds for any function. For the reverse, let $y \in f(A) \cap f(B)$. Then $y = f(a)$ for some $a \in A$ and $y = f(b)$ for some $b \in B$. Since $f(a) = y = f(b)$ and $f$ is injective, $a = b$. So $a \in A \cap B$ and $y = f(a) \in f(A \cap B)$. This gives $f(A) \cap f(B) \subseteq f(A \cap B)$. **Reverse direction.** Suppose $f(A \cap B) = f(A) \cap f(B)$ for all $A, B \subseteq X$. Let $x_1, x_2 \in X$ with $f(x_1) = f(x_2)$. Set $A = \{x_1\}$ and $B = \{x_2\}$. Then $f(A) \cap f(B) = \{f(x_1)\} \cap \{f(x_2)\} = \{f(x_1)\} \ne \varnothing$, so $f(A \cap B) \ne \varnothing$ by hypothesis. Since $A \cap B = \{x_1\} \cap \{x_2\}$, this set is non-empty, which forces $x_1 = x_2$. Hence $f$ is injective. [/solution] [problem] Let $f \colon \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = e^x$. Determine explicitly the image $f(A)$ and the preimage $f^{-1}(B)$ for $A = (-\infty, 0]$ and $B = [-1, 4]$. Is $f$ injective? Surjective? Bijective as a function $\mathbb{R} \to (0, \infty)$? *Difficulty: 2* [/problem] [solution] **Image of $A$.** Since the exponential function is strictly increasing and continuous, $f$ maps $(-\infty, 0]$ onto $(0, e^0] = (0, 1]$. The lower bound is not attained because $\lim_{x \to -\infty} e^x = 0$ and $e^x > 0$ for all $x$. Hence $f(A) = (0, 1]$. **Preimage of $B$.** We need all $x \in \mathbb{R}$ with $e^x \in [-1, 4]$. Since $e^x > 0$ for all $x$, the condition $e^x \ge -1$ is automatic. The condition $e^x \le 4$ gives $x \le \ln 4$. So $f^{-1}(B) = (-\infty, \ln 4]$. **Injectivity.** The function $f$ is injective: if $e^{x_1} = e^{x_2}$, taking logarithms gives $x_1 = x_2$. **Surjectivity.** As a function $f \colon \mathbb{R} \to \mathbb{R}$, it is not surjective because $e^x > 0$ for all $x$, so $-1 \notin \operatorname{im}(f)$. **Bijectivity onto $(0, \infty)$.** As a function $f \colon \mathbb{R} \to (0, \infty)$, it is surjective: for any $y > 0$, the equation $e^x = y$ has the solution $x = \ln y$. Since $f$ is also injective, it is a bijection $\mathbb{R} \to (0, \infty)$ with inverse $f^{-1}(y) = \ln y$. [/solution] ## References - P. R. Halmos, *Naive Set Theory*, Springer, 1974. Chapters 8--10. - K. Devlin, *The Joy of Sets: Fundamentals of Contemporary Set Theory*, 2nd ed., Springer, 1993. - T. Tao, *Analysis I*, 3rd ed., Springer, 2016. Chapter 3.