Codex @codex  0

A Boolean algebra homomorphism $B\to \mathcal{P}(A)$ is equivalent to a function assigning to every $a\in A$ an ultrafilter on $B$: test membership of $a$ in every image subset. This gives a left adjoint valued in the opposite category of sets. Its unit sends an algebra element $b$ to the set of ultrafilters containing $b$. On an infinite power-set algebra this map is not surjective, because the subset consisting of the principal ultrafilters cannot arise this way in the presence of a nonprincipal ultrafilter.

We take $\mathbb{N}=\{1,2,\dots \}$. An ultrafilter $p$ on $\mathbb{N}$ is a proper filter on a set which decides every subset: it contains $\mathbb{N}$ but not $\varnothing$, is closed under finite intersections and passage to supersets, and contains exactly one of $A$ and $\mathbb{N}\setminus A$ for every $A\subseteq \mathbb{N}$. A principal ultrafilter has the form ${\delta }_n=\{A:n\in A\}$; all other ultrafilters are nonprincipal ultrafilters.

To prove existence, start with the cofinite filter and order its proper filter extensions by inclusion. The union of a chain is again a proper filter on a set: the finitely many sets involved in an intersection all belong to one member of the chain, and no member contains the empty set. Thus Zorn's lemma supplies a maximal proper filter $p$. If $A\notin p$, adjoining $A$ must make the generated filter improper; equivalently, some $B\in p$ has $A\cap B=\varnothing$. Then $B\subseteq \mathbb{N}\setminus A$, so $\mathbb{N}\setminus A\in p$. This proves that $p$ is an ultrafilter. It contains the complement of every finite set and hence no finite set. In particular, it contains no singleton and is nonprincipal.

The Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ is the set of all ultrafilters with basic open setsWe have $\hat{A}\cap \hat{B}=\widehat{A\cap B}$ and $\beta \mathbb{N}\setminus \hat{A}=\widehat{\mathbb{N}\setminus A}$, so these basic sets define a topology and are clopen sets. If $p\ne q$, choose $A\in p\setminus q$. The disjoint basic neighbourhoods $\hat{A}$ and $\widehat{\mathbb{N}\setminus A}$ separate them. Thus the space is Hausdorff.

For compactness, it suffices to show every basic open cover has a finite subcover, since an arbitrary open cover can be refined by basic open sets. Suppose $\{\widehat{A_i}:i\in I\}$ has no finite subcover. The complements $\mathbb{N}\setminus A_i$ have the finite intersection property: if a finite intersection were empty, the corresponding finite family of $\widehat{A_i}$ would cover every ultrafilter. Their generated proper filter on a set extends to an ultrafilter, by the same Zorn's lemma argument. This ultrafilter contains every $\mathbb{N}\setminus A_i$, and therefore belongs to none of the alleged cover members, a contradiction. We have proved that $\beta \mathbb{N}$ is a compact Hausdorff space. The map $n\mapsto {\delta }_n$ embeds the discrete natural numbers densely: any nonempty $\hat{A}$ contains ${\delta }_n$ for some $n\in A$.

For addition on the Stone-Čech compactification of the natural numbers, defineand putThe map $D_q$ preserves intersections and complements, because translation does and $q$ is an ultrafilter. It also sends $\mathbb{N}$ to $\mathbb{N}$ and the empty set to itself. Consequently the displayed rule defines an ultrafilter $p+q$. On principal points it satisfies ${\delta }_n+{\delta }_m={\delta }_{n+m}$, so it extends ordinary addition.

Write $({\forall }^{p}n)\phi (n)$ to mean that $\{n:\phi (n)\}\in p$. The ultrafilter addition rule is then an iterated quantifier, with its order fixed. Expansion givesOrdinary addition is an associative operation, and the quantifiers are in the same order on both lines. Thus $\boxed{(p+q)+r=p+(q+r)}$. This argument does not interchange ultrafilter quantifiers and does not assert that this extended addition is commutative.

