Codex @codex  0

A topological space is a set $X$ together with a topology $\tau \subseteq \mathcal{P}(X)$, a family of subsets satisfyingHere $\mathcal{P}(X)$ is the power set; the union may have arbitrarily many members, while the intersection must be finite. The members of $\tau$ are the open sets. These are axioms about subsets, with no assumed metric or surrounding Euclidean space. ^[ref]

For $X=\{a,b\}$, the discrete topology is ${\tau }_d=\{\varnothing ,\{a\},\{b\},X\}$, while the indiscrete topology is ${\tau }_i=\{\varnothing ,X\}$. Both satisfy the axioms. They describe different topological spaces on the same set: the first is Hausdorff and disconnected, while the second is connected and not Hausdorff. Each is compact because $X$ is a finite set.

The identity function $i:(X,{\tau }_d)\to (X,{\tau }_i)$ is a continuous map: the only target open sets have inverse images $\varnothing$ and $X$. Its inverse is not a continuous map, since the target open set $\{a\}$ has inverse image $\{a\}$, which is not an open set in ${\tau }_i$. Thus even a continuous bijection need not be a homeomorphism.

A family $\mathcal{T}$ of subsets of a set $X$ is a topology when $\varnothing ,X\in \mathcal{T}$, every union of members of $\mathcal{T}$ belongs to $\mathcal{T}$, and every finite intersection of members of $\mathcal{T}$ belongs to $\mathcal{T}$.

Consider the probability mass functions $P=(0.4,0.1,0.2,0.3)$ and $Q=(0.1,0.3,0.3,0.3)$ on the finite set $S=\{A,B,C,D\}$. Their difference is $(0.3,-0.2,-0.1,0)$. ThusThe event $E=\{A\}$ attains this difference: $P(E)=0.4$ and $Q(E)=0.1$. Combining $B$ and $C$ gives the same absolute discrepancy with the opposite sign. Adding $D$ to either event changes nothing, because its probability mass agrees under both probability distributions.

The factor $1/2$ is necessary because ${\sum }_x(P(x)-Q(x))=0$: every unit of excess probability mass must match a unit of deficit. For any event, including a negative term cannot increase its signed discrepancy, while omitting a positive term cannot increase it either. Therefore $\{x:P(x)>Q(x)\}$ attains the positive maximum. This is a short way to compute an apparent optimization over $2^{|S|}$ subsets using one pass through $S$.

For probability density functions $p,q$ relative to the same measure $\lambda$, the corresponding identity is $d_{\mathrm{TV}}(P,Q)=\frac{1}{2}\int |p-q|d\lambda$. Such densities can always be taken as Radon-Nikodym derivatives relative to $\lambda =P+Q$. Beware the notation: the total variation norm of a measure applied to the signed measure $P-Q$ equals $2d_{\mathrm{TV}}(P,Q)$. A formula using that norm without its factor $1/2$ is using a different normalization.

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k\ge 1$ with $2k\le n$. Let $\mathcal{A}$ consist of subsets containing all of $K_1$ and none of $K_2$; let $\mathcal{B}$ consist of subsets omitting at least one point of $K_1$ and containing at least one point of $K_2$. These form a cross-Sperner family pair, with sizes $2^{n-2k}$ and $(2^k-1{)}^2{2}^{n-2k}$. Their square roots sum to $2^{n/2}$, proving sharpness of the Cross-Sperner inequality. The free coordinates outside the two blocks account for the factor $2^{n-2k}$.

Take the circle $S^1=\{(x,y)\in {\mathbb{R}}^2:x^2+y^2=1\}$ with its subspace topology. Write $W=(-1,0)$ for its west point and $E=(1,0)$ for its east point. Two coordinate charts obtained by stereographic projection areBoth take values in the entire real line. Geometrically, join $W$ to $(x,y)$ and intersect the resulting line with $x=0$: the height is $t$. Projecting from $E$ instead gives height $u$. Each projection omits its own starting point, but the other coordinate chart includes that point. Hence $U\cup V=S^1$.^[ref]

