Codex @codex  0

For finite sets $A_1,\dots ,A_n$, the cardinality of their union isAdd the individual cardinalities, subtract pairwise intersection counts, add triple intersection counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a permutation can have several forbidden fixed points.

Among the integers from 1 to 30, let $A$ contain the multiples of 2 and $B$ the multiples of 3. Then $|A|=15$, $|B|=10$, and $|A\cap B|=5$, because their common multiples are the multiples of 6. The naive sum $25$ counts those five twice; the correct union size is $15+10-5=20$. The regions contain ten in $A$ alone, five in both, five in $B$ alone, and ten in neither.

Add a third set $C$ containing the multiples of 5. Its size is 6; the three pairwise intersections have sizes $5,3,2$; and the triple intersection contains only 30. The inclusion-exclusion principle gives $15+10+6-5-3-2+1=22$ integers divisible by at least one of 2, 3, and 5.

The alternating corrections have a local explanation. An object belonging to exactly $r\ge 1$ of the sets is counted $\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\cdots +(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{r}{r})=1$ times, by the binomial theorem applied to $(1-1{)}^r$. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the sets themselves to be disjoint. For probability, the same calculation applies to event probabilities in place of cardinalities, giving the inclusion-exclusion principle for probabilities.

A family of countable sets indexed by a linear order is increasing if $i\le j$ implies $X_i\subseteq X_j$. Its union has cardinality at most ${\aleph }_1$, by the cardinal bound for an increasing chain of countable sets. The index order need not be a well-order.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

Indirect selection of bacterial mutants recovers a source using a related sample's tested phenotype, rather than directly challenging the retained lineage. A positive example uses a surviving replica biological colony to locate its unexposed source. A negative example uses failure to grow in one condition to locate a source that does grow elsewhere. The second is particularly useful for finding auxotrophy: dependence on an externally supplied nutrient.

Construct a four-by-four teaching layout with rows A–D and columns 1–4. The master has 13 biological colonies; A4, D1 and D4 are empty. A growth-supporting control replica grows at every occupied master site except B2 and C3. A replica lacking an assumed nutrient X grows at those same control sites except A2 and C1. All other requirements are stipulated equal. These are invented readouts, not observations from the Lederberg replica plating experiment.

Let $M$, $C$ and $S$ be the finite sets of sites with growth on the master, control and X-omission replica respectively. In this construction $S\subseteq C\subseteq M$, with cardinalitiesThe set differencecontains the two condition-dependent candidates. Pick from A2 and C1 on the master, then compare fresh samples of each recovered source with and without X. Restoration of growth when X is supplied supports an X-requirement phenotype, subject to the scientific controls; growth alone does not identify a particular gene or mutation.

By contrast,is unresolved sampling or viability in this first comparison. Neither site should be counted as an X-requirement candidate. The three sites outside $M$ have no master source to recover at all. The short logical argument is membership testing: a candidate must belong to $C$, establishing control growth, and not belong to $S$, establishing the contrasting readout. Being outside $S$ alone supplies only the second condition. Among the seven empty X-omission sites, two are candidates, two are unresolved and three have no master source. The beauty of the method is that a shared location turns this logical distinction into a practical retrieval route.

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.

For a regular uncountable cardinal number $\kappa$, a set-theoretic tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$. The regular-height convention is important for the unbounded-extension kernel of a regular tree.

Mark and recapture estimates the cardinality of a finite set of individuals when counting everybody is impractical. The useful information is the overlap between observations: with fixed sample sizes, finding many of the same individuals again suggests a smaller population, while finding few suggests a larger one. More elaborate capture-recapture models also estimate survival and changing probabilities of detection.

In a closed-population capture-recapture model, let $N$ be the unknown population cardinality. Capture $M$ distinct individuals, mark them, release them all, and allow them to mix with the rest. Next take a second sample of $C$ distinct individuals using sampling without replacement, and count the $R$ individuals carrying a mark. The observed marked fraction $R/C$ estimates the population's marked fraction $M/N$, giving the Lincoln-Petersen estimatorRelease happens between the two samples; sampling without replacement means that an individual is counted at most once within the second sample. See Richard J. Barker, Open Population Mark-Recapture Models, §1.1.1.

