Codex @codex  0

Pull the given finite coloring $\chi :\mathbb{N}\to [k]$ back to a finite coloring of unordered pairs by puttingThe ordering $a<b$ makes this a well-defined function on the edges of a complete graph. By Ramsey's theorem, some infinite set $X=\{x_1<x_2<\cdots \}$ has all its pairs of one color $r$ under $\tilde{\chi }$. ConsequentlyPossible coincidences between these products cause no difficulty, since the original finite coloring assigns each positive integer a single color.

The countable form of the omitting types theorem is as follows. Let $L$ be a countable first-order language and $T$ a consistent first-order theory in $L$. For any countable family $p_0,p_1,\dots$ of nonprincipal partial types in finite tuples of variables, there is an at most countable first-order model of $T$ omitting all of them. Nonprincipality means that no $T$-consistent first-order formula $\theta (\mathbf{x})$ entails every member of the type modulo $T$. A complete first-order theory with nonisolated complete types is the usual special case; neither an uncountable language nor an arbitrary uncountable family is covered by this statement.

Use the Godel completeness theorem to pass between consistency and the existence of a first-order model. Adjoin a countable stock $C$ of new constants. Construct finite conditions ${\Gamma }_s$ with $T\cup {\Gamma }_s$ consistent, interleaving three countable lists of requirements: decide each $L(C)$-sentence; provide a fresh constant witness for each existential sentence; and, for each $p_i$ and each tuple $\mathbf{t}$ of closed terms of its arity, add $\neg \psi (\mathbf{t})$ for some $\psi \in p_i$. Sentence decisions preserve consistency by choosing a consistent sign. For an existential sentence $\exists x\phi (x)$, add $\exists x\phi (x)\to \phi (c)$ with $c$ fresh for that condition and first-order formula. This is consistent: any first-order model of the old condition can interpret $c$ as a witness if one exists, and otherwise arbitrarily in the nonempty domain.

The omission step is the key Henkin omission extension lemma. Let $\sigma (\mathbf{c})$ be the logical conjunction of the current finite condition, listing every new constant occurring either there or in $\mathbf{t}$. If adding $\neg \psi (\mathbf{t})$ were inconsistent for every $\psi \in p_i$, then $T$ would entail $\sigma (\mathbf{c})\to \psi (\mathbf{t}(\mathbf{c}))$ for each such $\psi$. Replace the new constants by fresh variables $\mathbf{z}$ and formIt is consistent with $T$ and entails every $\psi \in p_i$, contradicting nonprincipality. Hence some omission extension is consistent. The construction need not be computable; countability merely permits all these requirements to be scheduled.

Let $T^{\ast }$ be the deductive closure of $T\cup {\bigcup }_s{\Gamma }_s$. It is consistent by the finite character of formal proofs, complete by sentence decisions, and has the Henkin witness property. Its term model consists of closed terms modulo provable logical equality and has at most countably many elements. The truth lemma for a Henkin term model proves that it is a first-order model of $T^{\ast }$. Every tuple in it is represented by closed terms, whose scheduled omission requirement supplies a negated member of each corresponding type. Thus

A universal sentence has the form $\forall \mathbf{x}\psi (\mathbf{x})$ with quantifier-free $\psi$, including an empty quantifier block. Embeddings preserve and reflect quantifier-free truth, so universal sentences pass to substructures of a first-order structure. For the converse Łoś-Tarski preservation theorem, let $T_{\forall }$ be all universal consequences of an arbitrary first-order theory $T$, and take $A\models T_{\forall }$. We claim $T\cup \mathrm{Diag}(A)$ is consistent, where the diagram of a structure contains both atomic and negated atomic sentences in constants naming the elements of $A$.

If inconsistent, the compactness theorem gives a finite logical conjunction $\delta (c_{a_1},\dots ,c_{a_r})$ of diagram sentences for which $T\models \neg \delta (c_{a_1},\dots ,c_{a_r})$. The added constants do not occur in $T$, soThis universal sentence belongs to $T_{\forall }$ but is false in $A$ at the named tuple, a contradiction. The compactness theorem therefore produces $B\models T$ containing an isomorphic embedded copy of $A$. The signed diagram ensures a genuine substructure of a first-order structure: functions are preserved, constants are included and relations are preserved and reflected. If the first-order model class of $T$ is closed under substructures of a first-order structure, this copy, and hence $A$, is a first-order model of $T$. We have provedNo countability assumption is needed for this second argument. An inconsistent first-order theory is covered as well, with a universally false axiom and an empty first-order model class.

One form of the Ehrenfeucht-Mostowski theorem says that, for every infinite first-order structure $M$ and every total order $I$, an elementary extension contains distinct elements $(a_i{)}_{i\in I}$ forming an order-indiscernible sequence. After a suitable Skolem expansion, their Skolem hull is a first-order model of $\mathrm{Th}(M)$, and every order automorphism of $I$ extends to a structure automorphism of that hull. If $M$ has a definable infinite linearly ordered subset $P$, the generators may lie in $P$ and their order may agree with that definable order. Uniqueness of the extended structure automorphism is asserted in the chosen Skolem expansion, rather than for every structure automorphism of its reduct.

