Codex @codex  0

For finite sets $A,B\subseteq G$ in an abelian group $G$, their difference set isHere $-b$ is the additive inverse in $G$. The difference set records possible displacements from a member of $B$ to a member of $A$; it is distinct from the set difference $A\setminus B$.

For the integer sets $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$,The positive differences for $B$ are $1,3,4,6,9,10$, each obtained once; reversing each ordered pair supplies the corresponding negative difference. Every nonempty finite set $S$ has $0\in S-S$, with $|S|$ representations $(s,s)$. Swapping the members of an ordered pair also shows $S-S=-(S-S)$. In the cyclic group $\mathbb{Z}/6\mathbb{Z}$, the subgroup $H=\{0,2,4\}$ satisfies $H-H=H$ as well as $H+H=H$.

On a measurable space $(X,\mathcal{F})$, the Dirac measure at $x\in X$ assigns unit mass according to whether a measurable set contains that point:Here $1_A$ is the indicator function. This is a probability measure, since ${\delta }_x(X)=1$. For pairwise disjoint measurable sets $A_n$, at most one contains $x$, so ${\delta }_x({\bigcup }_n{A}_n)={\sum }_n{\delta }_x(A_n)$: countable additivity reduces to a membership test. The definition works even when the singleton $\{x\}$ is not a measurable set. ^[ref]

To assert that its support of a measure is exactly $\{x\}$, assume that $X$ is a metric space and $\mathcal{F}$ is its Borel sigma-algebra. The singleton $\{x\}$ is then a closed set and a Borel set, with ${\delta }_x(\{x\})=1$. Every open neighbourhood of $x$ has mass one; every other point $y$ has an open ball of radius less than its distance from $x$, with mass zero. Thus $\mathrm{supp}{\delta }_x=\{x\}$. An abstract measurable space has no specified topology, so this topological conclusion is not part of the bare definition. Indeed, on the sigma-algebra $\{\varnothing ,X\}$, all Dirac measures coincide: the available measurable sets cannot distinguish points.

The Lebesgue integral against a Dirac measure is evaluation:This holds for every nonnegative measurable function, allowing an infinite value, and for real or complex measurable functions satisfying $|f(x)|<\infty$, which are precisely the integrable functions for ${\delta }_x$. For a nonnegative simple function, only the cell containing $x$ contributes to its integral; increasing simple functions and the monotone convergence theorem extend the identity. Splitting into positive and negative parts, and then real and imaginary parts, gives the remaining cases. This is why a Dirac measure turns integration into a point query.

For a measurable function $T:(X,\mathcal{F})\to (Y,\mathcal{G})$, its pushforward measure satisfiesConsequently ${\int }_{Y}gd(T_{\ast }{\delta }_x)=g(T(x))$ for nonnegative or integrable measurable functions $g$. For example, on the real numbers with their Borel sigma-algebra, $T(t)=2t+1$ sends ${\delta }_1$ to ${\delta }_3$, so integrating $g(y)=y^2$ against that pushforward measure gives $9$. ^[ref]

Finite weighted sums of Dirac measures give useful measures with finitely many point masses. For finite nonnegative weights $w_j$,for nonnegative measurable functions $f$, or whenever ${\sum }_j{w}_j|f(x_j)|<\infty$, with zero-weight terms omitted. Repeated locations have their weights added. On the real numbers, this is the finite version of the measure underlying the left-continuous cumulative function of an atomic measure; a positive-weight singleton is an atom of a measure. Unit weights at the distinct points of a finite set recover counting measure on that set. ^[ref]

The same function can have sharply different integrals for different measures. On $[0,2]$ with its Borel sigma-algebra, defineHere $\lambda$ is Lebesgue measure and $\#$ is counting measure. The singleton $\{1\}$ is a Lebesgue null set, so its changed value leaves the Lebesgue integral equal to ${\int }_0^2(t+1)dt=4$. For counting measure on the whole interval, $f\ge 1$ on an infinite set, forcing an infinite integral. On the smaller measure space $D=\{0,1,2\}$ with its power set and counting measure, the restricted function instead has integral $1+5+3=9$.

