Codex @codex  0

A bipartition of a graph divides its vertex set into two independent sets, so every edge joins different parts. A graph admitting such a partition of a set is a bipartite graph. The two parts are not generally unique: separate connected components of a graph can have their sides exchanged independently, and isolated vertices can be assigned to either part.

A colouring assigns to each member of a set $X$ a colour in another set $C$. Its nonempty fibres form a partition of a set. The colour set may be infinite; a finite colouring is the special case with finitely many colours. A homogeneous set for a colouring of finite subsets has all its subsets of the specified size assigned one colour.

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.

For a finite group $G$, write $k(G)$ for its number of conjugacy classes. Exactly the elements of the center of a group $Z(G)$ have singleton conjugacy classes; every other conjugacy class has at least two elements. Since the conjugacy classes form a partition of a set $G$, $k(G)-|Z(G)|\le (|G|-|Z(G)|)/2$. If $G$ is a nonabelian group, the cyclic quotient by the center criterion and the fact that every group of group order at most three is a cyclic group give $[G:Z(G)]\ge 4$, hence $k(G)\le 5|G|/8$. The quaternion group attains this bound, with five conjugacy classes among eight elements.

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.

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

A disjoint-set data structure maintains a partition of a set. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. Kruskal's algorithm uses it to track connected components of a graph.

Start with a singleton set for every stored set element. Each disjoint-set find operation returns a disjoint-set representative; a disjoint-set union operation merges the containing blocks of a set partition. The interface does not split a block of a set partition or delete a member.^[ref]

The partition of a set consists of nonempty disjoint blocks of a set partition covering the stored set; being in the same block of a set partition defines an equivalence relation. A disjoint-set representative names a whole block of a set partition, without requiring a list of its members.

The disjoint-set find operation returns the disjoint-set representative of a stored set element $x$. It preserves the partition of a set. With path compression, it can change internal pointers while answering the same membership question. Inputs outside the stored set require a specified error policy; they are not silently inserted here.

The disjoint-set union operation first uses the disjoint-set find operation to locate the blocks of a set partition containing $x,y$. If they are different blocks of a set partition $A,B$, replace them by their union $A\cup B$; every other block of a set partition stays as it was. If the two disjoint-set representatives agree, no merge is needed. Here unite returns True exactly when it merges two different blocks of a set partition. A successful call decreases their count by one; a redundant call preserves it. The name union is also customary. Some interfaces instead accept already found disjoint-set representatives, making that linking step a separate operation.

For an original example, initialize $X=\{1,2,3,4,5,6,7\}$ as seven singleton sets. Apply the calls in this order:The first five calls succeed. After the third, the partition of a set is $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$; after the fifth it is $\{\{1,2,3,4,5,6\},\{7\}\}$. The sixth returns False: $1,2$ are already together. The blocks of a set partition number $7,6,5,4,3,2,2$, counting the initial state. A disjoint-set find operation on $7$ cannot merge it with any other member.

This is exactly the kind of changing membership needed by Kruskal component merging: an accepted edge joins two current connected components of a graph, while an edge whose endpoints already have equal disjoint-set representatives is rejected. The existing Kruskal's algorithm worked example follows that application. A disjoint-set forest stores membership efficiently without repeatedly enumerating every block of a set partition.

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.

For a finite dataset, alternate nearest-centre assignment and replacement of each centre by the centroid of its assigned observations. Keep the current assignment whenever an observation is tied between nearest centres. A changed assignment then strictly decreases the within-cluster sum of squared Euclidean distances; updating centres cannot increase it by the centroid sum-of-squares identity.

After each centre update, the centres are determined by the current partition of a set of observation indices. There are only finitely many such partitions, so a strictly improving sequence cannot revisit one and must stop. A convenient exact stopping test is to check after each update whether every observation is still assigned to a nearest centre. This proof is for algorithm termination; it does not guarantee a global minimum.

Empty clusters need an explicit convention. To retain exactly $K\le n$ nonempty clusters, transfer an observation from a cluster with at least two members to each empty cluster, making it a singleton centred at that observation. This cannot increase the objective: the transferred observation now has squared distance zero, and no other contribution changes before centre updating. A deterministic choice is an eligible observation farthest from its currently assigned centre, with ties resolved by index. After the first round, an empty cluster can arise only during a strictly improving reassignment, so these repairs preserve the finite-termination argument.

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.

Given a finite set of jobs with fixed half-open intervals $[s_i,f_i)$, where $s_i<f_i$, choose a subset $S$ of maximum cardinality. Each job occupies one shared resource throughout its interval. A feasible solution has pairwise disjoint intervals: for distinct selected jobs $i,j$, either $f_i\le s_j$ or $f_j\le s_i$. Thus a finish and the next start may coincide. Every job has value one; occupied time is not the objective function.^[ref]

Consider these six original jobs, with arbitrary time units:Job $B=[1,3)$ can be followed immediately by $C=[3,5)$ and $D=[5,7)$. Job $A=[0,6)$ conflicts with all three. Starting the resource earlier is therefore not automatically beneficial: one long commitment can displace several shorter requests.

The earliest-finish greedy algorithm uses a sorting algorithm to put jobs in nondecreasing finish time. Scan that order, accepting the first job and then each job whose start is at least the last accepted finish. Break finish-time ties arbitrarily; an empty input returns the empty set. For these jobs, the order and decisions areAfter $B,C$, job $A$ starts before the current finish five and is rejected. Accept $D$; then reject $E=[6,9)$ because six is before seven. Finally accept $F=[8,10)$. The result is $S=\{B,C,D,F\}$, with cardinality four. Leaving $[0,1)$ idle makes room for more jobs.

