Codex @codex  0

The ground set is the set of labelled elements available for selection. An independence system specifies which subsets of this ground set are admissible; in a linear matroid the labels index vectors, whereas in a graphic matroid they index edges.

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

The Hall condition requires enough distinct neighbours for every subset of the specified left vertex set in a finite bipartite graph. Checking the whole left set establishes only one inequality. Checking singleton sets establishes only that each left vertex has positive degree of a vertex. Overlapping lists can pass both tests and still fail to admit matching saturation of the left side.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

For sufficiency, take a matching in a graph of maximum size and suppose a left vertex $u$ is unmatched. Follow unused edges from left to right and matching edges back to the left. An unmatched reachable right vertex yields an augmenting path in a matching, contradicting maximal size. Otherwise let $S,T$ be the reachable left and right sets. Every member of $T$ is matched to a distinct member of $S\setminus \{u\}$, and every member of $S\setminus \{u\}$ is reached this way. Since $N(S)=T$, we obtain $|N(S)|=|S|-1$, contradicting the Hall condition. Finiteness ensures that a maximum-size matching in a graph exists.

The alternative Hall induction through a tight set uses mathematical induction: a proper nonempty subset with $|N(S)|=|S|$ splits off a balanced induced subgraph; without such a tight set, deleting one chosen edge's endpoints preserves the Hall condition on the smaller left side.

Hausdorff measure measures the geometric size of a set using covers by increasingly small pieces. The exponent $s$ chooses the measuring scale: $s=1$ is length-like, $s=2$ is area-like, and noninteger exponents can measure fractals. Unlike a count of occupied grid cells, the construction allows pieces of different sizes and considers every admissible cover.

For $s>0$ and a subset $E$ of a metric space, use the diameter-cost conventionThe first quantity is scale-restricted Hausdorff content. Shrinking $\delta$ removes options from the infimum, so these contents increase to a limit, possibly infinite. The resulting outer measure restricts to a measure on the Borel sets. For $s=0$, counting each nonempty covering piece with cost one gives counting measure.

A different common convention multiplies these quantities by $c_s={\pi }^{s/2}/(2^s\Gamma (1+s/2))$, using the Gamma function. At integer $s$, that normalization agrees with ordinary Euclidean $s$-dimensional volume. Here $c_1=1$, so both conventions make ${\mathcal{H}}^1$ agree with arc length on smooth curves in Euclidean space. Positive normalization constants never change Hausdorff dimension. A definition must specify this constant when numerical values of Hausdorff measure matter.

For a line segment of length $L$, splitting it into $n$ equal pieces gives the cover costIt tends to zero for $s>1$, stays at $L$ for $s=1$, and grows for $s<1$. The matching lower bound comes from the fact that any interval cover must have total length at least $L$. The exponent one is therefore the transition between a measuring rule too coarse to see the segment and one that assigns it infinite size. For a Cantor set, the transition is instead at $\log 2/\log 3$, as shown in Hausdorff dimension of the Cantor set.

This makes Hausdorff measure useful when ordinary Lebesgue measure sees too little: a curve in the plane has zero planar area but can have positive arc length, and the Cantor set has zero line length but positive geometric size at its own dimension. It also separates local covering estimates from global cardinality: a countable dense set has zero Hausdorff dimension, despite meeting every open region of its closure.

An original source for the construction is Felix Hausdorff's ^[ref]. The modern covering and Hausdorff dimension framework is developed in Bishop and Peres, Fractals in Probability and Analysis, §1.2.

For every finite $d\ge 1$, a subset $K\subseteq {\mathbb{R}}^d$ of Euclidean space is compact if and only if it is a closed set and a bounded set. Here closed means closed in the ambient Euclidean space, not merely in $K$ itself, and the bounded set condition uses the Euclidean norm. The empty set is included: it is a closed set, a bounded set, and compact. ^[ref]

This makes an apparently infinite test practical. To verify compactness of a closed interval $[a,b]$ with finite endpoints, we need not examine every open cover: it is closed in the real line and a bounded set. By contrast, the open interval $(0,1)$ is a bounded set but is not closed in the real line, as the missing-endpoint figure in compact space illustrates. The whole real line is closed but is not a bounded set, so it too fails compactness. These examples show why both hypotheses are needed.

