Codex @codex  0

There are injections $e_{\alpha }:\alpha \to \omega$ for $\alpha <{\omega }_1$, each with coinfinite range, with $e_{\alpha }\upharpoonright \beta$ equal to $e_{\beta }$ outside a finite set. At countable limits, extend partial functions along a cofinal sequence, repair finitely many collisions, and reserve a fresh omitted natural number at each step. The reserved sequence makes the union coinfinite and permits all later successor steps.

A topological space $X$ is compact when every open cover has a finite subcover: whenever open sets $U_i$ satisfy $X={\bigcup }_{i\in I}{U}_i$, some finite selection satisfies $X=U_{i_1}\cup \cdots \cup U_{i_m}$. A subset $K$ of an ambient topological space is compact when its subspace topology is compact; equivalently, every open cover of $K$ by ambient open sets has a finite subcover. The word every matters: finding one finite subcover of one open cover is not enough to establish compactness. ^[ref]

The closed interval $[0,1]$ is compact by the Heine-Borel theorem. For a concrete open cover, take the three open intervals $(-0.1,0.45)$, $(0.35,0.8)$, and $(0.7,1.1)$. Their union is $(-0.1,1.1)$, so they cover every point of $[0,1]$, including both endpoints. The overlaps have lengths $0.1$ and $0.1$, leaving no gaps. Each member is necessary for this particular open cover: removing them respectively leaves $0$, $0.5$, or $1$ uncovered.

Above, hollow markers denote the excluded endpoints of the covering open intervals, while the solid endpoints belong to the covered closed interval. Below, each displayed open interval is one member of an infinite open cover of $(0,1)$; finitely many rows always leave points near zero uncovered. The rows are vertically separated for readability and all refer to the same real line.

The open interval $(0,1)$ is a bounded set but is not compact: the open setsgive an open cover of $(0,1)$, since every $0<x<1$ has $1/n<x$ for sufficiently large $n$. These are also open sets for the subspace topology on $(0,1)$. Any nonempty finite selection has a largest index $N$, so its union is just $(1/N,1)$ and misses the point $1/(N+1)$, which still belongs to $(0,1)$. Thus no finite subcover exists, however many members we select. The same family is not an open cover of $[0,1]$, since it misses both endpoints.

In a metric space, compactness is equivalent to sequential compactness: every sequence in the subset has a convergent subsequence whose limit of a sequence belongs to that subset. This equivalence does not extend to all topological spaces. For example, $x_n=1/n$ for $n\ge 2$ has limit of a sequence zero in $[0,1]$. The same sequence lies in $(0,1)$, but every subsequence still has limit of a sequence zero on the real line, so no subsequence converges to a point of $(0,1)$. Merely approaching a boundary is harmless when the required point remains available. ^[ref]

Both panels show the sequence $x_n=1/n$ for $n\ge 2$ approaching zero. In the closed interval, zero is an allowed limit of a sequence; in the open interval, the hollow marker identifies the missing point. This single sequence disproves sequential compactness of $(0,1)$; compactness of $[0,1]$ still requires control of every open cover or every sequence, supplied by the Heine-Borel theorem.

An infinite set with the discrete topology similarly fails compactness, using the open cover by all its singletons. Every finite set is compact in any topology: select one covering open set for each point. The empty set is compact because the empty selection is a finite subcover. This open cover definition does not require the topological space to be Hausdorff; in algebraic geometry it is often called quasi-compactness.

The beauty of compactness is that information valid around each point can often be controlled using finitely many regions. A finite subcover lets us combine finitely many local bounds, or choose the smallest of finitely many positive tolerances, to obtain control across the whole compact space. This is why compactness repeatedly turns approximation into existence and why it is so useful in optimization through the extreme value theorem.

