Codex @codex  0

A finite subset $A$ of the natural numbers, numbered from one, has the binary code ${\sum }_{j\in A}{2}^{j-1}$. Distinct finite subsets give distinct codes, because the largest differing exponent exceeds the sum of all smaller powers of two. Thus the finite subsets form a countable set, although the entire power set is an uncountable set by the Cantor diagonal argument. An enumeration transfers this coding to any countable set.

At each $\alpha \in S$, a countable family $E_{\alpha }\subseteq \mathcal{P}(\alpha )$ is supplied. Every $X\subseteq \lambda$ has $X\cap \alpha \in E_{\alpha }$ on a stationary subset of $S$. The countable-family diamond equivalence shows that this apparently weaker prediction is equivalent to a single diamond guess at each index.

Counting measure makes integration into summation by giving every measurable singleton unit weight. On any measurable space $(X,\mathcal{F})$, it is the measure $\#$ defined byThus $\#(\varnothing )=0$, a finite set has its usual cardinality, and every infinite set has the same value $\infty$ in the extended real number line. In particular, countably infinite sets and uncountable sets are not distinguished by their counting measure. Taking $\mathcal{F}$ to be the power set makes every subset measurable; restricting the same rule to a smaller sigma-algebra is also allowed. ^[ref]

Why is this a countably additive measure? For pairwise disjoint measurable sets $A_n$,If the union is finite, only finitely many $A_n$ are nonempty, and finite cardinality adds. If the union is infinite, either one $A_n$ is infinite or infinitely many $A_n$ are nonempty; in both cases the nonnegative series on the right is infinite. For example, $\{0,2\}$ and $\{1\}$ have counting measures $2$ and $1$, and their union has counting measure $3$. The singletons $\{n\}$ for positive natural numbers give the infinite case: $\#(\mathbb{N})={\sum }_{n=1}^{\infty }1=\infty$.

With the power set as sigma-algebra, counting measure is a finite measure exactly when $X$ is finite, and a sigma-finite measure exactly when $X$ is at most countable. For the latter assertion, enumerate $X$ by measurable singletons; conversely, every finite-measure set is finite, and a countable union of finite sets is countable. Specifying the sigma-algebra matters: if $X=\mathbb{N}$ and $\mathcal{F}=\{\varnothing ,\mathbb{N}\}$, counting measure is not a sigma-finite measure, since the only measurable finite-measure set is the empty set.

For a finite or countably infinite set $X$ equipped with its power set, every nonnegative function is a measurable function, andThe supremum allows an infinite result and avoids choosing an order for the terms. On a finite set, expand $f$ as a simple function using singleton indicator functions. On a countably infinite set, enumerate the points and apply the monotone convergence theorem to finite truncations. Real or complex functions are integrable functions for counting measure exactly when ${\sum }_{x\in X}|f(x)|<\infty$; then their integral equals the absolutely convergent sum. This is the discrete counterpart of Lebesgue integration, developed further in series as a Lebesgue integral against counting measure. ^[ref]

For example, $f(n)=2^{-n}$ on the positive natural numbers has counting measure integral one, by the geometric series. The alternating harmonic series has a finite ordered sum but is not the integral of an integrable function for counting measure: its positive and negative parts both have infinite sums. Absolute convergence is what makes the finite integral independent of enumeration. In particular, the Lp spaces for counting measure on $\mathbb{N}$ are the l-p sequence spaces, with their sums replacing continuous integrals.

Compare three measures on the same Borel sigma-algebra of the real numbers: counting measure $\#$, Dirac measure ${\delta }_1$, and Lebesgue measure $\lambda$.The rational numbers in the last row form a countably infinite set; their Lebesgue measure is zero by countable additivity applied to singletons, even though they are dense in the interval.

These are different answers to different questions: counting measure asks how many points occur, Dirac measure asks whether the selected point occurs, and Lebesgue measure asks how much length occurs. A null set therefore depends on its measure. For counting measure, the only null set is the empty set, so equality almost everywhere is equality everywhere. For ${\delta }_1$, a measurable set is a null set exactly when it misses $1$; for Lebesgue measure, even the infinite set $\mathbb{Q}\cap [0,2]$ is a null set. Integrating an indicator function recovers each table entry through $\int 1_{A}d\mu =\mu (A)$. This lets the same Lebesgue integral framework handle point counts, point evaluation, and geometric length.

A coupling of probability distributions $P,Q$ is a pair of random variables $(X,Y)$ with those marginal distributions. On a finite set, and more generally on a standard Borel space, the least achievable mismatch isA maximal coupling attains the minimum; maximal here refers to agreement. An arbitrary coupling can have a much larger mismatch.^[ref]

