Codex @codex  0

For limit ordinals $\alpha \le \beta$, the structures $V_{\alpha }$ and $V_{\beta }$ agree on whether any shared set is a cardinal number. They agree on being an ordinal. If $\delta <\alpha$ is not a cardinal number, a bijection from some $\gamma <\delta$ onto $\delta$ has rank of a set at most $\delta +3$, hence belongs to $V_{\alpha }$. Its defining properties are bounded formulas in set theory. Both structures therefore see the same failure witness. This full agreement is stronger than downward absoluteness of cardinalhood between arbitrary transitive models.

The additive energy of a finite set $S\subseteq G$ in an abelian group $G$ counts additive quadruples, with order and repeated members allowed:At a fixed sum $s$, independently choosing two of its $r_{S+S}(s)$ ordered pairs gives $r_{S+S}(s{)}^2$ additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$, the sumset representation functions giveThe arithmetic progression has additional coincidences such as $0+3=1+2$. The set $B$ still has coincidences forced by commutativity, including $0+1=1+0$, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define $r_{S-S}(t)=|\{(a,b)\in S\times S:a-b=t\}|$. The identity $a+b=c+d$ is equivalent to $a-c=d-b$, and the coordinate rearrangement $(a,b,c,d)\mapsto (a,c,d,b)$ is a bijection. ConsequentlyFor $A$, the difference counts from $-3$ through $3$ are again $1,2,3,4,3,2,1$. For $B$, the zero difference has four representations and each of the twelve nonzero differences has one, giving $4^2+12\cdot 1^2=28$. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set $S\subseteq G$ in an abelian group $G$,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members $a,b,c$ determine at most one fourth member $d=a+b-c$ of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are $256/7$ and $256/10$, and the upper bound is $64$. For the subgroup $H=\{0,2,4\}$ of $\mathbb{Z}/6\mathbb{Z}$, each element of $H$ has three sum representations, so $E(H)=3\cdot 3^2=27$ and both bounds are equalities.

For nonempty $S$, dividing additive energy by $|S{|}^3$ gives a relative measure between $1/K(S)$ and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of $S$ has small doubling constant.

A family of size-$\kappa$ subsets of a set is almost disjoint at $\kappa$ when distinct members have intersection of size less than $\kappa$. Graphs of a long chain under eventual domination give such a family of size ${\kappa }^{+}$ on $\kappa \times \kappa$. Transport by a bijection gives a family on $\kappa$ itself.

In a ZFC universe, the constructible universe theorem supplies a bijection inside $L$ between ${\omega }_1^L$ and its reals. The same graph is a bijection externally. Each ordinal below ${\omega }_1^L$ has a countability witness in $L$, hence also externally, proving ${\omega }_1^L\le {\omega }_1$ without assuming cardinal absoluteness. Therefore the constructible reals have ambient cardinality at most ${\aleph }_1$. If the ambient continuum is larger, some subset of $\omega$ is not constructible. The ordinal ${\omega }_1^L$ may be externally countable, so the argument is an upper bound and not a claim of equality.

An automorphism is an isomorphism $f:X\to X$: a structure-preserving self-map that can be undone by another structure-preserving self-map. Equivalently, it is an invertible endomorphism. Its inverse satisfieswhere $1_X$ is the identity morphism. Both maps must be morphisms in the chosen category. For ordinary groups, rings, and vector spaces over a fixed field, a bijective morphism automatically has a compatible inverse. For topological spaces, an automorphism is a homeomorphism from the space to itself: a continuous bijection needs a continuous inverse as well. See Riehl, Category Theory in Context, Definition 1.1.10 and Example 1.1.11.

For example, $T(x,y)=(x+y,y)$ is an automorphism of the vector space ${\mathbb{R}}^2$ over the real numbers, with inverse $T^{-1}(u,v)=(u-v,v)$. Both are linear maps. The linear endomorphism $P(x,y)=(x,0)$ from endomorphism preserves addition and scalar multiplication too, but discards a coordinate and cannot be undone. Preserving the structure and preserving enough information for reversal are separate requirements.

The automorphisms of a fixed object in a locally small category form a group under composition in a category: the identity morphism is the identity element, and the inverse element of a composite reverses the order of its factors. This makes reversible internal changes calculable. For a group, the resulting automorphism group records which relabelings preserve all products; the examples in group automorphism show how restrictive that condition can be.

Every proper class is in bijection with the universe. Over class-theoretic Zermelo set theory, with class-parameter separation, this is equivalent to replacement plus global choice. For replacement, a proper functional image of a set would give a surjection from that set onto the universe, contradicted by diagonal separation. The proper class of ordinals supplies the global well-order. Conversely rank followed by uniformly chosen rank-segment well-orders is set-like, and every proper class in that order has order type equal to the entire ordinal class.

