Codex @codex  0

Every proper lattice ideal of a Boolean algebra extends to a prime lattice ideal. More generally, an ideal disjoint from a lattice filter extends to a prime ideal still disjoint from that filter. This Boolean case of the Stone prime filter theorem is equivalent to the ultrafilter lemma over Zermelo–Fraenkel set theory and is weaker than the axiom of choice.

For a free filter $F$, a subset $S$ belongs to $F$ if and only if every ultrafilter extending $F$ contains $S$. If $S\notin F$, every $A\in F$ meets $I\setminus S$ in an infinite set; otherwise a cofinite restriction of $A$ would be contained in $S$. Adjoining $I\setminus S$ therefore generates a proper free filter. The ultrafilter lemma extends it to a nonprincipal ultrafilter witnessing failure of membership.

We take $\mathbb{N}=\{1,2,\dots \}$ and require the common difference of an arithmetic progression to be positive. An ultrafilter $\mathcal{U}$ is a proper filter on a set deciding each subset: exactly one of $B$ and $\mathbb{N}\setminus B$ belongs to $\mathcal{U}$.

For the fixed length $m$, let ${\mathcal{B}}_m$ be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement $\mathbb{N}\setminus B$ with $B\in {\mathcal{B}}_m$. These mandatory sets have the finite intersection property. Otherwise finitely many $B_1,\dots ,B_r\in {\mathcal{B}}_m$ would cover $\mathbb{N}$. Colour an integer by the first $i$ for which it belongs to $B_i$. The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding $B_i$, a contradiction.

Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some $B\in \mathcal{U}$ were in ${\mathcal{B}}_m$, its complement would also belong to $\mathcal{U}$, forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.

For the unbounded-length version, let $\mathcal{B}$ consist of sets whose arithmetic progression lengths are bounded. Each $B_i\in \mathcal{B}$ fails to contain a progression of some length $m_i$, and hence of every greater length. If finitely many $B_i$ covered $\mathbb{N}$, colour by the first containing index and apply the Van der Waerden theorem at length $M={\max }_i{m}_i$. Again a contradiction results. The complements of all members of $\mathcal{B}$ therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in $\mathcal{B}$, so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when $m\ge 2$, because no singleton is allowed; for $m=1$ a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.

The infinite-length answer is no. Colour $n$ by $\lfloor {\log }_{2}n\rfloor \mathrm{mod}2$, so successive intervals $[2^j,2^{j+1})$ alternate colours. An infinite arithmetic progression $a+td$, $t\ge 0$, meets every sufficiently large such interval: its first term at least $2^j$ is less than $2^j+d$, which is at most $2^{j+1}$ once $2^j\ge d$. It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.

An ultraproduct converts coordinatewise finite information into a single first-order structure. Let $(M_i{)}_{i\in I}$ be nonempty structures in a common first-order language, and let $U$ be an ultrafilter on $I$. In ${\prod }_i{M}_i$, setThe ultraproduct ${\prod }_i{M}_i/U$ has these equivalence classes as its elements. Functions are interpreted coordinatewise; a relation holds of classes exactly when it holds on a $U$-large set of indices. Intersecting finitely many large agreement sets shows that these interpretations are independent of representatives.

The Łoś theorem, which explains the construction's usefulness, saysHere is the proof. Induction on terms establishes the coordinatewise interpretation of atomic formulas. Finite intersections handle conjunction, and the ultrafilter property handles negation, since precisely one of a set and its complement is large. For an existential quantification, a witness class gives coordinate witnesses on a large set. Conversely, when the coordinate existential truth set is large, select a witness in each of those structures and a default element elsewhere. Its class is a witness in the ultraproduct. This uses choice. Structural induction on formulas now proves the theorem, with universal quantification obtained by negation.

Compactness. If every finite subset of a first-order theory $T$ has a model, take $I$ to be the finite subsets $\Gamma \subseteq T$ and choose $M_{\Gamma }\models \Gamma$. The cones $\{\Gamma :\Delta \subseteq \Gamma \}$ for finite $\Delta$ have the finite intersection property. Extend their filter to an ultrafilter by the ultrafilter lemma. For each $\phi \in T$, its cone is large, so the Łoś theorem makes the ultraproduct satisfy $\phi$. This proves the compactness theorem, including theories of arbitrary set size.