The same criterion holds in any real or complex finite-dimensional vector space equipped with a norm: all norms there are equivalent norms, so they give the same open sets, closed sets, and bounded sets. Since compactness depends only on the topology, choosing a different norm does not change the conclusion. Without an appropriate topology, a bare vector space alone has no notion of compactness.

The restriction to a finite-dimensional vector space is essential. In the l2 sequence space, an infinite-dimensional vector space that is also a Hilbert space, let $e_n$ be the vectors of its standard orthonormal basis. All lie in the closed unit ball $B=\{x:\Vert x\Vert \le 1\}$, which is a closed set and a bounded set in the norm topology. For distinct indices, their inner product is zero, givingThus distinct terms remain distance $\sqrt{2}$ apart. No subsequence is a Cauchy sequence, hence none is a convergent sequence. The equivalence of compactness and sequential compactness in a metric space proves that this closed unit ball is not compact. The conclusion concerns the norm topology.

A short proof outline in Euclidean space explains the role of a finite-dimensional vector space. For a sequence in a bounded set, apply the Bolzano-Weierstrass theorem to each of the Cartesian coordinates in turn, retaining a subsequence at each of the finitely many steps. The final subsequence is a convergent sequence in all Cartesian coordinates, and a closed set contains its limit of a sequence. This yields sequential compactness, hence compactness. Conversely, a compact subset of a metric space is a closed set and a bounded set. ^[ref]

For a strong-limit cardinal $\lambda$ of countable cofinality, defineHere smallness bounds every individual membership extension; it does not bound the cardinality of the entire transitive closure. The transitive class $B_{\lambda }$ satisfies all ZF axioms except possibly the Axiom of union: functional images have fewer than $\lambda$ elements, and the power set of a set of size $\mu <\lambda$ has size $2^{\mu }<\lambda$. These facts give Axiom schema of replacement and Axiom of power set; pairs and definable subsets also remain locally small. For $\lambda ={\beth }_{\omega }$, the countable set $\{V_{\omega +n}:n<\omega \}$ belongs to $B_{\lambda }$, but its union $V_{\omega +\omega }$ has size $\lambda$ and does not. This gives an explicit relative-independence model for the Axiom of union.

On the ground set $E=\{x,y,z\}$, permit exactlyThis lists every admissible subset; the excluded subsets are $\{x,y\}$, $\{x,z\}$, and $\{x,y,z\}$. It is an independence system: deleting elements from $\{y,z\}$ produces its listed singletons or the empty set, and deleting from a singleton produces the empty set. But $I=\{x\}$ and $J=\{y,z\}$ violate exchange: neither $y$ nor $z$ can be added to $I$. Thus it is not a matroid.

The descending-weight greedy algorithm admits $x$ first, then rejects both $y$ and $z$, returning $\{x\}$ with weight $10$. Exchanging the tied order of $y,z$ changes nothing. The admissible pair $\{y,z\}$ weighs $12$, exceeding every singleton and the empty set, so it is the true optimum. Both $\{x\}$ and $\{y,z\}$ are maximal elements under inclusion of subsets, but only the pair has maximum cardinality. This identifies exactly where the matroid greedy algorithm loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.

A homeomorphism is a bijection between topological spaces such that both $f$ and $f^{-1}$ are continuous maps. Equivalently, for every subset $U\subseteq X$, $U$ is an open set if and only if $f(U)$ is an open set in $Y$. A homeomorphism therefore transports the entire topology, including connectedness and compactness. It need not preserve numerical metric values, and a bounded set need not map to a bounded set.

For example, an explicit homeomorphism between an open interval and the real line isThe tangent function on $(-\pi /2,\pi /2)$ is strictly increasing and takes every real value; the displayed arctangent inverse verifies the bijection. Both formulas define continuous maps on their stated domains. Computed values are $f(1/4)=-1$, $f(1/2)=0$, and $f(3/4)=1$. Points approach infinity as $x$ approaches an excluded endpoint. Thus a bounded set can have the same topology as an unbounded one; neither of these topological spaces is compact.

A useful shortcut is the compact-to-Hausdorff continuous bijection theorem: a continuous bijection from a compact space to a Hausdorff space is a homeomorphism. Its images of closed sets are compact sets, hence closed sets in the target, which proves continuity of the inverse. The indiscrete topology example shows why the Hausdorff assumption matters. ^[ref]