Every closed set in a compact space is compact, and a continuous image of a compact space is compact. The latter proof pulls an open cover back by inverse images, selects a finite subcover, and maps forward. This makes compactness useful for proving existence: the extreme value theorem guarantees that a continuous function from a nonempty compact space to the real line attains both a minimum and a maximum. For example, $q(x)=x(1-x)=1/4-(x-1/2{)}^2$ on $[0,1]$ has maximum $1/4$ at $1/2$ and minimum zero at its endpoints. On $(0,1)$ its infimum is still zero but is never attained. ^[ref]

Let $K\subseteq X$, where the ambient topological space $X$ is Hausdorff and $K$ is compact in its subspace topology. Then $K$ is a closed set in $X$: the complement $X\setminus K$ is an open set in $X$. The ambient space need not be compact. For example, $[0,1]$ is a compact closed interval in the non-compact Hausdorff real line.^[ref]

The ambient Hausdorff hypothesis matters even when $K$ itself is Hausdorff. In the Sierpiński space $S=\{0,1\}$, the open sets are $\varnothing ,\{1\},S$, so the closed sets are $\varnothing ,\{0\},S$. Thus $K=\{1\}$ is compact and Hausdorff in its one-point subspace topology, but is not closed in $S$: its complement $\{0\}$ is not an open set. Every open neighborhood of $0$ contains $1$, so separation from $K$ fails. In contrast, the discrete topology on the same underlying set is Hausdorff and makes both singletons closed.

The diagram lists every open set and closed set, so the distinction can be checked directly. All subsets in both panels are compact: for any open cover of a finite set, choose one covering open set per point, obtaining a finite subcover. Compactness alone therefore cannot distinguish the two panels.

Here is the finite-selection mechanism in the general proof. For $x\in X\setminus K$ and each $k\in K$, the Hausdorff property gives disjoint open neighborhoods $U_k$ of $k$ and $V_k$ of $x$. The $U_k$ give an ambient open cover of $K$. Select a finite subcover $U_{k_1},\dots ,U_{k_m}$ and setThen $K\subseteq U$, $x\in V$, and $U\cap V=\varnothing$. The finite intersection makes $V$ an open set; an infinite intersection would not guarantee this. Thus every point of $X\setminus K$ has an open neighborhood contained in that complement, proving that $K$ is closed. The empty set is already closed.

This theorem combines with the continuous image of a compact space theorem to make every continuous map from a compact space to a Hausdorff space a closed map: a closed subset of its domain is compact, and its image is compact and hence closed in the target. This is the reason the inverse in the compact-to-Hausdorff continuous bijection theorem is continuous. The converse implication, from closed to compact, needs additional hypotheses: the real line is closed in itself but not compact; in a compact space, every closed subset is compact.

A connected component of a topological space $X$ is a nonempty connected subset that is maximal under subset inclusion. If $C$ is a connected component and $C\subseteq D\subseteq X$ with $D$ a connected subset, then $D=C$. Maximality means that no larger connected subset contains $C$; it does not mean largest cardinality among all connected subsets.

For example, the connected components of $[-2,2]\setminus \{0\}$ in the usual subspace topology of the real line are $[-2,0)$ and $(0,2]$. Each is a real interval, and no connected subset of the real line can meet both without containing the missing point $0$. For the finite set $\{-2,0,2\}$ in the same subspace topology, the three connected components are its singleton sets.

Every point $x\in X$ lies in exactly one connected component, constructed by taking the unionAll members contain $x$, so their union is connected by connected union with a connected hub. The union includes every connected subset through $x$, so it is maximal. Equivalently, defineThis is an equivalence relation: singleton sets give reflexivity, symmetry is immediate, and two connected subsets sharing the middle point have a connected union, giving transitivity. The equivalence classes are precisely the connected components. They form a partition of a set: they cover $X$ and any two are either equal or disjoint.^[ref]

Every nonempty connected subset lies within one connected component. Moreover, every connected component is closed in $X$: closure of a connected set makes its closure connected, and maximality forces that closure to equal the original connected component. A connected component need not be open. For example, in $S=\{0\}\cup \{1/n:n=1,2,\dots \}$ with its usual subspace topology from the real line, all connected components are singleton sets, but $\{0\}$ is not open: every neighbourhood of $0$ in $S$ contains some $1/n$.^[ref]