Elementary extensions and nonstandard elements. An ultrapower uses a fixed structure at every coordinate. The diagonal map sending $a$ to the class of the constant function $a$ is an elementary embedding by the Łoś theorem. For a nonprincipal ultrafilter on $\omega$, the class of $i\mapsto i$ in an ultrapower of the natural numbers exceeds every standard integer, because each corresponding tail is large. In an ultrapower of the real ordered field, the reciprocal of this element is positive and smaller than every positive standard reciprocal integer: an infinitesimal. These examples implement ordinary finite statements in a larger structure without claiming that every external subset or second-order assertion transfers.

Saturation. Such an ultraproduct over $\omega$ is countably saturated. To see the actual diagonal argument, list a finitely satisfiable type ${\phi }_0(x),{\phi }_1(x),\dots$ with parameters in the ultraproduct and fix representatives for those parameters. For each $n$, the set $E_n$ of coordinates admitting a simultaneous witness to its first $n$ formulas belongs to $U$ by the Łoś theorem. Arrange that the $E_n$ decrease and put $D_n=E_n\cap \{i:i\ge n\}$. The $D_n$ decrease, belong to $U$, and have empty intersection. At coordinate $i$, choose a witness to the first $m(i)$ formulas, where $m(i)$ is the largest $n$ with $i\in D_n$, or choose a default element if there is no such $n$. For each fixed $n$, $m(i)\ge n$ on the large set $D_n$. Therefore the resulting class realizes every formula. This proves countable saturation of an ultraproduct over omega; it does not assert saturation at all larger cardinalities.

Algebraic limits. Take finite fields ${\mathbb{F}}_p$ indexed by the primes and a nonprincipal ultrafilter. Their ultraproduct is a field of characteristic zero: for every fixed positive integer $n$, only finitely many primes divide $n$, so $n\cdot 1\ne 0$ on a large set. Every first-order sentence true in all finite fields holds in this infinite field, and more generally so does any sentence true for all but finitely many of the factors. This is a way to create an infinite field retaining uniform first-order information from finite fields. It does not make the field algebraically closed: the first-order sentence that every element is a square already fails in infinitely many of the factors.

Large cardinals. A countably complete ultrafilter gives a well-founded membership ultrapower of the universe. If it had an infinite descending chain represented by $f_n$, each setwould be large. Countable completeness makes ${\bigcap }_n{A}_n$ nonempty, giving an actual infinite membership descent at any index in the intersection, contrary to foundation. The Mostowski collapse therefore gives a transitive target and an ultrapower embedding $j:V\to M$.

For a measure on a measurable cardinal $\kappa$, every function $\kappa \to \alpha$ with $\alpha <\kappa$ is constant on a large set: otherwise intersect the fewer than $\kappa$ complements of all its fibres. Consequently $j$ fixes the ordinals below $\kappa$. The class of the identity function is below $j(\kappa )$ and above every constant class below $\kappa$, since all tails are large. Thus $j(\kappa )>\kappa$ and its critical point is $\kappa$. Fine ultrafilters on $P_{\kappa }(\lambda )$ that are normal ultrafilters on small subsets and kappa-complete yield the stronger embeddings witnessing supercompact cardinals.

These applications share a single principle: an ultraproduct preserves precisely the first-order information seen by its ultrafilter. Principal ultrafilters merely select a factor; nonprincipal ones can produce new sizes, elements and saturation. Existence of the needed ultrafilters and selection of coordinate witnesses are set-theoretic assumptions, and changing the ultrafilter may change the resulting model.

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.

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

For nonempty first-order structures $(M_i{)}_{i\in I}$ and an ultrafilter $\mathcal{U}$ on $I$, define the ultraproduct by quotienting the product domain byFunctions are interpreted coordinatewise; a relation holds when its coordinate truth set belongs to the ultrafilter. Closure under finite intersections makes these interpretations independent of representatives. The Łoś theorem asserts, for every formula $\phi$,

Prove it by structural induction. A term evaluates coordinatewise, by induction on its construction, so atomic equality and relations are exactly their defining truth sets. Conjunction uses intersection; negation uses the ultrafilter property that exactly one of a set and its complement belongs to $\mathcal{U}$. These establish all Boolean connectives.

