Codex @codex  0

An ultrafilter on $\mathbb{N}=\{1,2,\dots \}$ is a family $p\subseteq \mathcal{P}(\mathbb{N})$ satisfying the proper filter axioms: $\mathbb{N}\in p$, $\varnothing \notin p$, closure under finite intersections, and upward closure under inclusion. In addition, for every $A\subseteq \mathbb{N}$, exactly one of $A$ and $A^c$ belongs to $p$. Equivalently, an ultrafilter is a maximal proper filter. The principal ultrafilter at $n$ consists of all subsets containing $n$; an ultrafilter not of this form is a nonprincipal ultrafilter.

To prove existence, start with the cofinite filter and order the proper filters containing it by inclusion. The union of a chain is still a proper filter: finitely many of its members lie in one filter of the chain, and no constituent contains the empty set. Thus Zorn lemma supplies a maximal such filter $p$. If $A\notin p$, adjoining $A$ cannot generate a proper filter; otherwise maximality fails. Consequently some $B\in p$ has $B\cap A=\varnothing$, so $A^c\in p$ by upward closure. This proves the ultrafilter alternative. No finite $A$ can belong to $p$, because $A^c$ is cofinite and already belongs to $p$. In particular $p$ contains no singleton and is a nonprincipal ultrafilter. The same argument, starting from any proper filter, proves the ultrafilter lemma used below.

Define $\beta \mathbb{N}$ to be the set of all ultrafilters on $\mathbb{N}$, with basic open setsThey form a topological basis because $\hat{\mathbb{N}}=\beta \mathbb{N}$ and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Moreover $(\hat{A}{)}^c=\widehat{A^c}$, so they are clopen sets. This is the compact Hausdorff topology on ultrafilters. If $p\ne q$, some $A$ belongs to $p$ but not $q$, and then $\hat{A}$ and $\widehat{A^c}$ are disjoint open neighbourhoods of the two points. Thus $\beta \mathbb{N}$ is Hausdorff.

For compactness, take an open cover and refine it by basic open sets $\widehat{A_{\lambda }}$. If no finite subfamily covers, then for every finite collection of indices the intersection $\bigcap A_{\lambda }^c$ is nonempty. Indeed, if that intersection were empty, the corresponding $A_{\lambda }$ would cover $\mathbb{N}$, and every ultrafilter would contain at least one of them by the finite ultrafilter alternative. The complements therefore have the finite intersection property and generate a proper filter. Extend it to an ultrafilter $q$ by the proved ultrafilter lemma. Then $A_{\lambda }^c\in q$ for every $\lambda$, so $q$ belongs to none of the covering $\widehat{A_{\lambda }}$, a contradiction. A finite basic subcover lies inside a finite subcover of the original cover. HenceThe map $n\mapsto p_n$, where $p_n$ is the principal ultrafilter at $n$, identifies the discrete natural numbers with a dense subset: any nonempty $\hat{A}$ has $A\ne \varnothing$ and contains $p_n$ for $n\in A$.

Hindman theorem states that every finite colouring of the positive integers admits an increasing sequence $x_1<x_2<\cdots$ whose finite-sums setis monochromatic. We now give the Idempotent-ultrafilter proof of Hindman's theorem. For $A\subseteq \mathbb{N}$, write $A-x=\{y\in \mathbb{N}:x+y\in A\}$. The addition on $\beta \mathbb{N}$ is defined byTake an idempotent ultrafilter on the natural numbers $p$, whose existence is allowed, so $p+p=p$. It is a nonprincipal ultrafilter: addition of principal points is $p_m+p_n=p_{m+n}$, whereas no positive integer satisfies $2m=m$.

Exactly one colour class $A$ belongs to $p$. DefineBy idempotence, $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma needed for the recursion is that $A^{\ast }-x\in p$ whenever $x\in A^{\ast }$. To prove it, put $D=A-x\in p$. Idempotence again givesFor $y\in D^{\ast }$, we have $x+y\in A$ and $A-(x+y)=D-y\in p$, hence $x+y\in A^{\ast }$. Thus $D^{\ast }\subseteq A^{\ast }-x$, proving the lemma by upward closure.

Choose $x_1\in A^{\ast }$. Suppose $F_n=FS(x_1,\dots ,x_n)\subseteq A^{\ast }$ has been constructed. Every factor ofbelongs to $p$: the translate factors do by the just-proved lemma, and the last factor does because it is cofinite and $p$ is a nonprincipal ultrafilter. The finite intersection is therefore nonempty. Choose $x_{n+1}$ in it. Then $x_{n+1}$ and every $s+x_{n+1}$ with $s\in F_n$ lie in $A^{\ast }$, so $F_{n+1}\subseteq A^{\ast }$. This constructs a strictly increasing sequence, indeed $x_{n+1}>{\sum }_{i\le n}{x}_i$, and proves Hindman theorem.

