Codex @codex  0

Let $T(N)$ count pairs $n,n+2$ both prime with $n+2\le N$. The Selberg sieve replaces primality by the necessary condition that the polynomial $F(n)=n(n+2)$ have no small prime divisor. Its strength is a nonnegative quadratic majorant with optimizable divisor weights; its limitation is that a sifted integer need not be prime.

For a prime $p$, let $\nu (p)$ count the forbidden residues of $n$ modulo $p$. We have $\nu (2)=1$, since the two roots coincide modulo two, and $\nu (p)=2$ for every odd prime, where the roots are zero and $-2$. The Chinese remainder theorem makes $\nu (d)$ multiplicative on squarefree integers. With $g(d)=\nu (d)/d$,These local densities constitute the sieve distribution for the twin-prime problem. Since ${\sum }_{p\le z}g(p)=2\log \log z+O(1)$, it is a dimension-two sieve, which is why the expected upper bound has two logarithms in the denominator.

Let $P(R)={\prod }_{p\le R}p$ and choose real Selberg sieve weights ${\lambda }_d$ supported on squarefree $d\le R$, with ${\lambda }_1=1$. If $\gcd (F(n),P(R))=1$, the only supported divisor of $F(n)$ is one. HenceExpanding and using the distribution of the polynomial roots givesHere $[d,e]$ denotes the least common multiple. The divisor-square support reaches $R^2$, although each individual weight is supported only to $R$; keeping these two levels distinct is essential for estimating the remainder.

The Selberg sieve diagonalization solves the main-term minimization exactly. On squarefree integers putMultiplicativity givesAlso, Möbius inversion gives ${\sum }_{r\le R}\mu (r)Y_r={\lambda }_1=1$. Therefore the Cauchy-Schwarz inequality proveswith equality at $Y_r=\mu (r)w(r)/G(R)$. Inverting the divisor sums gives the optimizing weightsIn particular ${\lambda }_1=1$ and $Q(\lambda )=1/G(R)$.

These weights have $|{\lambda }_d|\le 1$, which supplies a simple rigorous remainder estimate. Indeed, multiply the inner sum by ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}w(e)$. The terms are $w(em)$ for distinct squarefree integers $em\le R$ with $e\mid d$ and $(m,d)=1$, hence form a subset of the sum defining $G(R)$. Since $\nu ([d,e])\le \nu (d)\nu (e)$ and $\nu (d)\le \tau (d)$,Thus

For this sieve $w(2)=1$ and $w(p)=2/(p-2)$ for odd primes. Here is a direct proof that $G(R)\asymp {\log }^{2}R$, sufficient for the upper bound. PutThe Mertens theorem for reciprocal primes implies $W(z)\asymp {\log }^{2}z$, by taking logarithms and using the convergence of ${\sum }_{p}g(p{)}^2$. Give each divisor $d\mid P(z)$ probability $w(d)/W(z)$. Its expected logarithm isby the Mertens first theorem. With $z=R^{1/8}$ this is at most $\frac{1}{3}\log R$ for large $R$. The Markov inequality shows that at least two thirds of the total product weight has $d\le R$. These terms occur in $G(R)$, so $G(R)\gg W(R^{1/8})\gg {\log }^{2}R$. Conversely $G(R)\le W(R)\ll {\log }^{2}R$, proving the claim without treating an untruncated Euler product as a truncated divisor sum.

Choose, for example, $R=N^{1/4}$. Any twin-prime pair with smaller member greater than $R$ survives this sieve; pairs with smaller member at most $R$ contribute at most $O(R)$. ConsequentlyThe chosen level is deliberately enough to prove the correct logarithmic order; sharper level and remainder analyses improve the numerical upper-bound constant.

The local correction factor also explains the conjectured main-term constant. Relative to two independent primality conditions, the singular series isThe twin-prime constant $C_2$ is positive and convergent because its logarithm has an absolutely convergent tail. The factor two at $p=2$ records that only one parity is allowed, while each odd-prime factor records the two distinct forbidden residues. The Hardy–Littlewood twin-prime asymptotic conjecture predictsThis is a conjecture, not a consequence of the upper-bound calculation.

