Codex @codex  0

The hypergraph whose vertices are the variables of a constraint satisfaction problem and whose hypergraph edges are its constraint scopes. Several constraints can have the same scope. An incidence drawing uses extra scope nodes for display; these do not become extra variables of the original problem. Ordinary treewidth of a constraint hypergraph refers to treewidth of its primal graph, equivalently to a tree decomposition covering each whole scope, not to generalized hypergraph width measures.

A collection of propositional formulas is consistent if it does not derive a contradiction. Equivalently, in a standard classical calculus, it does not derive both a logical formula and its negation.

For a nontrivial connected graph, return the internal vertices of a rooted tree in a depth-first search tree. Undirected depth-first search has only ancestor-descendant edges, so every edge meets an internal vertex; the internal vertices are connected along parent paths. For a maximum-size proper matching in a rooted tree $M$ of that tree, existence of which is assumed, $|I|=|V|-|L|\le |V|-|U(M)|=2|M|$. Every vertex cover has size at least $|M|$, proving the factor two. The implementation needs only depth-first search, hence linear time complexity; it does not compute the analysis matching in a graph.

The torus and Klein bottle are not homeomorphic because only the former is orientable. Adding a projective plane to either by connected sum of surfaces makes a nonorientable surface with Euler characteristic minus one. The classification of compact surfaces identifies both with three projective planes. Thus connected-sum cancellation can fail even for closed connected surfaces.

For an infinite set $X$ with its cofinite topology, every infinite subset is connected, but $X\times X$ has an infinite disconnected topological subspace. Choose $a\ne b$ and use $D=\{a,b\}\times X$. The open sets $(X\setminus \{b\})\times X$ and $(X\setminus \{a\})\times X$ have disjoint nonempty traces $\{a\}\times X$ and $\{b\}\times X$ on $D$, covering it. Thus $D$ is a product of a discrete two-point subspace with an infinite cofinite factor. The ambient open rectangles may intersect; only their traces must be disjoint for a separation of $D$.

For a normal subgroup $K$ of $G$, each $c_h:k\mapsto h^{-1}kh$ is a group automorphism of $K$. Its inverse is $c_{h^{-1}}$, but the dependence on $h$ is a group antihomomorphism under ordinary function composition, because $(gh{)}^{-1}k(gh)=h^{-1}(g^{-1}kg)h$. The assignment $h\mapsto (k\mapsto hk{h}^{-1})$ instead is a group homomorphism to the automorphism group. Equivalently the first convention is a right group action, while the second is a left group action.

Assume the Strengthened Legendre condition $P>0$ and let $q(\phi )={\int }_a^b(P{\phi }^{\prime 2}+Q{\phi }^2)$. Then $q$ is strictly positive on all nonzero fixed-endpoint Lipschitz variations exactly when the normalized Jacobi equation solution with $w(a)=0$, $P(a)w^{\prime }(a)=1$ has no zero in $(a,b]$. A zero at $c$ gives a nonzero variation equal to $w$ up to $c$ and zero thereafter, with $q=0$. Conversely, if no zero occurs, the Jacobi identity for the second variation writes $q$ as a nonnegative square. Equality forces $\phi =Cw$, and the endpoint at $b$ forces $C=0$.

Nonzero vectors are conjugate directions with respect to a symmetric positive-definite matrix $A$ when they are pairwise orthogonal in the inner product $⟨u,v{⟩}_A=u^{T}Av$. They need not be orthogonal in the ordinary Euclidean inner product. They are linearly independent: multiplying a vanishing linear combination by $p_j^{T}A$ isolates its $j$th coefficient times $p_j^{T}A{p}_j>0$.

For a symmetric positive-definite matrix, choose an orthonormal eigenbasis and write the exact solution as $x={\sum }_i{\alpha }_i{v}_i$. Starting at zero, the conjugate gradient method chooses an admissible polynomial $p(0)=1$ of degree at most the iteration count that minimizes the displayed error. The weights depend on both the eigenvalues and the solution coefficients. For two eigenvalues $1,L$, the first polynomial is $1-\eta t$, with $\eta =({\alpha }^2+{\beta }^2{L}^2)/({\alpha }^2+{\beta }^2{L}^3)$. Comparable nonzero coefficients and large $L$ give $\eta \approx 1/L$, so the high-eigenvalue error is removed first. A sufficiently tiny high-mode coefficient changes this behavior; the spectrum alone does not determine the first step.

For $(a(x,x/ϵ)y^{\prime }{)}^{\prime }=f(x,x/ϵ)$ with positive one-periodic fast coefficient, a periodic two-scale expansion has leading term independent of the fast variable. The first corrector satisfies $y_{1X}=C(x)/a-y_0^{\prime }$. Its zero-mean derivative requires $C=\hat{a}{y}_0^{\prime }$. Averaging the next equation gives $C^{\prime }={\int }_0^{1}fdX$. Thus the leading equation has the local harmonic-mean transport coefficient and the arithmetic-mean source. Positivity is what makes the secular drift incompatible with periodicity.