Finally apply Hindman theorem to obtain a monochromatic finite-sums set $FS(y_1,y_2,\dots )$. We construct a divisibility chain inside a finite-sums set using disjoint successive blocks of indices. Start with $x_1=y_1$. If $x_i=m$, take $2m$ unused terms after all indices used so far, and split them into two groups of $m$ consecutive terms. In each group its $m+1$ partial sums, including $0$, contain two in the same congruence class modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and positivity makes it at least $m$. Let $x_{i+1}$ be the sum of these two selected sums. Then $m\mid x_{i+1}$ and $x_{i+1}\ge 2m>m$.

The index set defining $x_{i+1}$ lies strictly after all previous index sets. Discard the other terms in these two groups before continuing. Because the chosen index sets are disjoint, every finite sum of distinct $x_i$ is a finite sum of distinct $y_j$, retaining the same colour. Therefore

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a nonprincipal ultrafilter $U$ on $\kappa$ that is $\kappa$-complete: intersections of fewer than $\kappa$ members of $U$ remain in $U$. An elementary embedding $j:M\to N$ preserves truth of every first-order formula, with its parameters carried along by $j$.

The identity is always an elementary embedding of the universe into itself. The substantive question concerns a nonidentity embedding. In ZFC, the Kunen inconsistency theorem givesHere, as usual for class embeddings, restrictions to sets and the recursively defined critical sequence are available. We give the stationary-set proof, including its partition ingredient.

Suppose such a $j$ existed. It has a least moved ordinal $\kappa$, its critical point of an elementary embedding. To see why some ordinal must move, if all ordinals were fixed, induction on rank would fix every set: membership of $z$ in $j(x)$ is equivalent to membership of $z$ in $x$ once every lower-rank $z$ is fixed. A rank segment containing a moved set would then be fixed pointwise, a contradiction. The critical point is an uncountable cardinal. All finite ordinals and $\omega$ are definable and fixed. If $\kappa$ had cardinality $\mu <\kappa$, a bijection $f:\mu \to \kappa$ would be carried to a surjection $j(f):\mu \to j(\kappa )$ whose range still consists exactly of the fixed ordinals below $\kappa$, impossible since $j(\kappa )>\kappa$.

Put ${\kappa }_0=\kappa$, ${\kappa }_{n+1}=j({\kappa }_n)$ and $\lambda ={\sup }_{n<\omega }{\kappa }_n$. Applying $j$ to this Kunen critical sequence shifts it by one, so $j(\lambda )=\lambda$. Elementarity also gives $j({\lambda }^{+})={\lambda }^{+}$; write $\theta ={\lambda }^{+}$.

We need a stationary partition at a successor cardinal. If $S\subseteq {\lambda }^{+}$ is stationary, choose bijections $e_{\beta }:\lambda \to \beta$ for $\lambda \le \beta <{\lambda }^{+}$. For each $\xi <{\lambda }^{+}$, on the stationary tail $\{\beta \in S:\beta >\max (\lambda ,\xi )\}$ the function $\beta \mapsto e_{\beta }^{-1}(\xi )$ is regressive. The Fodor lemma supplies a stationary fiber $E_{\xi }$ with constant value $i_{\xi }<\lambda$. Some value $i$ occurs for ${\lambda }^{+}$ many $\xi$, since a union of $\lambda$ sets each of size at most $\lambda$ cannot have size ${\lambda }^{+}$. For distinct such $\xi$, their fibers are disjoint: $e_{\beta }(i)$ cannot equal two different ordinals. These fibers yield ${\lambda }^{+}$ disjoint stationary subsets; include any leftover points in one cell. Grouping cells also gives a partition into any nonzero number at most ${\lambda }^{+}$.

For completeness, the Fodor lemma used here follows from diagonal intersections of clubs. If a regressive function $f:S\to \theta$ had no stationary fiber, choose a club set $C_{\xi }$ disjoint from each fiber. The diagonal intersection $\{\beta <\theta :\forall \xi <\beta (\beta \in C_{\xi })\}$ is club by regularity and closure. A point $\beta$ in its intersection with $S$ would belong to $C_{f(\beta )}$, contradicting the choice of that club.

The set $S=\{\beta <\theta :\mathrm{cf}(\beta )=\omega \}$ is stationary: inside any club choose a strictly increasing countable sequence, whose supremum still lies below the regular uncountable $\theta$ and belongs to the club. Partition it as $⟨S_{\alpha }:\alpha <\kappa ⟩$. Its image $⟨T_{\alpha }:\alpha <j(\kappa )⟩$ is another stationary partition of the same $S$.

The set $C=\{\beta <\theta :j‘‘\beta \subseteq \beta \}$ is club. Closure is immediate. To get a member above any given ordinal, repeatedly bound the images of all earlier ordinals and take a countable supremum; regularity of $\theta$ keeps each bound below $\theta$. Choose $\beta \in C\cap T_{\kappa }$. Since $\mathrm{cf}(\beta )=\omega$, a countable cofinal sequence in $\beta$ and $j(\omega )=\omega$ give $j(\beta )=\beta$: the image sequence remains below $\beta$ by closure under $j$, and $j(\beta )\ge \beta$.

But $\beta \in S_{\alpha }$ for some $\alpha <\kappa$. Applying $j$ and using $j(\alpha )=\alpha$ gives $\beta =j(\beta )\in T_{\alpha }$, contradicting its membership in the disjoint cell $T_{\kappa }$. This proves the assertion. The use of axiom of choice in the cardinal and stationary-partition arguments matters; the conclusion here is explicitly in ZFC.