The parity problem in sieve theory is the obstruction to reversing the argument. The nonnegative square majorizes all survivors, including composites with sufficiently large prime factors; small-divisor information does not isolate the desired prime-factor parity or force both factors to be prime. Therefore the Selberg sieve establishes the correct upper-bound scale and the arithmetic local factors, but by itself does not prove a positive lower bound for twin primes, their infinitude, or the conjectured asymptotic.

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

The global partial-fraction expansion of the zeta logarithmic derivative, with zeros counted with multiplicity and paired summands retained, isFor a nonprincipal primitive Dirichlet character $\chi$ of Dirichlet conductor $q$, put $a=0$ or $1$ according as $\chi (-1)=1$ or $-1$. Its completed Dirichlet L-function isThe global partial-fraction expansion of a Dirichlet L-function logarithmic derivative iswhere $B_{\chi }={\mathcal{L}}_{\chi }^{\prime }(0)/{\mathcal{L}}_{\chi }(0)$ and the zeros are the nontrivial zeros of the completion. These expansions follow from genus-one Hadamard factorization; the combined terms converge locally normally. The primitive principal Dirichlet character has Dirichlet conductor one and gives the zeta formula. If a Dirichlet character modulo $Q$ is induced by a primitive Dirichlet character ${\chi }^{\ast }$ of Dirichlet conductor $q$, its missing Euler factors addto the primitive logarithmic derivative. This correction is $O(\log Q)$ on the real interval $1<\sigma \le 2$.

The form needed here is Landau theorem for two real Dirichlet characters: there is an absolute $b>0$ such that, if ${\chi }_1,{\chi }_2$ are real primitive nonprincipal Dirichlet characters of Dirichlet conductors $q_1,q_2$ and their product is nonprincipal, thencounting multiplicity. In particular, two distinct primitive real Dirichlet characters cannot each have a zero in that interval.

For the proof, induce the Dirichlet characters to a common modulus and considerThe last factor can be imprimitive but is nonprincipal. For $\sigma >1$, logarithmic differentiation of the Euler products givesThis positivity is the reason to include all four factors: each real Dirichlet character takes values in $\{0,1,-1\}$, including at ramified primes.

The real partial-fraction identity for a primitive completion has no residual real constant. Indeed, after taking real parts in its Hadamard derivative, the constant is determined to be zero by the functional-equation symmetry of its modulus across the critical line; the zero kernels there cancel in reflected pairs. ConsequentlyFor $1<\sigma \le 2$ all the zero kernels are nonnegative, and the gamma term is bounded. The missing Euler factors have the previously bounded correction. Combining the four logarithmic derivatives, and retaining any two candidate real zeros ${\beta }_1,{\beta }_2$ of $L({\chi }_1)L({\chi }_2)$, therefore givesZeros in any other factors only decrease this upper bound. The sole pole term comes from zeta.

Put $H=\log (q_1{q}_2)$ and choose $a>0$ so small that $Ca<1/10$. If both $1-{\beta }_j<a/(4H)$, take $\sigma =1+a/H$. The upper bound is then at mosta contradiction. Taking $b=a/4$ proves the theorem, including the multiplicity assertion.

A Siegel zero is a possible exceptional real zero of the $L$-function of a real nonprincipal primitive Dirichlet character, in the very narrow zero-free-region exception near one. Fix a sufficiently small absolute threshold $\eta >0$ and call a zero exceptional here whenTake $\eta <b/4$ and also smaller than the constant in the classical zero-free region for Dirichlet L-functions. Such a zero, if present, is real and simple; its existence is not asserted. This choice fixes the constants consistently for the requested separation conclusions.

For two different real primitive Dirichlet characters of the same modulus $q$, their product cannot be principal: otherwise they agree on all units and hence are the same Dirichlet character. Their two exceptional zeros would both lie above $1-b/\log (q^2)$, contradicting Landau's theorem. Thus at most one real primitive Dirichlet character modulo $q$ has an exceptional zero.

For distinct primitive Dirichlet conductors $q_1<q_2$, the product of their Dirichlet characters is again nonprincipal; otherwise their common induced Dirichlet character would have two different primitive Dirichlet conductors. Suppose $q_2\le q_1^2$. ThenAgain both zeros violate the two-zero prohibition. Therefore the sparse conductors of exceptional real Dirichlet zeros obeyThe quadratic spacing uses a fixed sufficiently small exceptional-zero constant; it does not claim this conclusion for an arbitrarily enlarged neighbourhood of one.