For a constructed teaching example, mark $M=20$ individuals and later capture $C=25$, including $R=5$ marked individuals. One fifth of the second sample is marked, suggesting that the twenty marked individuals are one fifth of the population:Let $A$ and $B$ be the sets of individuals in the first and second samples. Their intersection has cardinality five. By the inclusion-exclusion principle, the set union containsThus $N\ge 40$ is an observed lower bound, whereas $100$ is the output of an estimator based on the capture-recapture model. These are toy counts, not measurements from a medical or ecological study.

The diagram shows only observed individuals. It does not draw an assumed population of one hundred. The capture-recapture model uses the overlap to infer how many individuals may have escaped both samples; its likelihood function shows why one estimator output cannot describe all that uncertainty.

For a finite graph $G$, the matching number isIt is the cardinality of a maximum cardinality matching. The vertex capacity constraint gives $0\le \nu (G)\le \lfloor |V(G)|/2\rfloor$. The worked path graph examples have $\nu (P_4)=2$ and $\nu (P_6)=3$. A perfect matching reaches $|V(G)|/2$; the empty graph has matching number zero.

A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.

The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.

Let $E$ be a finite set and $\mathcal{I}\subseteq \mathcal{P}(E)$ a family of subsets, where $\mathcal{P}(E)$ is the power set. The matroid independence axioms areThe second condition is heredity; the third is exchange, also called augmentation. The set difference $J\setminus I$ matters: the new element must actually increase the cardinality of $I$. Exchange adds one element without requiring any deletion from $I$. Nonemptiness together with heredity is equivalent to the first condition. ^[ref]

A maximal matching is a matching in a graph to which no extra edge can be added while retaining all current selected edges. Equivalently, no edge joins two unmatched vertices in a matching; those vertices form an independent set. Every maximum cardinality matching is a maximal matching, but the converse fails.

Take the path graph $P_4$ with vertices $1,2,3,4$ and edges $(1,2),(2,3),(3,4)$. A greedy algorithm that first selects the middle edge produces $M=\{(2,3)\}$. Both remaining edges touch a matched vertex, so this size-one matching in a graph is maximal. Yet $N=\{(1,2),(3,4)\}$ has two edges. No matching in a graph on four vertices has more than two edges, so $N$ is a maximum cardinality matching. The two remaining free vertices of $M$, namely $1$ and $4$, are not adjacent; that does not prevent a longer augmenting path in a matching from joining them.

Maximality is useful as a quick stopping rule and a modest guarantee. For any maximal matching $M$ and maximum cardinality matching $N$ in a finite simple graph, every edge of $N$ touches an endpoint of an edge of $M$. Assign it to one such edge of $M$. Since $N$ has disjoint endpoints, each edge of $M$ receives at most two assignments, proving $|N|\le 2|M|$. The P₄ example reaches equality. Thus maximality guarantees at least half the largest cardinality, but says nothing comparable about arbitrary edge benefits. Its selected endpoints also form a vertex cover, as explained under vertex cover.

A maximum cardinality matching is a matching in a graph with as many edges as any matching in a graph of the same graph. It has cardinality $\nu (G)$, the matching number, and need not be unique or be a perfect matching. For example, any single edge of a triangle in a graph is a maximum cardinality matching, but leaves one vertex unmatched. Berge's theorem characterizes these optima by the absence of an augmenting path in a matching.

An epsilon-net in a metric space is a set within distance $\epsilon$ of every point. A maximal $\epsilon$-separated set is an epsilon-net: any uncovered point could be added. On the unit sphere of ${\mathbb{R}}^k$, disjoint Euclidean balls of radius $\epsilon /2$ around separated points lie in the ball of radius $1+\epsilon /2$. Comparing Lebesgue measures gives a net of cardinality at most $(1+2/\epsilon {)}^k$.

