Absoluteness of cardinalhood in limit ranks Created 2026-10-05 Updated 2026-10-06
For limit ordinals , the structures and agree on whether any shared set is a cardinal number. They agree on being an ordinal. If is not a cardinal number, a bijection from some onto has rank of a set at most , hence belongs to . 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.
Additive energy Created 2026-09-24 Updated 2026-10-13
The additive energy of a finite set in an abelian group counts additive quadruples, with order and repeated members allowed:At a fixed sum , independently choosing two of its ordered pairs gives additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.
For and , the sumset representation functions giveThe arithmetic progression has additional coincidences such as . The set still has coincidences forced by commutativity, including , so its additive energy is not merely the sixteen identical-pair comparisons.
The same additive energy can be counted using the difference set. Define . The identity is equivalent to , and the coordinate rearrangement is a bijection. ConsequentlyFor , the difference counts from through are again . For , the zero difference has four representations and each of the twelve nonzero differences has one, giving . The sumset representation functions for sums and differences can look different while their squared totals agree.
For every nonempty finite set in an abelian group ,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members determine at most one fourth member 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 and , and the upper bound is . For the subgroup of , each element of has three sum representations, so and both bounds are equalities.
Sumset and difference-set sizes alongside additive energy and its bounds, including a cyclic subgroup
. Details. For nonempty , dividing additive energy by gives a relative measure between 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 has small doubling constant.
Adjoint lifting theorem for monad algebra functors Created 2026-10-07 Updated 2026-11-05
Let and be monads on categories and , with forgetful functors . Suppose and satisfy . If and has coequalizers of reflexive pairs, then has a left adjoint . Thus the square must specify an actual lifting to Eilenberg-Moore categories; the required coequalizers are taken in the category of algebras.[ref]
Topos Theory by Jaap van Oosten (2018). Theorem0.11, printed pp.x–xii: lifting square, adjunction and reflexive-coequalizer hypothesis
Writing for the free algebra functors, the construction starts withbecause the adjunctions give natural bijectionsAn algebra for a monad has the reflexive free-algebra presentation of a monad algebra . Transporting its two arrows through these bijections gives a reflexive pair between and ; its coequalizer defines . The universal property supplies .
This explains the theorem’s use in constructing adjoints of logical functors through power-object monadicity: the algebra presentation makes the missing adjoint explicit.
Almost disjoint family on a regular cardinal Created 2026-10-07 Updated 2026-10-14
In a ZFC universe, the constructible universe theorem supplies a bijection inside between and its reals. The same graph is a bijection externally. Each ordinal below has a countability witness in , hence also externally, proving without assuming cardinal absoluteness. Therefore the constructible reals have ambient cardinality at most . If the ambient continuum is larger, some subset of is not constructible. The ordinal may be externally countable, so the argument is an upper bound and not a claim of equality.
Automorphism Created 2026-09-24 Updated 2026-10-14
An automorphism is an isomorphism : a structure-preserving self-map that can be undone by another structure-preserving self-map. Equivalently, it is an invertible endomorphism. Its inverse satisfieswhere 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, is an automorphism of the vector space over the real numbers, with inverse . Both are linear maps. The linear endomorphism 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.
Axiom of limitation of size 2026-10-14
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.
Balanced parentheses 2026-10-14
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 balanced strings with pairs, including one empty string. This models nested syntax and the stack discipline that remembers the most recently opened unfinished part. Bijection Created 2026-09-24 Updated 2026-10-14
A bijection 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 , , is a bijection from to , whereas adding an unused target 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 from the integers to the even integers, with inverse on that specified codomain. A proper subset can therefore have the same cardinality as an infinite set. [ref]
https://discrete.openmathbooks.org/preview/sec_intro-functions.html. Levin, functions: injections, surjections and bijections
. Binary string Created 2026-10-06 Updated 2026-10-20
A binary string is a finite word over the alphabet . There are strings of length . Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.
Binomial coefficient Created 2026-09-24 Updated 2026-10-13
For nonnegative integers and , the binomial coefficientcounts the -element subsets of an -element set. To obtain the formula, first choose an ordered list of different members in ways. Each subset appears in exactly orders, so divide by that factorial. The cases and each have one selection, the empty set and the whole set. For integer outside , the combinatorial convention is .
For , , the calculation is . The left-hand panel lists all ten subsets of . 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 . Uniform selection of a -element subset similarly gives inclusion probability for each member when , as the double counting identity shows.
Bounded weak compositions Created 2026-10-07 Updated 2026-10-14
To count nonnegative tuples with and , mark violations . An intersection of violations indexed by is in bijection with unrestricted tuples of sum , 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.
Brauer first main theorem Created 2026-10-03 Updated 2026-11-05
Canonical graph labeling 2026-11-05
Canonical graph labeling computes a standardized labeled representative of a graph, with a fixed convention that assigns identical representatives exactly to isomorphic graphs. For finite graphs, a labeling is a bijection from the original vertices to a standard set such as . A canonicalization procedure chooses a representative adjacency structure, not simply the order in which vertices happened to be supplied.
One explicit convention labels a finite undirected simple graph in every possible way and chooses the lexicographically least upper-triangular adjacency matrix string. The article complete graph invariant proves that this representative, together with vertex count, determines the graph up to graph isomorphism. Efficient software seeks the same kind of isomorphism-invariant representative without literally enumerating every permutation. The authors' nauty and Traces project identifies canonical labeling and graph-automorphism computation as supported tasks.[ref]
nauty and Traces by Brendan McKay and Adolfo Piperno. project overview and Documentation
An original three-vertex path makes a subtle distinction visible. In the edge-string order , the least string is . It puts the central vertex at label3 and the two leaves at labels1and2. Either assignment of the two original leaves gives the same canonical adjacency matrix. The representative is fixed, while the map from original vertices to labels need not be unique.
This ambiguity is forced by graph automorphisms. If an automorphism exchanges two indistinguishable vertices, no injective vertex-naming rule can both remain unchanged by that exchange and give the two vertices different names. More formally, requiring for every automorphism forces whenever is injective. A graph with a nontrivial automorphism therefore cannot have fully symmetry-invariant distinct names for all original vertices.
Canonical graph labeling instead requires the resulting labeled graph to be invariant under relabeling of the input. A returned vertex permutation may select one among equivalent choices. For a triangle, all six labelings give the same adjacency matrix, while six different input-to-label maps remain possible.
Vertex colors, directed edges or other attributes must be included in the structure if the desired isomorphisms are to preserve them. Comparing outputs from different canonicalization conventions or program options also needs care: identical invariance goals do not require every implementation to choose the same representative.
Cantor pairing function Created 2026-09-24 Updated 2026-10-14
The Cantor pairing function is an explicit bijection between and , with the natural numbers numbered from zero:If , there are pairs on earlier diagonals, and the pair is at offset along diagonal . The formula therefore gives exactly the enumeration above. For example, .
Cantor-Schröder-Bernstein theorem Created 2026-09-24 Updated 2026-10-18
For arbitrary sets and , the precise equivalence isThe reverse direction uses the bijection 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]
Cantor-Schroeder-Bernstein Theorem by Paul Garrett. Paul Garrett, Cantor-Schroeder-Bernstein Theorem, p. 1, theorem and paragraph explicitly excluding the axiom of choice
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.
Cardinal collapse 2026-10-06
Cardinalhood is Pi-one definable 2026-10-06
An ordinal 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 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.
Cardinality Created 2026-10-03 Updated 2026-10-14
The cardinality of a set 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 shows that is no larger than : different members of receive different partners in . 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.
Cardinality of integer-periodic function spaces Created 2026-10-07 Updated 2026-11-05
For a fixed positive integer , integer-valued periodic functions on with period are in bijection with : record the values at and repeat. This is a countable set. Allowing any positive integer period gives a countable union of countable sets, which is still countable.
On the rational numbers the answer differs even with period one. Every rational number has a unique representative modulo in , and that representative set is a countably infinite set. Assigning arbitrary binary values to those representatives and extending periodically gives an injection from its power set into integer-valued period-one functions on . Thus there are uncountably many. The difference is the number of residue classes to which values can be assigned independently.