Here is an ultraproduct proof of the Ehrenfeucht-Mostowski theorem. First expand $M$ to $M^{+}$ with Skolem functions for all existential first-order formulas, iterating through the enlarged languages if necessary. This is done in the ordinary classical metatheory; the choice restriction in question 1 is not a restriction on this question. Fix a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$.

We can obtain an infinite sequence of distinct elements $b_0,b_1,\dots$ in an elementary extension $M_0$ of $M^{+}$ by one preliminary ultrapower. For each $n\ge 1$ choose a finite list of $n$ distinct elements of $M^{+}$. Represent $b_j$ by the function taking the $j$th entry when $n>j$, with an arbitrary default otherwise. Distinctness holds on a cofinite set, so follows from Łoś theorem. In the definably ordered variant, first name any parameters defining $P$, and choose each finite list increasingly inside $P$ instead; then $M_0\models P(b_j)$ and $b_j<b_k$ for $j<k$. Infinitude of an ordered set supplies every finite increasing chain. This preparatory step uses no Ramsey theorem.

For a finite subset $F=\{i_1<\cdots <i_r\}$ of $I$, define the ultrafilter ${\mathcal{U}}_F$ on ${\mathbb{N}}^F$ by nested membership, in this order:where $(\mathcal{U}n)Q(n)$ means $\{n:Q(n)\}\in \mathcal{U}$. This is the ordered Fubini product of ultrafilters. Closure under intersections and the decision between a set and its complement hold at each nested level, proving it is an ultrafilter. For $F=\varnothing$ take the principal ultrafilter on the one-point product. PutIf $F\subseteq G$, pull a function back along the projection ${\mathbb{N}}^G\to {\mathbb{N}}^F$. A test independent of an omitted coordinate is unchanged by its ultrafilter quantifier, so projection pushes ${\mathcal{U}}_G$ to ${\mathcal{U}}_F$. The induced map $N_F\to N_G$ is therefore an elementary embedding by Łoś theorem. These maps are coherent, giving a directed system indexed by finite subsets of $I$.

Take its directed limit of elementary embeddings $N$. One can verify elementarity directly: representatives of a finite tuple occur at a common stage; functions and atomic relations are interpreted there. In the existential step, a witness in the limit occurs with the parameters at some later common stage, and elementarity pulls the existence statement back. Thus every $N_F$ embeds elementarily into $N$, which contains an elementary copy of $M^{+}$.

For $i\in F$, let $a_i$ be the class of the coordinate function $\mathbf{n}\mapsto b_{n_i}$. Projection coherence makes this independent of $F$. If $i<j$, then for each fixed $n_i$ the set $\{n_j:n_j\ne n_i\}$ is cofinite. The nested test therefore gives $a_i\ne a_j$. In the ordered variant, the same argument with $n_j>n_i$ gives $P(a_i)$ and $a_i<a_j$.

For every first-order formula $\phi$ of the expanded language and every increasing tuple $i_1<\cdots <i_r$, Łoś theorem givesThe right-hand side depends on the first-order formula and tuple length, not on the indices. This proves order indiscernibility in the expanded language. Let $H$ be the Skolem hull of the generators in $N$. The Tarski-Vaught test gives $H\prec N$, and its reduct is a first-order model of $\mathrm{Th}(M)$.

An order automorphism $\pi$ of $I$ acts byIndiscernibility makes this well defined: combine the finite supports of two term expressions into one increasing tuple, and apply indiscernibility to their logical equality. Applying it to relation first-order formulas proves preservation of all relations; the inverse is induced by ${\pi }^{-1}$. Every element of the hull is such a term, so the extension is unique among structure automorphisms preserving the Skolem expansion. MoreoverThis proves the theorem, including its ordered version and structure automorphism conclusion, using ultrapowers and a directed limit throughout.

Use untyped lambda calculus and normal-order beta reduction. Write $c_n=\lambda fx.f^{n}x$ for the Church numeral of $n$. We will construct a closed term $F$ such thatwhen $f(\mathbf{n})$ is defined, and with no head normal form otherwise. The latter condition implies that the result is not in beta equivalence with any Church numeral, so both definedness and the output are represented.

First represent all total primitive recursive functions. The zero function is $\lambda \mathbf{x}.c_0$, the successor function isand the $i$th projection function is $\lambda x_1\cdots x_k.x_i$. Function composition in recursion theory is represented by $\lambda \mathbf{x}.G(H_1\mathbf{x})\cdots (H_r\mathbf{x})$. This composition claim is used here for total functions, whose inner terms all reduce to numerals.