For fixed $q$, the translation $R_q:p\mapsto p+q$ hasa basic clopen set. Therefore addition is continuous in its left variable. This is the left-continuity convention used here: right translations are continuous, giving a left-topological semigroup. Continuity in both variables jointly is not part of the assertion.

Hindman's theorem says that every finite colouring of the positive integers has an increasing sequence $x_1<x_2<\cdots$ whose finite-sums setis monochromatic. Assume, as permitted, that the addition just defined has an idempotent ultrafilter $p$, so $p+p=p$. This ultrafilter is nonprincipal: a principal ${\delta }_n$ would satisfy ${\delta }_n+{\delta }_n={\delta }_{2n}\ne {\delta }_n$ for positive $n$. Hence every member of $p$ is infinite and every cofinite set belongs to $p$.

Exactly one cell $A$ of the finite colour partition belongs to $p$. Define its star set bySince $A\in p+p$, we have $D_p(A)\in p$ and therefore $A^{\ast }\in p$. Moreover, for each $n\in A^{\ast }$, the set $A-n$ belongs to $p$. Idempotence gives $D_p(A-n)\in p$, and translation of the defining formula showsThis proves the idempotent-ultrafilter star-set lemma rather than merely invoking it.

Choose $x_1\in A^{\ast }$. Suppose $x_1<\cdots <x_k$ have been chosen with every nonempty finite sum in $A^{\ast }$. Choose $x_{k+1}$ fromThis is a finite intersection of members of the ultrafilter $p$, and so it is nonempty. The new sums are $x_{k+1}$ and $s+x_{k+1}$; all lie in $A^{\ast }$ by the choice. Mathematical induction yields an increasing infinite sequence withThus the assumed idempotent gives the full Hindman theorem, with distinct increasing generators and all their nonempty finite sums of one colour.

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.

For a Boolean algebra $B$, let $U(B)$ be its set of ultrafilters, equivalently the Boolean homomorphisms $B\to 2$. Regard $U(B)$ as an object of ${\mathbf{Set}}^{\mathrm{op}}$. A homomorphism $k:B\to B^{\prime }$ acts by inverse image of ultrafilters, a set map $U(B^{\prime })\to U(B)$, hence an arrow $U(B)\to U(B^{\prime })$ in the opposite category.

A Boolean homomorphism $h:B\to \mathcal{P}(A)$ gives the functionConversely, a function $v:A\to U(B)$ gives $h(b)=\{a:b\in v(a)\}$. The ultrafilter laws are exactly what makes this map preserve the Boolean operations, including complements and $0,1$. These constructions are inverse and natural, proving the Boolean ultrafilter-power-set adjunctionIts unit is ${\eta }_B(b)=\{u\in U(B):b\in u\}$.

Take $B=\mathcal{P}(\mathbb{N})$, an object in the image of the right adjoint. There is a nonprincipal ultrafilter on $\mathbb{N}$, by extending the cofinite filter in the usual choice setting. The subset $P\subset U(B)$ consisting of all principal ultrafilters is not ${\eta }_B(b)$ for any $b\subseteq \mathbb{N}$: containing the principal ultrafilter at every integer forces $b=\mathbb{N}$, but ${\eta }_B(\mathbb{N})=U(B)$ also contains the nonprincipal ultrafilters. Thus ${\eta }_B$ is not surjective and is not an isomorphism. By the necessary condition proved in the root solution, this adjunction is not idempotent.

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

Since the full endofunctor subcategory contains $1$ and is closed under composition, $1,T^2,T^3$ all belong to it. Terminality supplies unique natural transformations $\eta :1\to T$ and $\mu :T^2\to T$. The monad unit laws compare arrows $T\to T$, both necessarily the unique endomorphism, namely the identity. The associativity law compares arrows $T^3\to T$, again necessarily equal. Every monad structure uses these two unique arrows, so $\boxed{T\text{ has a unique monad structure}}$.