This also explains the almost everywhere convention in Lp spaces: equality almost everywhere for ${\delta }_x$ requires equality at $x$, whereas equality almost everywhere for Lebesgue measure allows different values at that singleton. A point value therefore cannot be read unambiguously from an equivalence class in an Lp space formed using Lebesgue measure.

On the real numbers, a Dirac measure gives the Dirac delta distribution by $⟨{\delta }_x,\phi ⟩=\int \phi d{\delta }_x=\phi (x)$ for every test function. The name Dirac delta function does not mean an ordinary function that is zero away from $x$ and infinitely high at $x$. Such a nonnegative measurable function still has Lebesgue integral zero, because its nonzero values occur on a Lebesgue null set. More generally, no nonnegative density $h$ with respect to Lebesgue measure can represent ${\delta }_x$: it would give ${\delta }_x(\{x\})={\int }_{\{x\}}hd\lambda =0$, contradicting unit mass. The measure and its associated distribution act on different kinds of inputs, namely measurable sets and test functions, but express the same point evaluation. ^[ref]

A discrete uniform distribution gives every element of a nonempty finite set $S$ the same probability. Write $n=|S|$ for its cardinality. A random variable $X$ with this law has support of a probability distribution $S$ and probability mass functionThe masses sum to $n(1/n)=1$. Conversely, if all $n$ masses equal $p$, their sum is $np=1$, so necessarily $p=1/n$. Thus equal chances determine the whole law.^[ref]

Counting now computes an event's probability: for any set $A$ of possible values,In particular, when $A\subseteq S$, the answer is $|A|/|S|$. The intersection matters: values outside the support of a probability distribution contribute zero. This turns a probability question into a combinatorics question, provided that equal chances are justified by the model.

For an ideal fair six-sided die, $S=\{1,2,3,4,5,6\}$ and each face has probability $1/6$. The event of an even integer is $\{2,4,6\}$, so its probability is $3/6=1/2$; the event $X\ge 5$ has probability $2/6=1/3$. Direct summation gives the expected value $\mathbb{E}X=21/6=7/2$ and the variance $\mathrm{Var}(X)=91/6-(7/2{)}^2=35/12$. The mean $7/2$ is a balance point between possible outcomes. These are exact consequences of stipulated fairness, rather than measured frequencies from physical dice.

Uniformity describes probabilities, not distances between values. For a second constructed model, stipulate equal-chance selection from $S=\{1,2,4,8\}$. Every value has probability $1/4$, despite the unequal gaps $1,2,4$. Here $\mathbb{P}(X\ge 4)=2/4=1/2$, while the expected value and variance areNeither the midpoint of the extreme values, $9/2$, nor a formula using only the cardinality gives these moments. For a general numerical support of a probability distribution, use its actual values:

Choosing an item from a finite list with equal chances is a basic building block of simple random sampling. A bijection that relabels the items preserves equal probabilities, although changing numerical labels can change the expected value and variance. A function that merges labels can destroy uniformity: for the fair-die model, $Y=\min (X,3)$ has masses $1/6,1/6,4/6$ at $1,2,3$, since four faces map to three. Always count the original equally likely outcomes.

An indicator random variable for membership in a set $A\subseteq S$ has a Bernoulli distribution with parameter $|A|/n$; counting that event over $r$ independent repetitions gives a binomial distribution with parameters $r$ and $|A|/n$. Equal chances among individual values need not produce equal chances among aggregated counts.^[ref]

Double counting establishes an identity by computing the cardinality of the same finite set in two ways. The useful step is to identify exactly what the members of that collection are; an algebraic equality then records two legitimate ways to organize them.

Take the ordered pairs $(S,x)$ where $S$ is a $k$-element subset of an $n$-element set and $x\in S$ is marked. Choosing $S$ first gives $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ pairs. Choosing $x$ first leaves $k-1$ members to choose from the other $n-1$, giving $n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. HenceFor five people and two-person teams, both counts give $20$: ten teams with two choices of a marked member, or five choices of that member with four choices of a teammate. The identity is explained by the bijection between these descriptions, rather than merely verified through factorials.