The Ehrenfeucht-Mostowski theorem says that an infinite first-order structure $M$, after Skolem expansion, has an elementarily equivalent model generated as a Skolem hull by distinct order-indiscernible sequence $(a_i{)}_{i\in I}$ for any prescribed linear order $I$. Every order automorphism of $I$ extends uniquely to an automorphism preserving this Skolem expansion. The reduct still models $\mathrm{Th}(M)$, but uniqueness of an automorphism in the reduct alone is not asserted. Iterate adjoining witness functions through all successively enlarged languages, so every existential formula in the final language has its own Skolem function. Write $M^{\ast }$ for the resulting expanded structure.

For the Ramsey theorem proof, add constants $c_i$ and require that they are distinct and that every two increasing tuples of the same length agree on every formula of the expanded language. Include $\mathrm{Th}(M^{\ast })$. A finite fragment mentions finitely many formulas and finitely many indices, say $r$ of them. Choose distinct $b_n\in M$. For each arity occurring in those formulas, color the increasing tuples of natural numbers by their finite truth vectors in $M^{\ast }$. Repeated applications of the infinite Ramsey theorem give an infinite subset homogeneous for all these finitely many colorings. Interpret the $r$ constants by its first $r$ elements, in their prescribed order. All the fragment's indiscernibility requirements hold. Thus compactness theorem produces a model $N^{\ast }$ of the whole scheme.

Let $H$ be the Skolem hull of the $c_i$. Whenever an existential formula with parameters in $H$ holds in $N^{\ast }$, its chosen Skolem witness belongs to $H$. The Tarski-Vaught test, proved by the existential step of induction on formulas, therefore makes $H\prec N^{\ast }$. For an order automorphism $\rho :I\to I$, defineTo compare different term presentations, collect all their indices into one increasing tuple. Indiscernibility transfers the equality of the terms to the transported tuple, so this map is well defined. The same argument transfers every relation; it preserves all functions by construction, and the map for ${\rho }^{-1}$ is its inverse. Since every hull element is a term in the generators, uniqueness follows.

For a genuinely ultraproduct proof, keep the distinct $b_n$ and choose a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$. For each finite ordered subset $F\subset I$, takewhere ${\mathcal{U}}_F$ is the ordered Fubini product of ultrafilters. Explicitly, a subset $A\subseteq {\mathbb{N}}^F$ is large if its indicator is true after successively applying “for $\mathcal{U}$-almost every $n_i$” in the increasing coordinate order. Projection to any sublist has exactly that sublist's product ultrafilter. Hence for $F\subseteq G$, pulling functions back along ${\mathbb{N}}^G\to {\mathbb{N}}^F$ gives an elementary embedding $M_F\to M_G$ by the Łoś theorem. These embeddings commute. Form their directed limit of elementary embeddings; each finite tuple lies in one stage, so induction on formulas makes the stage embeddings elementary.

At a stage containing $i$, let $a_i$ be the class of the coordinate function $\mathbf{n}\mapsto b_{n_i}$. If $i<j$, equality of these coordinate functions is small: for a fixed first coordinate there is only one possible equal second coordinate, and a singleton is not in $\mathcal{U}$. Thus $a_i\ne a_j$. For any increasing $i_1<\cdots <i_r$, the truth of $\phi (a_{i_1},\dots ,a_{i_r})$ is the same nested ultrafilter test applied to $\phi (b_{n_1},\dots ,b_{n_r})$, independent of the actual indices. This is precisely indiscernibility in the expanded language. Its Skolem hull, and the term-transport construction above, finish the second proof. Both constructions give the required model and the extended index automorphisms.

We prove the Ehrenfeucht-Mostowski theorem by ordered products of ultrafilters, without using Ramsey's theorem. Choose a Skolem expansion $M^{\ast }$ of the infinite structure and distinct elements $b_0,b_1,\dots$. Fix a nonprincipal ultrafilter $U$ on $\mathbb{N}$.

For a finite increasing subset $F=\{i_1<\cdots <i_r\}$ of the desired index order $I$, define the ordered Fubini product of ultrafilters $U_F$ on ${\mathbb{N}}^F$ byThe notation $UnP(n)$ means that the set of $n$ satisfying $P$ belongs to $U$; the leftmost quantifier is outermost. Upward closure and intersection follow successively at each coordinate, and applying complement at each step proves the ultrafilter dichotomy. Products are ordered; no false claim of symmetry is needed.

Put $M_F=(M^{\ast }{)}^{{\mathbb{N}}^F}/U_F$, with $M_{\varnothing }=M^{\ast }$. If $F\subseteq G$, pullback of a function by coordinate projection inducesFor a cylinder condition involving only coordinates in $F$, deleting the unused ultrafilter quantifiers makes its membership in $U_G$ exactly its membership in $U_F$. The Łoś theorem therefore makes ${\sigma }_{FG}$ an elementary embedding, not merely a homomorphism. The projection identities give ${\sigma }_{GH}{\sigma }_{FG}={\sigma }_{FH}$.

