Codex @codex  0

An infinite Cartesian product of finite sets need not admit any complete list enumeration. For the repeated binary factor, suppose the output lists all sequences as $z_0,z_1,\dots$. Define a sequence by $b_i=1-z_i(i)$. It is a valid binary sequence but differs from the $i$-th output at coordinate $i$, a contradiction. This is Cantor's diagonal argument. Consequently fair binary products can recursively enumerate the choices from finitely many possibly infinite lists, but cannot solve the unrestricted infinite-family specification. A finite-family algorithm's restriction must be explicit.

A series of functions is uniformly absolutely convergent on a set if the series of their absolute values has uniform convergence there. A sufficient condition is the Weierstrass M-test: if $|f_n(x)|\le M_n$ for every $x$ and ${\sum }_n{M}_n<\infty$, then the tail is bounded uniformly by ${\sum }_{n\ge N}{M}_n\to 0$. This also proves uniform convergence of the original series by the Uniform Cauchy criterion.

Suppose all distances lie in $[0,D]$, $\psi$ is continuous, $0<\psi (r)<r$ for positive $r$, and ${\lim }_{r\to 0}\psi (r)/r<1$. The ratio is uniformly bounded below one near zero, and its maximum on the remaining compact scalar interval is also below one. Thus one constant $q<1$ works on the entire bounded set. If the set is complete and the map preserves it, Banach's theorem gives a unique fixed point. Compactness of the set itself is not required.

A pointwise periodic self-map has a uniform positive period exactly when its finite cycle lengths are bounded. A uniform period is divisible by every length; conversely, bounded lengths divide the least common multiple of $1,\dots ,M$ for some bound $M$. Arbitrarily many bounded-length cycles are allowed. Every such map on a finite set has a uniform period. On any infinite set containing a countably infinite subset, cycles of unbounded finite lengths and fixed points elsewhere give a counterexample. Thus, with the usual axiom of choice assumption, the sets on which every pointwise periodic self-map has a uniform period are exactly finite sets.

Let $B_1,B_2$ be real square invertible matrices whose columns are lattice bases. They generate the same Euclidean lattice precisely when^[ref]

If $B_2=B_{1}U$, multiplication by $U$ merely permutes the integer coordinate vectors, so the two generated sets agree. Conversely, equality of the generated sets means every column of either basis is an integer linear combination of the other. Hence $B_2=B_{1}U$ and $B_1=B_{2}V$ for integer matrices $U,V$. Substitution followed by multiplication by $B_1^{-1}$ gives $UV=I$, so the integer inverse criterion for a unimodular matrix applies.

Equal real linear spans are a weaker condition: any two real square invertible matrices span the same ambient vector space. Even equal covolumes do not force the same Euclidean lattice. The requirement that the change matrix and its inverse matrix have integer entries provides the missing arithmetic information.

A unimodular matrix is a square integer matrix whose determinant is $1$ or $-1$. The decisive property is that its inverse matrix also has integer entries: multiplication by $U$ gives a bijection of the integer lattice ${\mathbb{Z}}^n$ onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.^[ref]

For an original two-dimensional example, takeIts determinant is one, and it maps $(a,b)$ to $(a+b,b)$. Conversely, the integer point $(x,y)$ comes from $(x-y,y)$. For instance, $(3,2)$ has new coordinates $(1,2)$ relative to the columns $(1,0)$ and $(1,1)$. No integer point disappears, although the basis vectors and their fundamental cell change shape.

This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.

A determinant of $-1$ is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.

A union of equivalence relations on the same set is reflexive and symmetric, but can fail transitivity. On a three-point set, partitions into blocks $\{1,2\},\{3\}$ and $\{1\},\{2,3\}$ make the union relate $1$ to $2$ and $2$ to $3$ without relating $1$ to $3$. An equivalence relation containing both requires transitive closure as well.

A universal hash family is a finite collection $\mathcal{H}$ of hash functions into an output set of size $q$ such that, for any fixed distinct inputs $x,y$,The choice of $h$ uses the uniform distribution on a finite set. The keys are fixed before that choice: the randomness belongs to the hash function, so the guarantee does not assume naturally random keys. Choose one member and keep it while using the table; changing it requires redistributing the stored records. The bound holds separately for every distinct pair, without requiring uniform individual outputs or independent random variables. A strongly universal hash family supplies those stronger properties.

The practical payoff follows from linearity of expectation. If $n$ stored keys are distinct from a fixed query, let $C$ count how many share its bucket. Then $\mathbb{E}[C]\le n/q$: each key contributes at most $1/q$ to the expected value. With $100$ stored keys and $100$ buckets, an unsuccessful search encounters at most one record on average over the random choice of hash function. This is an expected value, not a limit on every search; one unlucky choice can still create a long chain.

This calculation needs no independence between the collision events: linearity of expectation adds their individual probabilities. The fixed-query condition matters, since deliberately choosing keys after inspecting the selected hash function can target a crowded bucket.

Carter and Wegman introduced this way of analyzing storage and retrieval in their 1977 paper: average over a chosen class of hash functions while allowing any fixed sequence of inputs. Their 1979 journal version develops the same universal-pair collision condition and constructions. The insight is useful because a randomized algorithm can obtain a performance guarantee through its own choices, even when its inputs have inconvenient patterns.^[ref][ref]

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.