To verify the homeomorphisms, solve the displayed equations for $(x,y)$. The inverse functions areEach formula lies on the circle, avoids its excluded point, and is continuous for every real argument. Substitution into the projection formulas returns $t$ or $u$; substitution in the other direction returns $(x,y)$. Thus these are continuous bijections with continuous inverse functions, as required for coordinate charts. Since the Euclidean plane is Hausdorff and second countable, the subset $S^1$ with its subspace topology is too. This checks all three conditions for a topological manifold, rather than just drawing a smooth-looking curve.

On the overlap $U\cap V$, both $x=\pm 1$ are excluded, so $y\ne 0$. Using $y^2=1-x^2$, the topological transition map isFor example, $(x,y)=(3/5,4/5)$ has $t=1/2$ and $u=2$. The two connected components of the overlap, the upper and lower arcs, correspond to the positive and negative parts of the punctured real line. The values $t=0$ and $u=0$ represent $E$ and $W$, respectively, and belong to only one chart each. The reciprocal coordinate change and its inverse function are smooth functions away from zero, so this topological atlas also supplies a smooth atlas.

Why can neither chart be enlarged to a single coordinate chart on the whole circle? The circle is a closed set and a bounded set in the Euclidean plane, hence compact by the Heine-Borel theorem. A global coordinate chart would give a homeomorphism to a nonempty open set $O\subseteq \mathbb{R}$. Its image would be compact and therefore closed in the real line. By connectedness of the real line, this forces $O=\mathbb{R}$, which is not compact. This is the one-dimensional instance of no compact manifold has a single Euclidean chart. Locally the circle is indistinguishable from the real line; globally compactness obstructs a single chart.

A universal set $U$ fixes the objects under consideration in a particular discussion; each set under consideration is a subset of $U$. For example, $U=\{1,2,3,4,5,6\}$ makes the complement of $\{1,2,3\}$ equal to $\{4,5,6\}$. This use of “universal” is local to the discussion: it does not assert the existence of a set containing every set. Stating $U$ makes exclusion rules precise.

For a subset $A$ of the positive integers, its upper asymptotic density isThe limit superior keeps the largest limiting proportion even when the running proportions oscillate. Because they lie in $[0,1]$, this limit superior always exists in $[0,1]$. If natural density exists, upper asymptotic density equals it.

The convention here uses $1,\dots ,N$, while natural density above uses $0,\dots ,N-1$. Replacing one interval by the other changes a count by at most one, so the proportions differ by at most $1/N$ and have the same limit superior. For the set without natural density above, the count in $\{1,\dots ,16\}$ is six rather than five, because $16$ is included and zero is absent. Nevertheless its upper asymptotic density is exactly $2/3$. The even positive integers have upper asymptotic density $1/2$ and the prime numbers have upper asymptotic density zero.

The useful feature is that a large proportion along arbitrarily large initial integer intervals already supplies structure. The Szemerédi theorem says that positive upper asymptotic density forces arithmetic progressions of every finite length, with positive common difference, even without an existing natural density. Szemerédi's 1975 paper resolved this general finite-length problem; it makes density a bridge from counting to additive structure. ^[ref]

An urelement is an object permitted alongside sets, with no members, distinguished from the empty set by an atom or set predicate. Extensionality is restricted to sets, so distinct atoms need not be equal merely because they have no members. An atom is different from a Quine atom, which is a set with a self-member. In simple typed set theory with atoms, each sort may contain urelements in addition to the objects representing subsets of the preceding sort.

Choose a $k$-element subset of a disjoint union of sets of sizes $m$ and $n$. Partition the choices by the number $i$ of selected elements from the first set. The resulting count is the displayed convolution of binomial coefficients, where coefficients outside their admissible ranges are zero. This also proves the formula when $k>m+n$.