For primitive recursion use Church pairs and iteration. PutSuppose $G,H$ represent the total constituents of $f(\mathbf{x},0)=g(\mathbf{x})$ and $f(\mathbf{x},n+1)=h(\mathbf{x},n,f(\mathbf{x},n))$. DefineAfter $j$ iterations the pair reduces to $\mathsf{Pair}{c}_j{c}_{f(\mathbf{x},j)}$, by mathematical induction on $j$. Its second projection is the required result. This lambda definition of primitive recursion by pair iteration and structural induction on the primitive recursive construction give terms for all primitive recursive functions.

For an arbitrary partial computable function use the Kleene normal form theorem with its program index fixed. There are total primitive recursive functions $C(\mathbf{x},s)$ and $U(s)$ such that $C$ is zero exactly when $s$ codes a valid halting computation history on $\mathbf{x}$, and $U$ extracts that history's output. Checking finite coded configurations and each transition is primitive recursive. Determinism ensures that every accepted history on an input has the same output. HenceIf the input computation never halts, no history is accepted. Let $\hat{C},\hat{U}$ be the total numeral-representing terms already obtained. The Church numeral zero test is $\mathsf{Zero}=\lambda n.n(\lambda z.\mathsf{F})\mathsf{T}$, returning $\mathsf{T}$ exactly on zero. A Church Boolean applied to two arguments selects the appropriate branch without evaluating the other.

Take the fixed-point combinator $Y=\lambda h.(\lambda z.h(zz))(\lambda z.h(zz))$. For the input tuple defineExpanding the displayed abbreviations gives a genuine finite combinator. At a numeral code $c_j$, the total predicate computation terminates. If it returns a positive numeral, the false Church Boolean selects the next search code. If it returns zero, the true Church Boolean selects $\hat{U}{c}_j$, which reduces to the output numeral. If the least accepted code is $s$, a finite sequence of these tests reaches it and then produces $c_{U(s)}$.

If there is no accepted code, every test is false and head reduction moves through codes $0,1,2,\dots$ forever. At no finite point can a head variable or an outer numeral abstraction be produced: the applied search term must first unfold the fixed point and evaluate the next total test, and the decoder branch is always discarded. Thus it has no head normal form. The standard head-normalization property, or the Church-Rosser theorem together with normalization of normal-order reduction, rules out beta equivalence to a numeral. In particular, we have avoided a lazy-composition pitfall: an outer function that discards an argument need not force a divergent inner computation. The decoder is reached only after the guarded search succeeds. This proves lambda representation of partial computable functions:

Use the Fourier transform normalization $\hat{f}(\xi )={\int }_{\mathbb{R}}f(x)e^{-2\pi ix\xi }dx$. A precise version of the Poisson summation formula is that, for every Schwartz function $f\in \mathcal{S}(\mathbb{R})$,Both series have absolute convergence. Here being a Schwartz function means being smooth with ${\sup }_x|x^a{f}^{(b)}(x)|<\infty$ for all nonnegative integers $a,b$. This hypothesis makes the sums and the termwise operations below legitimate; the formula is not being asserted for arbitrary integrable functions.

Form the periodization of a Schwartz function $P_f(x)={\sum }_{n}f(x+n)$. Every differentiated series has uniform convergence on $[0,1]$, by rapid decay, so $P_f$ is a smooth periodic function of period one. Its $m$th Fourier coefficient isThe interchange follows from absolute convergence uniformly on this interval. Integration by parts shows that these Fourier coefficients decrease faster than every inverse power of $|m|$. Thus the Fourier series converges absolutely and uniformly to $P_f$; for example the standard convergence theorem for twice continuously differentiable periodic functions applies. Evaluating at zero proves the Poisson summation formula.

For $t>0$, scaling the given Gaussian Fourier transform givesApplying the Poisson summation formula gives the real-parameter Jacobi theta function transformation

For $\mathrm{Re}s>1$, termwise application of the Mellin transform is justified by integrating absolute values and givesEach positive $n$ contributes $\Gamma (s/2)(\pi n^2{)}^{-s/2}$, and the factor one half removes the equal positive and negative terms. This is the Mellin representation of the completed Riemann zeta function.

Split the integral at one. On $(0,1)$, the Jacobi theta function transformation writes $\theta (t)-1=t^{-1/2}-1+t^{-1/2}(\theta (1/t)-1)$. Integrating the first two terms and substituting $u=1/t$ in the third yields the pole-subtracted theta integral for the completed zeta function:The remaining integral is an entire function of $s$: $\theta (t)-1=O(e^{-\pi t})$, and on each compact set of $s$ this exponential dominates all powers of $t$ and all factors arising from differentiation. It therefore supplies a meromorphic continuation of $\Lambda$ to the whole plane, with simple poles at one and zero, of residues $1$ and $-1$, respectively. Its expression is unchanged by $s\mapsto 1-s$.

