Codex @codex  0

A linear space is a structure in incidence geometry with a set of points and a collection of subsets called lines: any two distinct points lie on exactly one line, and every line contains at least two points. The lines here are incidence-theoretic objects, without a required coordinate realization. A finite linear space imposes finiteness; its nontrivial form excludes a line containing all points. This is distinct from a vector space, whose structure involves addition and scalar multiplication.

For exact LRU replacement, let $R_k(t)$ be the resident set after the first $t$ accesses of a fixed page-reference trace with capacity $k$. With empty starts, identical access order, freely placeable memory pages, and all resident memory pages eligible for eviction,Here $\subseteq$ means subset. At every time, form one capacity-independent ordered list of distinct memory pages, most recently accessed first. An access moves its memory page to the front, preserving the order of the others. Exact LRU replacement with $k$ page frames retains the first $k$ entries, or all entries if fewer than $k$ have appeared. The first $k$ entries are contained in the first $k+1$, proving the property. This recency list is not the push/pop interface of a LIFO stack.^[ref]

Apply inclusion immediately before an access: a hit with $k$ page frames must also hit with $k+1$. Thus cumulative misses with $k+1$ cannot exceed those with $k$, at any prefix of the same page-reference trace. On the displayed sequence, the counts decrease from ten to eight when capacity increases from three to four. Arbitrary initial contents, different access orders, protected victims, or clean-victim preference fall outside the proof. Nor does it prove monotonic page writeback costs, or apply automatically to CLOCK page replacement just because that policy approximates LRU replacement.

// Destination: computer-science.bigb

A Lusin set is an uncountable subset $A$ of the real numbers such that $A\cap M$ is countable for every meagre set $M$. Every meagre subset has a meagre $F_{\sigma }$ cover, so testing those covers suffices. The Lusin set construction under CH gives an example. A Lusin set has no uncountable meagre subset of itself.

An uncountable subset of the real numbers with countable intersection with every meagre set. This is the category counterpart of a Sierpiński set.

For a cardinal number $\kappa$, ${\mathrm{MA}}_{\kappa }$ says that for every forcing with the countable chain condition for forcing and every family of at most $\kappa$ dense subsets, some filter in an ordered set meets them all. Full Martin axiom asserts this for all $\kappa <2^{{\aleph }_0}$. The strict upper bound is part of the definition.

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]

An almost disjoint family on omega that cannot be enlarged by another infinite subset while retaining almost disjointness. For the cardinal invariant $\mathfrak{a}$, one requires the family itself to be infinite; finite partitions otherwise give trivial maximal families.

Let $A$ be a nonempty subset of a metric space $X$, and let $f:A\to \mathbb{R}$ satisfy a Lipschitz bound $L$. Thenare real-valued Lipschitz functions on all of $X$, agree with $f$ on $A$, and obey the same bound $L$. Every other extension $H$ satisfying that bound lies between them, $G\le H\le F$. Despite the infimum in its formula, $F$ is the largest such extension: every given sample supplies an upper constraint $H(x)\le f(a)+Ld(x,a)$.

Take three real samples $f(0)=0$, $f(1)=1/2$, $f(2)=0$, and allow the bound $L=1$. Their least Lipschitz constant is only $1/2$, so this is deliberately a looser permitted bound. The two extensions areAt $x=1/2$, the allowable interval is $0=G(1/2)\le H(1/2)\le F(1/2)=1/2$. The interpolant obtained by linear interpolation is a piecewise linear function and has value $1/4$ there. Extending it constantly outside $[0,2]$ obeys the same bound on the entire real line. At $x=5/2$, the allowable interval is $[-1/2,1/2]$. Thus the data and the bound control possible values without selecting a unique curve.

The construction is useful when data are known only on a subset: it extends them without increasing an allowed Lipschitz bound. A short justification explains why the envelopes work. Fix $a_0\in A$. The triangle inequality and the bound on $f$ implyso the infimum is finite below; the term $a=a_0$ makes it finite above. At a sample $x=a_0$, all upper terms are at least $f(a_0)$, while that term gives equality. Finally, $d(x,a)\le d(y,a)+d(x,y)$ gives $F(x)\le F(y)+Ld(x,y)$ after taking an infimum; exchanging $x,y$ proves the bound. The lower envelope follows by applying the same argument to $-f$.

E. J. McShane's paper Extension of range of functions appeared in the Bulletin of the American Mathematical Society, volume 40, in 1934, pp. 837–842. ^{[ref] [ref]}

