Codex @codex  0

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

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.

The complement of a subset $A$ within a specified universal set $U$ contains exactly the set elements of $U$ excluded from $A$:Here $A^c$ depends on the chosen universal set. Within $U$, taking a complement performs logical negation (NOT) on membership. Writing $U\setminus A$ keeps the ambient set visible when there could be ambiguity.

For $A=\{1,2,3\}$, $B=\{3,4\}$, and $U=\{1,2,3,4,5,6\}$:If the universal set grows to $U^{\prime }=\{1,2,3,4,5,6,7\}$, the same sets have different complements: $U^{\prime }\setminus A=\{4,5,6,7\}$ and $U^{\prime }\setminus B=\{1,2,5,6,7\}$. In a database illustration, “records that fail this condition” therefore requires deciding which records are eligible to begin with; those eligible records form $U$.

For subsets $A,B\subseteq U$, De Morgan's laws exchange union and intersection when taking complements:For the same example, failing both conditions leaves $U\setminus (A\cup B)=\{5,6\}=(U\setminus A)\cap (U\setminus B)$. Failing at least one condition leaves $U\setminus (A\cap B)=\{1,2,4,5,6\}=(U\setminus A)\cup (U\setminus B)$. This is useful for rewriting exclusion rules into separate membership tests. The symmetry is also pleasing: exchanging union with intersection turns one rule into its partner.

A brief membership proof works in classical propositional logic. For any $x\in U$, let $P$ mean $x\in A$ and $Q$ mean $x\in B$. The truth table below checks all four possibilities, with $1$ meaning true and $0$ false:Each paired column agrees. Translating logical disjunction (OR), logical conjunction (AND), and logical negation (NOT) back into membership proves the two set equalities. For the general method of reducing set equalities to equivalences in propositional logic, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), §4.1.5 and Problem 4.5.

A historical perspective appears in Augustus De Morgan's ^[ref]: he describes treating each name together with its contradictory name. In the membership viewpoint here, a set and its complement likewise pair a condition with its logical negation.

A measure is complete when every subset of each null set is a measurable set. Such a subset also has measure zero by monotonicity. The completion of a measure extends it to a complete measure by adjoining all subsets of measurable null sets to its sigma-algebra.

The completion of a measure space adjoins every subset of every measurable null set to its sigma-algebra. A statement that two events or σ-algebras agree modulo null sets becomes literal after passing to the corresponding measure-algebra completion.

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.

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 map $f:X\to Y$ between topological spaces is continuous when every open set $V\subseteq Y$ has an inverse image $f^{-1}(V)=\{x\in X:f(x)\in V\}$ that is an open set in $X$. The notation denotes a subset, so $f$ need not have an inverse function.

For the continuous map $f:\mathbb{R}\to \mathbb{R}$, $f(x)=x^2$, with the usual metric topology,The two open intervals form an open set; an inverse image can split into separate pieces without violating continuity. The defining condition concerns inverse images, rather than images: here $f((-1,1))=[0,1)$ is not an open set in the real line. Checking this one inverse image illustrates the definition; it alone does not prove continuity for all target open sets.

A convex set permits every intermediate mixture of two of its points. If two choices meet its constraints, continuously averaging them also meets those constraints. This geometric property makes many feasible regions easier to explore: there is no forbidden gap along a straight move between feasible choices.

Formally, a subset $C$ of a real vector space is convex whenThe parameter $t$ traverses the entire line segment, including both endpoints. The definition does not require a closed subset, a bounded set, or a nonempty interior. The empty set, the whole vector space, and every affine subspace are convex; an open unit disk and a closed unit disk are both convex.^[ref]

The triangle inequality verifies the disk example directly: if $\Vert x\Vert ,\Vert y\Vert \le 1$, then $\Vert (1-t)x+ty\Vert \le (1-t)\Vert x\Vert +t\Vert y\Vert \le 1$. For the open disk, the last inequality is strict. The unit circle fails the same test: $(1,0)$ and $(-1,0)$ belong to it, but their midpoint $(0,0)$ does not. A curved route along the unit circle connects the endpoints, so being path-connected is weaker than being a convex set.

The distinction between a convex set and a convex function matters. The former concerns where one may choose a point; the latter concerns how a value changes along line segments. Convex optimization combines both: averaging preserves feasibility, and a convex function obeys an upper bound by the corresponding average of endpoint values. A convex set alone does not make an arbitrary objective a convex function or eliminate its inferior local minima.