invert :: [(a, a)] -> [(a, a)]
invert r = [(y, x) | (x, y) <- r]Thus , the converse relation. Swapping is a bijection, since doing it twice restores the original pair. Therefore distinct input pairs remain distinct; no equality constraint or duplicate removal is necessary.
Product (category theory) 2026-10-14
A binary categorical product of objects of a category is an object with categorical morphisms and . Its universal property is that, for every object and pair of arrows , , there is exactly one arrow satisfyingThe arrows are called the product projections. Existence lets us combine two maps; uniqueness means there is no extra unspecified information in the combined map.
In the Category of sets, take and . Their Cartesian product contains six ordered pairs, and the projection maps select the first and second coordinates. Let , , , , and , , . The unique required map is , , . Reading either coordinate recovers the corresponding input map.
In a partially ordered set viewed as a category, the projection arrows mean and . The universal property says that every common lower bound satisfies , so is the greatest lower bound. For subsets ordered by inclusion this is , the intersection; it is a different construction from the Cartesian product in the Category of sets because the allowed arrows have changed.
The universal property also compares any two proposed products: each supplies a unique map to the other compatible with the projections. The two composites have the same projections as the corresponding identity morphisms, so uniqueness makes them identities. Thus a categorical product is determined up to a unique projection-preserving isomorphism, which explains why we can use whichever concrete construction is convenient.
Product of finite probability distributions Created 2026-10-31 Updated 2026-11-05
Given two finite probability distributions, assign the product of their probability masses to each ordered pair. The support is the Cartesian product of the two positive-mass supports. Distributivity gives . This is the joint distribution for independent coordinate outcomes; it is a construction from the marginals, not a claim that arbitrary jointly observed coordinates are independent.
Projection map Created 2026-09-28 Updated 2026-11-05
A projection map from a Cartesian product selects specified coordinates. For the coordinate indexed by ,For example, forgets the second component of an ordered pair.
The product topology makes each coordinate projection map a continuous map. In the two-factor case , surjectivity depends on whether the omitted factor has an element, subject to the empty-set cases for Cartesian projections. For an arbitrary infinite family, simultaneous existence of the other coordinates can also involve the axiom of choice.
Replica plating spatial correspondence 2026-10-18
Replica plating spatial correspondence is the preserved association between a master site and its sampled sites on replicas. Label a master site by an ordered pair , specifying its row and column. Keeping the same orientation and viewing convention makes that label refer to the same source on every plate. The biological colonies need not have identical outlines, because the transferred samples can contain different numbers of biological cells.
A simple orientation check shows why a circular outline is insufficient. In a constructed four-by-four layout, a half-turn sends to . Thus B2, or , would be confused with C3, or . Applying the half-turn twice returns the original ordered pair, but applying it once generally selects the wrong source. An asymmetric orientation mark fixes that ambiguity. Two contact transfers also preserve the handedness when all plates are viewed from the same side: any reflection in going from plate to fabric is undone in going from fabric to plate. A fabric-side view must not be silently substituted for a plate-side view.
Simple graph 2026-10-14
An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair equals , so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; does not by itself determine . For example, and have the same edge set but different vertex sets.[ref]
https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec11.pdf. MIT, Graphs and Coloring, Section 1.1
In the six-vertex example, the vertex neighbourhood of is , so its degree of a vertex is . In label order , the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is . The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.
The adjacency matrix in the figure uses label order . Its entry is one exactly when , and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row is . The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.
The restrictions matter. A directed graph uses an ordered pair to distinguish from , so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another would raise and to four without adding a new neighbour. A self-loop at contributes two to its undirected vertex degree, making it four, because both endpoints lie at . Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.
For a transitive set , let be the history function on in the relative constructible hierarchy. By transfinite induction, for some finite , possibly depending on . The base and successor steps follow by forming finite ordered pairs and adjoining the next entry, using . These operations require finitely many subsequent definable power sets.
At a nonzero limit ordinal , the inductive bounds put every earlier in , since . This level satisfies finite relation closure for set-theoretic coding, independently of the availability of history functions. Consequently its coded relative constructible stage predicate computes the endpoints correctly. Finite pairing closure and the earlier histories show thatcontains exactly the pairs for . There are no extra indices: if and , increasing levels would give , contradicting Axiom of foundation. Thus is a definable subset of and belongs to . Extracting its domain and adjoining uses finitely many further operations, proving the induction step. Every nonzero limit therefore contains all with , as required by relative constructible level recognition.
Strongly universal hash family 2026-10-13
A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs and arbitrary specified outputs ,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the equal ordered pairs gives collision probability , so the family is also a universal hash family.
Here is a completely enumerable example. In the finite field , take the affine functions , using modular arithmetic modulo . Choose and as independent random variables, each with the uniform distribution on a finite set of all five finite field elements , including . There are equally likely hash functions. For , the ordered pair is . For instance gives ; gives . Every prescribed occurs exactly once, at .
Enumerating all affine hash functions over the finite field with five elements
. Each cell shows the unique coefficient pair (a,b) producing the displayed outputs at 0 and 1. Removing a = 0 deletes the diagonal and leaves dependent outputs despite uniform individual values. Details.Each row contains five choices, so each individual output has probability . Each cell has probability , and the five diagonal cells give collision probability . For any distinct , the same conclusion follows from and : a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.
The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.
Restricting to leaves permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given , the four values other than each have conditional probability and has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full -member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.
Summatory totient function 2026-10-20
The summatory totient function is . It counts the coprime ordered pairs with . The identity yields for a positive integer .
Sum of two squares Created 2026-10-20 Updated 2026-11-05
A sum of two squares representation of a nonnegative integer is an equality with integers . For example, has two representations even before changing signs or interchanging the two terms.
Counting conventions matter. If ordered pairs and signs are distinguished, the representation generates eight pairs, whereas generates only four and only one. Every perfect square is zero or one modulo four, so an integer congruent to three modulo four is impossible. That quick obstruction is insufficient by itself: also has no representation. The exact prime factorization criterion is the sum of two squares theorem.
Sumset Created 2026-09-24 Updated 2026-10-13
For finite sets in an abelian group , their sumset isEach distinct value occurs only once in this set, even if many ordered pairs produce it. When , repetitions are allowed: belongs to . For the two integer sets introduced above,For , the value comes from . For , 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 and six pairs with distinct members, counted without regard to order, produce ten distinct sums.
Every nonempty finite set of integers satisfies . To see this, list its members as . The distinct sumsall belong to . A nonconstant arithmetic progression attains this bound. The ordered list is essential: in the cyclic group , the subgroup instead satisfies , of cardinality three. Addition wraps around, for example in this group.
Sumset representation function 2026-10-14
For finite sets in an abelian group , the sumset representation function isIt counts ordered pairs in the Cartesian product, so and are different when , even though commutativity makes their sums equal. It is zero outside the sumset, andFor , its values at are . For , its values at the increasing elements of are . Both lists total sixteen, but the first concentrates more ordered pairs on fewer sums. This distinction is what additive energy quantifies.
Ordered-pair sums and representation counts for an arithmetic progression and a spread-out integer set
. Details. Syntax tree of a formula 2026-10-31
The syntax tree of a logical formula records its recursive construction. A propositional variable is a leaf, negation has one child, and binary implication has an ordered pair of children. A subformula occurrence corresponds to a node together with the subtree rooted there. Different occurrences may have identical formula strings.
Tagged encoding of a finite tuple 2026-10-31
Using distinct fixed tags , encode a tuple by the set . Injectivity of the ordered-pair construction makes the unique member with first coordinate recover . Thus a set can retain the order of a finite tuple when its entries are tagged, even if some coordinates coincide.
Triangular number pair-counting identity 2026-10-14
For distinct objects, the number of unordered pairs of different objects isOrdering the objects gives pairs with the first object, new pairs with the second, and so on down to one. Alternatively, ordered pairs count every unordered pair twice. The binomial coefficient therefore counts the edges of a complete graph on vertices. This is also consistent with the handshaking lemma: each vertex has degree of a vertex , and the degree sum counts every edge twice.
Unique readability theorem 2026-10-31
The unique readability theorem asserts uniqueness of the outer formation rule and its immediate components in a logical formula. For the fully parenthesized language with negation and implication, every formula is uniquely a variable, a negation of one formula, or an implication between an ordered pair of formulas. It gives a well-defined syntax tree and licenses recursive definitions and structural induction on formulas.
Unordered pair Created 2026-09-24 Updated 2026-11-05
An unordered pair is a set containing the specified elements, with no distinction between first and second positions. Hence . If , the notation denotes the singleton , rather than a two-element set.
For distinct , an unordered pair represents an edge in a simple undirected graph. An ordered pair instead represents a directed edge because reversing its entries changes the direction. If multiplicity must be retained even for equal elements, a multiset is needed instead of a set.
Unreduced rational representation 2026-10-14
Consider an original abstract data type whose values are rational numbers. Store an ordered pair of integers, interpreted as a numerator and a denominator. Use exact, unbounded integer arithmetic in this model. The storage space, representation invariant and abstraction function areThe representation invariant does not require a positive denominator or a reduced fraction. Consequently , and are three different concrete states with the same abstract rational number . Similarly, and both represent zero. The abstraction function is a surjection: every rational number has an integer numerator and a nonzero integer denominator, so every abstract value has a representation.
Both and violate the representation invariant; neither has a value under this abstraction function. By contrast, is completely valid. Simplifying it to the reduced fraction may be a useful implementation choice, but is not a requirement of this representation. Strengthening the representation invariant to require a positive denominator and a greatest common divisor of one would choose a unique stored representative for each rational number; every constructor and operation would then need to establish that stronger condition.
Equality of abstract values is therefore different from equality of stored ordered pairs. For valid and ,This defines an equivalence relation on : each equivalence class contains all representations of one rational number. An API equality operation can compare these cross-products using exact integer arithmetic. Comparing the two fields individually would incorrectly declare and unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.[ref]
8.3 Module Documentation. Section 8.3.1, Abstraction Functions: several concrete values mapping to one abstract value; Section 8.3.4, Representation Invariants: valid domain of AF



