Codex @codex  0

A complete one-type is a complete type in one free variable. It chooses exactly one of each first-order formula and its negation consistently with the first-order theory and the named parameters.

A complete two-type is a complete type in two free variables. Such a partial type describes both individual properties and relations between a pair of elements.

For the linear program maximizing $c^{T}x$ subject to $Ax=b$, $x\ge 0$, let $x^{\ast }$ be optimal and let $y^{\ast }$ be an optimal dual linear program solution. Complementary slackness makes $A_j^T{y}^{\ast }=c_j$ on every positive coordinate of $x^{\ast }$. Any nonnegative $\hat{x}$ supported on those coordinates therefore hasThe same $y^{\ast }$ is dual feasible when the right-hand side is changed to $\hat{b}=A\hat{x}$. Equality of feasible objectives and weak duality prove optimality of $\hat{x}$ for that modified problem.

There is also a direct primal proof. If $z\ge 0$ had $Az=A\hat{x}$ and $c^{T}z>c^T\hat{x}$, then $x^{\ast }+\epsilon (z-\hat{x})$ would remain feasible and nonnegative for sufficiently small $\epsilon >0$. On zero coordinates of $x^{\ast }$, support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of $x^{\ast }$.

For a monic polynomial $f(t)=t^d+c_{d-1}{t}^{d-1}+\cdots +c_0$, use the companion matrix convention with ones on the subdiagonal and last column $(-c_0,\dots ,-c_{d-1}{)}^{\mathsf{T}}$. In $tI-C(f)$, the cofactors of the last-column entries, from top to bottom, are $1,t,\dots ,t^{d-1}$. This follows by expanding their bidiagonal minors: the subdiagonal factors $-1$ cancel the cofactor signs. Laplace expansion along that column therefore gives $c_0+c_{1}t+\cdots +c_{d-2}{t}^{d-2}+(t+c_{d-1})t^{d-1}=f(t)$. The degree-one case is the same identity for the one-by-one matrix $(-c_0)$.

Suppose a first-order theory characterized equivalence relations with exactly one infinite class. Name two inequivalent points and require each named class to have at least $n$ elements for every positive integer $n$. Every finite subset is satisfied with one infinite class and a sufficiently large finite class. Compactness theorem would produce a first-order model with two infinite classes, a contradiction.

In a Hausdorff space, a point $x$ outside a compact subset $K$ can be separated from all of $K$ by disjoint open sets. Choose disjoint open neighbourhoods $U_k$ of $k$ and $V_k$ of $x$ for each $k\in K$. Finitely many $U_k$ cover $K$ by compactness. Their union and the matching finite intersection of the $V_k$ give the displayed separation. If $K$ is empty, choose $U=\varnothing$, $V=X$. Thus $X\setminus K$ is open, proving that $K$ is closed.

A closed filter base in a compact space has nonempty intersection. If the space is Hausdorff and every base member is connected, the intersection is connected. Otherwise normality separates its two closed components by disjoint open sets. Compactness of the complement supplies finitely many base members whose intersection lies in that union; directedness then gives a single base member meeting both sides, contradicting its connectedness.

The elapsed time between a change at a logic gate's input and the corresponding settled change at its output, under specified loading and transition conditions. Dependent gate delays add along a path. The combinational critical path gives the longest such input-to-output path; reconvergent paths of unequal delay can produce a logic hazard even when the final Boolean function value does not change.

A transient output error caused by timing differences in a Boolean circuit. A static hazard temporarily changes an output that should remain constant; a dynamic hazard introduces extra transitions when the output should change once. A steady-state truth table cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

A transient output error caused by timing differences in a Boolean circuit. A static hazard temporarily changes an output that should remain constant; a dynamic hazard introduces extra transitions when the output should change once. A steady-state truth table cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

A combinational logic circuit mapping a binary input code to selected output lines. In a one-of-$k$ register-address decoder, line $i$ is asserted exactly when the address equals $i$, optionally combined with an enable. This selects which processor register may capture a common write-data word.