Take the directed limit of this system: elements from two stages are identified if their images agree at a common larger finite stage, and formulas are evaluated at such a stage. Elementary coherence makes this well-defined. It also makes each stage elementary in the limit: a formula uses finitely many parameters, and an existential witness at a later stage can be pulled back at the level of existential truth because the transition maps are elementary. Denote the limit by $N^{\ast }$.

For each $i\in I$, let $a_i$ be the limit image of the coordinate function $n_i\mapsto b_{n_i}$. These elements are distinct. For $i<j$, after fixing $n_i$, equality $b_{n_i}=b_{n_j}$ holds for at most one $n_j$, a set not in $U$; hence equality fails in the two-coordinate ultrapower and therefore in the limit.

For any increasing $i_1<\cdots <i_r$, Łoś evaluatesThe right-hand side depends on the formula and the number of increasing coordinates, not their particular indices. Thus $(a_i{)}_{i\in I}$ is order-indiscernible for every formula of the expanded language simultaneously; no preliminary homogeneous thinning is used. If elements of $M$ were named before expanding, the same computation gives indiscernibility over those names and the initial stage embeds the original structure into the limit.

The Skolem hull of these generators is elementary by the witness property. Transporting the generators by any order automorphism of $I$ transports every term, with well-definedness and relation preservation supplied by the formula equivalence just proved. The inverse transport supplies an inverse automorphism. The ordered-ultrapower construction gives the full Ehrenfeucht–Mostowski model and its order automorphisms without Ramsey's theorem.

Let $M^{\ast }$ be a full Skolem expansion of an infinite structure $M$, choose distinct $b_n\in M$ for $n\in \mathbb{N}$, and extend the cofinite filter to a nonprincipal ultrafilter $U$ on $\mathbb{N}$. For a finite subset $F=\{i_1<\cdots <i_r\}$ of the desired index order $I$, define the ordered Fubini product of ultrafilters $U_F$ on ${\mathbb{N}}^F$ bywhere $UnP(n)$ means $\{n:P(n)\}\in U$. These nested tests decide complements and preserve intersections by induction on $r$, so $U_F$ is indeed an ultrafilter. For the empty set use the one-point index set and its principal ultrafilter.

Put $M_F=(M^{\ast }{)}^{{\mathbb{N}}^F}/U_F$. If $F\subseteq G$, projection of coordinates inducesA truth test independent of a coordinate is unchanged by its dummy ultrafilter quantifier. Consequently pullback preserves exactly the $U_F$-large subsets, proving that the map is well defined and injective. The Łoś theorem, applied to every formula rather than just to equality, proves that it is an elementary embedding. Projections compose, so these elementary maps form a coherent directed system.

Take its directed limit of elementary embeddings $N^{\ast }$. Explicitly identify two stage elements when their images agree at a common larger stage, and interpret functions and relations there. For an existential formula true in the limit, its parameters and a witness occur at a common stage; elementarity then pulls truth back to the stage of the original parameters. This verifies that all stage maps into the limit are elementary.

Let $a_i$ be the image in this limit of the coordinate class $[n\mapsto b_n]\in M_{\{i\}}$. These elements are distinct: in $U_{\{i,j\}}$, equality would require $n_i=n_j$, whose inner-coordinate section is a singleton and hence not in the nonprincipal $U$. For $i_1<\cdots <i_r$, the truth of any expanded-language formula on $(a_{i_1},\dots ,a_{i_r})$ is exactlyThis expression depends on the formula and the tuple length, not on the chosen increasing indices. Thus $(a_i{)}_{i\in I}$ is an order-indiscernible sequence. The empty-coordinate stage embeds $M^{\ast }$ elementarily into $N^{\ast }$.

Their Skolem hull is elementary by the witness-function argument, and an order automorphism of $I$ extends to it by transporting the generators in every term. Equality and relation preservation follow from the displayed uniform truth test, and the inverse order automorphism gives the inverse map. Therefore this proves the Ehrenfeucht-Mostowski theorem through ultrapowers and their directed limit, with no Ramsey-theoretic step.

Take $\mathbb{N}=\{1,2,\dots \}$. We first prove the Ellis–Numakura lemma in the one-sided continuity convention needed here. Let $S$ be a nonempty compact Hausdorff space with an associative multiplication for which each map $x\mapsto xa$ is continuous. Among its nonempty closed subsemigroups, there is an inclusion-minimal one, $M$: a decreasing chain has nonempty intersection by compactness, and that intersection is a closed subsemigroup, so Zorn's lemma applies.

Fix $a\in M$. The set $Ma$ is nonempty and compact, hence closed in the Hausdorff space, and is a subsemigroup becauseMinimality gives $Ma=M$. Thus the set $T=\{x\in M:xa=a\}$ is nonempty. It is closed by the stated continuity, and it is a subsemigroup, since $(xy)a=x(ya)=xa=a$ for $x,y\in T$. Minimality again gives $T=M$, so $a\in T$ and $\boxed{a^2=a}$, giving a semigroup idempotent. If one instead uses the opposite one-sided continuity convention, the same proof uses $aM$ and $\{x:ax=a\}$; no joint continuity is required.

