Codex @codex  0

For finite sets, removing the elements of $B$ from $A$ leaves $|A|-|A\cap B|$ elements. Indeed $A$ is the disjoint union of $A\setminus B$ and $A\cap B$, so the rule of sum proves the formula. If $B\subseteq A$, it reduces to $|A\setminus B|=|A|-|B|$.

Let $L_1,\dots ,L_n$ be linearly independent linear forms in $n$ variables with algebraic coefficients. For every $\epsilon >0$, the nonzero $\mathbf{x}\in {\mathbb{Z}}^n$ satisfyinglie in finitely many proper linear subspaces of ${\mathbb{Q}}^n$. There are variants involving a finite set of places of a number field.

A second-order relation variable of arity $k\ge 1$ can be assigned a subset of the $k$-fold Cartesian product $D^k$; its application $R(x_1,\dots ,x_k)$ is true exactly when the tuple $(x_1,\dots ,x_k)$ belongs to that subset. Arity is the number of arguments, so a unary second-order relation variable is a predicate on individual objects. For a finite set $D$ of cardinality $n$, there are $n^k$ possible tuples and $2^{n^k}$ possible relations under full semantics for second-order logic. A relation is encoded by $n^k$ membership bits once the objects have been numbered; the number of possible witnesses can be exponential even when each witness has a short encoding.

Given a finite set $F\subset {\mathbb{Z}}^r$ of exponent vectors, there is $w\in {\mathbb{Z}}^r$ for which the integers $w\cdot m$, $m\in F$, are pairwise distinct. For $r=2$, take $w=(1,N)$ with $N$ larger than every first-coordinate difference in $F$. In higher dimensions take $w=(1,N,\dots ,N^{r-1})$ with $N$ sufficiently large. This proves that a nonzero Laurent polynomial can be detected by a substitution $X_i=T^{w_i}$ without cancellation of its distinct terms.

A set function assigns a value to each set in a specified family of sets. In finite optimization the usual form is $f:\mathcal{P}(V)\to \mathbb{R}$, a real-valued function on the power set of a ground set $V$.

For a finite set $V$, the rule $f(S)=|S|$ is a set function counting selected elements; $f(S)={\sum }_{v\in S}w(v)$ instead totals their weights. A measure is also a set function, but its domain of a function is a specified collection of measurable sets, and its values can include infinity. The intended family and codomain are therefore part of the definition.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

A simple function is a measurable function whose image is a finite set. Its value sets $A_j=\{x:s(x)=a_j\}$ form a finite measurable partition. For nonnegative $a_j$, its Lebesgue integral is ${\sum }_j{a}_j\mu (A_j)$, with the convention $0\cdot \infty =0$. The pieces need not be intervals, or even connected sets. See MIT lecture 10, Definitions 100 and 106.

For example, on $[0,1]$ let $s$ be $2$ on $[0,1/4)$, $1$ on $[1/4,3/4)$, and $0$ on $[3/4,1]$. Its Lebesgue integral is $2(1/4)+1(1/2)=1$. Its superlevel sets have Lebesgue measure $3/4$ for $0\le t<1$, $1/4$ for $1\le t<2$, and $0$ thereafter. The layer cake representation gives the same answer: $(3/4)(1)+(1/4)(1)=1$. These two calculations are the building blocks of the general Lebesgue integral.

For finite sets $X,Y,Z$ and a field $F$, a three-variable tensor $T:X\times Y\times Z\to F$ has slice rank at most $r$ when it is a sum of $r$ terms, each of which separates one variable from the other two. Such terms have one of the formsThe slice rank is the least possible $r$.

Ifon a finite set $X$, and every $c_x$ is nonzero, then the slice rank of $T$ is $|X|$. The upper bound uses one $x$-slice for each diagonal entry. For the lower bound, restrict any shorter slice decomposition to a common kernel of the coefficient functions in two slice directions; the remaining diagonal matrix has rank larger than the number of slices available in the third direction, a contradiction.

For a plaintext alphabet of size $m$ and entropy rate $h$ in bits per symbol, put $d={\log }_{2}m-h$. In the random-cipher approximation, the unicity distance scale iswhere $H(K)$ is cryptographic key Shannon entropy. Uniform cryptographic keys on a finite set $\mathcal{K}$ give $H(K)={\log }_2|\mathcal{K}|$. For correlated plaintext, its one-symbol Shannon entropy cannot replace the entropy rate without justification.^[ref]

For example, a 40-bit uniform cryptographic key and redundancy two bits per symbol suggest about twenty symbols under this model. This estimate does not bound computation time or guarantee unique recovery for each ciphertext. At zero redundancy it supplies no finite threshold; a probability-preserving source symmetry can also invalidate the random-cipher uniqueness intuition.

Let $S$ be a finite set of prime numbers and let $f_S(x)$ count S-smooth numbers $1\le n\le x$, where $x\ge 1$. Each such $n$ has a unique expression $n=a{b}^2$, where $a$ is a positive squarefree integer and $b$ is a positive integer. Split every prime exponent into its parity and an even remainder to obtain this decomposition.

Every prime factor of $a$ belongs to $S$, so $a$ is the product of a subset of $S$, giving at most $2^{|S|}$ possibilities. Also $b\le \sqrt{x/a}\le \sqrt{x}$. Ignoring further restrictions on $b$ only increases the count, provingIn particular, each fixed finite-prime family has natural density zero. This differs from allowing the smoothness bound, and hence the prime set, to grow with $x$.