The doubling constant of a nonempty finite set $S\subseteq G$ in an abelian group $G$ isIt measures the cardinality of the sumset relative to the original set. For the integer examples, $K(A)=7/4$ and $K(B)=10/4=5/2$. A nonconstant arithmetic progression with $n$ members has doubling constant $(2n-1)/n$, which stays below two as $n$ grows. This is the sense in which its sumset has small growth.

In any abelian group, $K(S)\ge 1$: fixing $s_0\in S$ puts a translated copy $s_0+S$ inside $S+S$. The stronger integer bound gives $K(S)\ge 2-1/|S|$ only in that setting. A finite subgroup $H$ has $K(H)=1$, as does every coset $x+H$, since its sumset is $2x+H$. In particular $H=\{0,2,4\}\subseteq \mathbb{Z}/6\mathbb{Z}$ has doubling constant one.

Small doubling constant is useful because it constrains repeated growth, as in the Plünnecke-Ruzsa inequality. It signals structure such as arithmetic progressions and subgroups; precise descriptions depend on the ambient abelian group and are the subject of the Freiman-Ruzsa theorem. The additive energy bound below gives a simpler immediate consequence: $E(S)\ge |S{|}^3/K(S)$.

For a finite set of $n$ vertices, a simple graph selects some of their unordered pairs as edges. There are $n(n-1)$ ordered pairs of distinct vertices; each unordered pair is counted twice, giving $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possibilities. Hence every simple graph $G$ on those vertices satisfieswith equality exactly when $G$ is a complete graph. The binomial coefficient also shows why the count grows quadratically with the number of vertices.

Two functions $f:A\to X$ and $g:B\to X$, whose domains lie in one ambient set, are equivalent modulo finite changes when $A△B$ is a finite set and the functions disagree at only finitely many points of $A\cap B$. The symmetric difference inclusion $A△C\subseteq (A△B)\cup (B△C)$ handles domains in a transitive chain. An exceptional set for values must also include points of $A\cap C$ absent from the middle domain $B$; these lie in the finite difference $A\setminus B$.

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

A finite alphabet is an alphabet whose symbols form a finite set. The binary alphabet $\{0,1\}$ and a finite vocabulary of possible messages are examples.

A finite coloring of a set $X$ is a function $c:X\to C$ into a finite set $C$ of colors. A subset is monochromatic when the restriction of $c$ to it is constant.

For a finite set $F\subseteq I$ and open sets $U_i\subseteq X_i$ for $i\in F$, the setsform a basis of a topology for the product topology. The empty set intersection is $X$. Each basic open set is a cylinder set; all coordinates outside $F$ are free. Arbitrary open sets are unions of these basic tests and need not themselves depend on one fixed finite collection of coordinates.^[ref]

Why finitely many? Any topology making the projection maps continuous must contain their preimages of open sets, and hence finite set intersections of those preimages. Taking arbitrary unions supplies exactly the product topology. Intersecting two basic cylinder sets still restricts only the finite union of their coordinate sets.

A vector space is finite-dimensional when it has a finite set as a basis.

Let $X$ be a finite set, let every singleton have positive probability, and let $T:X\to X$ preserve that probability measure. For every $x\in X$,so every $x$ has a preimage. Thus $T$ is a surjection, and every surjection from a finite set to itself is a bijection.

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.

A finite repetition-free sequence in a set $X$ is an injective function from an initial segment $\{0,\dots ,k-1\}$ of the natural numbers into $X$, including the empty sequence for $k=0$. For a finite set of size $m$, the number of these sequences isThe order of each list is part of the data, so it can be enumerated without choosing an order on its underlying support.

