The first-order theory of a bijection with named inverse and no finite cycles has first-order models consisting of disjoint integer orbits. Atomic logical formulas reduce to for integer . An existential logical variable is either fixed by such a logical equality or must avoid finitely many points. This proves quantifier elimination and completeness. There is one complete one-type; the complete two-types are the integer offsets and the nonprincipal different-orbit partial type. There are countably many finite-arity partial types but countable first-order models with different numbers of orbits are not isomorphic.
Proof. Delete a perfect matching . The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection . Replace each by the graph path . The four vertices are distinct: the successor edges are not in , neither is a self-loop, and injectivity of excludes . Every edge of appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.
Topological order Created 2026-10-14 Updated 2026-11-05
A topological order of a finite directed graph is a sequence containing every vertex exactly once, with
Thus every directed edge points forward in the list. Equivalently, a bijection assigning positions satisfies for every directed edge . A topological ordering names the same kind of list. [ref]
The toy directed acyclic graph has exactly five topological orders: , , , , and . These lists were checked by enumerating all permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with , since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: and are consecutive in without a directed edge between them.
A directed cycle would force the impossible chain of position inequalities . In the toy example, adding requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a directed acyclic graph. The empty directed graph has the empty sequence as its topological order.
There is also a useful connection to partial orders: define when or there is a directed path from to . For a directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.
Topological space Created 2026-09-24 Updated 2026-10-14
A topological space is a set together with a topology , a family of subsets satisfying
Here is the power set; the union may have arbitrarily many members, while the intersection must be finite. The members of are the open sets. These are axioms about subsets, with no assumed metric or surrounding Euclidean space. [ref]
Figure 1.
Two topologies on the same two-point set and continuity of the identity map
. Details.
For , the discrete topology is , while the indiscrete topology is . 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 is a finite set.
The identity function is a continuous map: the only target open sets have inverse images and . Its inverse is not a continuous map, since the target open set has inverse image , which is not an open set in . Thus even a continuous bijection need not be a homeomorphism.
Topology Created 2026-09-24 Updated 2026-10-18
Topology studies topological spaces through open sets and continuous maps. Its central equivalence is a homeomorphism: a bijection that preserves continuity in both directions. This lets us distinguish spaces by connectedness or compactness even when numerical metric values are irrelevant. The open interval and the real line have the same topology in this sense, although only the former is a bounded set with its usual metric.
Figure 1.
Homeomorphisms, inverse images, and the effect of removing a point
. Details.
The upper panels show an explicit homeomorphism and the inverse image test for a continuous map. The lower panels exhibit an obstruction to a homeomorphism: removing any point from a circle leaves a connected space, whereas removing an interior point from a closed interval gives two connected components.
Homotopy is a different notion: it varies a continuous map continuously with a parameter and may collapse points. For example, contracts to zero. Thus this closed interval and a singleton have the same homotopy type, but there is no homeomorphism between them because there is no bijection. Homotopy equivalence need not preserve compactness. [ref]
The abstract viewpoint already appears explicitly in Tietze's 1923 paper: he describes topology as the study of properties invariant under invertible continuous maps with continuous inverses, and discusses axioms for neighbourhoods, citing Hausdorff's 1914 book, page 213. [ref]
Top-to-random card shuffle Created 2026-10-03 Updated 2026-11-05
The Top-to-random card shuffle removes the top card and inserts it in one of the positions uniformly. Its Stationary distribution is uniform on permutations. Each move is the inverse of a move of the Random-to-top card shuffle, so these chains are time reversals under that Stationary distribution.
In this group-walk setting they also have the same total variation mixing profile. Starting from the identity permutation, a random-to-top path multiplies independent identically distributed increments . The top-to-random increments have their inverse law. Reversing the order of an iid list leaves its joint law unchanged, so the product of inverse increments has the law of . Inversion is a bijection preserving the uniform distribution; it therefore preserves total variation distance to that distribution. Translation symmetry makes the distance independent of the starting permutation.
Consequently top-to-random shares the cutoff scale and order- window of random-to-top. The group symmetry is essential to this argument: time reversal alone does not give equality of worst-case total variation profiles for arbitrary Markov chains.
Totient divisor-sum identity Created 2026-10-14 Updated 2026-11-05
The divisor sum of Euler's totient function is the identity arithmetic function:
Equivalently, under Dirichlet convolution, with the constant-one arithmetic function. [ref]
To see why, group the integers by . Each is a positive integer divisor of . Within its group, with and , by the scaling identity for greatest common divisors. Dividing by gives a bijection with the integers counted by . The groups form a partition of a set, so
For , the groups with greatest common divisor are respectively . Their sizes are , totaling . Möbius inversion reverses this divisor sum to recover Euler's totient function from .
Choosing a new origin in a vector space transports its operations along . Since and , every vector space axiom transfers through this bijection. The new additive identity is and the additive inverse of is . This illustrates why an affine space has no preferred origin even though choosing one produces a vector space.
For a subset of a group and , its left translate is and its right translate is . In an additive abelian group, these are the same translated set . Multiplication by is a bijection, so translation preserves cardinality.
Left and right translates can differ in a noncommutative group. In the symmetric group , take and , composing permutations right to left. Then while . When is a subgroup, these translated sets are precisely left and right cosets. Translation lets additive combinatorics compare configurations without treating their absolute location as part of their shape.
Translation in a group Created 2026-09-24 Updated 2026-11-05
Left and right multiplication by a fixed group element are bijections, called left and right translations.
Both translations are bijections because the inverse element gives the inverse multiplication operation.
Take the circle with its subspace topology. Write for its west point and for its east point. Two coordinate charts obtained by stereographic projection are
Both take values in the entire real line. Geometrically, join to and intersect the resulting line with : the height is . Projecting from instead gives height . Each projection omits its own starting point, but the other coordinate chart includes that point. Hence .[ref]
Figure 1.
Two stereographic charts cover the circle and unfold it onto two real lines
. Details.
To verify the homeomorphisms, solve the displayed equations for . The inverse functions are
Each formula lies on the circle, avoids its excluded point, and is continuous for every real argument. Substitution into the projection formulas returns or ; substitution in the other direction returns . Thus these are continuous bijections with continuous inverse functions, as required for coordinate charts. Since the Euclidean plane is Hausdorff and second countable, the subset with its subspace topology is too. This checks all three conditions for a topological manifold, rather than just drawing a smooth-looking curve.
On the overlap , both are excluded, so . Using , the topological transition map is
For example, has and . The two connected components of the overlap, the upper and lower arcs, correspond to the positive and negative parts of the punctured real line. The values and represent and , respectively, and belong to only one chart each. The reciprocal coordinate change and its inverse function are smooth functions away from zero, so this topological atlas also supplies a smooth atlas.
Why can neither chart be enlarged to a single coordinate chart on the whole circle? The circle is a closed set and a bounded set in the Euclidean plane, hence compact by the Heine-Borel theorem. A global coordinate chart would give a homeomorphism to a nonempty open set . Its image would be compact and therefore closed in the real line. By connectedness of the real line, this forces , which is not compact. This is the one-dimensional instance of no compact manifold has a single Euclidean chart. Locally the circle is indistinguishable from the real line; globally compactness obstructs a single chart.
The bijections of a countably infinite set form an uncountable set. Partition an enumeration into disjoint pairs and encode an infinite binary sequence by independently fixing or swapping each pair.
Uncountable set Created 2026-09-24 Updated 2026-10-14
An uncountable set is a set for which no bijection with a subset of the natural numbers exists.
For , choose independent random variables, each with the uniform distribution on a finite set , and decode their values as a Prüfer sequence. Every sequence has probability , and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. [ref]
This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability and the path graph shape has probability . Also, for a fixed label , the Prüfer degree formula gives
Here the binomial distribution counts the independent code positions equal to . The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When , simply return the single isolated vertex.
Unimodular matrix Created 2026-09-24 Updated 2026-10-14
A unimodular matrix is a square integer matrix whose determinant is or . The decisive property is that its inverse matrix also has integer entries: multiplication by gives a bijection of the integer lattice onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.[ref]
For an original two-dimensional example, take
Its determinant is one, and it maps to . Conversely, the integer point comes from . For instance, has new coordinates relative to the columns and . No integer point disappears, although the basis vectors and their fundamental cell change shape.
Figure 1.
Two lattice bases generate exactly the same integer points
. Original drawings of the standard basis and the columns of . Both displayed cells have area one. The point has coordinates in the standard basis and in the sheared basis. Details.
This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.
A determinant of is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.
Two representations of a functor have unique mutually inverse morphisms carrying their specified universal elements to one another. Composing those morphisms preserves each universal element, so injectivity of the representing bijection makes the composites identities. Arbitrary isomorphisms of the underlying objects need not preserve the specified elements.
The universal countable uniform hypergraph is the unique, up to hypergraph isomorphism, countably infinite -uniform hypergraph with the hypergraph extension property. To prove uniqueness, enumerate two such structures and construct finite partial hypergraph isomorphisms. Alternately add the least unused vertex of the first enumeration to the domain and the least unused vertex of the second to the range. Prescribe its incidences with every -subset of the already matched vertices and apply the extension property in the other structure. The resulting union is a bijection preserving every hyperedge and nonedge. Existence follows from the countable random uniform hypergraph construction. A construction with only the forward steps embeds every countable -uniform hypergraph as an induced subhypergraph, explaining the word universal. Its isomorphism type is independent of .
An unlabelled combinatorial structure is a combinatorial structure considered up to an appropriate isomorphism, so the names assigned to underlying elements do not distinguish objects. For graphs, this means a bijection of vertices preserving adjacency. A different drawing or vertex numbering can therefore represent the same unlabelled graph.
On three labelled vertices there are simple graphs, but only four unlabelled types: the empty graph, one edge with an isolated vertex, the two-edge path, and the triangle. Simply dividing eight by cannot work because these types have different numbers of automorphisms.
More generally, relabelling gives a group action of the symmetric group on labelled structures. Unlabelled structures are its orbits, and the orbit-stabilizer theorem explains how automorphisms affect orbit size. Burnside's lemma counts the orbits by averaging fixed-point counts.
A verifier in an interactive proof is the efficient participant that evaluates a public statement using messages from a prover in an interactive proof and its own random choices. Its algorithm specifies which challenge to send, how to process the response and when to accept or reject. In the standard model it runs in probabilistic polynomial time in the public input length.[ref]
The verifier's guarantee concerns more than one successful conversation. Completeness of an interactive proof requires a suitable honest prover to succeed on true statements. Soundness of an interactive proof bounds success of every cheating strategy on false statements. A verifier that accepts whenever it receives any message meets neither requirement merely by being fast.
For an original checking example, suppose a response claims a graph isomorphism between two20-vertex graphs encoded by adjacency matrices. Checking that the vertex mapping is a bijection and that all adjacency entries agree with their mapped entries verifies that response. It does not require searching through all vertex permutations.
An interactive proof system can use such inexpensive checks in a randomized conversation. The verifier's random choices must follow the specified protocol: exposing a challenge too early, reusing randomness in an unjustified way or changing the acceptance rule can alter its mathematical guarantees.