By contrast, the earliest-start rule scans $A,B,C,D,E,F$. It accepts $A$, skips $B,C,D$, accepts $E$, and skips $F$. Its feasible solution $\{A,E\}$ contains only two jobs. Here $A$ and $E$ meet at time six and are compatible; $E$ and $F$ overlap on $[8,9)$.

There is also an elementary optimality certificate for this example. The four subsets $\{A,B\}$, $\{C\}$, $\{D,E\}$ and $\{F\}$ form a partition of a set of the jobs. A feasible solution takes at most one job from each group: $A,B$ overlap, as do $D,E$, and each other group is a singleton. Hence four is an upper bound, attained by $\{B,C,D,F\}$. Checking all $2^6=64$ subsets gives a unique optimum of size four: $\{B,C,D,F\}$.

The earliest-finish theorem states that this greedy algorithm maximizes job count for every finite instance of interval scheduling. For the exchange argument, let $q$ be the first job in an optimal feasible solution and $g$ an earliest-finishing job. Every later selected job $j$ satisfiesReplace $q$ by $g$; compatibility and cardinality survive. The remainder must be optimal among jobs starting at or after $f_g$, or improving it would improve the whole selection. Mathematical induction on the smaller remaining instance, starting with the empty set, completes the outline.^[ref]

Why is the algorithm fast? Once sorted, each job is examined once, using only the last accepted finish to decide compatibility. The scan takes $O(n)$ time; comparison sorting algorithms give total time complexity $O(n\log n)$ for $n\ge 2$, in Big O notation, assuming constant-cost endpoint comparisons. Already sorted input needs only the $O(n)$ scan.^[ref]

The reason the shortcut is correct is stronger than "finishing sooner looks good": the exchange argument preserves every later job of a suitable optimum. This is the problem-specific fact that permits final decisions without exploring all subsets.

The Kolmogorov axioms describe a consistent way to assign probabilities to events. Start with a sample space $\Omega$ and an event sigma-algebra $\mathcal{F}$: it contains $\Omega$ and is closed under complements and countable unions, hence also countable intersections. The probability measure is a function $\mathbb{P}:\mathcal{F}\to \mathbb{R}$ satisfyingThe triple $(\Omega ,\mathcal{F},\mathbb{P})$ is a probability space. The third axiom is countable additivity; the infinite series means the limit of a sequence of nonnegative partial sums. It applies to pairwise disjoint events, not to overlapping events and not to arbitrary uncountable unions.^[ref]

The sigma-algebra specifies which questions have probabilities, while the axioms specify how those probabilities fit together. For a finite sample space one can take the entire power set; a continuous model commonly uses a Borel sigma-algebra. Nonnegativity and normalization do not require equally likely outcomes or independence: those are additional modelling choices.

For an exact six-outcome model, take $\Omega =\{1,2,3,4,5,6\}$, $\mathcal{F}=\mathcal{P}(\Omega )$, and assign $\mathbb{P}(\{k\})=k/21$. The total is one because $1+2+3+4+5+6=21$. Define the probability of an event by summing the weights of its outcomes. The disjoint events $A=\{1,2\}$, $B=\{3,4\}$ and $C=\{5,6\}$ form a partition of a set withThis is a specified mathematical model, not measured die frequencies. The figure makes probability literal area: each region has the same height and a width proportional to its assigned mass. Regrouping disjoint events preserves their total area.

Several familiar rules are consequences, not further axioms. Finite additivity of a set function follows by appending empty events to the sequence in countable additivity; $\mathbb{P}(\varnothing )=0$ follows already by writing $\Omega =\Omega \cup \varnothing$ as a disjoint union. The complement rule of probability gives $\mathbb{P}(A^c)=1-\mathbb{P}(A)$ and therefore $0\le \mathbb{P}(A)\le 1$. Splitting larger events into a smaller event and a set difference shows $A\subseteq B\Rightarrow \mathbb{P}(A)\le \mathbb{P}(B)$.

For overlapping events, the inclusion-exclusion principle corrects double counting:In the six-outcome model, $D=\{2,3\}$ and $E=\{3,4\}$ give $5/21+7/21-3/21=9/21$, agreeing with the weight of $\{2,3,4\}$. This decomposition is useful because a complicated event can be assembled from simpler questions with known probabilities.

On a finite sample space, a family of pairwise disjoint events has only finitely many nonempty members, so finite additivity of a set function already handles every countable disjoint union. On an infinite sample space, the countable axiom additionally controls what is left beyond every finite stage. In the fair-coin waiting model of continuity of probability, the finite-stage calculations $\mathbb{P}(\text{first head at toss }j)=2^{-j}$ sum to $1-2^{-n}$ through toss $n$. Countable additivity makes the probability of a head at some finite toss equal to ${\sum }_{j\ge 1}{2}^{-j}=1$; finite-stage sums alone do not justify that passage. For the continuous uniform distribution on $[0,1]$, each singleton instead has probability zero, while their uncountable union has probability one. Countable, rather than unrestricted, additivity accommodates both models.

Historically, Kolmogorov's 1933 book Grundbegriffe der Wahrscheinlichkeitsrechnung established the influential axiomatic framework connecting probability theory with measure theory. The three conditions above are the modern presentation on a sigma-algebra. Shafer and Vovk's historical study explains that the original presentation began with finite additivity on an algebra of sets and added continuity for decreasing events with empty intersection, which supplies the countable extension.^[ref]

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]