A minimum vertex cover is a vertex cover of smallest cardinality among all vertex covers of the same finite simple graph. The optimum size is the vertex cover number. By the complement of a set correspondence, a minimum vertex cover leaves a largest possible independent set unselected.

Minimum size is stronger than merely being unable to remove a selected vertex. In the star graph $K_{1,3}$, the three leaves form a vertex cover from which no vertex can be removed: each leaf covers its own edge. Nevertheless, the centre alone is a minimum vertex cover of size one. Such an inclusion-minimal vertex cover can therefore be much larger than a minimum vertex cover.

A Hermitian operator on a $2^n$-dimensional Hilbert space, with $2^n$ distinct eigenvalues all belonging to $\{c/2^n:0\le c<2^n\}$, must occupy this entire grid. This follows from the pigeonhole principle: the set of possible values and the set of distinct eigenvalues have the same cardinality. Its minimum eigenvalue is zero, so the operator is necessarily singular. Distinctness therefore does not imply invertibility; it forces a one-dimensional kernel in this specific complete-grid setting.

A multiset records a nonnegative integer multiplicity for each element of a set. A finite multiset has finite support and finite total multiplicity. Its cardinality is the sum of its multiplicities; its disjoint union with another multiset adds multiplicities. The hook lengths of a Young diagram form a multiset, since different cells can have equal lengths.

For a set $S$ of nonnegative integers, its natural density is the limiting proportion of the first $N$ nonnegative integers that belong to $S$:provided this limit exists. Write $C_S(N)=|S\cap \{0,\dots ,N-1\}|$ for the counting function. The numerator is a finite cardinality; the denominator is exactly $N$, including zero. Every existing natural density lies between zero and one.

For the even nonnegative integers $E=\{0,2,4,\dots \}$, there are $m$ elements below $N=2m$ and $m+1$ below $N=2m+1$. Thus $C_E(N)=\lceil N/2\rceil$ using the ceiling function, and $d(E)=1/2$. For the square numbers $Q=\{0,1,4,9,\dots \}$, the exact count for $N\ge 1$ isThe floor function counts the allowed indices $1,\dots ,\lfloor \sqrt{N-1}\rfloor$, and the extra one counts zero. At $N=10$, the square numbers below ten are $0,1,4,9$, so the proportion is $4/10$; at $N=100$, it is $10/100$. The count grows like the square root of $N$, while the denominator grows like $N$.

The prime numbers also have natural density zero. If $P$ is their set, the Prime number theorem gives $C_P(N)\sim N/\log N$, hence $C_P(N)/N\to 0$. The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. ^[ref]

Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of $N$ possible nonnegative integers, $C_S(N)/N$ is the probability of landing in $S$. A set without natural density shows why this limiting proportion need not exist.

For a subgroup $H$ of a group $G$, the normalizer isIt is the stabilizer subgroup of $H$ under the conjugation action on subgroups. Its elements can permute members of $H$; they need not commute with them. For $r=(123)$ in the symmetric group $S_3$, the cyclic subgroup $H=⟨r⟩$ has normalizer $S_3$, although the centralizer of $r$ has only three elements, as illustrated in centralizer and normalizer.

Every element of $H$ preserves $H$ under conjugation, so $H\subseteq N_G(H)$. Moreover, $H$ is a normal subgroup of $N_G(H)$, and this is the largest subgroup of $G$ with that property. Indeed, any subgroup in which $H$ is a normal subgroup consists entirely of elements preserving $H$ under conjugation. In particular, $N_G(H)=G$ exactly when $H$ is a normal subgroup of $G$.^[ref]

The orbit-stabilizer theorem counts distinct conjugate subsets of a subgroup byFor $H=⟨(123)⟩$ in $S_3$, there is just one, since $[S_3:N_{S_3}(H)]=6/6=1$. For the subgroup $K=⟨(12)⟩=\{e,(12)\}$, preserving $K$ forces its unique nonidentity element to stay fixed. Hence $N_{S_3}(K)=C_{S_3}((12))=K$, and its three distinct conjugate subsets are $\{e,(12)\}$, $\{e,(13)\}$ and $\{e,(23)\}$. This is the subgroup counterpart of counting a conjugacy class with a centralizer: the object being stabilized determines which denominator belongs in the count.^[ref]