The reciprocal Gamma function is entire, with simple zeros at its nonpositive integer arguments. Consequentlyis holomorphic everywhere except for a simple pole at $s=1$, of residue one. The apparent pole at $s=0$ cancels; in fact $\Gamma (s/2{)}^{-1}\sim s/2$ gives $\zeta (0)=-1/2$. This proves the analytic continuation of the Riemann zeta function. The completed functional equation of the Riemann zeta function isThese are equalities of meromorphic functions; at apparent singularities they are interpreted by continuation. Equivalently, $\xi (s)=\frac{1}{2}s(s-1)\Lambda (s)$ is an entire function with $\xi (s)=\xi (1-s)$.

Write $\Gamma =S{L}_2(\mathbb{Z})$ and $G=G{L}_2(\mathbb{Q}{)}^{+}$. The double-coset Hecke algebra consists of $\Gamma$-bi-invariant complex functions on $G$ supported on finitely many double cosets, with convolutionEach double coset has finitely many orbits under left multiplication by $\Gamma$, by rational conjugation of finite-index modular subgroups. Thus the sum is finite and independent of representatives. The characteristic functions of the double cosets form its basis, and its right action on invariant modular forms is $f\ast h={\sum }_{\Gamma x}h(x)f{|}_{k}x$, using the determinant-normalized slash operator.

For a positive integer $n$, let ${\mathcal{M}}_n$ be all integral two-by-two matrices of positive determinant $n$. It is $\Gamma$-bi-invariant. Define $T(n)$ to be its indicator function, equivalently the sum of the distinct double cosets it contains, each with coefficient one. This is the convention consistent with the requested formula. For composite $n$, it need not be the single double coset of $\mathrm{diag}(1,n)$: for instance $2I\in {\mathcal{M}}_4$ cannot lie in that double coset, since multiplying by unimodular integral matrices preserves the greatest common divisor of the entries.

Prove all the needed subgroup facts directly. For a finite-index subgroup $L\subseteq {\mathbb{Z}}^2$, take $a$ to be the least positive first coordinate appearing in $L$ and $d$ the least positive second coordinate on its intersection with the second axis. Euclidean division then shows that the first-coordinate projection is $a\mathbb{Z}$ and $L\cap (\{0\}\times \mathbb{Z})=\{0\}\times d\mathbb{Z}$. Positivity follows, for example, because the finite quotient group kills a nonzero multiple of each coordinate vector. Choose $(a,b)\in L$ and reduce $b$ modulo $d$ to $0\le b<d$. Every vector of $L$ has first coordinate a multiple of $a$, and subtracting that multiple of $(a,b)$ leaves a multiple of $(0,d)$. Therefore these two vectors form a basis of $L$. The parameters $a,d,b$ are unique. Reducing the first coordinate modulo $a$ and then the second modulo $d$ gives precisely $ad$ quotient representatives, so $[{\mathbb{Z}}^2:L]=ad$.

Apply this row Hermite normal form in rank two to the row lattice of an integral matrix $A$ with $\det A=n$. Its row lattice contains $n{\mathbb{Z}}^2$, since $\mathrm{adj}(A)A=nI$, so it has finite index. Its two rows and the displayed two rows are bases of the same row lattice. The two inverse change-of-basis matrices have integer entries, so their determinants are integers whose product is one. Thus the change-of-basis matrix has determinant $\pm 1$; since both orientations are positive, its determinant is one. Thus each orbit under left multiplication by $\Gamma$ has exactly one of the determinant-n matrix representatives for Hecke operatorsThere are ${\sum }_{d\mid n}d$ such representatives, proving finiteness as well as the formula. The subgroup argument is a proof of the relevant Hermite normal form, not an invocation of an unproved lattice classification.

Consequently the normalized Hecke operator isIt preserves $M_k(\Gamma )$: right multiplication by $\Gamma$ permutes the left-multiplication orbits in ${\mathcal{M}}_n$, giving invariance, and cusp holomorphy under rational slash operators gives the holomorphy of each term at every cusp.

For a triangular representative the determinant-normalized slash operator is $f{|}_{k}A=n^{k/2}{d}^{-k}f((az+b)/d)$. Summing the Fourier expansion of a modular form over $b$ kills every index not divisible by $d$, by finite exponential orthogonality. ThusThe Fourier coefficients of a composite-index Hecke operator are thereforeIn particular $a_1(T_{n}f)=a_n(f)$. If $T_{n}f=\lambda f$, comparison of the $q$ coefficients gives

