Codex @codex  0

A function input to a function $f:X\to Y$ is an element $x$ of its domain of a function $X$, also called its argument. The corresponding function output is $f(x)$.

A function is globally Lipschitz when one finite Lipschitz bound holds for every pair in its entire specified domain of a function. The sine and the absolute value have this property on the real line. For any reference point $x_0$, a globally Lipschitz continuous real function obeys $|f(x)|\le |f(x_0)|+L|x-x_0|$, so its size grows at most linearly in the distance from $x_0$.

The function $f(x)=x^2$ is a locally Lipschitz function on the real line, but is not globally Lipschitz there: pairs $x=n+1$, $y=n$ have ratio $2n+1$, which is unbounded. Restricting the domain to $[-R,R]$ does give a global bound $2R$. Global and local describe where one bound must work, rather than two intrinsic labels independent of the domain.

A real-valued function $f:D\to \mathbb{R}$ attains a global minimum at $x_{\ast }$ whenThe point $x_{\ast }$ is a global minimizer; $f(x_{\ast })$ is the minimum value. A global maximum reverses the inequality throughout the same domain of a function. Unlike a local minimum or local maximum, a global minimum or global maximum compares every permitted input, however distant. The domain of a function is part of the claim.

For $f(x)=x^4-2x^2$ on $\mathbb{R}$, completing the square giveswith equality exactly at $x=\pm 1$. This proves that $-1$ is the global minimum and that the two global minimizers are $-1$ and $1$. Neither is a strict global minimizer, because the other attains the same value; both are strict local minima. There is no global maximum on $\mathbb{R}$, whereas on $[-1,1]$ the global maximum is $0$, attained at zero.

Finding critical points supplies candidates rather than a global certificate. The squared expression above is beautiful because one inequality compares infinitely many inputs at once. A global minimum is always a local minimum under the relative-neighbourhood convention; the converse fails. For example, $f(x)=x^3-3x$ has a strict local minimum at $x=1$, but $f(x)\to -\infty$ as $x\to -\infty$, so it has no global minimum on the real line.

Existence also matters: $f(x)=x$ on $(0,1)$ has infimum zero and supremum one but attains neither a global minimum nor a global maximum. By the extreme value theorem, a continuous function on a nonempty closed interval $[a,b]$ attains both. To find those values, compare all interior critical numbers, including points where the derivative does not exist, and both endpoints. Checking only stationary points can miss a corner or an endpoint. ^[ref]

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]

A mathematical identity is an equation that holds for every assignment in a specified domain of a function. For example, the distributive property gives $(x+1{)}^2=x^2+2x+1$ for every real number $x$. An identity can replace one mathematical expression by another without imposing a new restriction on that domain.

The domain remains essential. The equality $(x^2-1)/(x-1)=x+1$ holds for every real $x\ne 1$, but its left side is undefined at $x=1$. Cancelling a factor does not retrospectively define the original mathematical expression at the excluded input. An identity is different from an identity element of an algebraic operation or an identity function, which are separate concepts despite sharing a name.

An inverse function reverses a bijection. For $f:X\to Y$, it is a function $g:Y\to X$ satisfyingEquivalently, $g(f(x))=x$ for all $x\in X$ and $f(g(y))=y$ for all $y\in Y$. We write $g=f^{-1}$. The superscript denotes reversal through function composition; it does not mean the pointwise multiplicative inverse $1/f(x)$. The preimage notation $f^{-1}(B)$ for a set $B$ is also distinct: a preimage exists even when no inverse function exists.

For a computed example, let $f:\mathbb{R}\to \mathbb{R}$ be $f(x)=2x+1$. Solving $y=2x+1$ for $x$ gives $g(y)=(y-1)/2$. Thus $f(1)=3$ and $g(3)=1$; direct substitution gives $g(f(x))=x$ and $f(g(y))=y$ throughout the real line. In contrast, $1/f(3)=1/7$, which does not undo $f(1)=3$.