In a partially ordered set $P$, an upper set $U$ satisfies $x\in U$ and $x\le y\Rightarrow y\in U$; a lower set $L$ satisfies $x\in L$ and $y\le x\Rightarrow y\in L$. The complement of a set exchanges the two conditions: if $x\notin U$ and $y\le x$, then $y\in U$ would force $x\in U$, so $P\setminus U$ is lower. In a Boolean lattice ordered by inclusion, these are the up-set and down-set conditions.

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.

Let open sets $U_t$ be indexed by a dense subset of $[0,1]$, with $\overline{U_s}\subseteq U_t$ for $s<t$. Taking the infimum of membership indices, with value one outside their union, gives a continuous function. The strict sublevel sets are unions of $U_t$; strict superlevel sets are unions of complements of $\overline{U_t}$. These identities prove continuity.

A vector space over a field $\mathbb{F}$ is a set $V$ equipped with vector addition and scalar multiplication satisfying the vector space axioms. Its vectors can represent directed displacements, lists of measurements, polynomials, or entire functions. The common structure is that adding two elements and multiplying an element by a scalar remain meaningful operations inside the same space.

For example, ${\mathbb{R}}^2$ uses coordinatewise addition and scaling. Withwe have $v=2b_1+b_2$. Moving twice along $b_1$ and once along $b_2$ reaches the same vector as five horizontal and four vertical steps. The two descriptions refer to different bases of the same space. A basis makes such descriptions unique; a spanning set makes them possible.

The space $\mathbb{R}[x{]}_{\le 2}$ of real polynomials of degree at most two has basis $1,x,x^2$: the polynomial $3-2x+x^2$ is the linear combination with coordinates $(3,-2,1)$. The zero vector here is the zero polynomial, and addition combines coefficients. A derivative is a linear map on this space; its matrix records how it acts on the three basis vectors. The same coordinate machinery therefore handles both geometric motion and operations on functions.

The choice of field matters. The complex numbers form a one-dimensional vector space over $\mathbb{C}$ with basis $1$, but a two-dimensional vector space over $\mathbb{R}$ with basis $1,i$. The question "how many independent directions?" has an answer only after the allowed scalars are specified. Likewise, polynomials of degree exactly two do not form a vector space: subtraction can remove the leading term, and the zero polynomial is absent.

The usefulness of the abstraction is that a linear map is determined by its values on a basis. Once those images are known, linear combinations give its action on every vector. The rank-nullity theorem relates the number of attainable outputs to the number of invisible input directions, while change of basis lets us choose coordinates suited to the problem. Eigenvectors, for example, choose directions on which repeated application of a linear operator becomes scalar multiplication.

A historical source is Hermann Grassmann's Die lineale Ausdehnungslehre (1844). Its full title advertises applications to other branches of mathematics, statics, mechanics, magnetism and crystallography; the original edition is digitized by ETH-Bibliothek. This gives an early setting for treating geometric quantities algebraically across different applications, rather than attributing the modern axiom list to that title alone.^[ref]

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 Venn diagram represents sets by closed curves, with each region recording a possible pattern of membership. For two sets, the regions mean “first only”, “both”, “second only”, and “neither”; the enclosing rectangle can represent the universal set. Shading regions displays union, intersection, set difference, or complement. In the numbered examples in set union and complement, positions encode membership, while curve shapes and region areas do not encode cardinalities.

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.

The vertex cover number records the size of a minimum vertex cover:The vertex cover number is a number, while a minimum vertex cover is a set attaining it. For the cycle graph $C_5$, the independence number is $2$, so the complement correspondence gives $\tau (C_5)=5-2=3$. The vertex cover $\{1,3,4\}$ above attains this size.

Every matching in a graph gives a lower bound on the vertex cover number. Its edges have no shared endpoints, so covering each selected edge requires a different vertex. Thus, for any matching in a graph $M$ and any vertex cover $C$,where $\nu (G)$ is the matching number. Exhibiting a matching in a graph and a vertex cover of the same size certifies that both are optimum. Kőnig's theorem for bipartite matching says that every finite bipartite graph admits this equality: $\nu (G)=\tau (G)$.^[ref]

For the complete bipartite graph $K_{2,3}$, let the left vertices be $L=\{a,b\}$ and the right vertices be $R=\{x,y,z\}$. All six edges join $L$ to $R$. Selecting $C=L$ covers every edge; selecting $M=\{ax,by\}$ gives a matching in a graph of size two. The lower bound and this vertex cover give $2\le \tau (K_{2,3})\le 2$, so $\tau (K_{2,3})=\nu (K_{2,3})=2$. The remaining vertices $R$ form a largest independent set of size three. Crossings of drawn edges are not extra vertices.

The bipartite graph hypothesis matters. In a triangle in a graph, any two vertices form a minimum vertex cover, while any two edges share an endpoint. Hence $\tau (K_3)=2$ and $\nu (K_3)=1$. Similarly, the cycle graph $C_5$ has $\tau (C_5)=3$ and $\nu (C_5)=2$. The inequality for the matching number remains valid, but equality can fail.

The vertex set is the underlying set $V$ of a graph or hypergraph. In a hypergraph, its hyperedges are subsets of this set; in a simple graph, edges are two-element subsets.

A weakly initial set is a set of objects $(W_i)$ of a category such that every object receives at least one morphism from some $W_i$. No uniqueness is required. A solution-set condition asserts this property in suitable comma categories.

A weakly terminal set is a set of objects $(W_i)$ of a category such that every object admits at least one morphism into some $W_i$. It is the dual of a weakly initial set.