Functions and Mappings

A function is more than a formula: its input set, output set, and assignment rule determine what claims about it mean. This chapter keeps definitions, injectivity, surjectivity, composition, and inverses together because each answers a question about the same mapping. It builds on Naive Set Theory and prepares the view of a sequence as an indexed function [1][1] T. Button, Set Theory. Open Logic Project, 2026. Fall 2021 course text, revised July 2026. https://builds.openlogicproject.org/courses/set-theory/settheory-screen.pdf.

Specify the domain, codomain, and rule

DefinitionFunction

A function $f:A\to B$ assigns to every $a\in A$ exactly one element $f(a)\in B$. Its domain is $A$ and its codomain is $B$. Its image, or range, is $f[A]=\{f(a):a\in A\}$, a subset of $B$.

For $f:\mathbb Z\to\mathbb Z$ with $f(n)=n^2$, the codomain is all integers but the image is $\{0,1,4,9,\ldots\}$. We regard functions as typed mappings: equality requires the same domain, codomain, and outputs. Thus the same formula with a different declared codomain can have different mapping properties.

There is one function from $\varnothing$ to any set $B$, the empty function. There is no function from a nonempty $A$ to $\varnothing$. These cases follow from the definition; it is unnecessary to ban empty sets from the definition of function.

The graph of $f$ is the set of ordered pairs $(a,f(a))$. As a subset of $A\times B$, it must associate exactly one output with every input. A relation may associate several outputs or none, so not every relation is a function. Detailed relation theory belongs to Relations and Order.

A formula must actually define a function

The rule $x\mapsto1/x$ does not define a total function $\mathbb R\to\mathbb R$, but does define one on $\mathbb R\setminus\{0\}$. On the same declared domain and codomain, $1/x$ and $x^{-1}$ give exactly the same rule. The notation $f^{-1}$ for an inverse function, discussed below, is a separate use of the superscript.

A rule must also be independent of how an input is represented. For example, “send the rational number $a/b$ to its numerator $a$” is not well-defined, since $1/2=2/4$ would produce different outputs for the same rational number. To define a function on equivalence classes or other represented objects, check all allowed representations.

Images and preimages of sets

For $S\subseteq A$ and $T\subseteq B$, define

$$f[S]=\{f(x):x\in S\},$$ $$f^{-1}[T]=\{x\in A:f(x)\in T\}.$$

The first moves a subset forward; the second collects inputs whose outputs lie in a specified subset. The preimage notation is defined for every function and does not require an inverse function.

For $f:\mathbb R\to\mathbb R$, $f(x)=x^2$, the image of $\{-1,0,2\}$ is $\{0,1,4\}$, while the preimage of $\{1,4\}$ is $\{-2,-1,1,2\}$. Multiple inputs may contribute the same image element, which is listed only once.

PropositionImages preserve unions

For $C,D\subseteq A$,

$$f[C\cup D]=f[C]\cup f[D].$$

Proof

If $y\in f[C\cup D]$, choose $x\in C\cup D$ with $f(x)=y$. The input lies in at least one of $C,D$, so $y\in f[C]\cup f[D]$. Conversely, if $y$ belongs to either image, a witnessing input belongs to $C\cup D$, giving membership in its image. This proves both inclusions.

There is therefore no counterexample to equality here. Intersections behave differently:

$$f[C\cap D]\subseteq f[C]\cap f[D].$$

For the square function with $C=\{-1\}$ and $D=\{1\}$, the left side is empty but the right side is $\{1\}$. The two separate image memberships may be witnessed by different inputs.

Preimages preserve both unions and intersections, as well as complements relative to the declared sets:

$$f^{-1}[B\setminus T]=A\setminus f^{-1}[T].$$

For example, membership in the left side means that $x\in A$ and $f(x)\notin T$, exactly the condition on the right. A preimage test always concerns the same input $x$, explaining why no injectivity assumption is needed.

Injective, surjective, and bijective

Property	Meaning	How to prove it
Injective	Equal outputs force equal inputs	Assume $f(x)=f(y)$ and derive $x=y$
Surjective onto $B$	Every element of the codomain is reached	Take arbitrary $b\in B$ and construct $a\in A$ with $f(a)=b$
Bijective	Both of the above	Establish both obligations

To disprove injectivity, find distinct inputs with the same output. To disprove surjectivity, find a codomain element with no preimage. Having an output for every input is already required of a function; it is not the definition of surjectivity.