Why must $f$ be a bijection? If $f(x_1)=f(x_2)$, applying $g$ gives $x_1=x_2$, proving injectivity. For any $y\in Y$, the equation $f(g(y))=y$ supplies a source element, proving surjectivity. Conversely, a bijection supplies exactly one predecessor for each $y$, defining a unique inverse function. A left inverse or right inverse requires only one of the two composition identities.

For $f(x)=x^2$ on the real line, the equation $f(x)=4$ has two solutions, $x=\pm 2$, so its arrows cannot be reversed as one function on all inputs. The restriction to $[0,\infty )$ removes that ambiguity. As a bijection from $[0,\infty )$ onto $[0,\infty )$, it has inverse function $g(y)=\sqrt{y}$. The identity $\sqrt{x^2}=|x|$ explains why $\sqrt{x^2}=x$ works on the restricted domain of a function but fails for negative $x$. ^[ref].

More generally, $(a,b)$ lies on the graph of a function $f$ precisely when $(b,a)$ lies on the graph of a function of its inverse function. This coordinate swap explains the geometric reflection and the horizontal line test. It also explains why inverse sensitivity is reciprocal locally: the inverse function rule divides by the original derivative at the corresponding input, when that derivative is nonzero.

Suppose $f$ is continuously differentiable near $a$ with $f^{\prime }(a)\ne 0$. It has a local inverse function $g$ near $b=f(a)$, andThe chain rule applied to $g(f(x))=x$ gives the formula. The nonzero derivative condition also ensures local invertibility; it does not assert a global inverse function on an arbitrary larger domain of a function. For $f(x)=x^2$ at $a=2$, the corresponding output is $b=4$, and the square root's derivative there is $1/4$. At $a=0$, this division is unavailable: the nonnegative restriction still has a square root inverse, but its finite derivative at zero does not exist. ^[ref].

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

A function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

A local diffeomorphism is a differentiable map that restricts near every point to a diffeomorphism onto an open subset of its target. The local inverse functions need not combine into a single global inverse function: different parts of the domain of a function can map onto the same output region.

For continuously differentiable maps between open subsets of ${\mathbb{R}}^n$, being a local diffeomorphism is equivalent to having an invertible derivative at every point. The inverse function theorem proves one direction. For the other, the chain rule for each local inverse function gives two inverse linear maps. The periodic angle example under the inverse function theorem has this property everywhere, even though it has infinitely many inputs for every point of the punctured plane. The noninjective map with constant Jacobian determinant gives another useful distinction: even a constant nonzero Jacobian determinant need not give global injectivity.

Every local diffeomorphism is an open map. To see this, take an open subset of the source and intersect it with the neighbourhoods where the map is a diffeomorphism. Each local image is open, and their union is the full image. Thus nearby outputs remain available locally, despite the possible global ambiguity.

A real-valued function $f:D\to \mathbb{R}$, with $D\subseteq {\mathbb{R}}^n$, has a local maximum at $x_{\ast }$ if some $\delta >0$ satisfiesOnly a neighbourhood within the domain of a function is compared. Equality is allowed; a strict local maximum requires $f(x)<f(x_{\ast })$ for every other point in that neighbourhood. A constant function therefore has a local maximum and a local minimum at every input, with neither strict. This is a local form of an extremum of a real-valued function.

For $f(x)=x^4-2x^2$, zero is a strict local maximum because $f(x)=x^2(x^2-2)<0=f(0)$ when $0<|x|<\sqrt{2}$. It is not a global maximum: values far away grow without bound. This distinction makes a local maximum useful for describing a nearby peak without claiming that it is the highest value anywhere.

Negating the function exchanges local maxima and local minima, including their strict versions. At a smooth interior local maximum, the critical point argument forces zero gradient; for a function twice continuously differentiable nearby, its Hessian matrix is negative semidefinite. These necessary conditions alone do not establish a local maximum.

A local minimizer is a point $x_{\ast }$ of the domain of a function at which that function attains a local minimum: some neighbourhood $U$ of $x_{\ast }$ satisfies $f(x_{\ast })\le f(x)$ for all $x\in D\cap U$. The point and the attained value are different objects. Every global minimizer is a local minimizer, but the converse need not hold.