Finally suppose $a_0(f)\ne 0$ and $f$ is a simultaneous eigenfunction. Constant coefficients force ${\lambda }_n={\sigma }_{k-1}(n)$, so $a_n(f)=a_1(f){\sigma }_{k-1}(n)$ for all $n\ge 1$. Weight two cannot occur, by vanishing of weight-two level-one modular forms. For even $k\ge 4$, use the normalized Eisenstein series with its Fourier expansion of a normalized Eisenstein serieswhere $B_k$ is the Bernoulli number. Then $h=f-a_0(f)E_k$ is a cusp form with coefficients $(a_1(f)-a_0(f)c_k){\sigma }_{k-1}(n)$. The Fourier coefficient bound for a cusp form bounds these by $O(n^{k/2})$, but at arbitrarily large primes $p$ their magnitude is $|a_1-a_0{c}_k|(1+p^{k-1})$. Since $k-1>k/2$, the coefficient factor must vanish. All coefficients of $h$ then vanish, including its constant coefficient, so $h=0$ by its cusp expansion and the identity theorem. This proves the noncuspidal level-one Hecke eigenform characterization:

A real positive-definite kernel is a symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ such that, for every finite collection $x_1,\dots ,x_n$ and every $a\in {\mathbb{R}}^n$,Thus every kernel matrix is a positive semidefinite matrix; “positive definite” here does not require strict positivity. A Reproducing kernel Hilbert space is a Hilbert space $\mathcal{H}$ of functions on $\mathcal{X}$ in which every point evaluation is a continuous linear functional. Its reproducing property is $f(x)=⟨f,k_x{⟩}_{\mathcal{H}}$ with $k_x=k(\cdot ,x)\in \mathcal{H}$, and $k(x,y)=⟨k_y,k_x{⟩}_{\mathcal{H}}$. For a sum of positive-definite kernels, the quadratic form of its kernel matrix is a sum of nonnegative quadratic forms. Symmetry also survives summation. Consequently $\boxed{k=\sum _j{k}_j\text{ is a positive-definite kernel}.}$

For the representer theorem, put $V=\mathrm{span}\{k_{x_1},\dots ,k_{x_n}\}$. This is a closed finite-dimensional vector space. The orthogonal decomposition by a closed subspace gives $f=f_V+f_{\perp }$, where $f_V\in V$ and $f_{\perp }\perp V$. The reproducing property implies $f_{\perp }(x_i)=0$ for every observed input, and thereforeSince $\lambda >0$, any minimizer must lie in $V$. For $f_{\alpha }={\sum }_i{\alpha }_i{k}_{x_i}$, the reproducing property gives the evaluation vector $K\alpha$ and $\Vert f_{\alpha }{\Vert }_{\mathcal{H}}^2={\alpha }^{T}K\alpha$. Hence $Q_1(f_{\alpha })=M(\alpha )$. If $\hat{f}$ minimizes $Q_1$, its representation yields a minimizing $\hat{\alpha }$. Conversely, if $\hat{\alpha }$ minimizes $M$, then, for any $f\in \mathcal{H}$, representing $f_V=f_{\alpha }$ gives $Q_1(f)\ge M(\alpha )\ge M(\hat{\alpha })$. ThusThis is an equivalence of minimizers, not an existence or uniqueness assertion: the loss function is arbitrary. A singular kernel matrix also allows nonunique coefficients, since differences in $\ker K$ represent the zero function. Strict convexity of the loss was not used.

Now use the stated minimum-norm description of a sum of reproducing-kernel Hilbert spaces. Let $\hat{f}={\sum }_j{\hat{f}}_j$. If the minimizing tuple did not attain the minimum total squared norm among decompositions of $\hat{f}$, replacing it by that unique minimum-norm tuple would preserve the loss function and strictly lower the penalty. This contradicts optimality. ThereforeFor an arbitrary $f\in \mathcal{H}$, take its minimum-norm decomposition $(f_1,\dots ,f_p)$. Then $Q_1(\hat{f})=Q_2({\hat{f}}_1,\dots ,{\hat{f}}_p)\le Q_2(f_1,\dots ,f_p)=Q_1(f)$, proving that $\hat{f}$ minimizes $Q_1$.

Choose $\hat{\alpha }$ from the representer theorem for this minimizing sum, and define $g_j={\sum }_i{\hat{\alpha }}_i{k}_j(\cdot ,x_i)$. Write $K_j$ for the component kernel matrices. ThenBy uniqueness of the minimum-norm decomposition, $g_j={\hat{f}}_j$ for every $j$. This proves the common representer coefficients for a sum of kernels conclusion:The same coefficient vector works simultaneously. Even when $K$ is singular, changing that vector by $a\in \ker K$ leaves every component unchanged: $0=a^{T}Ka={\sum }_j{a}^T{K}_{j}a$ forces each nonnegative squared component norm to vanish.

Let $R$ denote the number of rejected null hypotheses and $V$ the number of rejected true null hypotheses. The familywise error rate is $\mathrm{Pr}(V\ge 1)$, whereas the false discovery rate is $\mathbb{E}[V/(R\vee 1)]$, with a zero contribution when $R=0$. A valid true-null p-value satisfies $\mathrm{Pr}(p_i\le t)\le t$ for $0\le t\le 1$.