ExampleThe codomain changes surjectivity

The function $x\mapsto x^2$ from $\mathbb R$ to $\mathbb R$ is neither injective nor surjective: $-1,1$ collide and $-1$ is not reached. From $\mathbb R$ to $[0,\infty)$, it is surjective but still not injective. Restricting both the domain and codomain to $[0,\infty)$ makes it bijective.

ProofA bijection with explicit witnesses

Let $f:\mathbb R\to\mathbb R$ be $f(x)=3x-2$. If $f(x)=f(y)$, then $3x-2=3y-2$, so $x=y$ and $f$ is injective. Given arbitrary $b\in\mathbb R$, choose $a=(b+2)/3$. It is real and satisfies $f(a)=b$, proving surjectivity. Therefore $f$ is bijective.

For finite domain and codomain of the same size, injectivity and surjectivity are equivalent: selecting distinct outputs uses all available outputs. That statement does not extend unchanged to infinite sets. The map $n\mapsto n+1$ from $\mathbb N$ to itself is injective but misses $0$.

Use mappings to compare cardinalities

The one-to-one pairing in Naive Set Theory is now precisely a bijection $f:A\to B$. It certifies $|A|=|B|$. An injection $A\to B$ places distinct elements of $A$ at distinct locations in $B$; this is the meaning of $|A|\le|B|$ for general sets.

If $B$ is countable and there is an injection $A\to B$, then $A$ is countable. For a finite $B$, there are only finitely many available locations. For a countably infinite $B$, scan an enumeration of $B$ and retain the locations used by the injection. Each element of $A$ is recovered at most once, and none is missed.

A related statement is useful for sequences: a nonempty set $A$ is countable exactly when some surjection $\mathbb N\to A$ exists. A finite nonempty list can be prolonged by repeating one element. Conversely, from a surjective list, keep each value only at its first occurrence; the resulting list is finite or countably infinite and includes every element. The empty set is countable too, but no function $\mathbb N\to\varnothing$ exists.

These are statements about the existence of mappings. The instruction to retain first occurrences explains a mathematical listing; without computable data and equality tests, it does not promise an executable enumeration algorithm.

Composition and what can be inferred from it

If $f:A\to B$ and $g:B\to C$, then $g\circ f:A\to C$ is defined by $(g\circ f)(a)=g(f(a))$. The function on the right acts first. Composition is associative but generally not commutative. Identity functions satisfy $\operatorname{id}_B\circ f=f=f\circ\operatorname{id}_A$.

For $f(x)=x+1$ and $g(x)=2x$ on $\mathbb R$, we get $(g\circ f)(x)=2x+2$ and $(f\circ g)(x)=2x+1$. Pointwise multiplication instead gives $(fg)(x)=2x(x+1)$. The operations answer different questions even when both functions share a numerical domain.

ProofComposing injective or surjective functions

If $f,g$ are injective and $g(f(x))=g(f(y))$, injectivity of $g$ gives $f(x)=f(y)$, then that of $f$ gives $x=y$.

If $f,g$ are surjective, take arbitrary $c\in C$. Choose $b\in B$ with $g(b)=c$, then $a\in A$ with $f(a)=b$. Thus $(g\circ f)(a)=c$. Therefore a composition of bijections is a bijection.

Some converse conclusions are weaker: if $g\circ f$ is injective, $f$ must be injective; if $g\circ f$ is surjective, $g$ must be surjective. One cannot conclude that both component functions are bijective merely because the composition is. An exercise below provides a counterexample.

Inverse functions and inverse images

A two-sided inverse of $f:A\to B$ is a function $h:B\to A$ satisfying

$$h\circ f=\operatorname{id}_A, \qquad f\circ h=\operatorname{id}_B.$$

Such an inverse exists exactly when $f$ is bijective. If $f$ is bijective, every $b\in B$ has exactly one preimage; assigning that preimage defines $h$. Conversely, the first identity makes $f$ injective, and the second makes it surjective. The inverse is unique and is denoted $f^{-1}$.

For $f(x)=3x-2$, the inverse is $f^{-1}(b)=(b+2)/3$, not $1/(3b-2)$. An injective $f:A\to B$ always has an inverse after regarding it as a bijection $A\to f[A]$; that does not make it invertible on all of $B$ when some outputs are missed.

The expression $f^{-1}[T]$ still denotes a preimage set even when no inverse function exists. When $f$ is bijective, it agrees with the image of $T$ under the inverse function. Keeping the brackets and domains explicit prevents the two meanings from being confused.