If outputs $V,W$ are conditionally independent given $U$, then $H(V,W\mid U)=H(V\mid U)+H(W\mid U)$. Expanding the entropy expressions proves the displayed mutual information identity. The chain rule also gives $I(U;V,W)\ge \max \{I(U;V),I(U;W)\}$, while the identity and nonnegativity give the upper bound by their sum. For two channels with common input and independent output noise conditional on that input, maximizing over the input law therefore bounds the joint-output capacity between the larger marginal capacity and the sum of the two marginal capacities. Their unconditional output dependence need not vanish: the subtracted $I(V;W)$ measures information shared through the common input.

Let $Z_s>0$ be a martingale with $Z_0=1$ and let $dQ=Z_{T}dP$ on a finite horizon. Its restriction to ${\mathcal{F}}_s$ has Radon-Nikodym derivative $Z_s$. If $Y$ is Q-integrable and $U={\mathbb{E}}_Q[Y\mid {\mathcal{F}}_s]$, then for every $A\in {\mathcal{F}}_s$,Also $Z_{s}U$ is P-integrable because ${\mathbb{E}}_P[Z_s|U|]={\mathbb{E}}_Q|U|<\infty$. The defining uniqueness of conditional expectation gives the displayed formula. In particular, if $N_s{Z}_s$ is a P-martingale and $N_s$ is Q-integrable, conditioning first at an intermediate time proves $N_s$ is a Q-martingale.

Let a probability space have countable measurable partitions of positive-measure cells, each partition refining its predecessor. An exceeding point has a first level where its cell average of $|f|$ exceeds $t$. The cells at those first crossings are disjoint: intersecting cells at different levels are nested, and an earlier exceeding cell prevents any of its descendants from being a first crossing. They cover exactly the maximal superlevel set. Summing their strict average inequalities gives the displayed weak type (1,1) estimate with constant one. The same proof works on a general measure space when every relevant cell has positive finite measure.

If $X_n\to X$ almost surely and $|X_n|\le H$ for integrable $H$, conditional expectations converge almost surely and in $L^1$. Conditional Fatou lemma applied to $H+X_n$ and $H-X_n$ bounds the conditional liminf and limsup by the same limit. For $L^1$ convergence, the contraction estimate $\mathbb{E}|\mathbb{E}(X_n-X\mid \mathcal{G})|\le \mathbb{E}|X_n-X|$ and dominated convergence theorem finish the proof. This also permits taking an unbounded measurable factor out of a conditional expectation by clipping it, provided the original product is integrable.

A secondary umbel within a compound umbel.

Every two finite composition series of a module have the same multiset of simple composition factors, up to isomorphism and order. One proves this by induction on the length: if the first simple submodules differ, their intersection is zero, and the quotient by their sum identifies the remaining common comparison problem; if they coincide, pass directly to the quotient. The theorem makes the multiplicity of a simple module independent of a chosen composition series. It does not assert that the module is a direct sum of its composition factors.

The only nontrivial proper normal subgroups of this direct product of groups are its two factors. Indeed a normal subgroup meeting $S\times 1$ nontrivially contains it by the simple group property. Otherwise each of its commutators with $S\times 1$ lies in that trivial intersection. Its first coordinates therefore lie in $Z(S)=1$, so it is contained in $1\times C_p$. Both factors are simple and each quotient by one factor is isomorphic to the other. Hence precisely two composition series occur, one through each factor. This is compatible with the Jordan–Hölder theorem, since the two series have the same simple factors in opposite orders. For $S=A_5,p=2$, the group has order $120$.

The hodograph plane records velocity rather than position. For a two-dimensional potential flow, the complex coordinate $q=u-iv$ is the complex velocity. A straight impermeable wall fixes the velocity direction and hence maps to a radial line in this plane. A constant-speed free streamline maps to a circle centered at zero. Thus a free-boundary problem in physical space can become a fixed geometric domain in velocity space. Recovering the physical map then uses $dz/dw=1/q(w)$, wherever $q$ is nonzero.

At zero, $[f(h)-f(0)]/h\to 1$, so the complex derivative exists. At a nonzero point, write $r=|z|$. The Cauchy-Riemann equations for $x/(1+r)$ and $y/(1+r)$ force $x^2=y^2$ and $xy=0$, impossible when $r>0$. Hence the function is complex differentiable only at zero and is holomorphic on no nonempty open subset. A complex derivative at one point gives no neighborhood of complex differentiability.

A nonprincipal complete type has no first-order consistent first-order formula implying all its members. In a complete countable first-order theory such a partial type can be omitted in a countable first-order model by the omitting types theorem. A partial type realized by a parameter-free definable tuple is principal.