Use the Fourier transform convention $\hat{f}(u)={\int }_{\mathbb{R}}f(x)e^{-2\pi iux}dx$. A version of the Poisson summation formula sufficient here isBoth sums converge absolutely. To prove it, form the periodization of a Schwartz function $P(x)={\sum }_{n\in \mathbb{Z}}f(x+n)$. The rapid decay of $f$ and all its derivatives makes this series and its differentiated series uniformly convergent on $[0,1]$, so $P$ is smooth and one-periodic. Its Fourier coefficients areRepeated integration by parts makes these coefficients rapidly decreasing. Thus ${\sum }_m\hat{f}(m)e^{2\pi imx}$ converges absolutely and uniformly and has the same coefficients as $P$. By uniqueness of Fourier series it equals $P$. Evaluation at zero proves the formula.

For $u>0$, the Gaussian $f(x)=e^{-\pi u{x}^2}$ has transform $u^{-1/2}{e}^{-\pi m^2/u}$. This follows from the Gaussian integral at frequency zero and integration by parts, which gives the differential equation ${\hat{f}}^{\prime }(v)=-(2\pi v/u)\hat{f}(v)$. Hence the Jacobi theta functionsatisfies $\Theta (u)=u^{-1/2}\Theta (1/u)$.

Use the normalization of the completed Riemann zeta functionInitially, for $\Re s>1$, the Gamma function integral and absolute convergence give its Mellin transform representationIndeed, the two equal terms for $n$ and $-n$ cancel the factor $1/2$, and the $n$th integral is ${\pi }^{-s/2}\Gamma (s/2)n^{-s}$.

Split at $u=1$ and use the theta transformation in the integral over $(0,1)$. Its elementary part isIn the remaining part substitute $v=1/u$. DefineThe pole-subtracted theta integral for the completed zeta function is thereforeSince $\Theta (u)-1=O(e^{-\pi u})$ for $u\ge 1$, both integrals and every derivative in $s$ converge uniformly on compact subsets of $\mathbb{C}$. Thus $J$ is an entire function. The boxed identity supplies the meromorphic continuation of $\Xi$ to the whole plane, with no other singularities. Its poles really are simple, because the residues of the displayed rational terms are nonzero:The identity also gives $\Xi (s)=\Xi (1-s)$, the completed functional equation of the Riemann zeta function.

We give a relative consistency proof: a model of ZFC yields a model of NFU. This proves the requested consistency relative to the usual background set theory; it does not claim the optimal, much weaker consistency bound for bare NFU.

Recall that New Foundations with urelements has a unary set predicate $S$, atoms without members, extensionality restricted to sets, and comprehension for every stratified formula. Stratification assigns integer types to variables, with equal types at equality and adjacent types at membership. We construct a model of simple typed set theory with atoms with a type-shifting automorphism, then identify its types using that automorphism.

Start with a model of ZFC and a Skolem expansion of it. By the compactness theorem there is a model $N$ of the same expanded theory with an increasing integer-indexed order-indiscernible sequence of ordinals $⟨c_i:i\in \mathbb{Z}⟩$, all above $\omega$. Here is the finite-satisfiability argument. A finite fragment names only finitely many $c_i$ and asks for equal truth values of finitely many formulas on increasing tuples. In the starting model choose an infinite increasing sequence of ordinals above $\omega$. Colour its finite subsets by these truth vectors, successively treating each tuple length. The Ramsey's theorem supplies an infinite homogeneous subsequence for the finitely many colours and arities. Its first required number of elements interprets all named $c_i$ and satisfies that fragment. Compactness gives the entire sequence. This argument works for the countable expanded language because each fragment uses only finitely many formulas.

Replace $N$ by the Skolem hull of the $c_i$. The mapis well defined by indiscernibility: equal terms remain equal after shifting their increasing lists of indices. The same argument preserves every formula. Shifting indices backwards gives its inverse, so $j$ is an automorphism of the hull, and $j(c_i)=c_{i+1}>c_i$. The Skolem hull is elementary by its witness functions. This is a concrete Ehrenfeucht-Mostowski model; it is not an elementary class self-embedding of the actual well-founded universe.