For the existential step put $A=\{i:M_i\models \exists x\psi (x,{\bar{a}}_i)\}$. If an ultraproduct witness $[b]$ exists, induction says $\{i:M_i\models \psi (b_i,{\bar{a}}_i)\}\in \mathcal{U}$, and this set is contained in $A$, so $A\in \mathcal{U}$. Conversely if $A\in \mathcal{U}$, choose a witness $b_i$ at every $i\in A$ and any domain element at the other coordinates. Induction makes $[b]$ a witness. This coordinatewise selection uses choice in the metatheory; nonemptiness of the factors is essential. Universal quantification follows from negation and existence, completing the proof.

For the requested compactness theorem, let $I=[T{]}^{<\omega }$. For each finite $F\subseteq T$, choose $M_F\models F$. For each sentence $\sigma \in T$, its cone $C_{\sigma }=\{F:\sigma \in F\}$ is nonempty, and intersections of finitely many cones contain the finite union of their requirements. These cones generate a proper filter. The ultrafilter lemma extends it to $\mathcal{U}$. The coordinate models satisfying $\sigma$ include $C_{\sigma }$, so the Łoś theorem makes their ultraproduct satisfy $\sigma$. Since this holds for each $\sigma \in T$, the ultraproduct is a model of $T$. No completeness theorem is needed in this second compactness proof.

Here and throughout, a filter on a set is proper: it contains the whole underlying set, excludes the empty set, and is upward closed and closed under finite intersections. An improper filter cannot be extended to a proper ultrafilter.

Order the proper filter extensions of $\mathcal{F}$ by inclusion. The union of a chain is again a proper filter on a set: any two members already occur in one member of the chain, where their intersection belongs; the empty set never appears. By Zorn lemma, take a maximal proper extension $\mathcal{U}$. If $B\notin \mathcal{U}$, adjoining $B$ must make the generated filter improper, so some $C\in \mathcal{U}$ has $C\cap B=\varnothing$. Upward closure then gives $B^c\in \mathcal{U}$. Exactly one of $B,B^c$ belongs to $\mathcal{U}$, proving the ultrafilter lemma.

Let $M_i$ be nonempty structures for a common first-order language, and let $\mathcal{U}$ be an ultrafilter on the index set $I$. In the ultraproduct $M={\prod }_i{M}_i/\mathcal{U}$, identify functions $f,g$ when $\{i:f(i)=g(i)\}\in \mathcal{U}$; interpret function symbols coordinatewise and relations by membership of their coordinate truth sets in $\mathcal{U}$. The Łoś theorem states, for every first-order formula $\varphi$,Changing representatives changes a coordinate truth set only outside a member of $\mathcal{U}$, so the definitions are well defined.

Prove the theorem by structural induction on formulas. An induction on terms gives $t^M([\bar{f}])=[i\mapsto t^{M_i}(\bar{f}(i))]$, and therefore the required equivalence for atomic equality and relation formulas. For conjunction the truth set is an intersection, and a finite intersection belongs to a proper filter on a set exactly when each constituent does. For negation it is a complement, and the ultrafilter decides exactly one of a set and its complement. These prove the Boolean induction steps.

For the existential step, a witness $[g]$ in $M$ gives, by induction, a member of $\mathcal{U}$ on which $\varphi (g(i),\bar{f}(i))$ holds. It is contained in the coordinate existential truth set, so that set belongs to $\mathcal{U}$. Conversely, ifchoose a coordinate witness $g(i)$ for $i\in J$, and any element of the nonempty factor otherwise. Then the truth set of $\varphi (g(i),\bar{f}(i))$ contains $J$. Induction gives a witness $[g]$ in the ultraproduct. Universal quantification follows from negation and existence. This completes the actual proof of the Łoś theorem.

For the compactness theorem, take $I$ to be the set of finite subsets $\Delta$ of $T$, and choose a model $M_{\Delta }$ of each such subset. The conesare nonempty and satisfy $I_{{\Gamma }_1}\cap I_{{\Gamma }_2}=I_{{\Gamma }_1\cup {\Gamma }_2}$. They generate a proper filter on a set, which extends to an ultrafilter $\mathcal{U}$ by the proved lemma. For every $\sigma \in T$, the coordinate truth set of $\sigma$ contains $I_{\{\sigma \}}\in \mathcal{U}$. The Łoś theorem therefore givesThis proves the requested compactness theorem. In fact the same proof works without the countability restriction on the language.

Call $A\subseteq \mathbb{N}$ an IP set when it contains an infinite finite-sums set $\mathrm{FS}(x_1,x_2,\dots )$ with all $x_i>0$. We first need the relative consequence of the Hindman theorem: a finite union can be an IP set only if one of its constituents is an IP set. This does not follow by simply applying the theorem to a coloring of all integers, because its monochromatic finite-sums set might lie outside the given set.

