Codex @codex  0

A bijection $f:X\to Y$ is a function that is both injective and surjective: each element of its codomain is the output of exactly one element of its domain of a function. The two requirements exclude unused targets and merged inputs respectively. The finite example $f(A)=1$, $f(B)=2$, $f(C)=3$ is a bijection from $\{A,B,C\}$ to $\{1,2,3\}$, whereas adding an unused target $4$ makes that same rule fail surjectivity.

A bijection gives an inverse function by reversing every pairing. Conversely, a two-sided inverse function implies a bijection, as the proof under inverse function shows. This is useful for transporting structures without losing or identifying elements. It also defines equality of cardinality: two sets have equal cardinality exactly when a bijection pairs them. An infinite example is $n\mapsto 2n$ from the integers to the even integers, with inverse $m\mapsto m/2$ on that specified codomain. A proper subset can therefore have the same cardinality as an infinite set. ^[ref].

A binary operation on a set $S$ is a function $\ast :S\times S\to S$. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since $2-3=-1$ leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On $S=\{0,1,2\}$, both $a\ast b=(a+b)\mathrm{mod}3$ and $a\diamond b=(a-b)\mathrm{mod}3$ return an element of $S$, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

The codomain of a function is its specified target set. The image of a function is a subset of the codomain, and equals it precisely for a surjective function. Changing a codomain can change whether the same input-output rule is surjective, as the quadratic function examples under function show.

The map $x\mapsto (x,f(x))$ is continuous into the product topology. It maps a compact space $X$ onto the graph of a function of a continuous $f$. Hence that graph is compact, whether or not the codomain is a Hausdorff space. Projection to $X$ is its continuous inverse.

On a nonempty domain of a function $X$, a constant function $f:X\to Y$ has one fixed value $c$ in its codomain:For example, $f(x)=2$ on the real line is a horizontal graph. Its image of a function is the singleton $\{2\}$ even though its domain of a function has infinitely many inputs. A constant function from the real line to the real numbers has derivative zero and every nonzero real period of a function; there is no smallest positive period. It supplies a reference level from which variation can be measured.

A constant map between vector spaces is a linear map only when its value is the zero vector, since a linear map must preserve zero. A nonzero constant map is still an affine map. In a Fourier series, the constant term records the period average, while the other terms describe oscillation around that level.

A continuous extension of a function $f:D\to Y$ to a larger domain $E\supseteq D$ is a continuous function $F:E\to Y$ satisfying $F(x)=f(x)$ for $x\in D$. The domain and codomain carry specified topologies. Prescribing values on a dense subset does not by itself prove the existence of a continuous extension.

If $f:X\to Y$ is a continuous map and $X$ is a connected space, then its image $f(X)$, with the subspace topology from $Y$, is a connected subset of $Y$. The whole codomain $Y$ need not be connected; the assertion concerns the values actually attained. No injectivity is required.^[ref]

For example, the continuous function $f(x)=x^2$ maps the connected closed interval $[-2,2]$ onto the connected closed interval $[0,4]$, even though opposite inputs have the same output. The same continuous function maps the disconnected union $[-2,-1]\cup [1,2]$ onto $[1,4]$. Thus a connected image does not imply a connected source: a continuous map can merge different connected components.

For a continuous function $r:[0,1]\to \mathbb{R}$ representing a continuous reading, $r(0)=0$ and $r(1)=1$ force some input with $r(t)=1/2$. Its image is a connected subset of the real line, hence a real interval containing both endpoint readings. For the synthetic model $r(t)=t^2$, the missing-value test is explicit: $r(1/\sqrt{2})=1/2$. A step reading equal to $0$ for $t<1/2$ and $1$ for $t\ge 1/2$ skips $1/2$, but fails continuity at $t=1/2$.

Proof outline: a separation of a topological space of $f(X)$ into nonempty open subsets pulls back under $f$ to nonempty open subsets of $X$. Their intersection is empty and their union is $X$, contradicting connectedness. This also shows why a continuous map sends each connected component of its source into a single connected component of its target.

The University of Oxford preliminary computer science examination whose original cover gives Trinity Term 2015, Thursday 25 June, and formal code A10100W1. The released archive contains it as 2015-cs3.pdf: publicly released examination archive. Printed pages 2–4 contain Questions 1–3; pages 5–7 contain Questions 4–6; pages 8–10 contain Questions 7–9.