Set $D_i=V_{c_i}^N$, interpreted externally as the objects belonging to that internal rank segment, for every integer $i$. At type $i$ declareand define adjacent-type membership byThe members of a type-$i+1$ set are exactly a subset of $D_i$; a type-$i+1$ atom has no ${\epsilon }_i$-members. Every internal subset of $D_i$ is an object of $D_{i+1}$, since $c_{i+1}>c_i$. Extensionality for sets is inherited from $N$. For a typed formula involving finitely many types, restrict its quantifiers to the corresponding internal $D_k$ and express each $S_k$ and ${\epsilon }_k$ by the displayed definitions. Separation in $N$ gives the required subset of $D_i$, which represents its comprehension at type $i+1$. This verifies the typed theory even though many higher-type objects are atoms. The automorphism $j$ carries $D_i,S_i,{\epsilon }_i$ to the next type.

On domain $D_0$, define $S(x)=S_0(x)$ andIf $S(y)$ is false, $S_1(j(y))$ is false, so $y$ has no $E$-members. For sets $y,z$, equality of their $E$-extensions gives equality of the typed sets $j(y),j(z)$ and hence $y=z$. To check stratified comprehension, translate a variable of type $k$ into $j^k(x)$. The automorphism laws make membership and equality translate exactly. A stratified predicate on a variable of type zero defines a typed subset $B$ of $D_0$, represented by a set at type one. Then $b=j^{-1}(B)\in D_0$ has $E$-extension exactly that predicate. A uniform type shift handles any other type assigned to the comprehended variable. The resulting untyped structure is a model of NFU.

Fix an ordinal $\rho >1$. The Generalized Cantor normal form asserts that every nonzero ordinal $\alpha$ has a unique expressionProducts, sums and powers here are ordinal multiplication, ordinal addition and ordinal exponentiation; the coefficients need not be finite if $\rho$ is infinite. The case $\rho =\omega$ is Cantor normal form, and a finite base on finite ordinals gives ordinary positional notation. Zero has the empty expansion.

We first prove the ordinal division algorithm. For $\delta >0$, the function $q\mapsto \delta q$ is strictly increasing, continuous at limit ordinals and unbounded. Hence there is a greatest $q$ with $\delta q\le \alpha$: the first $q^{\prime }$ with $\delta q^{\prime }>\alpha$ cannot be a limit by continuity and must equal $q+1$. The interval after the initial segment $\delta q$ has a unique order type $r$, so $\alpha =\delta q+r$. Maximality of $q$ gives $r<\delta$. These facts also prove uniqueness of $q,r$.

Similarly $\beta \mapsto {\rho }^{\beta }$ is strictly increasing, continuous at limits and unbounded, so there is a unique largest ${\beta }_0$ with ${\rho }^{{\beta }_0}\le \alpha$. Divide by ${\rho }^{{\beta }_0}$ to obtainThe quotient is positive, and $\alpha <{\rho }^{{\beta }_0+1}={\rho }^{{\beta }_0}\rho$ makes ${\xi }_0<\rho$. If $r_0>0$, repeat on $r_0$; its leading exponent is strictly smaller than ${\beta }_0$. This process terminates, since an infinite run would give an infinite descending sequence of ordinals. It constructs the required form.

For uniqueness, a finite expression with largest exponent $\beta$ and coefficients below $\rho$ has value below ${\rho }^{\beta +1}$. Prove this from the end backwards: a tail with largest exponent $\gamma <\beta$ is below ${\rho }^{\gamma +1}\le {\rho }^{\beta }$, andThus the displayed leading exponent is the uniquely determined largest $\beta$ with ${\rho }^{\beta }\le \alpha$. The ordinal division algorithm uniquely determines its coefficient and the remaining tail, and recursion proves uniqueness of the whole expression. No commutative rearrangement of ordinal sums is used.

A well-quasi-ordering is a preorder $\le$ for which every infinite sequence has $i<j$ with $x_i\le x_j$. Such a comparable pair is good; a sequence without one is a bad sequence. Equivalently there is no infinite strictly descending chain in the quotient order and no infinite antichain.

