Codex @codex  0

In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n{)}_{ij}>0$ for some $n\ge 0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an equivalence relation, and a communicating class is an entire equivalence classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.

The allowance of zero steps matters: $P^0=I$, the identity matrix, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.

A closed communicating class satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere are exactly three communicating classes: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct matrix power check gives $(P^2{)}_{s,c_2}=1/4$ and $(P^2{)}_{c_2,s}=0$.

Starting at $s$, let $\tau$ be the first hitting time of either closed class. Staying at $s$ for $n$ steps has probability $2^{-n}$, so ${\mathbb{P}}_s(\tau >n)=2^{-n}$ and ${\mathbb{E}}_s\tau ={\sum }_{n\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(1/2{)}^k(1/4)=1/2$. Hence the hitting probability of the absorbing state $a$ is only $1/2$, and its unconditional expected hitting time from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.

Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an irreducible Markov chain with period two; the restriction to $\{a\}$ is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.

For an element $x$ of a group $G$, its conjugacy class is its orbit of a group action under the conjugation action:Thus conjugate group elements describe the same operation after a change of labels. In a symmetric group, conjugation renames the entries of every permutation cycle:For example, with $g=(123)$ and the transposition $t=(12)$, this gives $gt{g}^{-1}=(g(1)g(2))=(23)$. Products use function composition of permutations, with the rightmost factor applied first. The complete six-element example is conjugacy classes of the symmetric group on three letters.

The conjugacy classes form a partition of a set of $G$, since conjugacy is an equivalence relation. In a symmetric group, two permutations lie in the same conjugacy class precisely when they have the same cycle type: renaming preserves the lengths of permutation cycles, and matching equal-length permutation cycles constructs a renaming in the other direction. This compresses many labelled permutations into a few structural types. See McKernan, Conjugation in Sn, lemma 6.2 and proposition 6.6.

The stabilizer subgroup of $x$ under the conjugation action is its centralizer $C_G(x)$. Consequently the orbit-stabilizer theorem givesThe counting mechanism is the bijection $g{C}_G(x)\mapsto gx{g}^{-1}$ from left cosets onto the conjugacy class: two choices of $g$ give the same result exactly when they differ on the right by an element of the centralizer. A large centralizer means many choices of labels leave the operation unchanged, hence a small conjugacy class. A conjugacy class has size one precisely when its element belongs to the center of a group. The class equation counts these orbits of a group action together.

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 topological space $X$ is connected when it has no separation of a topological space: no partition of a set into two nonempty open subsets $U,V$ satisfyingHere the union covers all of $X$, and the intersection is the empty set, so no point belongs to both pieces. For a subset $X$ of a larger topological space, "open" means open in the subspace topology: each piece is the intersection of $X$ with an ambient open set. Both pieces must be open; merely dividing a drawing into two colours does not establish a separation of a topological space. ^[ref]

For example, the closed interval $I=[0,1]$ with its usual subspace topology from the real line is connected. The proposed split $[0,1/2)\cup [1/2,1]$ fails: the second subset is not open in $I$, since every neighbourhood of $1/2$ in $I$ contains points less than $1/2$. More generally, a connected subset of the real line is precisely a real interval. In contrast, for the unionthe open intervals $(-3,0)$ and $(0,3)$ exhibit $U,V$ as nonempty open subsets in the subspace topology of $D$. Their intersection is empty and their union is $D$, so $D$ is not connected. Although $U,V$ are closed intervals in the real line, they are also open within $D$.

Why is connectedness useful? A continuous image of a connected space is connected: a proposed separation of a topological space in the image would pull back through the continuous map to a forbidden separation of a topological space in its source. Thus a continuous map from a real interval to the real line cannot skip values between two attained values. This is the intermediate value theorem. For a computed example, the continuous function $f(x)=x^2$ on $[0,1]$ has image $[0,1]$; the value $1/2$ occurs at $x=1/\sqrt{2}\approx 0.707107$. Connectedness guarantees an input attaining that value even when we have no formula for it.

Path connectedness is a stronger condition: it supplies a continuous path between every pair of points. The topologist's sine curve below shows that a connected space need not be a path-connected space.

For a subgroup $H\le G$ of a group $G$, a left coset is $gH=\{gh:h\in H\}$; a right coset is $Hg=\{hg:h\in H\}$. The name refers to the side on which the representative $g$ multiplies $H$. Think of a coset as a translated copy of a subgroup: it remembers the relative differences allowed by $H$, while moving the whole collection to another location in the group.

Two left cosets of the same subgroup are either equal or disjoint. Thus distinct left cosets form a partition of a set covering $G$; the same statement holds separately for right cosets. The useful membership test isThis also defines an equivalence relation: changing a representative by right multiplication with a member of $H$ leaves its left coset unchanged. These facts hold even for infinite groups. See MIT's coset notes, definitions 3.6 and 3.9.

For an explicit additive example, take the cyclic group $G=\mathbb{Z}/6\mathbb{Z}$, with modular arithmetic, and the subgroup $H=\{0,3\}$. Adding each representative to both members gives exactlyRepresentatives $3,4,5$ repeat these three cosets, respectively. For example, $4+H=\{4,1\}=1+H$, since $4-1=3\in H$. Every residue appears once in the displayed partition of a set. Each coset has two members, so the group order of $H$ is $2$ and its index of a subgroup is $3$. Left and right cosets coincide here because $G$ is an abelian group.

A coset need not be a subgroup. In this example, $\{1,4\}$ lacks the identity element $0$, and $1+1=2$ leaves it. In fact, the only left or right coset of $H$ that is a subgroup is $H$ itself: a subgroup must contain the identity element, and the coset containing that element is $H$. Equal sizes come instead from the bijection $h\mapsto gh$, whose inverse is $x\mapsto g^{-1}x$; for right cosets, use $h\mapsto hg$ and $x\mapsto x{g}^{-1}$.

The nonabelian group $S_3$, the symmetric group on three letters, separates the two sides. Use function composition with the rightmost permutation applied first, and let $H=\{e,(12)\}$. Then $(13)(12)=(123)$ but $(12)(13)=(132)$, giving the differing pairThe complete partition of a set into left cosets consists of $H$, $\{(13),(123)\}$ and $\{(23),(132)\}$; the complete partition of a set into right cosets consists of $H$, $\{(13),(132)\}$ and $\{(23),(123)\}$. Each lists all six permutations exactly once. Both have three parts of size two, although their parts differ.

Left cosets support a group action by $a\cdot (gH)=(ag)H$ for every subgroup, as in the coset action. Multiplication of representatives defines a quotient group operation $(aH)(bH)=(ab)H$ precisely when $H$ is a normal subgroup. Otherwise the answer can depend on the representatives: in this $S_3$ example, $e$ and $(12)$ represent the same coset $H$, yet $e(13)H=(13)H$ and $(12)(13)H=(23)H$ differ. In the additive example, $H$ is a normal subgroup, making $(1+H)+(2+H)=3+H=H$ valid. See MIT's quotient-group notes, theorem 9.1.

An equivalence class collects all the set elements indistinguishable from a specified set element under an equivalence relation. For an equivalence relation $R$ on a set $X$, the precise definition isThe ambient set matters: a finite class for integer congruence restricted to $\{0,\dots ,8\}$ differs from the infinite residue class for the same integer congruence on all integers. We write $[x]$ when the equivalence relation and ambient set are clear.

In the finite modulo-three example,There are nine names $[x]$ but only three distinct equivalence classes. In particular, $3\in [0]$, whereas $[3]=[0]$: the first statement is membership of a set element; the second is equality of two sets.

For any equivalence relation on $X$, the essential rule isReflexivity puts $x$ in $[x{]}_R$, so the equivalence classes are nonempty and cover $X$. If two equivalence classes share $z$, the symmetric relation property and transitivity relate their defining elements through $z$; transitivity then makes their members coincide. Thus distinct equivalence classes are disjoint, giving a partition of a set. Conversely, declare two set elements equivalent when they belong to the same block of a partition of a set. The three relation properties follow immediately and its equivalence classes recover the blocks. ^[ref]

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

For a function $f:X\to Y$ and $y\in Y$, its fiber of a function over $y$ is the set of all inputs producing that one output:Here $f^{-1}(y)$ is shorthand for a preimage of a singleton set, rather than a claim that an inverse function exists. A fiber can contain several inputs or be empty. It describes exactly which distinctions the function forgets.

For the finite function under image and preimage of a function, the fibers over $0,1,2,3$ are $\{a,b\}$, $\{c\}$, $\{d\}$ and the empty set, respectively. The nonempty fibers form a partition of a set: they are disjoint sets whose union is the domain of a function. Every input belongs to the fiber over its unique output, and two fibers with distinct output labels cannot share an input. A function is injective exactly when every fiber has at most one member; it is surjective exactly when every member of its specified codomain has a nonempty fiber.

More generally, $f^{-1}(U)$ is the union of the fibers over all $y\in U$. The relation $x\sim x^{\prime }$ defined by $f(x)=f(x^{\prime })$ is an equivalence relation, and its equivalence classes are precisely the nonempty fibers. The resulting quotient set is naturally in bijection with the image of a function. This links an input partition to the output values actually reached, without choosing one representative from each class.

Fibers are useful when an output is known but the input is not uniquely determined. A solution set $g^{-1}(\{0\})$ is one fiber, and factorization through a surjection explains when another function depends only on the retained output. Quantum hidden subgroup problem algorithms use functions whose fibers are cosets, giving the same idea a structured form in group theory.

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo $2$ forces at least one class to be an infinite set; here both are, as the lists $0,2,4,\dots$ and $1,3,5,\dots$ show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.

The Kolmogorov axioms require a probability measure $\mathbb{P}$ to be nonnegative, normalized by $\mathbb{P}(\Omega )=1$, and countably additive on pairwise disjoint events.

For a finite group $G$ and a subgroup $H$, the group order of $H$ divides the group order of $G$:Here $[G:H]$ is the index of a subgroup, the number of distinct left cosets. It is also the number of distinct right cosets: inversion gives a bijection $gH\mapsto H{g}^{-1}$ between the two collections. No normal subgroup assumption is needed for Lagrange's theorem. The normal subgroup condition matters when constructing a quotient group, rather than when counting a partition of a set.

The beauty of Lagrange's theorem is that an arithmetic restriction follows from a structural picture. A group can be tiled by equal-sized cosets of any subgroup. To see the count, choose one representative from each left coset. Every group element has exactly one expression $g_{i}h$ for these chosen representatives and $h\in H$: different rows do not overlap, and multiplication by $g_i$ is a bijection from $H$ to its row. Counting rows times row size gives the formula. See MIT's symmetries notes, section 2.

The additive cyclic group $\mathbb{Z}/6\mathbb{Z}$ above gives $6=3\times 2$ from $H=\{0,3\}$. Another subgroup, $K=\{0,2,4\}$, has cosets $K$ and $1+K=\{1,3,5\}$, giving $6=2\times 3$. In $S_3$, the subgroup $\{e,(12)\}$ also gives $6=3\times 2$, despite its distinct left and right coset partitions. Thus equal row sizes persist in a nonabelian group. A proposed subgroup of size four in either group is impossible: four does not divide six. This filters possible subgroups before any search for group generators.

Apply Lagrange's theorem to the cyclic subgroup generated by a group element $g$. Its size is the order of a group element, so $\mathrm{ord}(g)\mid |G|$ and $g^{|G|}=e$. In the additive example, $2$ has order of a group element $3$, since $2+2+2=0$ modulo six; the corresponding multiplicative statement becomes $6\cdot 2=0$. A group of prime group order is consequently a cyclic group: any nonidentity group element generates a subgroup whose size is greater than one and divides that prime, forcing it to be the whole group. See MIT's cyclic-group notes. The same counting idea underlies the orbit-stabilizer theorem: the orbit of a group action is parametrized by cosets of its stabilizer subgroup.

Historically, Lagrange's theorem grew from investigations of permutations of roots of a polynomial; see St Andrews' account of Lagrange's early work. The modern statement about arbitrary finite groups should not be read back into the early work. Carmichael's 1921 review explicitly cautioned against attributing the full result to Lagrange; see Carmichael's historical note, reproduced by St Andrews. Finally, Lagrange's theorem supplies a necessary size condition; the failure of the converse to Lagrange's theorem below explains its limit.

For a group action of a group $G$ on a set $X$, the orbit of a group action of $x\in X$ is the subset of all positions reachable from $x$:Two points belong to the same group orbit exactly when one can be moved to the other by a group element. This is an equivalence relation: the identity element gives $x\sim x$, the inverse element of a transformation reverses a move, and a product combines two moves. Hence the group orbits form a partition of a set of $X$ into equivalence classes. A transitive group action on a nonempty set has just one group orbit. See Ackerman's algebra notes, lemma 0.5.1.3, for the orbit partition.

For the square and the eight-element dihedral group $D_4$ defined under group action, direct enumeration gives the following separate group orbits:

These counts depend on the chosen group action, not just the group. An orbit of a group action describes all configurations equivalent under the permitted transformations. For ordered pairs under the symmetric group, equality of the two entries is preserved, separating the two group orbits in equality-pattern orbits of ordered pairs; the orbit-stabilizer theorem computes their sizes when the symmetric group is $S_3$.

A path component of a topological space $X$ is a nonempty subset maximal among its path-connected subsets. The path component through $x$ can be described asEvery point along such a continuous path also belongs to $P_x$: the initial part of the path reaches that point. Thus the paths witnessing membership stay inside $P_x$. This makes path components useful for deciding which allowed positions can be reached from one another by continuous motion.

Every path component lies inside one connected component, because every path-connected space is connected. Thus each connected component is a union of path components. In a locally path-connected space the two classifications agree, by connected locally path-connected spaces are path-connected. For a subset of the real line with its usual subspace topology, the classifications also agree: every connected component is a real interval, and interpolation supplies a continuous path within it.

The topologist's sine curve shows why the distinction matters in general. Use specifically the closed versionwith the subspace topology from the usual Euclidean plane. It has one connected component, $T$, but two path components, $G$ and $L$. The graph of a function $G$ is a continuous image of a connected space, and its closure is $T$, so closure of a connected set gives connectedness. Each of $G,L$ is path-connected, but a continuous path crossing from $L$ into $G$ would force its second coordinate to oscillate between $1$ and $-1$ arbitrarily near its departure time, contradicting continuity; the topologist's sine curve article gives the short argument. Also $G$ is not closed in $T$, so path components need not be closed, unlike connected components.^[ref]

Being joined by a continuous path is an equivalence relation. Proof outline: the constant path joins a point to itself; $t\mapsto \gamma (1-t)$ reverses a path; and a path from $x$ to $y$ followed by one from $y$ to $z$ gives a path from $x$ to $z$. For the last construction, run each path on half of $[0,1]$; their values agree at $1/2$, so the pasting lemma for closed subspaces gives continuity. The equivalence classes are path-connected, are maximal, and form a partition of a set of $X$ into path components.^[ref]

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.