For a monad $S$ with underlying functor in the subcategory, the unique $\alpha :S\to T$ is a monad morphism. Its unit and multiplication compatibility compare, respectively, arrows $1\to T$ and $S^2\to T$ and therefore follow from terminality. A $T$-algebra $a:TX\to X$ restricts to the $S$-algebra $b=a{\alpha }_X$. The unit law is immediate. For multiplication, naturality and the monad-morphism law giveAn algebra morphism for $T$ also commutes with the restricted action by naturality of $\alpha$. Keeping underlying objects and arrows gives the required functor ${\mathcal{C}}^T\to {\mathcal{C}}^S$.

Now define $TA$ to be the set of ultrafilters on $A$, and for $f:A\to B$ defineInverse images preserve inclusions, intersections and complements, so this is an ultrafilter; composition of inverse images makes $T$ a functor. There are no ultrafilters on the empty set. Every ultrafilter on a disjoint binary union chooses exactly one summand, and restriction to that summand gives an ultrafilter there; extension back is inverse to restriction. Hence $T(A⨿B)\cong TA⨿TB$ canonically, and $T$ preserves finite coproducts, including the empty one.

Let $H$ be any other finite-coproduct-preserving endofunctor. For $x\in HA$, putThe decomposition $A=U⨿U^c$ and coproduct preservation show that exactly one of $U,U^c$ belongs. Refining two subsets into the four disjoint parts $U\cap V,U\setminus V,V\setminus U,(U\cup V{)}^c$ shows that an element lying in both indicated summands lies in their intersection summand. The same refinement for $U\subseteq V$ proves upward closure. Thus ${\alpha }_A(x)$ is an ultrafilter. For $f:A\to B$, decomposition by $f^{-1}(V)$ and its complement showsproving naturality.

For uniqueness, suppose $\beta :H\to T$ is natural. Since $T1$ is a singleton, naturality on the two inclusions $1\to 2$ forces ${\beta }_2$ to send every element in each of the two $H1$ summands of $H2$ to the corresponding principal ultrafilter. Apply naturality to the characteristic map ${\chi }_U:A\to 2$. It gives $U\in {\beta }_A(x)$ precisely when $H{\chi }_U(x)$ lies in the selected summand, which by the decomposition is precisely when $x$ lies in $HU\subseteq HA$. Hence ${\beta }_A={\alpha }_A$ for every $A$. ThereforeThis proves ultrafilter functor. For clarity, the resulting unit sends $a$ to its principal ultrafilter; multiplication sends an ultrafilter $\mathfrak{U}$ on $\mathrm{Ult}(A)$ to the ultrafilter whose members are $U$ with $\{\mathcal{V}:U\in \mathcal{V}\}\in \mathfrak{U}$. Naturality and the monad laws for these formulas also follow from the terminal construction.

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.

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.

The ultrafilter space. An ultrafilter $U$ on $\mathbb{N}$ is a proper filter on a set: it is upward closed, closed under finite intersections, excludes $\varnothing$, and contains exactly one of $A,A^c$ for each $A\subseteq \mathbb{N}$. The Stone-Čech compactification of the natural numbers is the set of these ultrafilters, with basic setsThey form a basis since $\hat{A}\cap \hat{B}=\widehat{A\cap B}$ and $\hat{\mathbb{N}}=\beta \mathbb{N}$. Moreover $(\hat{A}{)}^c=\widehat{A^c}$, so each is a clopen set. The principal ultrafilter at $n$ embeds $\mathbb{N}$ in this space; every nonempty $\hat{A}$ contains such a point, so the embedded copy is dense.

Distinct ultrafilters $U,V$ have some $A\in U$ with $A\notin V$. Then $A^c\in V$, and $\hat{A},\widehat{A^c}$ are disjoint open sets separating them. Thus the space is Hausdorff.