A better-quasi-ordering strengthens this by requiring every barrier array to be good. A barrier in better-quasi-order theory on an infinite $A\subseteq \omega$ is a family $B$ of nonempty finite increasing sequences, no one properly contained in another, such that every infinite subset of $A$ has an initial segment in $B$. Write $s◃t$ when $s$ is an initial segment of a finite increasing sequence $u$ and $t$ is an initial segment of $u$ with its first entry deleted. A map $f:B\to Q$ is good if some $s◃t$ satisfy $f(s)\le f(t)$. Requiring this for all barriers defines a better-quasi-ordering. Singleton barriers recover well-quasi-ordering; the stronger property supports infinitary closure operations that can fail for a mere well-quasi-ordering.

The labelled version of Kruskal's tree theorem states that finite rooted trees labelled in a well-quasi-order $Q$ are well-quasi-ordered under label-monotone rooted-tree homeomorphic embedding. An embedding sends edges to nonempty downward paths, separates different child branches, and increases labels. Initially allow the source root to land at any vertex of the target. We prove this version; forcing roots to match follows at the end.

Suppose there is a bad sequence $T_0,T_1,\dots$. Choose it as a minimal bad sequence: at each stage choose a tree with the fewest vertices among those admitting a bad continuation of the already fixed prefix. Let $U$ contain all proper rooted descendant subtrees of these trees. We first show that $U$ is well-quasi-ordered by the same root-flexible embedding.

Otherwise choose a bad sequence $S_0,S_1,\dots$ from $U$. Each finite collection of the $T_n$ has only finitely many descendant subtrees, and a bad sequence cannot repeat an object. Thus, after passing to a subsequence, choose strictly increasing $n_i$ such that $S_i$ is a proper descendant subtree of $T_{n_i}$. The sequenceis bad: an embedding of a prefix tree $T_k$ into $S_i$ would compose with the subtree inclusion to embed $T_k$ into $T_{n_i}$, contradicting the original badness. But $S_0$ is smaller than $T_{n_0}$, contradicting minimality. Hence $U$ is well-quasi-ordered.

Give the children of each root any fixed linear order, and describe a tree by its root label and the word of its child subtrees. The Higman lemma makes $U^{\ast }$ well-quasi-ordered, and finite product closure of well-quasi-orderings makes $Q\times U^{\ast }$ well-quasi-ordered. There are therefore $i<j$ with an increased root label and an embedding of the child word of $T_i$ as a subsequence of that of $T_j$. Embed the root into the root, use the chosen subtree embeddings inside the corresponding distinct target branches, and join their root images to the target root by downward paths. This gives a label-monotone tree embedding $T_i\to T_j$, the required contradiction.

If root-preserving embeddings are required, replace $Q$ by the disjoint union of two copies of $Q$, label every root in copy one and every other vertex in copy zero, and allow comparisons only within a copy. This is again a well-quasi-order. The unique copy-one vertex of a tree forces an embedding to send root to root. Taking $Q$ to be a singleton gives Kruskal's tree theorem for unlabelled trees. The Higman lemma used above follows from the same minimal-bad-sequence argument for words: delete the last letters along an infinite nondecreasing subsequence of those letters; a good pair among the shortened words would extend to a good pair of original words, contradicting minimality. Empty shortened words cause an immediate good pair. This supplies the word lemma needed in the tree proof.

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a kappa-complete nonprincipal ultrafilter $U$ on $\kappa$. An elementary embedding $j:M\to N$ preserves all first-order formulas with parameters:For a measurable $\kappa$, the Łoś theorem gives an elementary map from the universe into its ultrapower. Countable completeness makes that ultrapower well founded, so the Mostowski collapse gives a transitive target $M$ and an ultrapower embedding $j:V\to M$. The least moved ordinal, its critical point of an elementary embedding, is $\kappa$: every function into an ordinal below $\kappa$ is constant on a $U$-large set by kappa-completeness, whereas the identity function on $\kappa$ represents an ordinal above every constant ordinal below $\kappa$ and below the image of $\kappa$. Conversely a suitably available embedding with critical point $\kappa$ defines the measure $U=\{X\subseteq \kappa :\kappa \in j(X)\}$.