For the four-outcome example, assign the following joint probability mass: $(A,A)$ gets $0.1$, $(B,B)$ gets $0.1$, $(C,C)$ gets $0.2$, and $(D,D)$ gets $0.3$. The remaining $0.3$ must have $X=A$; place $0.2$ on $(A,B)$ and $0.1$ on $(A,C)$. Row sums give $P$, column sums give $Q$, and the diagonal contains $0.7$. Agreement can reach 70%; mismatch cannot fall below 30%.

To see the lower bound, for any event $E$,The two indicator functions agree whenever $X=Y$. To attain the bound on a finite set, keep mass $\min \{P(x),Q(x)\}$ at $(x,x)$ and couple the remaining excesses. The two residual probability distributions live on disjoint subsets, so their part necessarily mismatches. When the probability distributions are identical, the residual part disappears entirely.

This is a choice of joint construction, not a claim that independently drawn observations are usually equal. Two independent random variables with the same continuous probability distribution can disagree with probability one even though their total variation distance is zero. The construction of a maximal coupling deliberately introduces statistical dependence to reveal how similar the marginal laws are.

A cover of a set $E$ is a family of sets whose union contains $E$. The members may overlap and may include points outside $E$; intersecting each member with $E$ gives a cover by its subsets. An open cover requires its members to be open sets. In Hausdorff measure, countable covers with a bound on each member's diameter determine geometric size. Constructing one inexpensive cover supplies an upper bound, while a lower bound must control all allowed covers.

Two set families $\mathcal{A},\mathcal{B}$ are cross-Sperner when no member of either is a subset of a member of the other, including equality. Thus $\mathcal{A}\cap \mathcal{B}=\varnothing$. Neither family need itself be an antichain. On the Boolean lattice of subsets of $[n]$, the Cross-Sperner inequality bounds $\sqrt{|\mathcal{A}|}+\sqrt{|\mathcal{B}|}$ by $2^{n/2}$.

The definable power set $\mathcal{D}(X)=\mathrm{Def}(X)$ consists of the subsets of $X$ definable over the first-order structure $(X,\in )$ by a first-order formula with parameters from $X$. Satisfaction for a set structure makes this a definable operation in ZF. Iterating it produces the constructible hierarchy and the relative constructible hierarchy; their unions are the constructible universe and the relative constructible universe.

De Morgan's laws exchange logical conjunction and logical disjunction when a logical negation moves across them:Here $\equiv$ denotes logical equivalence: the two propositional formulas agree under every Boolean valuation.^[ref]

A complete verification uses the four rows of a truth table. In input order $(0,0),(0,1),(1,0),(1,1)$, both sides of the first logical equivalence have output sequence $(1,1,1,0)$; both sides of the second have $(1,0,0,0)$. A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing logical negation inward without changing AND to OR is wrong.

For the events in Boolean operations on events, the corresponding set identities areOne can prove these identities by checking an arbitrary set element $u\in U$: its two membership truth values obey De Morgan's laws. The same reasoning works for any two subsets of a common universal set.

For a nested program test, let $R$ mean “backup recent”, $V$ mean “backup verified”, and $O$ mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present givesThe transformed condition reads “backup stale or unverified, and no override”. Apply the second of De Morgan's laws at the outside, then the first at the inner logical conjunction. For $(R,V,O)=(1,0,0)$ it rejects; changing only $O$ to one makes it accept. With Boolean operands in Python, not ((recent and verified) or override) and ((not recent) or (not verified)) and (not override) have the same result and inspect the operands in the same order, with the same skipped operands.

The discrete metric sets $d(x,x)=0$ and $d(x,y)=1$ for distinct points. It induces the discrete topology, and its Cauchy sequences are exactly the eventually constant sequences.

Every nonempty set equipped with the discrete metric is a bounded set, even if it is an infinite set. For $0<r<1$, both the open ball and closed ball about $a$ are the singleton $\{a\}$. At $r=1$, the open ball is still $\{a\}$, but the closed ball is the whole space; for $r>1$, both are the whole space. Every subset is both an open set and a closed set. Consequently the boundary of the radius-one closed ball is empty, even though every point other than $a$ is at distance exactly one. Also, the closure of $B_d(a,1)$ is $\{a\}$, rather than the radius-one closed ball.

If $E\subseteq [0,1]$ is a Lebesgue measurable set and $0\le b\le \lambda (E)$, some measurable subset $B\subseteq E$ has Lebesgue measure $b$. The function $F(t)=\lambda (E\cap [0,t])$ has Lipschitz continuity with constant $1$, starts at $0$ and ends at $\lambda (E)$; the intermediate value theorem proves the assertion. Applying the assertion successively to remaining portions of $E$ gives pairwise disjoint measurable pieces with any finite list of nonnegative measures whose sum is at most $\lambda (E)$. This is a concrete consequence of non-atomic measure structure, which fails for general measures containing an atom of a measure.