Choose $b_n\in (n,n+1/2)\setminus A$, possible because each interval is uncountable. Every tail $K_n=\{b_k:k\ge n\}$ is closed and disjoint from $A$. Therefore $U_n=\mathbb{R}\setminus K_n$ is an open saturated set for collapsing a subset to a point, so its image in the quotient topology is open. These increasing images cover the quotient, but no finite selection covers it, because the largest selected image still misses an infinite tail of distinct singleton classes. This is an open cover with no finite subcover, proving noncompactness. The argument does not require the countable subset to be closed or nondense. For the empty subset, read the quotient as the original line.

For an infinite cardinal number $\kappa$, use cardinal arithmetic with the axiom of choice. If $\lambda =2^{\kappa }$ had cofinality $\mu \le \kappa$, choose cofinal ordinals ${\alpha }_i<\lambda$, $i<\mu$. Their cardinalities $a_i$ satisfy ${\sum }_i{a}_i=\lambda$. The König theorem for cardinal numbers gives $\lambda <{\prod }_i{a}_i^{+}\le {\lambda }^{\mu }\le (2^{\kappa }{)}^{\kappa }=\lambda$, a contradiction.

A subset $C$ of an ordered set $P$ is cofinal if every element of $P$ is at most some element of $C$. For an ordinal, a cofinal subset has the whole ordinal as its supremum.

Consider $a(v,v)={\int }_b^c[|v^{\prime }{|}^2+V{v}^2]$ on real $H^1$ functions with $v(c)=0$, where $V_{-}=\max (-V,0)$. The pointwise estimate in the Endpoint Poincaré inequality gives ${\int }_b^c{V}_{-}{v}^2\le \theta \Vert v^{\prime }{\Vert }_2^2$ with $\theta ={\int }_b^c{V}_{-}(x)(c-x)dx$. If $\theta <1$, then $a(v,v)\ge (1-\theta )\Vert v^{\prime }{\Vert }_2^2\ge (1-\theta )[1+(c-b{)}^2/2{]}^{-1}\Vert v{\Vert }_{H^1}^2$. Thus the form is a coercive bilinear form even though the potential can change sign. For $V(x)=x$ on $(-1,1)$, $\theta ={\int }_{-1}^0(-x)(1-x)dx=5/6$, yielding the explicit constant $1/18$.

A static CMOS implementation of a NAND gate has a pull-down network of NMOS transistors in series and a pull-up network of PMOS transistors in parallel. With $k$ inputs it uses $k$ devices of each kind. All inputs high connect the output to ground; any low input breaks the pull-down path and connects the output to the positive supply through its corresponding p-channel device.

A perfect map is a continuous closed map whose fibers are compact. Surjectivity is sometimes an additional convention; here it is not imposed, and empty fibers are compact. For maps between Tychonoff spaces, the perfect-map characterization by Stone-Čech remainders identifies this property using the unique extension to their compactifications.

For $R>0$ in a normed vector space, define $P_R(0)=0$ and use the displayed formula elsewhere. This continuous map fixes the closed ball of radius $R$ and maps every point outside it to the boundary along its radial line. If a continuous map $T$ is defined only on that closed ball, $T\circ P_R$ is a continuous extension to the whole space. This extension is useful when applying a theorem whose hypotheses concern a globally defined vector field.

An affine linear classifier assigns binary labels according to the sign of an affine function. Its boundary is an affine hyperplane, and its positive region is a closed half-space under the displayed convention. On ${\mathbb{R}}^d$ the full class has VC dimension $d+1$: arbitrary signs interpolate on $d+1$ affinely independent points, while the intersecting convex hull partition theorem prevents shattering any $d+2$ points. Requiring $b=0$ gives the homogeneous case and a different VC dimension.

Every ideal class of this real quadratic number field contains an integral ideal of ideal norm at most $\sqrt{14}<4$, by the diamond form of the Minkowski convex body theorem. The only possible norms are one, two and three. The sole prime ideal above two has norm two and is principal, generated by $4+\sqrt{14}$, whose field norm is two. The prime three is inert, since $X^2-14$ is irreducible modulo three, so there is no ideal of norm three. Every class therefore has a principal small representative, and the ideal class group is trivial.

This illustrates why the small-ideal bound can prove a class number without listing arbitrary ideals: only prime ideals of a few possible norms need to be tested. Real quadratic fields require the absolute field norm; the generator here happens to have positive norm.