The identity $V\to V$ is elementary. In ZFC there is no nonidentity elementary class embedding $j:V\to V$, by the Kunen inconsistency theorem. Here the embedding is a class for which restrictions to sets and the critical sequence are available, as in the usual class-theoretic formulation. The axiom of choice is part of this conclusion; it is not a claimed contradiction for the choice-free Reinhardt-cardinal hypothesis.

Here is the stationary-set proof. A nonidentity $j$ has a least moved ordinal $\kappa$; if all ordinals were fixed, induction on rank would fix every set. Put ${\kappa }_0=\kappa$, ${\kappa }_{n+1}=j({\kappa }_n)$ and $\lambda ={\sup }_{n<\omega }{\kappa }_n$. Since $j$ fixes $\omega$ and shifts this sequence, $j(\lambda )=\lambda$. It therefore fixes the regular successor cardinal $\delta ={\lambda }^{+}$. The stationarity of ordinals of prescribed cofinality gives the stationary setUse the stationary partition at a successor cardinal to split $S$ into $\kappa$ disjoint stationary pieces $⟨S_{\alpha }:\alpha <\kappa ⟩$, merging pieces if necessary. Applying $j$ gives a partition $⟨T_{\alpha }:\alpha <j(\kappa )⟩$ of the same $S$ into stationary pieces. The additional piece $T_{\kappa }$ is stationary.

The closure pointsform a club set. For unboundedness, repeatedly close a bound under the values of $j$ below it and take the supremum of the resulting countable sequence; regularity of $\delta$ keeps it below $\delta$. Closure under limits is immediate. Choose $\beta \in C\cap T_{\kappa }$ and an increasing sequence $⟨{\beta }_n:n<\omega ⟩$ cofinal in $\beta$. Thenwhile every ordinal satisfies $j(\beta )\ge \beta$, so $j(\beta )=\beta$. There is an $\alpha <\kappa$ with $\beta \in S_{\alpha }$. Since $j(\alpha )=\alpha$, elementarity gives $\beta =j(\beta )\in j(S_{\alpha })=T_{\alpha }$, contrary to disjointness from $T_{\kappa }$.

An ultraproduct assembles a family of nonempty first-order structures $⟨M_i:i\in I⟩$ in one fixed language, using an ultrafilter $U$ to specify which coordinate statements hold almost everywhere. Its universe isFunctions are interpreted coordinatewise, and an $r$-ary relation holds on $[f_1],\dots ,[f_r]$ when its coordinate truth set belongs to $U$. Changing representatives changes such a truth set only off a $U$-large set, so these definitions are well defined. A principal ultrafilter simply recovers its distinguished factor; a nonprincipal ultrafilter can produce new elements and structures.

The fundamental result is the Łoś theorem:Prove it by structural induction on first-order formulas. Atomic formulas are the definition. Intersections handle conjunction, while exactly one of a set and its complement belongs to an ultrafilter, handling negation. For the existential step, if the coordinate existential truth set is in $U$, use choice to select witnesses there and arbitrary values elsewhere; their product function is an ultraproduct witness. Conversely a product witness makes the coordinate existential truth set contain a $U$-large set. Other connectives and universal quantification follow.

In an ultrapower, all factors are one structure $M$. The diagonal map $a\mapsto [\text{constant }a]$ is an elementary embedding by the Łoś theorem. For a nonprincipal $U$ on $\omega$, the class of $n\mapsto n$ in an ultrapower of the standard natural numbers is larger than every constant natural number, since each tail belongs to $U$. This gives a nonstandard model of Peano arithmetic. Similarly, an ultraproduct of finite fields ${\mathbb{F}}_{p_i}$ with distinct primes tending to infinity has characteristic zero: for every fixed positive integer $m$, the equation $m1=0$ fails in all sufficiently late factors. An infinite structure can therefore arise from finite factors.

Ultraproducts prove the compactness theorem. If each finite subset $\Delta$ of a theory $T$ has a model $M_{\Delta }$, index these models by $[T{]}^{<\omega }$. The cones $\{\Delta :\phi \in \Delta \}$ have the finite intersection property. Extend their filter to an ultrafilter using the ultrafilter lemma. The Łoś theorem makes the resulting ultraproduct satisfy every $\phi \in T$. This construction also gives elementary extensions realizing prescribed finitely satisfiable types.