Restrictions and partial functions

For $D\subseteq A$, the restriction $f|_D:D\to B$ keeps the same outputs on a smaller domain. It is a total function on its own declared domain $D$. A partial function $p:A\rightharpoonup B$ instead has an actual domain $D\subseteq A$ while retaining $A$ as the ambient input set; some ambient inputs may have no output.

The reciprocal rule is partial on ambient input set $\mathbb R$, but total as a map $\mathbb R\setminus\{0\}\to\mathbb R$. To encode missing outputs, introduce a fresh symbol $\bot\notin B$ and define a total map $p^*:A\to B\cup\{\bot\}$ which agrees with $p$ on $D$ and returns $\bot$ elsewhere. This changes the codomain explicitly; it does not prove that the original rule had an output at every input.

Exercises

ExerciseCheck the type of an input

For a mapping with domain $\{0,1\}\times\mathcal P(\mathbb Z)$ and codomain $\mathbb N$, explain why $(1,\{-3,6\})$ is a valid input and $9$ a valid output value, while $(8,-7)$ is not a valid input.

Show solution

Solution

The first component must lie in $\{0,1\}$, and the second must be a subset of $\mathbb Z$. The first pair meets both requirements. The second has an invalid first component and an integer rather than an integer subset as its second component. Knowing that $9$ is in the codomain does not determine which input, if any, maps to it.

ExerciseRepair the domain or the rule

Do $x\mapsto\sqrt x$ and the relation $y^2=x$ define functions $\mathbb R\to\mathbb R$? Give a precise function obtained by making appropriate restrictions.

Show solution

Solution

The real square-root rule is undefined for negative inputs. The relation $y^2=x$ also allows two outputs for positive $x$. Requiring $x\ge0$ and choosing the nonnegative root gives the function $[0,\infty)\to[0,\infty)$, $x\mapsto\sqrt x$. Its existence and uniqueness are properties of the real numbers, not consequences of merely writing the relation.

ExerciseA surjection from integer pairs

For $f:\mathbb Z^2\to\mathbb Z$, $f(m,n)=2m-n$, determine whether $f$ is injective and whether it is surjective.

Show solution

Solution

It is surjective: for arbitrary $z\in\mathbb Z$, take $(m,n)=(0,-z)$. It is not injective, since $(0,0)$ and $(1,2)$ both map to $0$. Every claimed witness belongs to the declared product domain.

ExerciseA bijective composition need not have bijective factors

Take $A=C=\{0\}$ and $B=\{0,1\}$. Let $f:A\to B$ send $0$ to $0$, and let $g:B\to C$ send both inputs to $0$. Check $g\circ f$, $f$, and $g$.

Show solution

Solution

The composition is the identity on the singleton and hence bijective. But $f$ misses $1$ and is not surjective; $g$ identifies two distinct inputs and is not injective. This refutes the claim that a bijective composition forces both factors to be bijections.

ExerciseWhen do images preserve intersections?

Prove that an injective $f$ satisfies $f[C\cap D]=f[C]\cap f[D]$. Identify where injectivity is used.

Show solution

Solution

The forward inclusion holds for every function. For the reverse, take $y=f(c)=f(d)$ with $c\in C$ and $d\in D$. Injectivity gives $c=d$, so this common input lies in $C\cap D$ and witnesses membership on the left. The square-function counterexample in the text shows why the equality can fail without injectivity.

ExerciseCompute an inverse and a preimage

For $f:[0,\infty)\to[0,\infty)$, $f(x)=x^2$, find its inverse and compute $f^{-1}[T]$ for $T=[1,4]$. Repeat the preimage computation when the domain is all of $\mathbb R$.

Show solution

Solution

On the nonnegative domain, the inverse is $y\mapsto\sqrt y$ and the preimage of $[1,4]$ is $[1,2]$. On all reals, the preimage becomes $[-2,-1]\cup[1,2]$, even though the function is no longer injective and has no two-sided inverse. This distinguishes a preimage operation from an inverse function.

Continue with Sequences and Series. For detailed properties of elementary real functions, see the calculus collection; their long catalogue is not needed to establish the mapping concepts here.

References

1. [1] T. Button, Set Theory. Open Logic Project, 2026. Fall 2021 course text, revised July 2026. https://builds.openlogicproject.org/courses/set-theory/settheory-screen.pdf ↩