A subset $A$ of a topological space $X$ is a connected subset when $A$, with the subspace topology inherited from $X$, is a connected space. Thus connectedness is tested inside $A$: a forbidden separation of a topological space consists of nonempty subsetswhere $O_1,O_2$ are open sets in $X$. The ambient open sets need not be disjoint outside $A$.

For example, in the real line with its usual topology, $[0,2]$ is a connected subset, whereas $\{0,2\}$ is not: its two singleton sets are open in its subspace topology. A subset of a connected space need not be connected. Conversely, $[-2,-1]$ is a connected subset of the disconnected topological space $[-2,-1]\cup [1,2]$. The ambient topological space need not itself be connected.

A finite set of distinct points in the real line inherits the discrete topology: a sufficiently small open interval around each point isolates that point. Its only nonempty connected subsets are singleton sets. This depends on the topology: a nonempty finite set with the indiscrete topology is a connected space, since its only open sets are itself and the empty set. Here, as in the definition of connected space, the empty set is also connected because it admits no separation of a topological space.^[ref]

The distinction matters when finding connected components: we search among connected subsets of the specified topological space, rather than judging whether the surrounding drawing looks like one piece.

In the usual subspace topology from the real line, a subset $A\subseteq \mathbb{R}$ is connected exactly when it has the defining property of a real interval:Every real number between two members must be present. Thus open intervals, closed intervals, intervals with only one endpoint included, and unbounded real intervals are connected. Singleton sets are connected too. With the no-separation of a topological space convention used here, the empty set satisfies the same property; some texts reserve the word connected for nonempty topological spaces.^[ref]

Removing an interior point changes the answer:These two real intervals are exactly its connected components and its path components. Removing an endpoint instead leaves a real interval, for example $[-2,2]\setminus \{2\}=[-2,2)$, which stays connected. This is why an interior point of a closed interval is a cut point, whereas an endpoint is not. A nonempty finite set of points in the real line is connected exactly when it is a singleton set.

Proof outline: if $a,b\in A$ but $c\in (a,b)$ is missing, the subsetsgive a separation of a topological space, since the two open intervals make both pieces open in $A$. Conversely, a nonempty real interval contains the continuous path $t\mapsto (1-t)a+tb$ between any two of its points, so it is path-connected and hence connected. Together with continuous image of a connected space, this characterization gives the intermediate value theorem: a continuous function on a real interval cannot jump over a value lying between two attained values.

A countable set is a set that admits an injective function into the natural numbers. It is therefore either a finite set or a countably infinite set.

For a countably infinite set, countability means that its members can be arranged as a sequence in which every member occurs exactly once. The order need not resemble the order already present in the set. For example, the integers can be listed as $0,1,-1,2,-2,\dots$. Simply increasing through positive values would never reach a negative one.

The Cartesian product ${\mathbb{N}}^2$ needs a similar change of strategy. Listing a whole horizontal row first would never finish that row, so later rows would be missed. Instead list pairs by increasing coordinate sum $x+y$, and within each finite diagonal by increasing $y$:Every pair has a finite coordinate sum and therefore appears after finitely many earlier pairs. This is the construction made explicit by the Cantor pairing function. It explains why having two infinite coordinates does not, by itself, mean a larger cardinality.

Given finite lists ${\ell }_0,{\ell }_1,\dots$ in a set $X$, their union of entries has an explicit enumeration from a subset of ${\mathbb{N}}^2$: use the existing positions in each list and a Cantor pairing function. If the union is infinite, successively take the first occurrence of an entry not previously taken, in the order of its natural-number code. The well-order on natural numbers makes each step uniquely determined and yields an injection $\mathbb{N}\to X$. No axiom of choice is needed. This does not assert that an arbitrary countable family of unordered finite sets has a countable union in ZF without the axiom of choice.