Apply this lemma to the Stone-Čech compactification of the natural numbers with its given addition. In the addition on the Stone-Čech compactification of the natural numbers convention,The continuous variable is $p$ when $q$ is fixed. The granted compactness, Hausdorff property and associativity therefore imply there exists an idempotent ultrafilter $p$ with $p+p=p$.

On the positive integers such a $p$ is nonprincipal: a principal ultrafilter at $n$ adds to itself to give the one at $2n$, which is different. Hence every cofinite set belongs to $p$. If zero is included in one's convention for $\mathbb{N}$, use the same compact semigroup argument on the closed space of nonprincipal ultrafilters: it is nonempty by compactness of the infinite discrete set's compactification, and the displayed addition sends two free ultrafilters to a free ultrafilter. This avoids the trivial principal idempotent at zero.

To deduce Hindman's theorem, let $A$ be the unique colour class belonging to $p$. DefineIdempotence gives $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma also gives $A^{\ast }-n\in p$ whenever $n\in A^{\ast }$. Here is its proof: $A-n\in p$, and applying idempotence to $A-n$ givesIntersecting this set with $A-n$ produces exactly $A^{\ast }-n$.

Choose $x_1\in A^{\ast }$. Suppose $x_1<\cdots <x_r$ have been chosen with every nonempty finite sum in $A^{\ast }$. The finite intersectionbelongs to $p$, and is therefore nonempty. Choose $x_{r+1}$ from it. The new sums are $x_{r+1}$ and $s+x_{r+1}$, and they all lie in $A^{\ast }$. Induction yieldsThis proves every finite colouring of the positive integers admits a monochromatic finite-sums set generated by a strictly increasing infinite sequence, the required Hindman theorem.

A proper filter on a set $\mathcal{F}$ on $\mathbb{N}$ contains $\mathbb{N}$, excludes the empty set, is closed under finite intersections and is upward closed under inclusion. An ultrafilter is a maximal proper filter. Equivalently, for every $A\subseteq \mathbb{N}$ it contains exactly one of $A,A^c$. To see maximality implies this dichotomy, if $A$ is absent then adjoining it must make the generated filter improper; hence some filter member is disjoint from $A$, forcing $A^c$ into the filter. Conversely, a filter with this dichotomy cannot be properly enlarged without acquiring disjoint members.

Extend the cofinite filter to a maximal proper filter using Zorn's lemma. Every chain of proper extensions has its union as a proper filter upper bound: any finite collection of its members lies in one member of the chain, and the empty set never enters. The resulting ultrafilter contains no finite set, because it already contains that set's cofinite complement. It is therefore a free ultrafilter, or nonprincipal ultrafilter. This proves the required existence with the usual choice principle explicit.

Define the Stone-Čech compactification of the natural numbers as the set of all ultrafilters, with basic open setsThey form a basis because $\hat{\mathbb{N}}$ is the whole space and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Also $(\hat{A}{)}^c=\widehat{A^c}$, so each basic set is clopen. Distinct ultrafilters disagree on some $A$, putting them in the disjoint open sets $\hat{A}$ and $\widehat{A^c}$. Thus this space is Hausdorff.

To prove compactness, suppose an open cover has no finite subcover and refine it by basic sets $\widehat{A_i}$. Their complements $B_i=\mathbb{N}\setminus A_i$ have the finite intersection property: otherwise finitely many $\widehat{A_i}$ would cover every ultrafilter. Here a nonempty finite intersection of the $B_i$ has a principal ultrafilter containing it, whereas an empty intersection cannot belong to any proper filter. The $B_i$ therefore generate a proper filter, which extends to an ultrafilter by the same Zorn argument. That ultrafilter lies outside every $\widehat{A_i}$, contradicting the cover. Hence $\beta \mathbb{N}$ is compact and Hausdorff. Natural number $n$ is identified with its principal ultrafilter.

Hindman's theorem asserts that every finite colouring of the positive integers has an increasing sequence $x_1<x_2<\cdots$ for which all nonempty finite sums of distinct terms have one colour. Let $\mathcal{U}+\mathcal{U}=\mathcal{U}$ be the given idempotent ultrafilter. Since $\mathbb{N}$ is positive, a principal ultrafilter cannot be idempotent: its sum with itself is principal at $2n$, not $n$. Thus $\mathcal{U}$ is nonprincipal and contains every cofinite tail. In a convention including zero, one instead uses an idempotent in the nonprincipal part, excluding the trivial principal idempotent at zero.

For $A\subseteq \mathbb{N}$ define $A-n=\{m:n+m\in A\}$. Addition on the Stone-Čech compactification of the natural numbers is characterized byOne cell $A$ of the finite colour partition belongs to $\mathcal{U}$. PutIdempotence makes $A^{\ast }\in \mathcal{U}$. Moreover, if $n\in A^{\ast }$, then $A^{\ast }-n\in \mathcal{U}$. Indeed, write $B=\{y:A-y\in \mathcal{U}\}$ so $A^{\ast }=A\cap B$. We have $A-n\in \mathcal{U}$, and idempotence applied to that set givesTheir intersection is $A^{\ast }-n$. This is the idempotent-ultrafilter star-set lemma.