The printed codomain in Question 2(b) is inconsistent with its formula, and an unrestricted zero extension of the binomial coefficients makes the premise in (ii) vacuous beyond the finite row. Question 6(b) retains the initial profile $x(1-x)$ on $(0,L)$, which is incompatible with continuity at the upper initial corner unless $L=1$ but is meaningful on the printed open ranges. Question 9(c)(iii) omits the integration variable after both differential signs. These are source qualifications, not missing source material.

For a surjective function $f:B\to A$ and a function $g:B\to C$, there is a unique function $h:A\to C$ with $g=h\circ f$ if and only if $g$ is constant on each fiber of a function of $f$. Define $h(a)$ to be the common value on $f^{-1}(a)$; it is well-defined and unique because that fiber is nonempty. This uniquely specified value requires no simultaneous arbitrary choices.

For a concrete example, restrict the codomain of the finite function above to its image of a function $I=\{0,1,2\}$, making $f:A\to I$ surjective. Define $g(a)=g(b)=5$, $g(c)=7$ and $g(d)=9$. Then $h(y)=2y+5$ on $I$ gives $g=h\circ f$: knowing the output of $f$ is enough to compute $g$. If instead $g(a)\ne g(b)$, no such $h$ can exist, because $h(f(a))=h(f(b))$ must be the same value.

The surjectivity assumption supplies uniqueness on the full target. If the original unused target value three were retained, the factorization would impose no condition on $h(3)$, and different extensions could agree on every actual input. Thus factorization through a surjection formalizes when a compressed description retains all information needed for a later calculation.

// Target: combinatorics.bigb

For a function $f:X\to Y$ and $y\in Y$, its fiber of a function over $y$ is the set of all inputs producing that one output:Here $f^{-1}(y)$ is shorthand for a preimage of a singleton set, rather than a claim that an inverse function exists. A fiber can contain several inputs or be empty. It describes exactly which distinctions the function forgets.

For the finite function under image and preimage of a function, the fibers over $0,1,2,3$ are $\{a,b\}$, $\{c\}$, $\{d\}$ and the empty set, respectively. The nonempty fibers form a partition of a set: they are disjoint sets whose union is the domain of a function. Every input belongs to the fiber over its unique output, and two fibers with distinct output labels cannot share an input. A function is injective exactly when every fiber has at most one member; it is surjective exactly when every member of its specified codomain has a nonempty fiber.

More generally, $f^{-1}(U)$ is the union of the fibers over all $y\in U$. The relation $x\sim x^{\prime }$ defined by $f(x)=f(x^{\prime })$ is an equivalence relation, and its equivalence classes are precisely the nonempty fibers. The resulting quotient set is naturally in bijection with the image of a function. This links an input partition to the output values actually reached, without choosing one representative from each class.

Fibers are useful when an output is known but the input is not uniquely determined. A solution set $g^{-1}(\{0\})$ is one fiber, and factorization through a surjection explains when another function depends only on the retained output. Quantum hidden subgroup problem algorithms use functions whose fibers are cosets, giving the same idea a structured form in group theory.

A function $f:X\to Y$ assigns exactly one output in the specified codomain $Y$ to each input in its domain of a function $X$. Its rule may be a formula, a finite table, or another unambiguous assignment. The outputs actually reached form its image of a function $f(X)\subseteq Y$. A codomain states where outputs are allowed; the image of a function records where they actually land. Oscar Levin's introduction makes this distinction explicit. ^[ref].

For example, $f:\mathbb{R}\to \mathbb{R}$, $f(x)=x^2$, has the entire real line as its domain of a function and codomain, but its image of a function is $[0,\infty )$. Both $-2$ and $2$ give the output $4$: several inputs sharing an output is permitted. Assigning two distinct outputs to one input is not permitted. A partial function can be undefined at some elements of a larger specified source set; an ordinary function on $X$ must be defined at every element of $X$.

Three properties describe how a function uses its target. An injective function never sends distinct inputs to the same output. A surjective function reaches every member of its specified codomain. A bijection does both, pairing each source element with exactly one target element. These are different requirements, as finite arrow diagrams show.

The chosen codomain matters even when the formula does not change. The function $x\mapsto x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not surjective, whereas the same rule from $\mathbb{R}$ to $[0,\infty )$ is surjective. Both fail injectivity. Further restricting the domain of a function to $[0,\infty )$ makes it a bijection onto $[0,\infty )$, with square root as its inverse function.

Functions make transformations composable: if $f:X\to Y$ and $g:Y\to Z$, their function composition is $(g\circ f)(x)=g(f(x))$. Identifying each intermediate codomain prevents attempting to feed an output into a rule that is not defined there. When a transformation is a bijection, an inverse function recovers the original input without ambiguity. This is useful whenever information must be transported or a calculation reversed.