For the closed testing procedure, choose a level-$\alpha$ local test of every nonempty intersection $H_I={\bigcap }_{i\in I}{H}_i$. Reject $H_i$ only if every intersection containing it is rejected by its local test. If any true null hypothesis is rejected, the local test of $H_{I_0}$ must reject. Since that intersection is true, its rejection probability is at most $\alpha$. If $I_0$ is empty there can be no false rejection. This proves strong closed-testing control of the familywise error rate, under arbitrary dependence, provided each local test is valid under its whole intersection null.

For the Benjamini-Hochberg procedure, order the p-values and setwith maximum zero if the set is empty; reject the first $R$ hypotheses. To prove its false discovery rate bound, fix a true-null index $i$. Replace $p_i$ by zero and let $R_i$ be the modified rejection count. This is a function of the other p-values and satisfies $R_i\ge 1$.

The Benjamini-Hochberg leave-one-out identity isHere is its deterministic justification. If $i$ was rejected, lowering its value cannot decrease $R$, and leaves all ordered values of ranks greater than $R$ unchanged. No such rank can newly satisfy its threshold, so $R_i=R$. Conversely, if $R_i=r$ and $p_i\le \alpha r/m$, at least $r-1$ other values and $p_i$ are at most this threshold. Therefore the original procedure has $R\ge r$. Monotonicity under decreasing $p_i$ also gives $R\le R_i=r$, so $R=r$ and $i$ is rejected. This establishes the identity; harmless deterministic tie-breaking also covers the artificial zero introduced in the modified data.

The assumed independence makes $p_i$ independent of $R_i$. Conditional on $R_i=r$, validity of the p-value impliesSum over $i\in I_0$ to obtainIf true-null p-values are exactly uniform rather than merely valid, the first inequality is equality. No restriction on dependence among the false-null p-values is needed beyond their joint independence from the true-null values.

For the requested Simes inequality, apply this result to the $m_0$ true-null p-values alone, for $m_0>0$. Every rejection is now false, so $V=R$ and the false discovery rate is the probability of any rejection. The event of at least one Benjamini-Hochberg procedure rejection is exactlyIts probability is at most $\alpha$. This holds for $\alpha \in [0,1]$; with no true nulls the written minimum and division by $m_0$ are undefined and the error-control statement is instead vacuous.

The final step-up rule is the Hochberg procedure. Use Simes tests as the local tests for a closed testing procedure: reject $H_I$ when ${\min }_r{p}_{(r,I)}/r\le \alpha /|I|$. Under any true intersection all its p-values are valid and independent, so the Simes inequality proves level $\alpha$ for its local test. The implication supplied in the question says that whenever the Hochberg procedure rejects $H_{(i)}$, every intersection containing $(i)$ passes its local Simes test. Thus every such rejection is also a closed-testing rejection. ConsequentlyThe true-null independence assumption is essential to this particular proof of local-test validity; the arbitrary-dependence guarantee of closed testing does not create valid local tests automatically.

For $\lambda >0$ and labels $Y_i\in \{-1,1\}$, with squared-norm penalty normalized as $\lambda {\alpha }^{T}K\alpha$, the kernel soft-margin support vector machine solvesHere $(u{)}_{+}=\max (u,0)$ is the hinge loss building block, and $K_i$ is column $i$ of the symmetric kernel matrix. The prediction iswith a fixed class choice, for example $+1$, when the score is zero. Other positive rescalings of the penalty change numerical coefficients in the optimality equation but not the zero-coefficient conclusion.

For a finite convex function $f:{\mathbb{R}}^n\to \mathbb{R}$, its subdifferential at $x$ isFor $f(x)=h(c^{T}x+b)$, affine composition preserves the defining convexity inequality: for $0\le t\le 1$,If $v\in \partial h(u)$, the subgradient inequality gives $f(y)\ge f(x)+v{c}^T(y-x)$, proving $cv\in \partial f(x)$.

Conversely, let $g\in \partial f(x)$ and first suppose $c\ne 0$. For every $z\in \ker c^T$, the function is constant along $x+tz$. Applying the subgradient inequality for both signs of $t$ shows $g^{T}z=0$. Thus $g$ is in the span of $c$, or $g=cv$ with $v=g^{T}c/\Vert c{\Vert }_2^2$. Substituting $y=x+(a-u)c/\Vert c{\Vert }_2^2$ gives $h(a)\ge h(u)+v(a-u)$ for every real $a$. Hence $v\in \partial h(u)$. If $c=0$, $f$ is constant and $\partial f(x)=\{0\}$; since finite convex $h$ on all of $\mathbb{R}$ has a nonempty subdifferential at $b$, $c\partial h(b)=\{0\}$ as well. This handles the case in which the suggested orthogonal projection would be undefined. ThereforeThis proves the subdifferential under scalar affine composition identity with all its degenerate cases.