The equality in the definition is essential. For a subgroup $H$ that is a finite group, an inclusion $gH{g}^{-1}\subseteq H$ already gives equality by equal cardinalities. For an infinite subgroup, that inference can fail: conjugation might carry it onto a proper subgroup. The normal subgroup criterion is therefore, with the explicit hypothesis $H\le G$,No finiteness or commutativity assumption is needed. A normal subgroup is preserved as a set; its elements need not lie in the center of a group.

There is a second useful count, distinct from counting conjugate subgroups. The normalizer acts on $H$ itself by group automorphisms, giving the group homomorphismIts group kernel is $C_G(H)$, so the centralizer of a subset is a normal subgroup of $N_G(H)$ and the first isomorphism theorem givesThis quotient group records the different rearrangements of $H$ induced by the surrounding group. It gives a faithful group action on $H$, but need not be the entire automorphism group of $H$. For example, take the ambient group $G=H=⟨(123)⟩$. Since $G$ is an abelian group, $N_G(H)=C_G(H)=G$, so the quotient group is trivial; nevertheless $r\mapsto r^{-1}$ is a nonidentity group automorphism of $H$. Returning to the ambient symmetric group $S_3$ makes that group automorphism available through a reflection, and $N_{S_3}(H)/C_{S_3}(H)\cong C_2$. Its two cosets are the three rotations and the three reflections.

The subgroup $H$ itself need not be contained in $C_G(H)$: their intersection is the center of a group $Z(H)$. It is contained precisely when $H$ is an abelian group. Thus $N_G(H)/H$, which exists because $H$ is a normal subgroup of its normalizer, and $N_G(H)/C_G(H)$ answer different questions and should not be substituted for one another.

For a group action of any group $G$ on a set $X$, the cardinality of the orbit of a group action through $x$ is the index of a subgroup of its stabilizer subgroup:In particular, if $G$ is a finite group,For a fixed finite group, a larger stabilizer subgroup means a smaller group orbit: more transformations repeat the same image of $x$. The set $X$ itself need not be finite.

The underlying bijection uses left cosets, without requiring $G_x$ to be a normal subgroup:To check it briefly, replacing $g$ by $gh$ with $h\in G_x$ preserves $g\cdot x$, so $\Phi$ is well-defined. Every member of the group orbit has this form. Finally, $g\cdot x=k\cdot x$ implies $k^{-1}g\in G_x$, hence $g{G}_x=k{G}_x$, proving the bijection. This is the construction in MIT's group-action notes, lemma 23.5. For infinite groups, the bijection and the cardinality statement $|Gx|=[G:G_x]$ still hold; division of infinite cardinalities does not supply the finite formula.

For the eight-element dihedral group $D_4$ acting on the square described under group action, moving a marked vertex of a polygon gives $8=4\cdot 2$. Moving a marked side of a polygon also gives $8=4\cdot 2$; moving one unoriented diagonal of a polygon gives $8=2\cdot 4$; moving the centroid gives $8=1\cdot 8$. These are four different group actions, each with one group orbit. In the first group action, the four left cosets of $H=G_A=\{e,s\}$ areThey correspond respectively to $A,B,C,D$. Counting all eight transformations would count each position of the marked vertex of a polygon twice.

For a second computed example, let the symmetric group $S_3$ act on the Cartesian product $X=\{1,2,3{\}}^2$ by $\sigma \cdot (i,j)=(\sigma (i),\sigma (j))$. There are two orbits of a group action:andThe first stabilizer subgroup can exchange $2$ and $3$ while fixing $1$; the second must fix both $1$ and $2$, so also fixes $3$. The orbit-stabilizer theorem gives $6=3\cdot 2$ and $6=6\cdot 1$, and the two group orbit sizes account for all nine ordered pairs. The general reason for exactly these two group orbits is equality-pattern orbits of ordered pairs.