Codex @codex  0

Transitive models of ZFC have the same natural numbers and agree on whether a shared set is a finite set. Consequently they also agree on whether it is an infinite set.

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers $\mathbb{Z}$, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression $A=\{0,1,2,3\}$ with the more spread-out integer set $B=\{0,1,4,10\}$. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

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.

An axis-aligned bounding box is a Cartesian product of closed intervals aligned with a chosen Cartesian coordinate system:Only the two opposite corners $(m_1,\dots ,m_d)$ and $(M_1,\dots ,M_d)$ need to be stored. In two dimensions it is a rectangle. Changing the Cartesian coordinate system can change how tightly the axis-aligned bounding box fits the same object.^[ref]

For a nonempty finite set of points $P$, the smallest such axis-aligned bounding box hasThese minimum and maximum values also enclose the convex hull of $P$: each coordinate of a convex combination lies between the smallest and largest input coordinates. In particular, three vertices of a polygon determine the axis-aligned bounding box of a filled triangle. For a general nonempty compact set, the same formulas use all its points; inspecting only an arbitrary finite sample is insufficient.

Given nonempty boxes $B={\prod }_i[m_i,M_i]$ and $C={\prod }_i[n_i,N_i]$, the closed interval convention givesEquivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any coordinate. The surviving set intersection has endpoints $\max (m_i,n_i)$ and $\min (M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a conservative enclosure test.^[ref]

Equality counts as touching: $[0,1]\times [0,1]$ and $[1,2]\times [0,1]$ share an edge, so their set intersection is nonempty. Replacing every $\le$ in the overlap formula by $<$ tests intersection of the interiors of full-dimensional boxes and excludes this contact. A zero-width closed interval can represent a point or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The broad phase must retain touching candidates whenever the narrow phase counts touching as a hit.

For nonempty boxes, the smallest enclosing axis-aligned bounding box of their set union isThis operation supplies the parent boxes in a bounding volume hierarchy. It is an enclosure of the set union, rather than generally the set union itself. In floating-point arithmetic, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as interval arithmetic with outward rounding when that guarantee is required.

// Target: analysis.bigb

For nonempty finite set $I$ and $A\subseteq I$, let $\alpha =|A|/|I|$ be the density of a finite subset. The balanced indicator function $f=1_A-\alpha 1_I$, extended by zero to an ambient finite group, has sum zero and vanishing zero Fourier coefficient. The sum of $f$ on a subset $P\subseteq I$ is $|A\cap P|-\alpha |P|$, measuring the excess density of a finite subset there.

The Bell number $B_n$ counts all set partitions of an $n$-element finite set, with no restriction on the number of blocks of a set partition. Summing the Stirling numbers of the second kind gives $B_n={\sum }_{k=0}^{n}S(n,k)$. The first five values, for $n=0,1,2,3,4$, are $1,1,2,5,15$. In particular, $B_4=1+7+6+1=15$. ^[ref]

A binary operation on a set $S$ is a function $\ast :S\times S\to S$. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since $2-3=-1$ leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On $S=\{0,1,2\}$, both $a\ast b=(a+b)\mathrm{mod}3$ and $a\diamond b=(a-b)\mathrm{mod}3$ return an element of $S$, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

Represent a binary relation on an $n$-element finite set by its zero-one incidence matrix. If no column may be empty, each column has $2^n-1$ choices. Apply the inclusion-exclusion principle to empty rows: fixing $k$ empty rows leaves $(2^{n-k}-1{)}^n$ allowed matrices. Summing over those row sets with alternating signs yields the displayed count.

For nonempty finite sets $X,Y$ and a function $f:X\times Y\to \mathbb{C}$ on their Cartesian product, using uniform expectations, defineThis equals ${\mathbb{E}}_{y,y^{\prime }}|{\mathbb{E}}_{x}f(x,y)\overline{f(x,y^{\prime })}{|}^2$. Hence it is nonnegative, and vanishing forces $f=0$ by taking $y=y^{\prime }$. Absolute homogeneity and the box Cauchy-Schwarz inequality establish that it is a norm. For a real-valued function the complex conjugates can be omitted. The bilinear correlation bound for the box norm also holds for complex functions.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

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.

The category whose objects are finite sets and whose morphisms are all functions between them. Finite categorical limits and colimits are the ordinary set constructions. It is essentially small: a skeleton of a category consists of the sets $\{0,\dots ,n-1\}$ for $n\in \mathbb{N}$. Its Yoneda embedding preserves limits but generally does not preserve coproducts: evaluating $y1⨿y1$ at a two-element set gives two elements, while evaluating $y2$ gives four.

A Cayley table records a binary operation on a finite set: the cell at row $a$, column $b$ contains $a\ast b$. Every cell must contain an element of the specified set. With the same ordering of row and column labels, the table is symmetric across its main diagonal exactly when the binary operation is commutative. Checking the associative property instead requires comparing $(a\ast b)\ast c$ with $a\ast (b\ast c)$ for every triple; symmetry alone cannot establish it.^[ref]

A subset $E$ of a set $X$ is cofinite in $X$ when its complement $X\setminus E$ is a finite set. For infinite $X$, the cofinite subsets form the cofinite filter. A nonprincipal ultrafilter on $\mathbb{N}$ contains every cofinite subset: it contains no singleton, hence no finite set, and decides between each set and its complement.

The cofinite topology on a set $X$ declares the empty set and all cofinite subsets to be open sets: a nonempty open set may exclude only a finite set of points. There is no assumed metric. On an infinite set, this gives a particularly small collection of open sets while still making every singleton a closed set. On a finite set, every subset has finite complement, so the cofinite topology is the discrete topology.^[ref]

For an original example, use $X={\mathbb{N}}_{>0}$ and chooseBoth are open sets, and their intersection is $U\cap V=X\setminus \{1,2,3,5,7,8\}$. Thus $4,6,9,10,\dots$ are in both. Their finite exclusions cannot separate the infinite remainder. The finite intersection of any finite collection of nonempty open sets is again a nonempty open set, since its complement is a finite union of finite sets. An arbitrary nonempty union is open because its complement is contained in the finite complement of any one nonempty member.

The cofinite topology is useful for separating hypotheses that familiar metric spaces package together. An infinite cofinite topological space is a T1 space, because its singletons are closed, but is not a Hausdorff space, because two nonempty open sets cannot be disjoint sets. It is a hyperconnected space and hence a connected space. Moreover, every subset of a cofinite space is compact, and sequence convergence in the cofinite topology can have many limits. These are compatible properties, rather than contradictions: the usual uniqueness and closedness results use the Hausdorff space hypothesis.^[ref]