A function class is a set whose elements are functions, usually sharing a common domain of a function and codomain.

For functions $f:X\to Y$ and $g:Y\to Z$, their function composition is $g\circ f:X\to Z$, defined by $(g\circ f)(x)=g(f(x))$. The rightmost function is applied first. Matching the intermediate codomain and domain of a function makes the expression well-defined.

For self-maps of the real numbers, take $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. Thus function composition need not be commutative. It does have the associative property: both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ evaluate to $h(g(f(x)))$ whenever each intermediate codomain matches the next domain of a function. The identity function leaves composition unchanged, making self-maps particularly useful as a monoid of transformations.

A function output is the value $f(x)$ assigned by a function $f:X\to Y$ to a function input $x$. It belongs to the codomain $Y$; all such function outputs together form the image of a function $f(X)$.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

For a real-valued function drawn in the plane, the horizontal line test asks whether every horizontal line intersects its function graph at most once. This is exactly injectivity, since two intersections at the same height mean two inputs have the same output. A missing height is compatible with injectivity, so an inverse function is then defined on the image of a function; it is an inverse on the entire specified codomain only when surjectivity also holds.

The image of a function asks which outputs a chosen set of inputs reaches. A preimage asks which inputs reach a chosen set of outputs. Both constructions apply to every function, including one that loses information by sending several inputs to the same output. Their difference is useful whenever a transformation must be followed forward or a condition on its result must be traced back.

Consider the function $f:A\to B$ withEvery input has exactly one output, but zero has two inputs and three has none. The full image of a function is $f(A)=\{0,1,2\}$, a proper subset of the codomain $B$. Selecting inputs $\{a,c\}$ gives image $\{0,1\}$. Selecting outputs $\{0,2\}$ instead gives preimage $\{a,b,d\}$.

The function is not injective, because $f(a)=f(b)$, and is not surjective onto $B$, because three is absent from its image. Restricting only the codomain to $\{0,1,2\}$ makes the same rule surjective; it remains noninjective. This separates the output set actually reached from the target set specified in the definition. The definitions of images of a function and preimages, including the distinction from an inverse function, are given in Richard Hammack, Book of Proof, §12.6: Image and Preimage.

Given injections $f:X\to Y$ and $g:Y\to X$, start with the set difference $A_0=X\setminus g(Y)$: these are exactly the inputs for which $g^{-1}$ is unavailable. Follow both functions repeatedly, using the natural-number recursion theorem to defineThus $A$ contains all the $X$ members reachable from any starting point in $A_0$. The notation $f(A_k)$ and $g(f(A_k))$ denotes images of a function. If $A_0$ is the empty set, then every $A_k$ is empty and $g^{-1}$ alone gives the desired bijection.

Define a function on all of $X$ byHere $g^{-1}$ is the inverse function from $g(Y)$ to $Y$, obtained by restricting the codomain of $g$ to its image. It is well defined because $g$ is injective. Every $x\notin A$ belongs to $g(Y)$, since $A_0\subseteq A$, so the second rule is always available where it is used.

The decisive set identity isThe last equality holds because every $A_k$ with $k\ge 1$ lies in $g(Y)$, whereas $A_0$ is disjoint from $g(Y)$. Consequently, for any $y\in Y$,Indeed, $g(y)$ cannot belong to $A_0$; if it lies in $A$, the identity gives $g(y)=g(f(a))$ for some $a\in A$, and injectivity gives $y=f(a)$. The converse follows directly by applying $g$.

Now $f$ restricts to a bijection from $A$ onto $f(A)$. The displayed equivalence says that $g$ restricts to a bijection from $Y\setminus f(A)$ onto $X\setminus A$, so its inverse function bijects the remaining inputs with the remaining outputs. The two input sets partition $X$ and the two output sets partition $Y$. Their combined function $h$ is therefore both injective and surjective.

No choice function is needed: $A$ is fixed by the given injections, and each required $g^{-1}(x)$ is unique. We neither choose a representative from each chain nor enumerate $X$. This is a proof in ordinary classical ZF, even when no well-ordering of the sets exists there.^[ref]

The function is surjective, also called onto, when every element of its codomain has at least one preimage:The condition concerns the specified codomain, not just the formula defining the function.

The image of a function is the set of values actually attained as its argument ranges over its domain of a function:It is a subset of the codomain $B$, and need not equal $B$.