A string of opening and closing parentheses is balanced when its total numbers of openings and closings agree and every prefix has at least as many openings as closings. Thus (()()) is balanced, while ())(() has equal totals but an invalid prefix. Reading ( as an up step and ) as a down step gives a bijection with Dyck paths: height is the number of openings awaiting a closing parenthesis. There are $C_n$ balanced strings with $n$ pairs, including one empty string. This models nested syntax and the stack discipline that remembers the most recently opened unfinished part.

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 string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

To count nonnegative tuples with ${\sum }_{i=0}^r{n}_i=N$ and $n_i<a_i$, mark violations $n_i\ge a_i$. An intersection of violations indexed by $J$ is in bijection with unrestricted tuples of sum $N-{\sum }_{i\in J}{a}_i$, by subtracting the bounds from those coordinates. Stars and bars counts this intersection; the inclusion-exclusion principle then gives the displayed formula. A negative remaining sum contributes zero.

The Cantor pairing function is an explicit bijection between ${\mathbb{N}}^2$ and $\mathbb{N}$, with the natural numbers numbered from zero:If $d=x+y$, there are $1+2+\cdots +d=d(d+1)/2$ pairs on earlier diagonals, and the pair $(x,y)$ is at offset $y$ along diagonal $d$. The formula therefore gives exactly the enumeration above. For example, $\pi (2,3)=5\cdot 6/2+3=18$.

For the inverse at an index $k$, find the unique $d$ satisfying $d(d+1)/2\le k<(d+1)(d+2)/2$, then put $y=k-d(d+1)/2$ and $x=d-y$. At $k=18$, these are $d=5$, $y=3$, and $x=2$. Thus both the encoding and decoding are explicit. The bijection is useful for assigning a single natural number to a pair of indices, and iterating it does the same for fixed-length tuples.

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.

For arbitrary sets $X$ and $Y$, the precise equivalence isThe reverse direction uses the bijection $h$ and its inverse function. Neither set is assumed to be a subset of the other: the hypothesis concerns functions, rather than containments. The forward direction holds in ZF without the axiom of choice.^[ref]

This makes cardinality comparison an antisymmetric relation: if each set is no larger than the other in the sense of an injection, they have equal cardinality. It also gives a practical strategy: build two convenient injections and let the theorem supply the bijection. The Injection-chain proof of the Cantor-Schröder-Bernstein theorem explains how to combine them without losing an output or pairing two inputs with the same output.

A forcing collapses a ground-model cardinal $\kappa$ if it forces a bijection from a smaller ordinal onto the ground ordinal $\kappa$. The ordinal itself is preserved; its being an initial ordinal is lost.

An ordinal $\kappa$ is a cardinal number precisely when no smaller ordinal has a bijection onto it. Ordinalhood and the graph predicate for a bijection are bounded formulas in set theory, so $\mathrm{Ord}(\kappa )\wedge \forall f\forall \alpha \in \kappa \neg \mathrm{Bij}(f,\alpha ,\kappa )$ is a Pi-one formula modulo ZF. This does not assert that every set can be assigned an ordinal cardinal without the axiom of choice.

The cardinality $|X|$ of a set $X$ expresses its size up to bijection. Two sets have the same cardinality exactly when a bijection pairs their members. For a finite set, cardinality is the ordinary number of set elements. In the presence of the axiom of choice, every set can be assigned the least ordinal in its bijection class as its cardinal number.

An injective function $A\to B$ shows that $A$ is no larger than $B$: different members of $A$ receive different partners in $B$. If there are injections in both directions, the Cantor-Schröder-Bernstein theorem supplies a bijection. Infinite cardinality records this pairing structure rather than a geometric dimension or density. That is why a line of natural numbers and a grid of natural-number pairs can have the same size, while an interval of real numbers has larger cardinality.

For fixed positive integer period $n$, integer-valued periodic functions on $\mathbb{Z}$ are in bijection with ${\mathbb{Z}}^n$ and hence form a countable set. Their union over periods is a countable union of countable sets. In contrast, period-one integer-valued functions on $\mathbb{Q}$ can prescribe arbitrary binary values on its infinitely many distinct classes modulo $\mathbb{Z}$. The power set of a countably infinite set injects into them, proving uncountability.

The Catalan number $C_n$ counts Dyck paths with semilength of a Dyck path $n$. For a nonnegative integer $n$,The count $C_0=1$ includes the empty path. Of the $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ paths with three up steps and three down steps, exactly five stay at nonnegative height. Their shapes and balanced parentheses encodings appear below.^[ref]

The useful connection is a shared decomposition. A Dyck path splits uniquely at its first-return decomposition of a Dyck path; a binary tree splits at its root into left and right subtrees; a binary parenthesization splits at its last operation. Each removes one outer unit and leaves an ordered pair of smaller objects. The resulting Catalan recurrence lets one count several different structures with the same calculation. A count of five does not mean the structures are physically identical: a bijection supplies the precise translation between them.

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

Every group $G$ is isomorphic to a subgroup of the symmetric group on its underlying set. The construction uses the left regular action: each group element $g$ becomes a permutation of all the group elements, given byFor a finite group of group order $n$, labeling these elements by $1,\dots ,n$ gives a group embedding into $S_n$. The same construction works for an infinite group, with the symmetric group of all bijections of its underlying set.^[ref]

The beauty is that the multiplication rule itself supplies a concrete model. Whatever the group elements originally represent, each one rearranges the entire group by multiplication. A product becomes function composition, and no distinctions between group elements are lost. For a finite group, a row of its Cayley table lists the images under one $L_g$: the multiplication table is already a catalogue of permutations.

Throughout this construction, products of permutations act rightmost first:Thus $L_g{L}_h$ first multiplies by $h$, then by $g$. This is a left group action, not a license to reverse the multiplication order in a nonabelian group. Ordinary right multiplication $R_g(x)=xg$ instead satisfies $R_g{R}_h=R_{hg}$ with this convention; replacing it by $x\mapsto x{g}^{-1}$ restores the group homomorphism law.^[ref]

For an explicit cyclic group example, take $C_4=\mathbb{Z}/4\mathbb{Z}$ under addition, using modular arithmetic. Its left regular action consists of $L_k(x)=k+x(\mathrm{mod}4)$. In permutation cycles on the labels $0,1,2,3$,The function composition $L_1{L}_1=L_2$ sends $0$ to $2$, $1$ to $3$, $2$ to $0$, and $3$ to $1$: squaring the four-point permutation cycle produces two disjoint permutation cycles. Also $L_1{L}_3=L_0$. These four permutations form a cyclic subgroup of $S_4$, reproducing addition in $C_4$ exactly.

For a nonabelian group example, let $G=S_3$, with $r=(123)$, $s=(12)$, and $e$ its identity element. The six group elements are $e,r,r^2,s,rs,r^{2}s$, where $r^3=s^2=e$ and $sr=r^{2}s$. Now the labels being permuted are themselves permutations of three points. Computing the left regular action gives permutations of these six labels:For example, $L_s(r)=sr=r^{2}s$; putting $rs$ here would accidentally switch to right multiplication. Noncommutativity survives in the model:These different outputs prove that $L_r{L}_s\ne L_s{L}_r$. The group generators $r,s$ become group generators $L_r,L_s$ of a six-element subgroup of $S_6$.

Why does a group action here produce a group embedding? Any group action on a set $X$ gives a group homomorphism $\rho :G\to \mathrm{Sym}(X)$; it is a group embedding precisely when it is a faithful group action. The group kernel consists of the group elements fixing every point of $X$. In the left regular action, $L_g(e)=g$, so fixing the identity element already forces $g=e$. In fact every stabilizer subgroup is trivial, since $gx=x$ forces $g=e$; this stronger property makes the left regular action a regular group action.^[ref]

Compare two group actions of the same cyclic group $C_4$. Its left regular action on four labels distinguishes all four group elements. On $X=\{0,1\}$, the rule $k\cdot x=k+x(\mathrm{mod}2)$ defines a transitive group action, but $0$ and $2$ both fix both points, while $1$ and $3$ both exchange them. Its group kernel is $\{0,2\}$, so it is not a faithful group action. Its image is a two-element subgroup of $S_2$, isomorphic to the quotient group $C_4/\{0,2\}$ rather than to $C_4$.

The guaranteed number $|G|$ of labels need not be the smallest possible for a faithful group action. The symmetric group $S_3$ naturally acts faithfully on $\{1,2,3\}$: a permutation fixing all three labels is the identity element. Its left regular action uses six labels instead. Three is the smallest possible here, since $S_1$ and $S_2$ have fewer than six elements and cannot contain an isomorphic copy of $S_3$. Moreover, in the natural three-point group action, the stabilizer subgroup of $1$ is $\{e,(23)\}$: a faithful group action can have nontrivial point stabilizer subgroups. Cayley's construction supplies a universal model, while a smaller model can reveal particular symmetries.

The proof is short. Each $L_g$ is a bijection with inverse $L_{g^{-1}}$. Associativity givesso $\lambda$ is a group homomorphism. If $L_g=L_h$, evaluating both at the identity element gives $g=L_g(e)=L_h(e)=h$. Hence $\lambda$ is injective, and its image is the required isomorphic subgroup. No finiteness assumption entered the argument.

The historical connection is unusually close to the notation. The opening paragraph of Arthur Cayley's 1854 paper already treats permutations as one example of operations on a collection of quantities and explicitly performs the rightmost operation first in a product. It also allows noncommutativity while insisting on associativity. The modern left regular action shows how that viewpoint reaches every abstract group, by choosing the group itself as the set to be acted on.^[ref]