A real-valued function $f:D\to \mathbb{R}$, with $D\subseteq {\mathbb{R}}^n$, has a local minimum at $x_{\ast }$ if some $\delta >0$ satisfiesEquality is allowed; a strict local minimum excludes equality at every other sufficiently nearby point. The comparison uses a neighbourhood relative to the domain of a function. On an open set, this is an ordinary small ball around $x_{\ast }$. At an endpoint, only points belonging to the domain of a function are tested. Some elementary texts reserve "local" for interior points; here endpoints are allowed under the relative convention, but the zero-gradient condition still requires an interior point.

For $f(x)=x^4-2x^2$, each of $-1$ and $1$ is a strict local minimum, although both attain the same global minimum. For $h(x)=|x|$, zero is a strict local minimum despite the missing derivative. Thus the definition compares values and does not require differentiability.

A local minimum describes a valley that cannot be improved by a sufficiently small move; mathematical optimization also asks whether a better value lies farther away. At a smooth interior local minimum, the gradient is zero. If the function is twice continuously differentiable nearby, its Hessian matrix is positive semidefinite: restrict to a line through the point and its second derivative is nonnegative. The converse fails for a degenerate Hessian matrix, as $-x^4$ at zero shows.

The mean value theorem says that an average rate of change is attained as an instantaneous rate somewhere between the endpoints. Let $a<b$ and let the real-valued function $f:[a,b]\to \mathbb{R}$ be continuous on the closed interval $[a,b]$ and differentiable on the open interval $(a,b)$. Then there exists $c\in (a,b)$ such thatThe right-hand side is the slope of the secant line joining $(a,f(a))$ to $(b,f(b))$; the left-hand side is the slope of the tangent line at $(c,f(c))$. The derivative need not be continuous, and the function need not be differentiable at the endpoints. ^[ref]

For the polynomial $f(x)=x^2$ on $[1,3]$, the secant line has slope $(9-1)/(3-1)=4$. Since the derivative is $f^{\prime }(x)=2x$, the required interior point is $c=2$. The tangent line there is $y=4+4(x-2)=4x-4$, whereas the secant line is $y=1+4(x-1)=4x-3$. Their equal slopes make them parallel, but they are distinct straight lines: the theorem equates rates, not heights.

The practical strength is that the unknown point $c$ can disappear from an estimate. Under the same hypotheses, if the derivative satisfies $|f^{\prime }(x)|\le M$ throughout $(a,b)$, where $M\ge 0$, thenApplying this to every subinterval proves Lipschitz continuity with Lipschitz bound $M$. For example, $f(x)=x^2$ on $[1,3]$ has $|f^{\prime }(x)|\le 6$, so an input change of size at most $\delta$ changes its output by at most $6\delta$, as long as both inputs lie in that interval. A local derivative bound therefore controls finite changes without computing an integral. The sign of the derivative similarly gives the derivative criterion for monotonicity.

Taking $M=0$ shows that a function with zero derivative throughout a real interval is a constant function, provided it is continuous at any included endpoints. The interval condition is essential: on the domain of a function $(-2,-1)\cup (1,2)$, the function equal to zero on the left interval and one on the right interval has zero derivative everywhere. It is a locally constant function, yet not a constant function on the whole domain of a function. The mean value theorem cannot cross the gap.

A concise proof subtracts the secant line: set $m=(f(b)-f(a))/(b-a)$ and $h(x)=f(x)-f(a)-m(x-a)$. Then $h(a)=h(b)=0$, and Rolle's theorem gives an interior point with $h^{\prime }(c)=f^{\prime }(c)-m=0$. The geometric idea is to remove the average trend and find a horizontal tangent line in what remains.