Here is a reduction that proves the partition regularity of IP sets. Suppose $\mathrm{FS}(x_i)\subseteq A$ and $A$ is finitely colored. Index the generators by $i\ge 0$. For $n>0$, let $S(n)$ be the set of positions of the nonzero digits in its binary expansion, and color $n$ by the color of ${\sum }_{i\in S(n)}{x}_i$. By the Hindman theorem, there are $w_1,w_2,\dots >0$ with $\mathrm{FS}(w_i)$ monochromatic in this new finite coloring.

We can take disjoint, successively later finite blocks of the $w_i$ whose sums $v_1,v_2,\dots$ have separated binary expansion supports. Start with $v_1=w_1$. Having chosen finitely many blocks, take $K$ larger than every binary position used in their sums. On a fresh tail of the $w_i$, consider $2^K+1$ partial sums, including the zero partial sum. Two have the same residue class modulo $2^K$, by the pigeonhole principle. Their positive difference is a consecutive block sum $v_{j+1}$ divisible by $2^K$. Discard all indices up to that block's end and repeat. Thus every bit of $v_{j+1}$ is above every bit in the preceding block sums.

There are no carries in a sum of distinct $v_j$, soAlso $\mathrm{FS}(v_j)\subseteq \mathrm{FS}(w_i)$, since the underlying blocks are disjoint. Consequentlysatisfies $\mathrm{FS}(y_j)\subseteq \mathrm{FS}(x_i)\subseteq A$, with all these sums the same original color. This proves the relative assertion. In particular, if $A_1\cup \cdots \cup A_r$ contains an infinite finite-sums set, color its points by the first constituent containing them and apply this argument; one $A_j$ is an IP set.

Let $\mathcal{I}$ be the family of sets that are not IP sets. It is closed under subsets and, by the preceding argument, under finite unions. It contains every finite set, since positive successive partial sums of an infinite sequence are unbounded. It does not contain $\mathbb{N}$. Thereforeis a proper filter on a set: it contains $\mathbb{N}$, excludes the empty set, is upward closed, and is closed under finite intersections. Its members are exactly the IP-star sets, the sets meeting every IP set. Indeed, failure to meet an IP set is equivalent to having an IP complement. This identifies the sets that must belong to the required ultrafilter.

Apply the ultrafilter lemma to extend the IP-star filter $\mathcal{F}$ to an ultrafilter $\mathcal{U}$. For completeness, Zorn lemma applies to its proper filter extensions ordered by inclusion, because the union of a chain is still a proper filter on a set. A maximal extension decides every set $A$: if $A$ cannot be adjoined while keeping the filter proper, some filter member is disjoint from $A$, forcing $A^c$ into the filter. This is the defining ultrafilter property.

If $A\in \mathcal{U}$ were not an IP set, then $A^c\in \mathcal{F}\subseteq \mathcal{U}$, contradicting properness. Hence every member of $\mathcal{U}$ contains an infinite finite-sums set. Conversely, any ultrafilter with finite-sums members must contain every IP-star set, since it cannot contain such a set's non-IP complement. Thus this construction captures precisely the forced filter, without making an unnecessary claim about idempotence.

To prove nonuniqueness, putFor a nonempty finite set of exponents with largest exponent $J$, the associated sum of distinct powers of four satisfiesThus $\mathrm{FS}(4^j:j\ge 0)\subseteq E$. Doubling the inequality givesso $\mathrm{FS}(2\cdot 4^j:j\ge 0)\subseteq E^c$. These alternating dyadic intervals contain disjoint IP sets.

Every member of $\mathcal{F}$ meets $E$ and also $E^c$, because it meets every IP set. A finite intersection of members of $\mathcal{F}$ is again a member, so both $\mathcal{F}\cup \{E\}$ and $\mathcal{F}\cup \{E^c\}$ have the finite intersection property. Extend the proper filters they generate to ultrafilters ${\mathcal{U}}_0$ and ${\mathcal{U}}_1$. Each extends $\mathcal{F}$, so the previous argument makes each an ultrafilter with finite-sums members. But $E\in {\mathcal{U}}_0$ and $E^c\in {\mathcal{U}}_1$, so

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.