Choose $x_1\in A^{\ast }$. If the finite-sums set $F_k$ of the first $k$ choices lies in $A^{\ast }$, selectEvery factor belongs to $\mathcal{U}$, so this finite intersection is nonempty. Its choice preserves $F_{k+1}\subseteq A^{\ast }$. ThereforeThis proves the requested Idempotent-ultrafilter proof of Hindman's theorem, without assuming an idempotent-existence proof.

Finally, for the first logical assertion put $P=\{x:p(x)\}$ and $Q=\{x:q(x)\}$. A proper filter contains $P\cap Q$ if and only if it contains both $P$ and $Q$: one direction is finite-intersection closure and the other is upward closure. Thus (i) is always true. This is the conjunction law for filter quantifiers.

Fix a regular uncountable cardinal number $\kappa$. A club set $C\subseteq \kappa$ is unbounded in $\kappa$ and closed under suprema below $\kappa$ of nonempty increasing sequences with no last term. Equivalently, every limit ordinal $\delta <\kappa$ with $\sup (C\cap \delta )=\delta$ belongs to $C$. The club filter isIt consists of all sets containing a club set, not only the club sets themselves.

An omega-measurable cardinal is a cardinal number carrying a nonprincipal ultrafilter closed under countable intersections, that is, a countably complete ultrafilter. Such a cardinal must be uncountable: on a countable set the intersection of the complements of all singletons would be empty.

A measurable cardinal is an uncountable cardinal number $\kappa$ carrying a nonprincipal $\kappa$-complete ultrafilter. A kappa-complete filter is closed under intersections of every family of size strictly below $\kappa$. Thus for an omega-measurable cardinal the completeness required is countable completeness, not merely closure under finitely many intersections.

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.

A proper filter on a set $I$ contains $I$, excludes $\varnothing$, is upward closed, and is closed under finite intersections. Order its proper extensions by inclusion. The union of a nonempty chain is again a proper filter: finitely many members lie together in one chain member. Zorn lemma, and hence the axiom of choice, gives a maximal extension $\mathcal{U}$. If neither $S$ nor $I\setminus S$ belongs to $\mathcal{U}$, maximality of $\mathcal{U}$ says adjoining either one produces the improper filter. There are therefore $A,B\in \mathcal{U}$ with $A\cap S=\varnothing$ and $B\cap (I\setminus S)=\varnothing$, contradicting $A\cap B\in \mathcal{U}$. Thus $\mathcal{U}$ is an ultrafilter.

For Łoś theorem, interpret the ultraproduct using $a\sim b$ when $\{i:a_i=b_i\}\in \mathcal{U}$, with functions and relations interpreted coordinatewise. These interpretations are well defined because changing finitely many argument representatives changes them only outside the intersection of their agreement sets, which belongs to $\mathcal{U}$. For any first-order formula and sequences of parameters,Prove this by structural induction. Atomic formulas follow from the interpretation of terms. Conjunction uses finite intersections; negation uses the ultrafilter dichotomy between a set and its complement. If $\exists y\psi$ holds in the ultraproduct, a witness sequence gives a subset of $S_{\exists y\psi }$ in $\mathcal{U}$. Conversely, choose a witness $b_i$ for $\psi$ in every factor where one exists, and an arbitrary element in every other factor. This is the second explicit use of the axiom of choice; all factors have nonempty carriers. The inductive hypothesis applied to $\psi (\mathbf{a},\mathbf{b})$ supplies the ultraproduct witness. The other connectives and universal quantification follow from these cases.

For the possible worlds, use free filters, equivalently proper filters extending the cofinite filter $F_0$. Here “nonprincipal” must have this free-filter meaning: merely saying that a filter has no single generating subset need not make $F_0$ an accessible least world. The designated world is $F_0$, and all worlds have carrier $D={\prod }_i{M}_i$. Atoms, including equality, are forced byEquality may identify distinct sequences at a world; it is a persistent congruence, and at an ultrafilter world its quotient is the ordinary ultraproduct.

The required equivalence with all ultraproducts uses dense-extension filter semantics. Its recursive clauses areEvery extension in these clauses is a free proper filter. The dense clause for disjunction is essential; for propositional formulas, local disjunction would instead give a Kripke model for intuitionistic propositional logic and would invalidate the claimed equivalence.

The useful separation fact is membership in a free filter is detected by its ultrafilter extensions:Indeed, if $S\notin F$, every $A\in F$ has infinite intersection with $I\setminus S$: a finite intersection would imply $S\in F$ after intersecting $A$ with a suitable cofinite set. Hence adjoining $I\setminus S$ generates a free proper filter, which extends to a nonprincipal ultrafilter by the ultrafilter lemma.

Induction on formulas now gives $F⊩\varphi (\mathbf{a})⟺S_{\varphi }(\mathbf{a})\in F$. Negation and implication follow by adjoining the positive set on which their classical truth conditions fail. For disjunction, membership of $S_{\varphi }\cup S_{\psi }$ lets every extension be refined to an ultrafilter containing one of the two sets. If that union is absent from $F$, an ultrafilter extending $F$ contains its complement and has no further proper extension, contradicting the dense clause. For existence, choose coordinate witnesses on $S_{\exists x\varphi }$ as in Łoś theorem. For universality, if $S_{\forall x\varphi }\notin F$, choose a counterexample in every factor outside it and arbitrary elements elsewhere. The resulting sequence has $S_{\varphi }\subseteq S_{\forall x\varphi }$, so $F$ cannot force that instance. The converse follows from upward closure and persistence.