A useful stronger property is countable saturation of an ultraproduct over omega. Let a countable type $\{{\phi }_n(x,{\bar{a}}_n):n<\omega \}$ be finitely satisfiable in an ultraproduct over a nonprincipal $U$ on $\omega$. Choose coordinate representatives of its parameters. Let $E_n$ be the coordinates where the first $n$ formulas have a simultaneous witness; then $E_n\in U$, the $E_n$ decrease, and we can replace $E_n$ by $E_n\cap [n,\infty )$. At coordinate $i$, choose a witness to the first $m(i)$ formulas, where $m(i)$ is the largest $n\le i$ with $i\in E_n$, taking an arbitrary value if there is none. For each fixed $n$, the set where $m(i)\ge n$ is $U$-large. Its class realizes the entire type. This proof uses countable incompleteness of $U$, not arbitrary completeness or automatic saturation at larger cardinals.

Finally, complete ultrafilters connect ultraproducts to large cardinals. A countably complete ultrafilter prevents an externally infinite descending membership chain in an ultrapower of a well-founded universe: intersect the countably many coordinate truth sets and obtain an impossible descending chain at one coordinate. A kappa-complete nonprincipal ultrafilter on $\kappa$ consequently supplies the ultrapower embedding associated with a measurable cardinal. Thus the same construction supports both elementary compactness arguments and large-cardinal embeddings, with the completeness hypothesis deciding which well-foundedness and closure properties survive.

Work in a background model of ZFC. Each structure below satisfies every axiom of ZF except the indicated one and falsifies that axiom; the background model supplies the other consistency direction.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe transitive class $B_{\lambda }$ inherits extensionality and foundation. Definable subsets of its sets remain in it. If $x\in B_{\lambda }$, a functional image of $x$ has size at most $|x|<\lambda$; every member of that image is already hereditary, so the image belongs to $B_{\lambda }$. This verifies replacement, even though its values can have unbounded ranks. Also $|\mathcal{P}(x)|=2^{|x|}<\lambda$ by the strong limit cardinal property, and each subset of $x$ is locally small. This verifies the Axiom of power set. Pairing and infinity follow similarly. Butsince $|V_{\omega +n}|={\beth }_n<\lambda$ while $|V_{\omega +\omega }|=\lambda$. This is failure of sumset without failure of replacement or power set.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$. This is a transitive class. A countable union of countable transitive closures is countable, so it is closed under pairs, unions and functional images of its countable domains; these facts verify pairing, union and replacement. Separation, foundation and infinity also hold. Every subset of $\omega$ is hereditarily countable, but the full power set $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem and cannot be a member of $H_{{\omega }_1}$. Since every candidate internal power set would have to contain all those subsets, the power-set axiom fails.

For replacement, take the rank-initial transitive set $V_{\omega +\omega }$. A limit rank contains the empty set and is closed under pairs, unions, subsets and power sets; it contains $\omega$, and foundation and extensionality are inherited. Fix the parameter $V_{\omega }$. The definable mapis internally described by a finite sequence of power-set iterations. Each finite sequence belongs to $V_{\omega +\omega }$, so the definition is genuinely functional there. Its range has rank $\omega +\omega$ and is not in the structure. Thus this instance of replacement fails.

For extensionality, use the non-extensional membership model with one atom. Start with an atom $a$ having no members and build the ordinary cumulative coded sets over it, including a separate empty set. Interpret membership by the contents of a set code and give $a$ no members. The two different objects $a,\varnothing$ have identical empty extensions. Foundation holds by the code ranks; pure finite ordinals give infinity; pairs, unions, definable subsets and functional ranges have their usual set codes. For unrestricted power set, include the atom as well as all ordinary subset codes: the atom satisfies $a\subseteq x$ vacuously for every $x$. This detail is necessary because the formulas here are the unmodified ZF formulas, without a set predicate. The collection still has a set code, so the Axiom of power set holds. All axioms except extensionality are satisfied.