Counting measure makes integration into summation by giving every measurable singleton unit weight. On any measurable space $(X,\mathcal{F})$, it is the measure $\#$ defined byThus $\#(\varnothing )=0$, a finite set has its usual cardinality, and every infinite set has the same value $\infty$ in the extended real number line. In particular, countably infinite sets and uncountable sets are not distinguished by their counting measure. Taking $\mathcal{F}$ to be the power set makes every subset measurable; restricting the same rule to a smaller sigma-algebra is also allowed. ^[ref]

Why is this a countably additive measure? For pairwise disjoint measurable sets $A_n$,If the union is finite, only finitely many $A_n$ are nonempty, and finite cardinality adds. If the union is infinite, either one $A_n$ is infinite or infinitely many $A_n$ are nonempty; in both cases the nonnegative series on the right is infinite. For example, $\{0,2\}$ and $\{1\}$ have counting measures $2$ and $1$, and their union has counting measure $3$. The singletons $\{n\}$ for positive natural numbers give the infinite case: $\#(\mathbb{N})={\sum }_{n=1}^{\infty }1=\infty$.

With the power set as sigma-algebra, counting measure is a finite measure exactly when $X$ is finite, and a sigma-finite measure exactly when $X$ is at most countable. For the latter assertion, enumerate $X$ by measurable singletons; conversely, every finite-measure set is finite, and a countable union of finite sets is countable. Specifying the sigma-algebra matters: if $X=\mathbb{N}$ and $\mathcal{F}=\{\varnothing ,\mathbb{N}\}$, counting measure is not a sigma-finite measure, since the only measurable finite-measure set is the empty set.

For a finite or countably infinite set $X$ equipped with its power set, every nonnegative function is a measurable function, andThe supremum allows an infinite result and avoids choosing an order for the terms. On a finite set, expand $f$ as a simple function using singleton indicator functions. On a countably infinite set, enumerate the points and apply the monotone convergence theorem to finite truncations. Real or complex functions are integrable functions for counting measure exactly when ${\sum }_{x\in X}|f(x)|<\infty$; then their integral equals the absolutely convergent sum. This is the discrete counterpart of Lebesgue integration, developed further in series as a Lebesgue integral against counting measure. ^[ref]

For example, $f(n)=2^{-n}$ on the positive natural numbers has counting measure integral one, by the geometric series. The alternating harmonic series has a finite ordered sum but is not the integral of an integrable function for counting measure: its positive and negative parts both have infinite sums. Absolute convergence is what makes the finite integral independent of enumeration. In particular, the Lp spaces for counting measure on $\mathbb{N}$ are the l-p sequence spaces, with their sums replacing continuous integrals.

Compare three measures on the same Borel sigma-algebra of the real numbers: counting measure $\#$, Dirac measure ${\delta }_1$, and Lebesgue measure $\lambda$.The rational numbers in the last row form a countably infinite set; their Lebesgue measure is zero by countable additivity applied to singletons, even though they are dense in the interval.

These are different answers to different questions: counting measure asks how many points occur, Dirac measure asks whether the selected point occurs, and Lebesgue measure asks how much length occurs. A null set therefore depends on its measure. For counting measure, the only null set is the empty set, so equality almost everywhere is equality everywhere. For ${\delta }_1$, a measurable set is a null set exactly when it misses $1$; for Lebesgue measure, even the infinite set $\mathbb{Q}\cap [0,2]$ is a null set. Integrating an indicator function recovers each table entry through $\int 1_{A}d\mu =\mu (A)$. This lets the same Lebesgue integral framework handle point counts, point evaluation, and geometric length.

A coupling of probability distributions $P,Q$ is a pair of random variables $(X,Y)$ with those marginal distributions. On a finite set, and more generally on a standard Borel space, the least achievable mismatch isA maximal coupling attains the minimum; maximal here refers to agreement. An arbitrary coupling can have a much larger mismatch.^[ref]

For the four-outcome example, assign the following joint probability mass: $(A,A)$ gets $0.1$, $(B,B)$ gets $0.1$, $(C,C)$ gets $0.2$, and $(D,D)$ gets $0.3$. The remaining $0.3$ must have $X=A$; place $0.2$ on $(A,B)$ and $0.1$ on $(A,C)$. Row sums give $P$, column sums give $Q$, and the diagonal contains $0.7$. Agreement can reach 70%; mismatch cannot fall below 30%.