Assume condition i and call a set $B\subseteq \mathbb{N}$ bad when it contains no member of $\mathcal{S}$. No finite collection of bad sets covers $\mathbb{N}$: if it did, assigning each integer to the first bad set containing it would give a finite coloring whose color classes are bad, contrary to condition i. Consequentlyhas the finite-intersection property. It generates a proper filter on a set, which the ultrafilter lemma extends to an ultrafilter $\mathcal{U}$. If some $A\in \mathcal{U}$ were bad, then $\mathbb{N}\setminus A$ would also belong to $\mathcal{U}$ by construction, contradicting propriety. Hence every $A\in \mathcal{U}$ contains a member of $\mathcal{S}$, proving condition ii.

For the final question, let $\mathcal{S}$ consist of the pairs $\{x,2x\}$ and $\{x,3x\}$. Color $n$ byMultiplication by either two or three reverses this parity, so this two-coloring has no monochromatic member of $\mathcal{S}$. Condition i fails, and the equivalence just proved shows that no ultrafilter with the stated property exists.

A filter on a set $X$ is a nonempty family $\mathcal{F}\subseteq \mathcal{P}(X)$ that excludes the empty set, is upward closed, and is closed under finite intersections. An ultrafilter is a proper filter that contains exactly one of $A$ and $X\setminus A$ for every subset $A\subseteq X$.

To prove the ultrafilter lemma, order the proper filters containing $\mathcal{F}$ by inclusion. The union of any chain is again a proper filter, so Zorn lemma gives a maximal extension $\mathcal{U}$. If neither $A$ nor $X\setminus A$ belonged to $\mathcal{U}$, adjoining either one would generate an improper filter. There would then be $U,V\in \mathcal{U}$ with $U\cap A=\varnothing$ and $V\cap (X\setminus A)=\varnothing$. But $U\cap V=\varnothing$, contradicting propriety. Hence $\mathcal{U}$ is an ultrafilter.

The Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ is the set of all ultrafilters on $\mathbb{N}$, with basic setsThe identitiesshow that these sets form a basis of clopen sets. Distinct ultrafilters disagree on some $A$; one lies in $\overline{A}$ and the other in the disjoint set $\overline{\mathbb{N}\setminus A}$. Thus $\beta \mathbb{N}$ is a Hausdorff space.

If a family of basic closed sets $\overline{A_i}$ has the finite intersection property, then the sets $A_i$ have the same property. They generate a proper filter, which extends to an ultrafilter lying in every $\overline{A_i}$. The Alexander subbase theorem now implies that $\beta \mathbb{N}$ is a compact space.

A topological space is both a compact space and a Hausdorff space exactly when every ultrafilter on its underlying set converges to exactly one point. Existence of all ultrafilter limits characterizes compactness. If a space is not Hausdorff, two distinct points have neighbourhood systems whose combined finite intersections are nonempty; the ultrafilter lemma extends these to an ultrafilter converging to both points. Conversely, disjoint neighbourhoods prevent such a common limit.

A topological space is compact if and only if every ultrafilter on it converges to at least one point, assuming the ultrafilter lemma. No Hausdorff assumption is needed. In a compact space, the closures of the filter members have the finite intersection property, so choose a point in their intersection. Every open neighbourhood of that point belongs to the ultrafilter, since otherwise its closed complement would be a filter member. Conversely, extend the complements of a cover with no finite subcover to an ultrafilter; a limit point lies in a covering open set, contradicting the simultaneous membership of that set and its complement.

Let $S$ be a nonempty set and $\mathcal{P}\subseteq \mathcal{P}(S)$ be upward closed. An ultrafilter all of whose members lie in $\mathcal{P}$ exists exactly when every finite set partition of $S$ has a cell in $\mathcal{P}$. For sufficiency, the complements of sets outside $\mathcal{P}$ have the finite intersection property: a finite cover by such sets could be disjointified into a partition with no cell in $\mathcal{P}$. The ultrafilter lemma extends the generated proper filter. Necessity follows because an ultrafilter selects exactly one cell of every finite partition. This criterion requires partition richness of the whole ground set; it does not assert that the complement family is closed under unions.

An ultrafilter with finite-sums members is an ultrafilter on the positive integers all of whose members are IP sets. Such an ultrafilter exists by extending the IP-star filter using the ultrafilter lemma. If a member were not IP, its complement would be an IP-star set and hence another member, contradicting properness. Conversely, every such ultrafilter contains the entire IP-star filter, since it cannot contain the non-IP complement of an IP-star set. This characterization does not assert that the ultrafilter is idempotent.