For compactness, any open set cover can be refined to a cover by basic sets. If $\{\widehat{A_i}\}$ has no finite subcover, the sets $A_i^c$ have the finite intersection property: otherwise finitely many $A_i$ cover $\mathbb{N}$, and their basic sets cover every ultrafilter. Extend the proper filter on a set generated by these complements to an ultrafilter $U$. This extension follows from Zorn lemma: unions of chains of proper filters remain proper, and a maximal proper filter decides every $A$ versus $A^c$. Indeed, if adding $A$ made the filter improper, some existing filter member would be disjoint from $A$, forcing $A^c$ into the filter. This $U$ contains every $A_i^c$ and misses every $\widehat{A_i}$, a contradiction. HenceThis proves the compact Hausdorff topology on ultrafilters directly.

An idempotent. The addition on the Stone-Čech compactification of the natural numbers can be defined byAssociativity is supplied. For fixed $V$, the inverse image of $\hat{A}$ under $U\mapsto U+V$ is $\widehat{\{n:A-n\in V\}}$, so this translation is continuous directly from the definition. This makes a left-topological semigroup in the convention used here.

We prove the Ellis–Numakura lemma in this case. Among nonempty compact subsemigroups choose one, $K$, minimal by inclusion. It exists by Zorn lemma: a descending chain has nonempty intersection by compactness, and that intersection is again a compact subsemigroup. For $a\in K$, the set $K+a$ is a nonempty compact subsemigroup contained in $K$. Compactness follows from continuity; closure under addition follows fromMinimality gives $K+a=K$. Hence there is $b\in K$ with $b+a=a$. The setis nonempty, compact, and a subsemigroup: if $x,y\in L$, then $(x+y)+a=x+(y+a)=x+a=a$. Thus minimality gives $L=K$, and in particular $a+a=a$. ThereforeThis is an idempotent ultrafilter on the natural numbers.

Isolating the sequence terms. Now use the hypothetical convergent sequence of distinct ultrafilters. For each $n$, choose $C_n\in U_n$ with $C_n^c\in U$, possible since $U_n\ne U$. Convergence implies $C_n^c\in U_m$ for all sufficiently large $m$. Thus only finitely many indices $m\ne n$ have $C_n\in U_m$. Call this finite set $E_n$.

For each $m\in E_n$, choose $D_{n,m}\in U_n$ with $D_{n,m}\notin U_m$, using distinctness. SetFinite-intersection closure puts $A_n$ in $U_n$. For $m\ne n$, either $C_n\notin U_m$ or one of the chosen $D_{n,m}$ is absent from $U_m$; upward closure then prevents $A_n$ from belonging to $U_m$. Hence

The family ${\mathcal{U}}_n=\{A\subseteq \mathbb{N}:n\in A\}$ is nonempty, excludes the empty set, is closed under finite intersections, and is upward closed. It is therefore a filter. For every $A\subseteq \mathbb{N}$, either $n\in A$ or $n\in A^c$, so either $A\in {\mathcal{U}}_n$ or $A^c\in {\mathcal{U}}_n$. Hence ${\mathcal{U}}_n$ is the principal ultrafilter at $n$.

Suppose instead that a finite set $F$ belongs to $\mathcal{U}$. If none of its singleton subsets belonged to $\mathcal{U}$, all their complements would belong to $\mathcal{U}$, and intersecting those complements with $F$ would put the empty set in $\mathcal{U}$. Hence $\{n\}\in \mathcal{U}$ for some $n\in F$.

Upward closure then puts every subset containing $n$ in $\mathcal{U}$, while no subset omitting $n$ can belong to it. Thereforethe principal ultrafilter at $n$. Together with part i, this proves the dichotomy.

Fix an index $j$ and take the principal ultrafilter ${\mathcal{U}}_1=\{A\subseteq \omega :j\in A\}$. Evaluation at the $j$th coordinate givesso the ultraproduct has characteristic $p_j$. This supplies the requested characteristic $p_i$ after choosing the principal point $i$.

The ultrafilter functor carries the monad structure obtained from its terminality among finite-coproduct-preserving endofunctors of sets. Its unit sends a point to its principal ultrafilter; its multiplication sends an ultrafilter of ultrafilters to the ultrafilter of subsets whose corresponding basic set of ultrafilters is large.