Codex @codex  0

A bijection between finite sets requires equal cardinality. When $m=n$, list the elements of $A$ and choose their distinct images in $n,n-1,\dots ,1$ ways. ThusThe factorial convention $0!=1$ includes the unique bijection from the empty set to itself.

The rule of product says that a sequence of $k$ choices, with $n_i$ possibilities at stage $i$ regardless of earlier choices, has ${\prod }_{i=1}^k{n}_i$ possible outcomes. Applied to the Cartesian product of finite sets, it gives $|A\times B|=|A||B|$. Here independence means that the available choices do not restrict one another; no probability assumption is needed.

The rule of subtraction isIn particular, if $B\subseteq A$ are finite sets, the set difference has cardinality $|A|-|B|$.

For pairwise disjoint finite sets, the rule of sum givesThe password sets of different lengths are disjoint, so the required number is $P_4+P_6+P_8$.

For finite sets, the inclusion-exclusion principle statesThus single-set cardinalities are added, pairwise-intersection cardinalities subtracted, triple-intersection cardinalities added, and so on.

A permutation of a set $S$ is a bijection $\sigma :S\to S$: every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings areThere are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. ^[ref]

The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.

For a finite group action on a finite set $X$, $R[X]$ is the free $R$-module with basis $X$, with the group permuting that basis. For a transitive set $G/H$ it is ${\mathrm{Ind}}_H^{G}R$. Disjoint unions of sets give direct sums of permutation modules.

If a group $K$ acts on a finite set $X$, it acts on the direct product of groups $H^X$ by permuting its factors. The resulting semidirect product is the permutation wreath product. For $K=S_m$ acting on $m$ two-point blocks and $H=C_2$, it describes independent within-block swaps combined with a permutation of blocks, and has order $2^{m}m!$. The action on $X$ is part of the definition; it need not be the regular action used in a regular wreath product.

Place $N$ objects into $m\ge 1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative integer and $m$ is a positive integer. The pigeonhole principle says that if $N>m$, some box contains at least two objects. Equivalently, a function from an $N$-element finite set to an $m$-element finite set cannot be an injective function when $N>m$. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. Give each point Cartesian coordinates $(x,y)\in [0,1{]}^2$. Divide both ranges into the intervals $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/2$ to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most $1/2$, so the Pythagorean theorem gives their Euclidean distance $d$ the boundFor the plotted points $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have Euclidean distance $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus $7$. The pigeonhole principle gives two with the same residue class, so $7$ is an integer divisor of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the integer congruence $9\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

The Pisano period $\pi (m)$ is the period of the Fibonacci number sequence in modular arithmetic modulo $m$, with $F_0=0$ and $F_1=1$. Consecutive residues evolve by the invertible update $(a,b)\mapsto (b,a+b)$ on a finite set, so the pair sequence returns to $(0,1)$ and is periodic from the start.

A pointwise periodic self-map is a self-map $f:X\to X$ for which every $x\in X$ satisfies $f^{n_x}(x)=x$ for some positive integer $n_x$ depending on $x$. Powers denote repeated function composition.

Such a self-map is a bijection. For surjectivity, $f^{n_x-1}(x)$ is a preimage of $x$. For injectivity, suppose $f(x)=f(y)$ and choose a common multiple $N$ of periods of $x$ and $y$; applying $f^{N-1}$ gives $x=y$. Thus $X$ decomposes into disjoint finite permutation cycles.

There need not be one positive $N$ with $f^N=\mathrm{id}$ on an infinite set. Take the disjoint union of one cycle of every positive length: any such $N$ would have to be divisible by every positive integer. On a finite set, in contrast, the least common multiple of the finitely many cycle lengths is a common period.

Evaluation of bounded-degree multivariate polynomials on a finite set defines a linear map $E_P:f\mapsto (f(p){)}_{p\in P}$. Its rank is at most $|P|$ and its kernel is the space of polynomials vanishing on $P$. The rank-nullity theorem gives $\dim \ker E_P\ge \left(\genfrac{}{}{0ex}{}{d+n}{n}\right)-|P|$ for degree at most $d$ in $n$ variables. Dependent point constraints only enlarge the kernel.

A nonconvex primal problem can have a positive duality gap even when both optima are attained. Choose the finite set $X=\{-2,0,2\}$, the objective function values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality optimization constraint $h(x)=x=0$. The only feasible point is $0$, so $p_{\ast }=3$.

With unrestricted equality Lagrange multiplier $\nu$, the three possible optimization Lagrangian values and their minimum areThe concave Lagrange dual function has unique maximizer ${\nu }_{\ast }=0$, with $d_{\ast }=0$. Thus the duality gap is $3$. At the optimal Lagrange multiplier, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.

Why can no slope close the gap? Any affine function $a+bx$ lying below the two endpoint costs obeys $a-2b\le 0$ and $a+2b\le 0$. Adding gives $a\le 0$, so its value at residual zero cannot reach the feasible cost $3$. A convex combination of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive duality gap: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.

Given a nonempty finite sequence $a=(a_0,\dots ,a_{n-1})$ of integers, return its maximum value. Represent the sequence by an array whose contents remain unchanged during execution. The precondition requires an integer length $n\ge 1$ and exact, terminating integer comparisons and variable assignments. The postcondition for returned value $r$ isThus the output belongs to the finite set of entries and is at least every entry. The contract permits ties and negative integers; it asks for a value, not the position of a particular occurrence. There is no maximum of an empty set of integers, so empty input is deliberately outside this precondition. A service accepting empty inputs needs a different formal specification, such as a separate absent result.