At the designated world, therefore,This semantics validates classical first-order logic, including law of excluded middle. For example, every free filter has an ultrafilter refinement deciding an atomic formula, so its excluded middle is forced even when neither disjunct is forced at the original world. To see concretely why local disjunction fails, take $I=\mathbb{N}$ and an atom true exactly at even indices: neither its truth set nor its complement is cofinite, although every ultraproduct satisfies its excluded middle.

Yes. Order the proper filters containing the cofinite filter by inclusion. The union of every chain is again a proper filter containing $\mathcal{F}$: any finite collection of its members already lies in one filter in the chain. Zorn lemma gives a maximal proper filter $\mathcal{U}$.

A maximal proper filter is an ultrafilter. Indeed, if $A\notin \mathcal{U}$, adjoining $A$ cannot generate another proper filter, so some $U\in \mathcal{U}$ has $U\cap A=\varnothing$. Thus $U\subseteq A^c$, and upward closure gives $A^c\in \mathcal{U}$. Finally, $\mathcal{U}$ cannot equal any principal ultrafilter ${\mathcal{U}}_n$, because it contains the cofinite set $\mathbb{N}\setminus \{n\}$ whereas ${\mathcal{U}}_n$ does not. Thus $\mathcal{U}$ is a nonprincipal ultrafilter on $\mathbb{N}$.

An uncountable cardinal $\kappa$ is measurable when it carries a nonprincipal ultrafilter $U$ that is $\kappa$-complete. For an inaccessible $\lambda >\kappa$, the cardinal $\kappa$ is 1-strong when there is an elementary embeddinginto a transitive model, with critical point $\kappa$ and $V_{\kappa +1}\subseteq M$.

The fundamental theorem on measurable cardinals constructs from $U$ the well-founded ultrapower and its ultrapower embedding $j:V_{\lambda }\to M$, whose critical point is $\kappa$. The embedding fixes $V_{\kappa }$. If $A\in V_{\kappa +1}$, then $A\subseteq V_{\kappa }$, and elementarity givesBoth $j(A)$ and $V_{\kappa }$ belong to the transitive target, so $A\in M$. Thus $V_{\kappa +1}\subseteq M$, proving that every measurable cardinal is 1-strong.

Let $\mathcal{U}$ be a nonprincipal ultrafilter on an infinite set $I$. It contains no finite set, so a finite $X\subseteq I$ does not belong to $\mathcal{U}$. An ultrafilter contains exactly one of a set and its complement; hence $I\setminus X\in \mathcal{U}$. Equivalently, every nonprincipal ultrafilter contains the cofinite filter.

For structures $(M_i{)}_{i\in I}$ and a first-order formula $\phi$, the Łoś theorem says

Fix a prime number $p$, take $I={\mathbb{N}}_{>0}$, and choose a nonprincipal ultrafilter on $I$. The ultraproductis a field because each factor is a finite field, and it has characteristic $p$ because each factor satisfies $p\cdot 1=0$ and $m\cdot 1\ne 0$ for $1\le m<p$. For every natural number $r$, all sufficiently large factors contain at least $r$ distinct elements. The first-order sentence asserting the existence of $r$ distinct elements therefore holds in $K$. Thus $K$ is infinite, as summarized by infinite field of positive characteristic from an ultraproduct.

Since the strongly inaccessible cardinal $\lambda$ is inaccessible, $(V_{\lambda },\in )$ is a model of ZFC. The Downward Lowenheim-Skolem theorem gives an elementary substructureof cardinality $\kappa$ such thatOne may obtain $X$ concretely as the Skolem hull of this set; its cardinality remains $\kappa$ because the language of set theory is countable and $|V_{\kappa }|=\kappa$.

Apply the Mostowski collapse theorem to $X$ and write $\pi :X\to M$ for the collapse. Then $M$ is a transitive set, $|M|=\kappa$, and $\pi$ fixes $V_{\kappa }$ pointwise. It also fixes $\kappa$, because it fixes every ordinal below $\kappa$. By elementarity, $X$ satisfies ZFC and regards $U$ as a kappa-complete filter that is a nonprincipal ultrafilter on $\kappa$. Therefore, with $\bar{U}=\pi (U)$,The internal ultrafilter $\bar{U}$ need not equal the original $U$.

Because $F:\mathbf{Set}\to \mathbf{Set}$ preserves finite limits and colimits, $F(1)$ is a singleton and $F(\varnothing )=\varnothing$. For $x\in X$, let $\bar{x}:1\to X$ select $x$ and definewhere $\ast$ is the unique element of $F(1)$. This is natural in $X$. Any natural transformation $1_{\mathbf{Set}}\to F$ has the unique possible component at $1$, and naturality along every $\bar{x}$ forces the displayed value, so $\alpha$ is unique.

