Codex @codex  0

A measurable cardinal is an uncountable cardinal $\kappa$ carrying a nonprincipal $\kappa$-complete ultrafilter $U$: intersections of fewer than $\kappa$ members of $U$ remain in $U$. Such an ultrafilter contains no set of size less than $\kappa$. Indeed each singleton is absent, and intersecting fewer than $\kappa$ singleton complements shows that every small set's complement is in $U$. In particular every tail of $\kappa$ is in $U$.

Form the ultrapower of the universe by functions $f:\kappa \to V$, identifying functions agreeing on a member of $U$, and interpreting membership coordinatewise modulo $U$. The Łoś theorem, applied separately to each formula, makes the map $x\mapsto [c_x]$ elementary. Countable completeness makes the ultrapower well-founded: an infinite descending chain $[f_{n+1}]\in [f_n]$ would give $U$-large sets witnessing each step, whose countable intersection is nonempty; a coordinate in that intersection would give an infinite descending membership chain in the original universe. The relation is extensional and set-like, so the Mostowski collapse theorem gives a transitive class $M$ and an elementary ultrapower embedding $j:V\to M$.

For each $\alpha <\kappa$, every function $\kappa \to \alpha$ is constant modulo $U$. If no fibre were in $U$, intersecting the fewer than $\kappa$ fibre complements would give the empty set in $U$. Induction on $\alpha$ therefore shows that the collapsed ultrapower ordinal $j(\alpha )$ has precisely the elements $\beta <\alpha$, soThe identity function $\mathrm{id}:\kappa \to \kappa$ represents an ordinal below $j(\kappa )$, and every constant $\alpha <\kappa$ is below it modulo $U$, since a tail is large. ConsequentlyThus the canonical collapsed embedding is not the identity; its first moved ordinal is $\kappa$. For a general measure the identity-function class need not collapse to exactly $\kappa$; that stronger equality holds for a normal measure. The argument above needs only its lower bound.

Conversely, suppose $j:V\to M$ is elementary, $M$ is transitive, its critical point is $\kappa$, and its derived measure is a set, as for the usual definable or amenable class embeddings. DefineBecause $\kappa <j(\kappa )$, elementary preservation of complements and intersections makes this an ultrafilter. It is nonprincipal since $j(\{\alpha \})=\{\alpha \}$ for $\alpha <\kappa$. For a sequence of $\gamma <\kappa$ large sets, $j$ fixes the index ordinal $\gamma$ and takes the intersection to the intersection of their images; $\kappa$ belongs to every image and hence to the intersection. Thus $U$ is $\kappa$-complete. The set-existence qualification excludes treating an arbitrary external class map as a set parameter without justification.

For context, measurability already implies regularity and the strong-limit property. A cofinal sequence of length below $\kappa$ partitions $\kappa$ into that many bounded, hence small, pieces; completeness and their absent fibres contradict covering all of $\kappa$. If there were $\kappa$ distinct subsets of some $\lambda <\kappa$, for each coordinate choose the $U$-large side deciding its membership bit. The intersection of these $\lambda$ large sets would still be large, but all its indices would label the same subset, so it would have at most one member. This contradiction gives $2^{\lambda }<\kappa$. Thus the first moved ordinal is an uncountable strongly inaccessible cardinal, in addition to being measurable.

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.

A model-theoretic ultralimit is the elementary direct limit of a chain of successive ultrapowers along their diagonal embeddings. We will build two such chains with isomorphic limits. This is not a topological ultrafilter limit and does not require the stronger claim that one ultrapower of each structure is already isomorphic.

First prove the Frayne embedding lemma, including the relative form needed to make the diagrams commute. If $C\equiv D$, expand the language by constants naming every element of $D$, and let $\mathrm{ED}(D)$ be its complete elementary diagram. Index by finite subsets $s$ of this diagram. The finitely many constants in $s$ can be interpreted in $C$ so that $s$ holds: existentially quantifying them gives a sentence true in $D$ and hence in $C$. Choose such interpretations, and give unused constants an arbitrary fixed value in the nonempty domain of $C$.