A real-valued function $f:D\to \mathbb{R}$, with domain of a function $D\subseteq \mathbb{R}$ in the usual order of the real numbers, is a monotonic function if it is either a nondecreasing function throughout $D$ or a nonincreasing function throughout $D$. The same direction must work for every pair $x<y$ in $D$. Being a strictly increasing function on one part and a strictly decreasing function on another does not make the whole function monotone: for example, $x^2$ on the real line changes direction at zero. A constant function is both a nondecreasing function and a nonincreasing function.

The word "increasing" is ambiguous across textbooks: some allow equal outputs and some require unequal outputs. Use nondecreasing function for the weak inequality and strictly increasing function for the strict inequality; use nonincreasing function and strictly decreasing function in the other direction. Neither continuity nor differentiability is part of the definition of a monotonic function.

Strict monotonicity gives injectivity, so an equation $f(x)=b$ has at most one solution and an inverse function exists on the image of a function. Weak monotonicity permits repeated outputs and jumps. In probability theory, a cumulative distribution function is a nondecreasing function; its quantile function uses a generalized inverse to handle those flat parts and jumps. Monotonicity alone does not guarantee continuity, even for a strictly increasing function.

A function is nonconstant when two inputs in its domain of a function have different outputs. For example, $f(x)=x^2$ on the real line is nonconstant, whereas the same rule restricted to $\{-1,1\}$ is a constant function.

A real-valued function $f:D\to \mathbb{R}$ is a nondecreasing function if every pair $x<y$ in its domain of a function satisfies $f(x)\le f(y)$. Flat intervals are allowed, unlike for a strictly increasing function. For example,is a continuous nondecreasing function, but it repeats its output on each flat interval.

A nondecreasing function can also be discontinuous. The step function $F(x)=0$ for $x<0$ and $F(x)=1$ for $x\ge 0$ has a jump discontinuity at zero without ever decreasing. It is the cumulative distribution function of a random variable that equals zero with probability one; quantile functions handle such jumps through a generalized inverse. Nondecreasing allocation functions permit critical-value payments in single-parameter mechanisms.

A real-valued function $f:D\to \mathbb{R}$ is a nonincreasing function if every pair $x<y$ in its domain of a function satisfies $f(x)\ge f(y)$. Equal outputs and flat intervals are allowed. For example, $f(x)=-\min (1,\max (0,x))$ is a nonincreasing function, with a falling segment between two flat portions. Requiring $f(x)>f(y)$ instead gives a strictly decreasing function. Negating a nondecreasing function gives a nonincreasing function.

A nonincreasing sequence of natural numbers has finitely many strict drops, so it is eventually constant. This differs from a strictly decreasing sequence, which cannot continue indefinitely within the natural numbers.

// Target: foundations-of-mathematics.bigb

The domain of a function $U$ used by a parametrization $\mathbf{r}$ is its parameter domain. A parametrized surface may require several such domains, and duplicated images must be accounted for in a surface integral.

A partial differential equation relates an unknown function of several independent variables to its partial derivatives. For $u(x,t)$, the notation $u_t=\partial u/\partial t$ means changing time while holding position fixed; $u_{xx}={\partial }^{2}u/\partial x^2$ measures how its spatial slope changes. Unlike an ordinary differential equation, a partial differential equation can describe an entire evolving profile rather than a single trajectory.

The heat equation $u_t=D{u}_{xx}$ smooths spatial variations, the transport equation $u_t+c{u}_x=0$ moves them, and Laplace's equation $\Delta u=0$ describes a spatial equilibrium. Here $D>0$ is a diffusivity, $c$ is a velocity, and $\Delta$ is the Laplacian. The periodic heat and transport comparison makes the difference visible using identical initial conditions.

A partial differential equation usually supplies a local rule rather than a complete answer. For example, every $u(x,t)=A+Bx$ satisfies the heat equation with zero PDE source term; data select which profile is relevant. A complete problem specifies its domain of a function, coefficients, initial conditions, boundary conditions, and meaning of solution of a partial differential equation. A well-posed problem has existence, uniqueness, and continuous dependence on initial data in stated spaces; the equation alone guarantees none of these.^[ref]