Here is an original reproducible finite set with 40 points and 512 coordinates. Let $e_1,\dots ,e_4$ be the first four vectors of the standard basis of ${\mathbb{R}}^{512}$. With point indices $i=0,\dots ,39$, generateThe four groups have different centers, and the standard normal random variables perturb all 512 coordinates. Generate the coordinates in row order using NumPy's PCG64 pseudorandom number generator with seed 20261013. Then keep this finite set fixed. A second PCG64 stream with seed 424242 generates a $32\times 512$ matrix of independent random variables with the standard normal distribution; divide it by $\sqrt{32}$ to obtain the Gaussian Johnson–Lindenstrauss transform.

For all 780 unordered pairs, compute the distance ratio $r_{ij}=\Vert T{x}_i-T{x}_j{\Vert }_2/\Vert x_i-x_j{\Vert }_2$. In this draw, its minimum is approximately $0.733010$ and its maximum $1.478785$, giving a maximum relative error in Euclidean distance of about $0.478785$. The squared-distance ratios $r_{ij}^2$ instead range from approximately $0.537304$ to $2.186806$: their maximum relative error is about $1.186806$. Thus this particular draw fails a 20% distance tolerance. The Johnson–Lindenstrauss lemma does not assert that every draw into 32 dimensions must succeed.

The two bands of original Euclidean distances distinguish pairs within a group from pairs between groups. Their spread after the linear map shows why checking an average distance is insufficient: the Johnson–Lindenstrauss lemma controls every pair. The dashed 20% distance band is an illustrative tolerance, not a confidence interval or a squared-distance band. The affine hull of 40 points has dimension at most 39; 512 is the ambient coordinate count, and no full-dimensionality assumption is required. For this draw the bi-Lipschitz distortion is approximately $1.478785/0.733010=2.017414$.

Now keep the same points and draw 48 fresh Gaussian Johnson–Lindenstrauss transforms for each target dimension $k\in \{8,16,32,64,128\}$. NumPy's SeedSequence(314159).spawn(240) supplies distinct PCG64 streams, ordered first by target dimension, then by draw. Each stream generates a new $k\times 512$ random matrix, normalized by $1/\sqrt{k}$; no map is a row prefix of another map. Each plotted value is

The observed median maximum relative errors in Euclidean distance are approximately $0.735$, $0.520$, $0.381$, $0.267$, and $0.184$, respectively. All pairs fall inside the 20% distance tolerance in $0$, $0$, $0$, $0$, and $35$ of the 48 draws, respectively. These are computations on one synthetic finite set, rather than optimal dimension bounds or measured physical data. The displayed quantiles describe the sampled maps; they do not certify a success probability for other sets. Even at 128 dimensions, 13 of the sampled maps fail this tolerance.

The practical benefit is that each point acquires fewer coordinates while its pairwise Euclidean distances can remain useful. The choice of target dimension balances compression, accuracy, and failure probability. For example, a conservative sufficient squared-distance tolerance $\epsilon =0.2$ with $n=40$ and $\delta =0.05$ gives $k\ge 1195$ by the explicit bound above. Here that exceeds the ambient dimension, so the identity map is better for a certified guarantee. The much smaller dimensions in the plots illustrate observed behavior without claiming that this sufficient bound is sharp.

A finite-state machine processes inputs using a finite set of automaton states and input-dependent automaton transitions. An automaton state records everything the machine remembers; an automaton transition says how that memory changes on the next symbol. A finite-state machine may also emit outputs. Here the emphasis is on recognizing a formal language: start in a designated automaton state, read a word from an alphabet, and accept exactly when the final automaton state is designated accepting.

Finite memory does not impose a maximum input length. A finite-state machine can read arbitrarily long words, revisiting its automaton states indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For divisibility by three, a word of binary digits can describe an enormous integer, yet its congruence class modulo three is all that the machine needs to retain. Two already-read words giving the same automaton state behave identically under every subsequent continuation in a DFA.

This makes finite-state machines useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a regular expression. The beautiful design question is which distinctions about the past matter to the future. DFA minimization makes that question precise by merging indistinguishable states of a deterministic finite automaton. Both DFAs and NFAs recognize exactly the regular languages.