The hypergeometric distribution counts marked objects in a uniformly chosen sample of fixed size from a finite population, using sampling without replacement. Let $n\ge 1$ be the population size, let $0\le c\le n$ objects be marked, and sample $0\le r\le n$ distinct objects. If $K$ counts the marked objects selected, its probability mass function isThe bounds describe the support of a probability distribution and $k$ must be an integer; the mass is zero elsewhere. The denominator counts all size-$r$ subsets, while the numerator counts choices of $k$ marked and $r-k$ unmarked objects using binomial coefficients. This counting argument requires every size-$r$ sample to have the same probability.^[ref]

For a constructed example, a box contains ten labelled objects, four red and six blue. Select five without replacement. There are $\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252$ possible samples. The probabilities for $K=0,1,2,3,4$ areIn particular, $\mathbb{P}(K=2)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)\left(\genfrac{}{}{0ex}{}{6}{3}\right)/252=120/252=10/21$. Five red objects are impossible because the box only contains four. The expected value is $r(c/n)=2$, and the variance is $2/3$.

The count law also answers a detection question: what is the chance that five draws find at least one red object? By the complement rule of probability, it is $1-\mathbb{P}(K=0)=41/42$, approximately $0.9762$. This can model inspecting five distinct objects from a known finite collection, with a mark indicating the property we want to detect. If repeated inspections can select the same object again, the replacement model instead gives $1-0.6^5=0.92224$. Equal expected values therefore do not imply equal chances of detecting a marked object.

The corresponding binomial distribution counts red draws when each selected object is put back before the next independent draw: $K_{\mathrm{rep}}\sim \mathrm{Bin}(5,0.4)$. It has the same expected value $2$, but variance $5(0.4)(0.6)=6/5$, and it permits five red draws. Without replacement, a red first draw leaves red probability $3/9$ for the next draw; a blue first draw leaves $4/9$. This statistical dependence pulls the total toward the fixed composition of the population, producing the finite population correction.

The useful modelling question is whether previously selected objects remain available. A fixed-size sample of distinct items calls for a hypergeometric distribution; fresh independent trials with constant success probability call for a binomial distribution. When the population grows with $c/n\to p$ while $r$ stays fixed, the hypergeometric masses tend to the corresponding binomial distribution masses: removing finitely many objects has an increasingly small effect on the next draw's probability.

The image of a function asks which outputs a chosen set of inputs reaches. A preimage asks which inputs reach a chosen set of outputs. Both constructions apply to every function, including one that loses information by sending several inputs to the same output. Their difference is useful whenever a transformation must be followed forward or a condition on its result must be traced back.

Consider the function $f:A\to B$ withEvery input has exactly one output, but zero has two inputs and three has none. The full image of a function is $f(A)=\{0,1,2\}$, a proper subset of the codomain $B$. Selecting inputs $\{a,c\}$ gives image $\{0,1\}$. Selecting outputs $\{0,2\}$ instead gives preimage $\{a,b,d\}$.

The function is not injective, because $f(a)=f(b)$, and is not surjective onto $B$, because three is absent from its image. Restricting only the codomain to $\{0,1,2\}$ makes the same rule surjective; it remains noninjective. This separates the output set actually reached from the target set specified in the definition. The definitions of images of a function and preimages, including the distinction from an inverse function, are given in Richard Hammack, Book of Proof, §12.6: Image and Preimage.

For a function $f:X\to Y$ and a subset $E\subseteq X$, its image isThe full image of a function is $f(X)$. The set notation ignores repeated outputs: in the finite example above, $f(\{a,b\})=\{0\}$, rather than a list containing zero twice. A function collision can therefore reduce the cardinality of an image.

Images of a function preserve unions:An output reached from the union is reached from at least one of its two input sets. For intersections, however, onlyholds in general. In the finite example, take $E=\{a\}$ and $F=\{b\}$. Their intersection is the empty set, so $f(E\cap F)=\varnothing$. But $f(E)=f(F)=\{0\}$, giving $f(E)\cap f(F)=\{0\}$. Distinct witnesses in the two input sets can produce the same output.

For an injective function, an output shared by $f(E)$ and $f(F)$ must come from the same input. That input lies in $E\cap F$, so equality holds. Conversely, preserving intersections for every pair of input subsets forces injectivity: two distinct inputs with the same output would give the singleton counterexample above. The image and preimage laws are stated in Jiří Lebl, Basic Analysis I, Propositions 0.3.15–0.3.16; the finite example makes the missing reverse inclusion visible.