For each diagram sentence $\delta$, its cone $\{s:\delta \in s\}$ has the finite intersection property with the other cones. Extend the generated filter to an ultrafilter $U$. For $d\in D$, let $f_d(s)$ be its chosen interpretation at coordinate $s$. The mapis elementary by Łoś: every formula true of a tuple from $D$, or its negation, is a diagram sentence and holds on its corresponding cone. In particular distinct named elements stay distinct.

If $C⪯D$, the construction can keep every constant naming $c\in C$ equal to that same $c$ at every coordinate. For a finite diagram fragment, existentially quantify just the names outside $C$; the resulting formula with parameters in $C$ is true in $D$, hence true in $C$. Thus the finite realizations still exist with all those old names fixed. ConsequentlyThis relative extension of the diagonal map is the essential strengthening.

Now let $A_0\equiv B_0$. The nonrelative lemma embeds $B_0$ into an ultrapower $A_1$ of $A_0$. Identify the image with a copy of $B_0$ inside $A_1$. Since $B_0⪯A_1$, the relative lemma embeds $A_1$ into an ultrapower $B_1$ of $B_0$ extending its diagonal map. Rename this larger structure so that the displayed copy of $A_1$ is a literal elementary substructure. Next apply the relative lemma over $A_1⪯B_1$ to embed $B_1$ into an ultrapower $A_2$ of $A_1$ fixing its diagonal copy. Continue alternately. We obtain a coherent elementary chainwith $A_0⪯A_1$ as well. Each inclusion $A_n\to A_{n+1}$ is, up to these coherent identifications, the diagonal embedding into its ultrapower; the same holds for $B_n\to B_{n+1}$. It is the relative clause, not merely the existence of arbitrary elementary embeddings, which guarantees this.

By the elementary chain theorem, the unions of the two subsequences are elementary limits. They are the same structure: each $A_n$ lies in a subsequent $B_n$, and each $B_n$ lies in $A_{n+1}$. Hence the alternating ultrapowers give isomorphic ultralimits construction provesConversely each ultrapower and each elementary direct limit has the same first-order theory as its starting structure. Isomorphic ultralimits therefore imply $A_0\equiv B_0$ as well. Thus the conclusion exactly characterizes elementary equivalence at the level of ultralimits.

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.

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.

A model-theoretic ultralimit is the direct limit of a chain of successive ultrapowers along their diagonal elementary maps. It is not the topological notion of a limit along an ultrafilter. We first prove the precise relative embedding lemma needed to synchronize two such limits.

If $A\prec B$, then $B$ embeds elementarily into an ultrapower of $A$, with the embedding restricting on $A$ to its diagonal map. To prove this Frayne embedding lemma, use the elementary diagram of $B$ with the elements of $A$ treated as named parameters. Every finite fragment $\Delta$ of that diagram has a realization in $A$: replace its finitely many names from $B\setminus A$ by variables and existentially quantify their conjunction. It is true in $B$, and hence true in $A$ by elementarity. Choose these simultaneous realizations for each finite fragment, keeping every parameter from $A$ interpreted as itself; give unmentioned names an arbitrary default in the nonempty $A$.

On the index set of finite fragments, extend the filter of cones $\{\Delta :\Delta \supseteq \Gamma \}$ to an ultrafilter $U$. For each $b\in B$, let $g_b(\Delta )$ be its value in the chosen coordinate realization. Every diagram sentence is satisfied on its cone, so the Łoś theorem makes $b\mapsto [g_b]$ an elementary embedding $B\to A^I/U$. Inequalities in the diagram ensure injectivity. If $b\in A$, all its coordinates equal $b$, giving exactly the diagonal map.

There is also the initial version: if merely $A\equiv B$, then $A$ embeds elementarily into an ultrapower of $B$. A finite fragment of the elementary diagram of $A$, with all its names replaced by variables, yields an existential sentence true in $A$ and hence in $B$. The identical finite-fragment and cone construction therefore proves this version without already assuming an embedding.