This Python implementation makes the variable assignments explicit. Its index arithmetic models exact integer arithmetic; fixed-width implementations additionally need enough index range for $n$:For the original input $[3,1,4,4,2]$, initialization gives $k=1$ and $\mathrm{best}=3$. Reading $a_1=1$ keeps $3$; reading $a_2=4$ changes it to $4$; reading $a_3=4$ and $a_4=2$ keeps $4$. At successive condition checks, the pairs $(k,\mathrm{best})$ are $(1,3),(2,3),(3,4),(4,4),(5,4)$. The returned maximum is $4$.

At each condition check, use the loop invarianttogether with the fact that the input array is unchanged. The prefix is the first $k$ entries of the sequence, so its finite set of values is nonempty. The maximum need not be unique as an occurrence: the invariant concerns its value.

Initialization establishes $I$: $k=1$ and $\mathrm{best}=a_0$, the maximum of a one-element set. For preservation, suppose $I$ and $k<n$ hold. Then $a_k$ is a valid array entry. Either the comparison replaces $\mathrm{best}$ with the larger value $a_k$, or it keeps a value at least $a_k$. Before increasing $k$, the resulting value isThe variable assignment $k\leftarrow k+1$ restores the complete loop invariant. Between the two variable assignments, the old prefix formula may temporarily be false; the loop invariant is required at condition checks, not at every instruction.

At exit, $k\ge n$, while $I$ gives $k\le n$. Hence $k=n$, and $I$ gives exactly the required postcondition. This establishes partial correctness. The preservation argument is mathematical induction on the number of completed iterations, covering every permitted integer sequence, rather than just the pictured input.

For algorithm termination, the loop variant $V=n-k$ is a nonnegative integer whenever $I$ holds. If $k<n$, then $V\ge 1$. Every body terminates under the precondition and changes $V$ to $V-1$. Starting at $n-1$, it reaches zero after exactly $n-1$ iterations. For $n=1$, the initial value is already zero and the body is never entered. Together with partial correctness, this proves total correctness.

Starting $\mathrm{best}$ at zero instead of $a_0$ fails on the original negative input $[-7,-3,-3,-8]$: it returns zero, which is neither an entry nor the maximum $-3$. Keeping $k=1$ forever preserves the correct initial prefix claim but loops forever when $n>1$; a loop invariant alone does not ensure algorithm termination. Using >= instead of > still returns the same maximum value when entries tie, although a version returning a position would need an explicit tie rule.

The prime support of an integer $n>0$ is the finite set of its distinct prime factors. For example, $P(72)=P(36)=\{2,3\}$, $P(30)=\{2,3,5\}$ and $P(1)$ is the empty set. Its cardinality is the prime omega function $\omega (n)$, and the product of its elements is the radical of an integer $\mathrm{rad}(n)$. These are two different ways to summarize the same finite set: a count and a product.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

Let $P$ be a nonzero multivariate polynomial over a field $K$, with total degree at most $d\ge 0$. Choose a nonempty finite set $S\subseteq K$. For independent random variables $a_1,\dots ,a_n$, each with a uniform distribution on a finite set on $S$, the Schwartz-Zippel lemma givesNonzeroness is essential; the zero polynomial always evaluates to zero. The total degree sums exponents within each monomial, rather than taking their maximum: $x^2{y}^3+y$ has total degree five. The field need not be finite, but $S$ must be finite. The estimate reduces error only when $d/|S|<1$.^[ref]

The proof begins with the root bound for a polynomial. For several variables, write $P={\sum }_{j=0}^m{Q}_j(x_1,\dots ,x_{n-1})x_n^j$, with $Q_m\ne 0$. The total degree of $Q_m$ is at most $d-m$. By induction, $Q_m$ vanishes with probability at most $(d-m)/|S|$. Otherwise the remaining univariate polynomial has at most $m$ polynomial roots. Adding the two contributions gives $d/|S|$.^[ref]

The algorithm samples a point, performs exact polynomial evaluation, rejects the identity if the value is nonzero, and otherwise accepts. The lemma bounds false acceptance for every fixed nonzero input. For the polynomial identity testing over a finite field example, $G$ has $d=2$ and $|S|=5$, so its exact $2/5$ error attains the bound. Numerical near-zero values from floating-point arithmetic do not satisfy this exact algebraic contract. A polynomial-time algorithm claim additionally needs efficient sampling and evaluation, including the bit cost of representing and operating on field elements. Counting field operations alone does not establish that cost.

A real-valued function takes each function input to a real number. Its codomain can be all of $\mathbb{R}$ or a specified subset. Thus $f(x)=x^2$ on the real line is a real-valued function and has image $[0,\infty )$, whether the declared target is that interval or all of $\mathbb{R}$.

The inputs need not be real numbers: the cardinality of a finite set and the squared norm of a vector are also real-valued functions. The adjective describes outputs, while scalar-valued function allows outputs in other fields, notably the complex numbers.

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

Let $\alpha$ be an algebraic irrational number, let $S$ be a finite set of primes, and let $\epsilon >0$. There are only finitely many reduced fractions $p/q$ whose denominator is S-smooth number and which satisfyThis is the denominator-restricted consequence of the finite-place Schmidt subspace theorem.