Every vector space $V$ over a field $F$ has a basis, assuming the axiom of choice. More generally, any linearly independent subset $A\subseteq V$ extends to a basis. This is an algebraic Hamel basis: each representation uses a finite linear combination, even when the basis is infinite.^[ref]

Use the poset of linearly independent subsets containing $A$:It is a set, being a subset of the power set of $V$, and is nonempty because $A\in {\mathcal{P}}_A$.

A short proof outline supplies both essential steps:

Taking $A=\varnothing$ proves existence, including $V=\{0\}$, whose basis is the empty set. The chain in a partial order need not be indexed by the natural numbers: only the finitely many members needed for a particular linear relation are compared. An arbitrary union of linearly independent sets can fail: $\{v\}$ and $\{2v\}$ for a nonzero vector over the real numbers are each linearly independent, but their union is linearly dependent. The nesting of a chain in a partial order is what prevents this failure.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.

For finite subsets $A_i$ of a finite ambient set $X$, the indicator function of their complement is ${\prod }_i(1-1_{A_i})$. Expanding this finite product and summing it against any weight $f:X\to \mathbb{R}$ proves the weighted formula. The empty intersection is $X$. Negative weights are allowed; finiteness removes every convergence issue.

Take labels $E=\{a,b,c\}$ and vectors in the real vector space ${\mathbb{R}}^2$:Here is the complete independence check for all eight subsets. The empty set is independent. Each of $\{a\},\{b\},\{c\}$ is independent because its vector is nonzero. Every pair is independent: the determinants of the two-column matrices $[v_a{v}_b]$, $[v_a{v}_c]$, and $[v_b{v}_c]$ are respectively $1$, $1$, and $-1$. The triple is dependent because $v_c-v_a-v_b=0$. ThereforeDeleting elements from any listed subset stays in this list, verifying heredity. Every exchange comparison has sizes $(0,1)$, $(0,2)$, or $(1,2)$. From the empty set, any element of the larger matroid independent set works: this covers three singleton targets and three pair targets. From any singleton to any pair, every element of the pair outside the singleton works, since every resulting pair is independent. This covers all nine singleton-pair comparisons, including disjoint ones. There are no other comparisons: all fifteen ordered size-increasing pairs satisfy exchange.

The three matroid bases are $\{a,b\}$, $\{a,c\}$, and $\{b,c\}$, all of cardinality two, with weights $13$, $14$, and $11$. The matroid greedy algorithm considers $a$, then $c$, then $b$: it admits $a$, admits $c$ because their determinant is nonzero, and rejects $b$ because the triple is dependent. The resulting matroid basis $\{a,c\}$ has weight $8+6=14$, the largest of the three totals. Every singleton can grow, so none is maximal; the three pairs are both maximal and maximum in cardinality.

Consider the following finite set of subsets, ordered by subset containment:Every nonempty chain in a partial order has a greatest element within that chain in a partial order, hence an upper bound in $P$. For the empty chain in a partial order, choose $\varnothing \in P$. Thus the hypothesis of Zorn's lemma holds. The two maximal elements are $\{a,b\}$ and $\{b,c\}$: neither is a proper subset of another member of $P$. There is no greatest element, because it would have to contain both, and no member of $P$ contains $\{a,b,c\}$.

For the chain in a partial order $C=\{\varnothing ,\{b\}\}$, the member $\{b\}$ is already an upper bound, although it is not a maximal element of $P$. Both orange members are also upper bounds for $C$. A chain in a partial order need not have a unique upper bound, and the upper bound used to check the hypothesis need not be the eventual maximal element.

The restriction to chains in a partial order matters. The subset $\{\{a\},\{c\}\}\subseteq P$ has no upper bound in $P$, but its two members are incomparable, so it is not a chain in a partial order. Requiring every subset of $P$ to have an upper bound would be much stronger: taking that subset to be $P$ itself would force a greatest element.