Start with $A_0=A$. Use the initial version to place $A_0$ elementarily in an ultrapower $B_0$ of $B$. Relabel embedded copies so we can regard the elementary maps as inclusions. Apply the relative version to $A_0\prec B_0$ to obtain an ultrapower $A_1$ of $A_0$ containing $B_0$, and whose inclusion of $A_0$ is its diagonal map. Next apply it to $B_0\prec A_1$ to obtain an ultrapower $B_1$ of $B_0$ containing $A_1$, again fixing the earlier diagonal inclusion. Continuing gives an elementary chainThe common union $C$ is elementary over every stage by the elementary chain theorem, andThe first presentation is a model-theoretic ultralimit of $A$. The second, preceded by the initial diagonal embedding of $B$ into $B_0$, is a model-theoretic ultralimit of $B$. Each consecutive same-letter inclusion is precisely the corresponding ultrapower diagonal map, not just an unspecified elementary embedding. Thus the two limits are identified with the same structure $C$, proving

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

No. The ten residue classes modulo $10$ form a finite partition, so an ultrafilter $p$ contains exactly one class $C_r$. The addition formula shows that $p+p$ contains $C_{2r}$: for $n\in C_r$, the translate $C_{2r}-n$ is $C_r$ and belongs to $p$. If $p$ is an idempotent ultrafilter, uniqueness of its selected class gives $2r\equiv r(\mathrm{mod}10)$, hence $r=0$.

Thus every idempotent ultrafilter contains the multiples of $10$, and cannot also contain their complement. This is the zero-residue constraint for idempotent ultrafilters, valid for every finite modulus.

Put $\kappa =|X|$, an infinite cardinal number. The original PDF has the double exponent $2^{2^{|X|}}$; the single-exponent expression in the TeX aid is a transcription error.

We explicitly construct an independent family of subsets with $2^{\kappa }$ members on a set of size $\kappa$. LetFor each finite $s$ there are finitely many possibilities for $H$. The collection of finite subsets of an infinite cardinal has size $\kappa$, so $|D|\le \kappa$; the points $(\{\xi \},\varnothing )$ give the reverse bound. Thus $|D|=\kappa$.

For every $B\subseteq \kappa$ defineTo verify independence, take distinct $B_1,\dots ,B_n$ and bits ${\epsilon }_1,\dots ,{\epsilon }_n$. For each pair $i<j$, choose a point of $B_i△B_j$ and let $s$ contain all these finitely many points. The traces $B_i\cap s$ are pairwise distinct. SetThen $(s,H)\in A_{B_i}$ exactly for those $i$ with ${\epsilon }_i=1$. Every finite Boolean pattern is therefore realized. The cases $n=0,1$ work by the same definition, allowing $s=\varnothing$. In particular the sets $A_B$ are all distinct, so the finite-trace independent family construction gives exactly $2^{\kappa }$ independent members.

For each function $\epsilon :\mathcal{P}(\kappa )\to \{0,1\}$, prescribe $A_B$ when $\epsilon (B)=1$ and $D\setminus A_B$ when $\epsilon (B)=0$. Independence gives the finite intersection property. Their finite intersections generate a proper filter on a set: its members are the subsets of $D$ containing one of those intersections.

To extend this to an ultrafilter, order its proper filter extensions by inclusion. The union of a chain is again a proper filter, so Zorn's lemma supplies a maximal one, $U_{\epsilon }$. If neither a subset $Y$ nor its complement belonged to this filter, adjoining $Y$ would still generate a proper filter: otherwise some existing member would be disjoint from $Y$ and force its complement into the filter already. Maximality therefore gives the ultrafilter dichotomy. Using the ambient axiom of choice, choose such an extension for every $\epsilon$.