Let $m_i=Y_i(\hat{\mu }+K_i^T\hat{\alpha })$ be a fitted support-vector-machine margin. The subdifferential of the hinge loss yields choicesApplying the affine-composition identity and the subdifferential sum rule to the convex objective, its optimum satisfiesThe second equation is the intercept condition. Since $K$ is invertible, multiplying the first by $K^{-1}$ gives the kernel support-vector coefficient from hinge activity formulaIn particular $\boxed{m_i>1⟹{\hat{\alpha }}_i=0.}$ Invertibility is needed for this statement about the chosen coefficients: for $K=11^T$ with two positive labels, $\hat{\mu }=2$ and $\hat{\alpha }=(1,-1{)}^T$ give zero objective and both margins equal to two, while both coefficients are nonzero. A singular kernel matrix allows coefficient changes in the null space without changing the fitted function.

At prediction time, the sum can omit all zero coefficients, requiring only the number of evaluations of the positive-definite kernel corresponding to retained support vectors rather than all $n$. This need not remove the cost of forming or solving with a dense training kernel matrix. Every misclassified point has $m_i\le 0<1$, including a score-zero tie assigned to the opposite class, so $t_i=1$ and ${\hat{\alpha }}_i=Y_i/(2n\lambda )\ne 0$. Thus many classification errors imply many active support vectors and little prediction-time sparsity benefit. Correctly classified points inside the unit margin can also have nonzero coefficients; a point exactly on the margin need not have a nonzero coefficient.

The most plausible cause is strong dependence between the latent variables and covariance hyperparameters in their joint posterior distribution. In the usual conditionally independent Gaussian process classification model, put $F=(f(x_1),\dots ,f(x_n))$, $w={\sigma }^{-2}$, and $C=w^{-1}{R}_{\tau }$. The probit regression likelihood is $\ell (F)={\prod }_i\Phi ((2y_i-1)F_i)$, while $F\mid w,\tau$ has a multivariate normal distribution with covariance matrix $C$.

For distinct inputs and positive length scales, $R_{\tau }$ is positive definite. Its Gaussian probability density function contributesThe unit-rate exponential prior distribution on $w$ therefore givesIts scale is tightly tied to the current magnitude and shape of $F$. Changing $\tau$ changes the eigenvectors and eigenvalues of its covariance matrix; a latent vector typical under the old covariance may be very atypical under a substantially different one. Holding $F$ fixed can thus restrict the range of a hyperparameter update, and holding the hyperparameters fixed restricts the next latent-function update. Even exact sampling of each full conditional distribution can move slowly along a narrow ridge of the joint posterior distribution.

Binary observations provide limited information about the absolute size of large correctly signed latent values. This can leave substantial scale uncertainty and strengthen the dependence. Long correlation lengths can also make the covariance matrix nearly singular and the latent coordinates highly dependent. These are plausible explanations for a large mixing time, not proofs that every data set causes slow convergence. A blocked Gibbs sampler removes dependence within its chosen blocks, but not dependence between them. Repeated identical inputs should be represented by one shared latent value; otherwise the nominal Gaussian matrix is singular and the displayed inverse formula must be replaced by a representation on its support.

Let $s={\sigma }^2$ and $\vartheta =(s,{\tau }_1,\dots ,{\tau }_m)$. With conditional independence of the binary observations given the latent function, defineThe prior distribution is specified on the precision $s^{-1}$, not on $s$. Its Jacobian determinant givesand the marginal posterior density is proportional to $p(\vartheta )L(\vartheta )$. Working instead with precision or logarithmic coordinates is possible, provided all corresponding Jacobian determinants are included.

Choose an importance sampling density $g_{\vartheta }$ covering the support of $\ell (F){\phi }_{C_{\vartheta }}(F)$, draw $F_1,\dots ,F_M$ independently from it, and use the nonnegative unbiased likelihood estimatorEach summand integrates to $L(\vartheta )$, proving unbiasedness. A simple always-valid choice is the latent Gaussian prior distribution, $g_{\vartheta }={\phi }_{C_{\vartheta }}$, when the covariance matrix is nonsingular. Then the estimator is just the average of the bounded values $\ell (F_j)\in (0,1)$. For duplicate inputs, sample only the distinct latent values and multiply all likelihood contributions at each common input. A Gaussian approximation to the latent posterior distribution, or its mixture with the Gaussian prior distribution, can reduce relative variance while keeping complete support. Its approximation does not replace the exact weights.

The pseudo-marginal Metropolis–Hastings algorithm stores both the current $\vartheta$ and its estimator randomness $u$; write their sampling law as $m_{\vartheta }(u)$. Propose ${\vartheta }^{\prime }\sim q(\vartheta ,\cdot )$, independently generate $u^{\prime }\sim m_{{\vartheta }^{\prime }}$, compute $\hat{L}({\vartheta }^{\prime },u^{\prime })$, and accept the pair withHere $q(\vartheta ,{\vartheta }^{\prime })$ denotes the proposal probability density function from $\vartheta$ to ${\vartheta }^{\prime }$. On rejection retain both the old parameter and the old likelihood estimate. Initialize with a positive estimate. One must not independently refresh the denominator after rejection.