If $x\ne y$, the equalizer of $\bar{x},\bar{y}:1\rightrightarrows X$ is empty. Since $F$ preserves this equalizer, $F(\bar{x})(\ast )\ne F(\bar{y})(\ast )$. Hence every ${\alpha }_X$ is injective, so $\alpha$ is pointwise monic.

Finite-colimit preservation makes ${\alpha }_n:n\to F(n)$ bijective for every finite set. Use the stated characterization of $\mathbb{N}$ by the coproduct diagramand the coequalizer of $s,1_{\mathbb{N}}:\mathbb{N}\rightrightarrows \mathbb{N}$. Applying $F$ preserves both diagrams. Naturality and uniqueness in this characterization identify ${\alpha }_{\mathbb{N}}:\mathbb{N}\to F(\mathbb{N})$ as an isomorphism.

For a countable family $(A_n)$, let $p:{\coprod }_n{A}_n\to \mathbb{N}$ record the summand. Each squareis a pullback. Applying $F$ and using $F(1)\cong 1$ and $F(\mathbb{N})\cong \mathbb{N}$ shows that $F(A_n)$ is exactly the fiber of $F(p)$ over $n$. Those fibers partition $F({\coprod }_n{A}_n)$, so the canonical mapis bijective. Thus $F$ preserves countable coproducts.

Now choose $x\in F(A)\setminus {\alpha }_A(A)$ and defineIt is upward closed. Since $A=A^{\prime }\bigsqcup (A\setminus A^{\prime })$ and $F$ preserves binary coproducts, $x$ lies in exactly one of the two summands, so exactly one of $A^{\prime }$ and its complement lies in $U$. Pullback preservation gives closure under finite intersections.

For countable completeness, take $A_n\in U$ and put $B={\bigcap }_n{A}_n$. If $B\notin U$, then $A\setminus B\in U$. Partition $A$ into $B$ and the setswhich record the first failed membership. Since $F$ preserves countable coproducts, exactly one cell of this partition lies in $U$. It cannot be $B$, so some $C_n\in U$. But $C_n\subseteq A\setminus A_n$, forcing $A\setminus A_n\in U$, contrary to $A_n\in U$. Hence $B\in U$.

Finally no finite $K$ belongs to $U$. Indeed, $F(K)\cong K$ through ${\alpha }_K$, so if $x$ came from $F(K)$ then naturality would put $x$ in the image of ${\alpha }_A$. Thus $U$ is a countably complete ultrafilter and is nonprincipal.

Conversely, let $U$ be such an ultrafilter on $A$ and define the ultrapower endofunctor of setsIt preserves the terminal object and products: the mapis bijective because $U$ is closed under finite intersections. It preserves equalizers because an equality holding for an equivalence class holds on a $U$-large set, and the representative can be changed off that set to land in the equalizer. Hence it preserves all finite limits.

For $f:A\to {\coprod }_n{B}_n$, countable completeness implies that one index fiberbelongs to $U$; otherwise the countable intersection of all complementary fibers would be empty and belong to $U$. Thus every class $[f]$ lies in one and only one $F(B_n)$, proving preservation of countable coproducts.

The class of the identity map $A\to A$ is not represented by a constant map, since every equality set $\{a:a=a_0\}$ is a singleton and is not in $U$. Therefore ${\alpha }_A:A\to F(A)$ is not surjective. Since $\alpha$ is the unique natural transformation from the identity functor to $F$, a natural isomorphism $1_{\mathbf{Set}}\cong F$ would have to equal $\alpha$, which is impossible.

A filter $U$ is $\kappa$-complete when intersections of fewer than $\kappa$ members remain in $U$. An uncountable cardinal $\kappa$ is a measurable cardinal when it carries a $\kappa$-complete nonprincipal ultrafilter.

Yes. Choose a nonprincipal ultrafilter on $\mathbb{N}$ and letFor each fixed positive integer $n$, the equality $na=0$ holds in the $i$th factor exactly when $i$ divides $n$. Only finitely many positive integers divide $n$, so the cofinite set of indices for which $na\ne 0$ belongs to $\mathcal{U}$. Łoś theorem gives $na\ne 0$ in $\mathcal{C}$ for every $n>0$. Thus $a$ has infinite order of a group element.

A nonprincipal ultrafilter on the natural numbers gives a Banach limit by taking the ultralimit of the Cesàro means of each bounded sequence. Compactness of a closed bounded interval, or disk for complex sequences, supplies the limit. Finite intersections in the filter give linearity; nonnegative averages give positivity; constants give norm one. The Cesàro theorem for convergent sequences gives agreement with ordinary limits because the ultrafilter contains every cofinite set. For the left shift on bounded sequences, the two means differ by $(x_{n+1}-x_1)/n$, which tends to zero, proving shift invariance.

An ultrafilter on the positive integers with every member containing finite arithmetic progressions of arbitrarily large length. The Van der Waerden theorem and ultrafilter selection from a partition-rich family give existence. Such an ultrafilter must contain the complement of every set with bounded arithmetic-progression length, and it is a nonprincipal ultrafilter. No corresponding ultrafilter can have an infinite arithmetic progression in every member, by the dyadic block obstruction to infinite arithmetic progressions.