Distinct functions differ at some $B$. Their ultrafilters respectively contain $A_B$ and its complement, and cannot be equal. There are $2^{2^{\kappa }}$ such functions. Transporting the ultrafilters along a bijection $D\to X$ proves the lower bound. The upper bound is immediate because every ultrafilter is a subset of $\mathcal{P}(X)$:Thus the number of ultrafilters on an infinite set is

If the complement of a truth set belongs to a proper filter on a set, the truth set itself cannot belong: their intersection is empty. Hence the right side always implies the left side.

The reverse implication can fail. In the cofinite filter, the set of even integers is absent, but its odd complement is absent as well. The filter-quantified evenness assertion is false, while the filter-quantified assertion of oddness is also false. Therefore (iii) can be false.

For an ultrafilter the equivalence is true, precisely because it contains exactly one of any set and its complement. The filter quantifier preserves conjunction for arbitrary proper filters, but its full classical Boolean behaviour requires the ultrafilter property.

Membership of either truth set in a filter on a set implies membership of its union, by upward closure. The converse need not hold. For the cofinite filter, take $p(x)$ to mean that $x$ is even and $q(x)$ that $x$ is odd. The union of their truth sets is all of $\mathbb{N}$, while neither truth set is cofinite.

Thus the left side of the printed equivalence is true and its right side false: (ii) can be false. An ultrafilter does satisfy the equivalence, because its dichotomy forces one member of a finite union into the ultrafilter. General filters need not have that dichotomy. This is one aspect of the Boolean failure of the cofinite-filter quantifier.

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.

Let $R={\prod }_i{\mathcal{M}}_i/F$ be the reduced product by a proper filter on a set. Its underlying equivalence relation is $f\sim g$ when $\{i:f(i)=g(i)\}\in F$. Operations are interpreted coordinatewise, and a relation holds of the classes exactly when its coordinate truth set belongs to $F$.

Evaluation of a first-order term commutes with passage to the quotient, by mathematical induction on terms. Consequently the desired equivalence holds for every atomic formula, including logical equality. For a formula $\theta$ and representatives $\bar{f}$, write $S_{\theta }=\{i:{\mathcal{M}}_i\models \theta (\bar{f}(i))\}$.

For logical conjunction, $S_{\theta \wedge \psi }=S_{\theta }\cap S_{\psi }$. The filter on a set axioms giveThus the induction hypothesis transfers a conjunction in both directions.

For existential quantification, first suppose $R\models \exists y\theta (y,[\bar{f}])$. Choose a representative $g$ of a witness. Induction gives $S_{\theta (g,\bar{f})}\in F$, and this set is contained in $S_{\exists y\theta }$. Upward closure therefore gives $S_{\exists y\theta }\in F$.

Conversely, suppose $A=S_{\exists y\theta }\in F$. For each $i\in A$, choose a coordinate witness $g(i)$, and choose an arbitrary element of $M_i$ outside $A$. These simultaneous choices use the axiom of choice, as does the usual product construction. Then $A\subseteq S_{\theta (g,\bar{f})}$, so that truth set belongs to $F$. Induction gives $R\models \theta ([g],[\bar{f}])$, providing the required witness. Thereforefor every primitive positive formula. The exam's tame formulas are exactly this fragment, built using logical conjunction and existential quantification. No ultrafilter dichotomy was used.

Take $I=\{0,1\}$ and the proper filter on a set $F=\{I\}$. In the first-order language with unary predicates $P,Q$, let both factors be one-element first-order structures. Set $P$ true and $Q$ false in the first factor, and reverse these truth values in the second.

The reduced product also has one element $a$. Neither $P(a)$ nor $Q(a)$ holds there: their truth sets are $\{0\}$ and $\{1\}$, neither belonging to $F$. ThusLogical disjunction can therefore break the equivalence. A union can belong to a filter on a set without either summand belonging to it; the corresponding union property does hold for an ultrafilter.