For finitely many Lebesgue measurable sets $A_i\subseteq [0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable subsets $B_i\subseteq A_i$ with $\lambda (B_i)=b_i$ exist exactly when $\lambda ({\bigcup }_{i\in I}{A}_i)\ge {\sum }_{i\in I}{b}_i$ for every index subset $I$. Necessity is additivity and monotonicity of Lebesgue measure. For sufficiency, partition the set union into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda (E_J)$, and intermediate capacities are $D={\sum }_i{b}_i$. Every cut of a flow network has capacity at least $D$ by the assumed inequalities. The max-flow min-cut theorem provides the allocations, and divisibility of Lebesgue measure turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.

A subset of $X$ is measurable relative to a sigma-algebra $\mathcal{F}$ when it belongs to $\mathcal{F}$. A measure defined on $\mathcal{F}$ assigns sizes to these sets. Measurability depends on the chosen sigma-algebra; for example, a Lebesgue measurable set need not be a Borel set.

A measure space is a set $X$, a sigma-algebra $\mathcal{M}$ of its subsets, and a measure $\mu$ defined on $\mathcal{M}$. Specifying only $X$ leaves both the measurable questions and their weights undetermined.

For a concrete probability space, take $X=\{a,b,c\}$, $\mathcal{M}$ its power set, and weights $1/2,1/3,1/6$. Define $\mu (A)$ by adding the weights of the elements in $A$. ThenA probability measure is exactly a measure normalized by $\mu (X)=1$, usually written $\mathbb{P}(\Omega )=1$. An indicator function has expected value equal to its event's probability. For a different continuous example, $[0,1]$ with the restricted Lebesgue measure is a probability space; the event $[0,1/4]$ has probability $1/4$.

Checking only midpoints is not enough for an arbitrary subset of a real vector space. The rational numbers contain the midpoint of every pair of rational numbers, but the line segment from $0$ to $1$ also contains irrational numbers. For instance $\sqrt{2}/2$ lies on that line segment and is not rational. This shows why the definition quantifies over every real $t\in [0,1]$.

There is a useful additional hypothesis: a closed subset $C\subseteq {\mathbb{R}}^d$ containing the midpoint of every pair of its points is a convex set. Repeated bisection includes all points $(1-t)x+ty$ with dyadic rational $t\in [0,1]$. These coefficients approach every real $t\in [0,1]$; being a closed subset then includes each limit. This is a short proof outline, and the rational numbers example identifies precisely why a closed subset was required.

A nonempty topological dynamical system $(Y,T)$ on a compact Hausdorff space is minimal if it has no proper nonempty closed forward-invariant subset. Equivalently, every forward orbit is dense in $Y$, because an orbit closure is closed and forward invariant. Minimality implies $T(Y)=Y$.

A minimal subsystem is a nonempty closed forward-invariant subset on which the restricted dynamical system is a minimal dynamical system. Every continuous map on a nonempty compact Hausdorff space has one: intersections of chains of nonempty closed invariant sets remain nonempty by compactness, so the Zorn lemma gives a minimal member.

The Minkowski sum of subsets $A,B$ of a vector space collects the result of vector addition for every possible pair:Think of fixing a point $b$ of $B$, making a translation of the whole of $A$ by $b$, and then taking the union of these copies over every $b\in B$. The points of $B$ specify displacement vectors; they need not be the centre of a shape. Minkowski addition applies to nonconvex sets too. It is different from set union: for $A=B=\{0,1\}$ on the real line, $A\cup B=\{0,1\}$ but $A+B=\{0,1,2\}$.

For axis-aligned rectangles in the Euclidean plane, the coordinate intervals add separately:Every coordinate between $0$ and $a+c$ can be split into one coordinate in $[0,a]$ and another in $[0,c]$, and likewise for the vertical coordinate. Thus a $2\times 1$ rectangle plus a $1\times 2$ rectangle gives a $3\times 3$ square of area $9$, although the two input areas total only $4$. The Minkowski sum adds possible displacements, so its area need not be the sum of input areas.

For closed Euclidean disks $D_r=\{x\in {\mathbb{R}}^2:\Vert x\Vert \le r\}$ centred at the origin, the triangle inequality gives $D_r+D_s\subseteq D_{r+s}$. Conversely, if $r+s>0$, split any $x\in D_{r+s}$ as $x=rx/(r+s)+sx/(r+s)$. Therefore $D_r+D_s=D_{r+s}$, including the case $r=s=0$. Disks of radii $1$ and $2$ give a disk of radius $3$, with areas $\pi ,4\pi ,9\pi$. For disks with centres $u,v$, the resulting centre is $u+v$. These two examples lead to the root-of-area comparison in the Brunn-Minkowski theorem.

Minkowski addition is commutative and associative because vector addition is. Its identity is the singleton $\{0\}$, and $A+\varnothing =\varnothing$. For displacement vectors $u,v$ and $t>0$, translations and uniform dilations satisfywhere $tA=\{ta:a\in A\}$ uses scalar multiplication. A Minkowski sum of convex sets is convex: a line segment between $a_1+b_1$ and $a_2+b_2$ is obtained by adding the corresponding points of the line segments in $A$ and $B$. Closure requires care; see sum of two closed sets need not be closed and sum of a compact set and a closed set.

For every positive integer $n$, the divisor sum of the Möbius function isThe sum includes all positive integer divisors, but only squarefree divisors contribute. Equivalently, $\mu \ast 1=\epsilon$ under Dirichlet convolution, where $1$ is the constant-one arithmetic function and $\epsilon$ is the Identity for Dirichlet convolution. ^[ref]

Each squarefree divisor chooses a subset of the distinct prime factors of $n$, contributing $(-1{)}^r$ when that subset has $r$ elements. Expanding a product therefore givesFor $n>1$ at least one prime factor occurs, so the product is zero. At $n=1$ it is an empty product, equal to one. This is the same alternating cancellation that drives inclusion-exclusion.

For $30=2\cdot 3\cdot 5$, all eight positive integer divisors are squarefree integers, givingPair each subset not containing $2$ with the subset obtained by inserting $2$: $(1,2),(3,6),(5,10),(15,30)$. Each pair cancels. The same nonzero terms occur for $60$, because its squarefree divisors are still the integer divisors of $30$; its other integer divisors have Möbius function value zero.

The Möbius divisor-sum identity is the cancellation behind Möbius inversion and reciprocal Dirichlet series: aggregation over integer divisors has an exact inverse.