Finally, $V_{\omega }$, the hereditarily finite sets, satisfies every axiom except infinity. Pairs, unions, power sets and subsets of finite sets are finite, and every functional image of a finite domain is finite, so the full replacement schema holds. An inductive set would contain every finite von Neumann ordinal and would be infinite, whereas every member of $V_{\omega }$ is finite. Hence infinity fails.

The axiom of determinacy, $\mathsf{AD}$, says that every infinite game of perfect information in which two players alternately choose natural numbers and Player I wins according to a specified payoff $A\subseteq {\omega }^{\omega }$ is a determined infinite game. A strategy specifies a move at every finite position where its player moves; it is winning if every compatible infinite play is won by that player.

Finite games are determined by backward induction. For infinite games, open determinacy has a direct proof. Let $T$ consist of the finite positions whose extension cylinder sets lie in the open payoff $A$. Build the winning-position attractor in an infinite game by transfinite recursion: start with $T$, add an I-position if some successor has already entered, add a II-position if every successor has already entered, and take unions at limit stages. The process stabilizes because there are only countably many finite positions.

At a position in the attractor but outside $T$, I can choose a successor with strictly smaller entry rank, and every move of II has smaller entry rank. There is no infinite descending sequence of ordinals, so I forces entry into $T$ and wins. Outside the attractor, every I-move stays outside it, while II can choose a successor outside it; that strategy avoids $T$ forever. Since $A$ is open, a play belongs to $A$ exactly when some prefix belongs to $T$. Thus II wins from outside the attractor. This proves determination for open payoffs; swapping the players proves it for closed payoffs too. The stronger Borel determinacy theorem gives determination for every Borel set payoff, whereas $\mathsf{AD}$ asserts this for arbitrary payoffs.

To contradict $\mathsf{AD}$ from choice, enumerate both players' strategies as $⟨{\sigma }_{\alpha }:\alpha <\mathfrak{c}⟩$ and $⟨{\tau }_{\alpha }:\alpha <\mathfrak{c}⟩$, where $\mathfrak{c}=2^{{\aleph }_0}$. There are $\mathfrak{c}$ strategies because the set of finite positions is countable; there are also $\mathfrak{c}$ plays following any fixed strategy because the other player's moves are arbitrary. At stage $\alpha$ of the choice diagonalization of an undetermined game, choose a fresh play $x_{\alpha }$ following ${\sigma }_{\alpha }$ and then a different fresh play $y_{\alpha }$ following ${\tau }_{\alpha }$, avoiding all earlier reservations. This is possible because fewer than $\mathfrak{c}$ plays have been reserved at every $\alpha <\mathfrak{c}$; regularity of $\mathfrak{c}$ is not required.

Set $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. Every ${\sigma }_{\alpha }$ loses on $x_{\alpha }\notin A$, and every ${\tau }_{\alpha }$ loses on $y_{\alpha }\in A$. Thus neither player has a winning strategy, and AD and AC are inconsistent together.

The assertions are relative independence results. We construct countermodels in a background model of ZFC; if ZF is consistent, its constructible universe gives a model of ZFC as well. The original model satisfies foundation and choice, supplying the positive sides.

For failure of foundation, use a Rieger-Bernays permutation model. Let $\pi$ interchange the old $\varnothing$ and $\{\varnothing \}$ and fix every other object, and put $xEy$ iff $x\in \pi (y)$. The new extension of $y$ is the old set $\pi (y)$, so the representative of any old extension $b$ is ${\pi }^{-1}(b)$. Bijectivity gives extensionality. Translate formulas recursively by this definition of $E$. Old separation gives each new definable subset, and old replacement gives each new functional range; apply ${\pi }^{-1}$ to the resulting extension to obtain its new representative.

Explicitly, a new pair is represented by ${\pi }^{-1}(\{x,y\})$; the new union of $a$ is represented by ${\pi }^{-1}({\bigcup }_{x\in \pi (a)}\pi (x))$; and the new power set of $a$ is represented byStarting from the new empty set, iterate the new successor and collect these iterates by old replacement, obtaining an inductive set. The old axiom of choice selects a member from each nonempty extension and thereby gives new choice functions. However the old object $q=\varnothing$ now satisfies $qEq$ and has exactly itself as its member: it is a Quine atom. Its new singleton has no $E$-minimal member, so foundation fails.