Use the same two-index filter on a set $F=\{\{0,1\}\}$, with a unary predicate $P$ true only in the first one-element factor. In the reduced product, $P(a)$ is false, so $\neg P(a)$ is true. ButLogical negation also breaks the equivalence. For a general proper filter on a set, a set and its complement can both be absent. In an ultrafilter, exactly one belongs, which is the step used to transfer logical negation in the Łoś theorem.

An ultrafilter $U$ on $X$ is kappa-complete if, for every index set $J$ with $|J|<\kappa$ and every family $(A_j{)}_{j\in J}$ of members of $U$,The bound is strictly fewer than $\kappa$ sets. In particular every ultrafilter is ${\aleph }_0$-complete, since this requires only finite intersections; countably complete ultrafilters require intersections of countably many members, equivalently ${\aleph }_1$-completeness.

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.

The club filter completeness argument works for every regular uncountable $\kappa$. Let $\mu <\kappa$ and let $C_i$ be a club set for each $i<\mu$. Their intersection is closed. To prove it unbounded, start above any prescribed $\beta <\kappa$ and choose an increasing sequence $({\delta }_n{)}_{n<\omega }$ so that ${\delta }_{n+1}$ lies above a chosen point of every $C_i$ greater than ${\delta }_n$. $\kappa$ is a regular cardinal, so the supremum of these $\mu$ choices remains below $\kappa$. The resulting countable supremum $\delta ={\sup }_n{\delta }_n$ likewise remains below $\kappa$. For each $i$, the chosen $C_i$ points are cofinal in $\delta$, so closure gives $\delta \in C_i$. Thus the intersection is a club set. Intersecting fewer than $\kappa$ members of the club filter still contains such an intersection of clubs. In particular, $\boxed{{\mathcal{D}}_{{\omega }_2}\text{ is }{\aleph }_2\text{-complete}}$.

It is not an ultrafilter. For a regular infinite $\theta <\kappa$, the setis stationary. Given a club set $C$, build in $C$ a strictly increasing continuous sequence of length $\theta$ and take its supremum $\delta <\kappa$. Closure gives $\delta \in C$, and the cofinality of an increasing ordinal supremum gives $\mathrm{cf}(\delta )=\theta$. This proves the stationarity of ordinals of prescribed cofinality.

At $\kappa ={\omega }_2$, the disjoint sets $S_{\omega }^{{\omega }_2}$ and $S_{{\omega }_1}^{{\omega }_2}$ are both stationary. A club contained in either $S_{\omega }^{{\omega }_2}$ or its complement would miss one of these stationary sets. Thus neither $S_{\omega }^{{\omega }_2}$ nor its complement belongs to ${\mathcal{D}}_{{\omega }_2}$, and

Take the least omega-measurable cardinal $\kappa$, with a countably complete ultrafilter $U$ on $\kappa$ that is nonprincipal. We prove that $U$ is $\kappa$-complete. This will give $\boxed{\kappa \text{ is measurable}}$.

Suppose $\mu <\kappa$, $A_i\in U$ for $i<\mu$, and ${\bigcap }_{i<\mu }{A}_i\notin U$. Then $B=\kappa \setminus {\bigcap }_{i<\mu }{A}_i$ belongs to $U$. For $x\in B$ let $g(x)$ be the least $i<\mu$ with $x\notin A_i$. The pushforward ultrafilteris a countably complete ultrafilter on $\mu$; this uses $B\in U$, so $U$ restricts to an ultrafilter on $B$. For each $i$, the fibre $g^{-1}[\{i\}]$ is contained in $\kappa \setminus A_i$, hence is not in $U$. Thus $W$ is nonprincipal. If $\mu$ is finite or countable, countable completeness already rules this out. Otherwise $|\mu |<\kappa$ would be an omega-measurable cardinal, contradicting minimality of $\kappa$.

Therefore every intersection of fewer than $\kappa$ members of $U$ lies in $U$. Since $\kappa$ is uncountable, it is a measurable cardinal. This proves that the least omega-measurable cardinal is measurable, even if the originally supplied cardinal carried only a countably complete ultrafilter.

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.