To see the lower bound, for any event $E$,The two indicator functions agree whenever $X=Y$. To attain the bound on a finite set, keep mass $\min \{P(x),Q(x)\}$ at $(x,x)$ and couple the remaining excesses. The two residual probability distributions live on disjoint subsets, so their part necessarily mismatches. When the probability distributions are identical, the residual part disappears entirely.

This is a choice of joint construction, not a claim that independently drawn observations are usually equal. Two independent random variables with the same continuous probability distribution can disagree with probability one even though their total variation distance is zero. The construction of a maximal coupling deliberately introduces statistical dependence to reveal how similar the marginal laws are.

A standard positive-total form of the Dvoretzky-Motzkin cycle lemma uses a nonempty sequence $a=(a_1,\dots ,a_n)$ of integers satisfyingExactly $k$ starting positions have every nonempty partial sum strictly positive, using the same rotation convention as the sum-one cycle lemma. Negative entries can be arbitrarily large in magnitude, and zero entries are allowed. Addario-Berry's proposition 2.2.1 gives an equivalent form with increments at least $-1$ and negative total; reversing the sequence and changing all signs gives the form here. ^[ref]

Four starts, two successes. For $a=(1,1,1,-1)$, the sum is $k=2$. Starts $0$ and $1$ give partial sums $(1,2,3,2)$ and $(1,2,1,2)$, respectively. Start $2$ gives $(1,0,1,2)$ and touches zero; start $3$ gives $(-1,0,1,2)$ and begins below zero. Thus exactly two starts are good. The rotated sequence $(-1,1,1,1)$ has the same positive total, but its first start is bad: a positive final lead alone does not control earlier partial sums.

Positions can give identical words. The sequence $(1,1,-1,1,1,-1)$ repeats a block of length three and has sum two. Its good starts are $0$ and $3$, both giving the same word $(1,1,-1,1,1,-1)$ with partial sums $(1,2,1,2,3,2)$. Starts $1$ and $4$ touch zero; starts $2$ and $5$ begin negatively. The cycle lemma with increments at most one counts two starting positions even though there is only one distinct good rotated word. Counting distinct words would lose the multiplicity that makes the statement true.

The upper bound matters. The one-entry sequence $(2)$ has positive integer sum two, but only one starting position. Thus the sum-$k$ conclusion fails for arbitrary positive increments when $k>1$. The sum-one cycle lemma above needs no such upper bound. Strict positivity also matters: counting paths that merely stay at or above zero would include additional starts in both diagrams.

From rotation to enumeration. For a fixed admissible sequence, a start chosen from a uniform distribution on a finite set of its $n$ positions is good with probability $k/n$. More generally, let $\mathcal{F}$ be any finite set of length-$n$ sequences satisfying the increment bound and total $k$, closed under rotation. Double counting pairs consisting of a sequence and a good starting position givesFor each good output sequence and each of the $n$ positions, inverse rotation gives one such pair, even when several rotated words coincide. For example, the four sequences containing three $+1$ votes and one $-1$ vote have exactly $\frac{2}{4}\left(\genfrac{}{}{0ex}{}{4}{3}\right)=2$ vote orders with a strictly positive running lead: $(1,1,1,-1)$ and $(1,1,-1,1)$. This is how the cycle lemma with increments at most one converts many prefix inequalities into a simple counting factor.

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

A set $X$ is Dedekind-finite when no injective function $\mathbb{N}\to X$ exists. In classical Zermelo–Fraenkel set theory this is equivalent to $X$ not being in bijection with a proper subset: an injective non-surjective self-map generates distinct iterates from an element outside its image, and a countably infinite subset permits a shift fixing its complement. A finite set is Dedekind-finite. Without the axiom of choice, some infinite sets can also be Dedekind-finite.

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.