Correctness follows from the extended posterior densityThe pair proposal is $q(\vartheta ,{\vartheta }^{\prime })m_{{\vartheta }^{\prime }}(u^{\prime })$. Its Metropolis–Hastings acceptance probability simplifies to the displayed ratio, since the auxiliary densities cancel. Hence detailed balance holds for $\tilde{\pi }$. Integrating over $u$ gives $p(\vartheta )L(\vartheta )$ by unbiasedness, so the parameter marginal distribution is exactly the intended posterior distribution for any fixed positive $M$. This is exactness of the stationary target, not independent exact samples or a guarantee of rapid convergence. Large relative variance of the likelihood estimates can produce long holding times, so marginalizing $F$ does not by itself guarantee an improvement in mixing time.

The relevant Penrose singularity theorem states: a connected time-oriented four-dimensional globally hyperbolic spacetime with a noncompact Cauchy hypersurface, a nonempty compact orientable boundaryless trapped surface, and the null convergence condition is future null-geodesically incomplete. Under the Einstein field equations, the null energy condition supplies the curvature hypothesis. A trapped surface here is spacelike and has both future normal null expansions strictly negative. The conclusion is an incomplete null geodesic, not necessarily a divergent curvature invariant at an identifiable point.

Suppose, for contradiction, that every future null geodesic is complete. Write $S$ for the trapped surface andThe equality follows because the causal future of a compact set is closed in a globally hyperbolic spacetime. This future horismos is a closed achronal boundary. It is nonempty: the restriction of a Cauchy time function to compact $S$ has a minimum, and a point at that minimum cannot be chronologically preceded by another point of $S$.

Normalize the two future null normal directions along $S$ against a smooth future timelike field, fixing the affine scale continuously. Their initial null expansions are continuous and strictly negative. Compactness of the normalized normal bundle gives a uniform $c>0$ with ${\theta }_{\pm }\le -c$ everywhere on $S$. The preceding null focusing theorem forces a conjugate point to a spacelike surface along each normal generator within affine length $L=2/c$.

By the supplied boundary-generator result, every point of $E^{+}(S)$ is reached by an orthogonal future null geodesic which has no earlier conjugate point. No such boundary generator can remain on the boundary beyond its first focal point. Every point of $E^{+}(S)$ therefore lies inThe parameter set is compact. Future null completeness makes its geodesic flow defined throughout this common finite interval, and smooth dependence on initial data makes its image $K$ compact. Since $E^{+}(S)$ is closed and contained in $K$, it is compact. This is the compactness of the future horismos of a trapped surface step; a merely pointwise finite bound would not suffice without compactness and uniform normalization.

Choose a smooth complete timelike vector field, obtained if necessary by positive rescaling against a complete auxiliary Riemannian metric. Its inextendible integral curves of a vector field meet a chosen smooth Cauchy hypersurface $C$ exactly once. Projection along those curves defines a continuous map ${\pi }_C:E^{+}(S)\to C$. The achronal set property makes this map an injective function: two boundary points on the same timelike integral curve of a vector field would be timelike related.

An achronal boundary is a topological hypersurface without boundary, even at nonsmooth generator junctions; the submanifold property allowed in the question supplies this fact. Thus domain and codomain are both three-dimensional topological manifolds without boundary. Invariance of domain makes ${\pi }_C(E^{+}(S))$ open in $C$. Compactness makes it closed in the Hausdorff space $C$, and it is nonempty. Connectedness of the spacetime gives connectedness of $C$, so this image is all of $C$. That would make $C$ compact, contradicting the noncompact Cauchy hypersurface hypothesis. The completeness assumption is false, proving the theorem.

The noncompactness hypothesis and strict trapping are essential to this version. Global hyperbolicity cannot simply be omitted in the compactness and projection steps, and nonpositive initial expansion with zeros does not supply the uniform focusing bound used here.

For $0<\alpha \le 1$, uniform Lipschitz-$\alpha$ means that one constant $M$ satisfies $|f(x)-f(y)|\le M|x-y{|}^{\alpha }$ for every $x,y\in [0,1]$. The resulting Hölder space has normFor the subsequent estimates at general $\alpha >0$, use the higher-order Hölder class convention: write $\alpha =r+\beta$ with $r\ge 0$ an integer and $0<\beta \le 1$, and require $f\in C^r([0,1])$ with $f^{(r)}$ uniformly Lipschitz-$\beta$. ThusAt integer $\alpha =k$, this uses $C^{k-1,1}$; the alternative classical $C^k$ convention is stronger on this compact closed interval and also suffices for the estimates.