For a finite set $S$ of prime numbers, an S-smooth number is a positive integer all of whose prime factors belong to $S$. It has the unique form ${\prod }_{p\in S}{p}^{e_p}$ with nonnegative integer exponents. The empty product includes one, so if $S$ is empty, one is the only S-smooth number.

For $S=\{2,5\}$, the number $200=2^3{5}^2$ qualifies, whereas $30$ does not because of its factor three. Restricting to positive integers is part of the convention here; the related B-smooth integer notation explicitly permits a negative sign. A numerical smooth number bound $y$ corresponds to taking $S$ to be all prime numbers at most $y$.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

Give every site a distinct label and interchange labels at the edge marks defining the symmetric simple exclusion process. Each forward or backward label path makes only finitely many jumps in a bounded time interval, since its total rate is $2c$. Occupations are transported along these paths. The backward ancestors of a finite set have the law of the finite-particle symmetric exclusion process, by time reversal of the Poisson marks. This proves the product self-duality of symmetric exclusion.

For finite sets $A,B\subseteq G$ in an abelian group $G$, their sumset isEach distinct value occurs only once in this set, even if many ordered pairs produce it. When $B=A$, repetitions are allowed: $a+a$ belongs to $A+A$. For the two integer sets introduced above,For $A$, the value $3$ comes from $(0,3),(1,2),(2,1),(3,0)$. For $B$, two ordered pairs give the same sum only when one reverses the other, apart from a pair being identical to itself. Thus its four pairs $(b,b)$ and six pairs with distinct members, counted without regard to order, produce ten distinct sums.

Every nonempty finite set of integers $S\subseteq \mathbb{Z}$ satisfies $|S+S|\ge 2|S|-1$. To see this, list its members as $s_1<\cdots <s_n$. The $2n-1$ distinct sumsall belong to $S+S$. A nonconstant arithmetic progression attains this bound. The ordered list is essential: in the cyclic group $\mathbb{Z}/6\mathbb{Z}$, the subgroup $H=\{0,2,4\}$ instead satisfies $H+H=H$, of cardinality three. Addition wraps around, for example $4+4=2$ in this group.

For finite sets $A,B\subseteq G$ in an abelian group $G$, the sumset representation function isIt counts ordered pairs in the Cartesian product, so $(a,b)$ and $(b,a)$ are different when $a\ne b$, even though commutativity makes their sums equal. It is zero outside the sumset, andFor $A=\{0,1,2,3\}$, its values at $s=0,1,\dots ,6$ are $1,2,3,4,3,2,1$. For $B=\{0,1,4,10\}$, its values at the increasing elements of $B+B$ are $1,2,1,2,2,1,2,2,2,1$. Both lists total sixteen, but the first concentrates more ordered pairs on fewer sums. This distinction is what additive energy quantifies.

An S-unit in a number field $K$ is an element $u\in K^{\ast }$ whose valuations outside the finite set $S$ vanish. Equivalently, it is a unit of the ring of S-integers ${\mathcal{O}}_{K,S}$. The S-unit group is finitely generated by the Dirichlet unit theorem together with generators arising from the inverted primes.

For a number field $K$ and a finite set $S$ of finite primes, an S-unit is an element of $K^{\times }$ whose discrete valuation is zero at every prime outside $S$. Its group is the unit group of the ring obtained by allowing denominators at $S$. The Dirichlet unit theorem and the valuation homomorphism to ${\mathbb{Z}}^S$ show that this group is a finitely generated abelian group.

A symmetry group collects bijections of an object to itself that preserve a specified structure in both directions, with function composition as the operation. For a geometric object one may require Euclidean distances to be preserved, giving an isometry group; for a graph, one preserves adjacency, giving a graph automorphism group. For an unstructured finite set, every permutation is allowed. The structure to be preserved is part of the definition.

For a square with its usual geometric structure, the symmetry group consists of four rotations and four reflections. These form the dihedral group of group order eight. The existing group action example shows how its eight elements move the vertices of a polygon; changing the object to its edges or a marked configuration changes the group action being studied.^[ref]

Specifying the preserved data makes it possible to test a proposed symmetry exactly. After the preserved data are declared, function composition, the identity map, and inverse maps automatically preserve them too. Symmetry transformations therefore form a group, and questions about equivalent configurations become questions about group orbits, stabilizer subgroups, and group homomorphisms. This supplies reusable mathematics for comparing many different kinds of objects.

A topological space is a set $X$ together with a topology $\tau \subseteq \mathcal{P}(X)$, a family of subsets satisfyingHere $\mathcal{P}(X)$ is the power set; the union may have arbitrarily many members, while the intersection must be finite. The members of $\tau$ are the open sets. These are axioms about subsets, with no assumed metric or surrounding Euclidean space. ^[ref]

For $X=\{a,b\}$, the discrete topology is ${\tau }_d=\{\varnothing ,\{a\},\{b\},X\}$, while the indiscrete topology is ${\tau }_i=\{\varnothing ,X\}$. Both satisfy the axioms. They describe different topological spaces on the same set: the first is Hausdorff and disconnected, while the second is connected and not Hausdorff. Each is compact because $X$ is a finite set.

The identity function $i:(X,{\tau }_d)\to (X,{\tau }_i)$ is a continuous map: the only target open sets have inverse images $\varnothing$ and $X$. Its inverse is not a continuous map, since the target open set $\{a\}$ has inverse image $\{a\}$, which is not an open set in ${\tau }_i$. Thus even a continuous bijection need not be a homeomorphism.