Double counting establishes an identity by computing the cardinality of the same finite set in two ways. The useful step is to identify exactly what the members of that collection are; an algebraic equality then records two legitimate ways to organize them.

Take the ordered pairs $(S,x)$ where $S$ is a $k$-element subset of an $n$-element set and $x\in S$ is marked. Choosing $S$ first gives $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ pairs. Choosing $x$ first leaves $k-1$ members to choose from the other $n-1$, giving $n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. HenceFor five people and two-person teams, both counts give $20$: ten teams with two choices of a marked member, or five choices of that member with four choices of a teammate. The identity is explained by the bijection between these descriptions, rather than merely verified through factorials.

Every subset $A$ of a cofinite topological space is a compact subset. To see the finite reduction directly, take an open cover of a nonempty $A$ by open sets of $X$ and choose one member $U$ containing a point of $A$. Since $U$ has finite complement, the set $A\setminus U$ is finite. Choose a covering member for each of those remaining points. Those members together with $U$ are a finite subcover. The empty set is already compact.

Equivalently, the subspace topology on $A$ is itself cofinite: for finite $F\subseteq X$, the trace of $X\setminus F$ is $A\setminus (F\cap A)$. The argument applies again inside $A$. A concrete open cover $\{X\setminus \{k\}:k\in X\}$ of $X={\mathbb{N}}_{>0}$ needs only the two members $X\setminus \{1\}$ and $X\setminus \{2\}$ when these labels are distinct: each fills the other's single gap.

On $X={\mathbb{N}}_{>0}$, the subset of even integers is compact but not closed, because it is infinite and proper. A compact subset of a Hausdorff space is guaranteed to be closed, whereas compactness without the Hausdorff space assumption does not suffice. Changing the topology changes compactness: the same infinite set with its discrete topology has the singleton open cover, which has no finite subcover. The finite-exception argument is special to finite complements; in the cocountable topology, compact subsets of a cocountable space must instead be finite.

An exponential generating function encodes a sequence using the displayed factorial denominators. It is especially useful for counting labelled combinatorial structures: taking an unordered set of structures with positive size corresponds to exponentiating their exponential generating function. The rooted-tree generating function illustrates this through $T=z{e}^T$.

For a nonnegative integer $n$, the factorial $n!$ is the product of the positive integers from $1$ to $n$, with the empty product equal to $1$:Thus $1!=1$, $2!=2$, $3!=6$, $4!=24$ and $5!=120$. The factorial counts the permutations of $n$ distinct objects: arranging $A,B,C$ gives exactly $ABC,ACB,BAC,BCA,CAB,CBA$. The choice tree in permutation shows the three choices for the first position, two for the second, and one for the last.

The value $0!=1$ has a counting explanation: the empty set has exactly one ordering, the empty list. Equivalently, it has exactly one bijection to itself, the empty function. There are no choices to make, and one completed outcome. The factorial therefore obeys the recurrence relationThe useful distinction is how many positions are filled. For integers $0\le k\le n$, choosing and ordering $k$ distinct objects by sampling without replacement gives the falling factorial, while choosing an unordered $k$-element subset gives the binomial coefficient:For five people, assigning captain and deputy gives $5!/3!=20$ outcomes; choosing a two-person team gives $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Every team has exactly $2!$ assignments of the two roles, explaining the division. When $k=0$, both counts are one. The factorial is useful here because one count of full orderings yields both formulas by cancellation and by forgetting order. ^[ref]

Distinctness matters. If the two copies of $A$ in $AAB$ are indistinguishable, the visible arrangements are just $AAB,ABA,BAA$, numbering $3!/2!=3$. Temporarily labelling them $A_1,A_2$ gives six permutations, but exchanging the two labels leaves each visible word unchanged, so every word was counted $2!$ times.

Proof outline. For $n\ge 1$, choose the first object in $n$ ways, then order the remaining $n-1$ objects in $(n-1)!$ ways. The rule of product gives the recurrence relation; repeated application gives the displayed product, starting from the one empty ordering. This explains why the factorial grows quickly: every additional distinct object introduces another multiplicative factor.

If $S\subseteq \kappa$ is stationary and $f(\alpha )\in A_{\alpha }$ for a kappa-filtration, then $f$ is constant on a stationary subset. Restrict to limit indices and use continuity to find a smaller stage containing each value. Fodor lemma fixes that stage on a stationary subset. Its size is less than $\kappa$, so club filter completeness makes one value fiber stationary.