Ramsey Algebras and Strongly Reductible Ultrafilters

(1)

BULLETINof the MALAYSIANMATHEMATICAL

SCIENCESSOCIETY http://math.usm.my/bulletin

Bull. Malays. Math. Sci. Soc. (2)37(4) (2014), 931–938

Ramsey Algebras and Strongly Reductible Ultrafilters

WENCHEANTEH

School of Mathematical Sciences, Universiti Sains Malaysia, 11800 Penang, Malaysia [email protected]

Abstract. Hindman’s Theorem says that every finite coloring of the positive natural numbers has a monochromatic set of finite sums. A Ramsey algebra is a structure that satisfies an analogue of Hindman’s Theorem. It is known that Martin’s Axiom implies the existence of strongly summable ultrafilters, that is nonprincipal ultrafilters generated by sets of finite sums. Strongly reductible ultrafilters are analogues of strongly summable ultrafilters. As- suming Martin’s Axiom, this paper shows the existence of nonprincipal strongly reductible ultrafilters for a nondegenerate Ramsey algebra.

2010 Mathematics Subject Classification: 03E50, 05D10

Keywords and phrases: Strongly summable ultrafilter, strongly reductible ultrafilter, Ram- sey algebra, Hindman’s Theorem.

1. Introduction

The set of natural numbers{0,1,2, . . .}is denoted byω. Suppose⟨xi⟩_i∈ω is a sequence of natural numbers. Let FS(⟨x_i⟩_i∈ω)denote the set{ ∑_i∈Fxi∣F∈ P_f(ω)/{∅} }, whereP_f(ω) is the set of all finite subsets ofω. Hindman’s Theorem [6] says that for every finite partition of the set of positive natural numbersN=X₀⊍X₁⊍ ⋯ ⊍X_N, there exists a sequence⟨x_i⟩_i∈ωof positive natural numbers such that for some 0≤ j≤N, we have FS(⟨x_i⟩_i∈ω) ⊆X_j. According to Hindman [5], Galvin knew that Hindman’s Theorem would follow from the existence of what Galvin called an almost translation invariant ultrafilter, that is, an ultrafilterU onN such that{x∈N∣X−x∈U} ∈UwheneverX∈U, whereX−x= {y∈N∣x+y∈X}. In 1972 Hindman [5] showed that Hindman’s Theorem (then unproven) together with the continuum hypothesis implies the existence of almost translation invariant ultrafilters.

In 1975, Galvin and Glazer (see [3] or [7]) showed the existence of almost translation invariant ultrafilters without the continuum hypothesis. An almost translation invariant ultrafilter is exactly an idempotent element of the semigroup(βN,+), where+is the extension of addition onNtoβN, the Stone- ˇCech compactification ofN. As(βN,+)is a compact right topological semigroup, it has an idempotent element.

However, as accounted by Hindman in [8], van Douwen pointed out in 1985 that the ultrafilterU produced in Hindman’s proof has the stronger property that it is generated by

Communicated byAng Miin Huey.

Received:June 17, 2013;Revised:September 10, 2013.

(2)

sets of finite sums, which means

for everyX∈U, there existsa⃗∈^ωNsuch that FS( ⃗a) ⊆X and FS( ⃗a) ∈U,

and he asked whether such ultrafilters can be shown to exist inZFC. Hindman [8] called such ultrafiltersstrongly summableand showed that Martin’s Axiom implies their existence.

Later, Blass and Hindman [1] showed that their existence implies the existence ofP-points.

It is a well known theorem of Shelah [12, VI, § 4] that the existence ofP-points cannot be proven inZFC. Therefore, the existence of strongly summable ultrafilters is independent of ZFC.

ARamseyalgebra [13, 14] is a structure which possesses the property analogous to that possessed by the algebra(N,+) as in Hindman’s Theorem. Assuming Martin’s Axiom, we will show the existence of the analogue of strongly summable ultrafilters for a Ramsey algebra.

Ramsey algebras are also closely related to Ramsey spaces, structures that have proper- ties analogous to those of Ellentuck’s space [4]. Every algebra can be associated to a certain topological space of infinite sequences. It follows from the abstract version of Ellentuck’s Theorem by Carlson [2] that such a space is Ramsey if and only if the associated underlying algebra is Ramsey.

2. Preliminaries

To us analgebrais a pair(A,F ), whereAis a nonempty set andFis a collection of operations onA, none of which is nullary. SupposeBis a nonempty subset ofAand supposeB is closed under f in the usual sense for each f∈ F. If f isn-ary, let f↾Bdenote the restric- tion of f toBⁿwith codomainB. The algebra(B,{f ↾B∣ f ∈ F })is called asubalgebra of(A,F ). Note that f ↾Bandg↾Bcan be equal when f andgare distinct. Our notions of “algebra” and “subalgebra” are different from but compatible with that in the theory of universal algebra.

The set of infinite and finite sequences inA are denoted by ^ωA and^<ωA respectively.

Supposea⃗= ⟨a0,a1,a2, . . .⟩. Forn≥1, leta⃗↾ndenote the initial segment of a⃗of length n, namely⟨a₀,a₁, . . . ,a_n−1⟩. Forn∈ω, leta⃗−ndenote the sequence⟨a_n,a_n+1,a_n+2, . . .⟩. If s⃗= ⟨s₀,s₁, . . . ,s_n⟩and⃗t= ⟨t₀,t₁,t₂, . . .⟩, then∣⃗s∣is the length ofs⃗and the concatenations⃗∗ ⃗t ofs⃗and⃗tis⟨s₀,s₁, . . . ,s_n,t₀,t₁,t₂, . . .⟩.

Apre-partial orderingon a setAis a binary relation onAwhich is reflexive and transitive.

Fix an algebra(A,F )for the rest of this section.

Definition 2.1. An operation f on A is anorderly compositionofFiff there exist g,h1, . . . ,hn

∈ Fsuch that f(x¯₁, . . . ,x¯_n) =g(h₁(x¯₁), . . . ,h_n(x¯_n)). (For notational convenience, we will use a symbol with a bar over it to indicate a list.) We say thatFisclosed under orderly com- positioniff f ∈ F whenever f is an orderly composition ofF. The collection of orderly termsoverFis the smallest collection of operations on A that containsF and the identity function on A and that is closed under orderly composition.

Definition 2.2. Supposea,⃗⃗b are infinite sequences in A. We say thata is a⃗ reductionof⃗b with respect toF, and writea⃗≤_F⃗b iff there are finite sequences⃗b_nand orderly terms f_n overFfor n∈ω such that⃗b₀∗ ⃗b₁∗ ⃗b₂∗ ⋯ is a subsequence of⃗b anda(n) =⃗ f_n(⃗b_n)for all n∈ω.

(3)

Definition 2.3. Supposea,⃗⃗b are finite sequences in A. We say thata is a⃗ reductionof⃗b, and writea⃗⊴_F ⃗b iff there are finite sequences⃗b_nand orderly terms f_noverF for n< ∣ ⃗a∣such that⃗b₀∗ ⃗b₁∗ ⋯ ∗ ⃗b_∣⃗_a∣−1is a subsequence of⃗b anda⃗= ⟨f₀(⃗b₀),f₁(⃗b₁), . . . ,f_∣⃗_a∣−1(⃗b_∣⃗_a∣−1)⟩.

It is easy to check that≤_F is a pre-partial ordering on ^ωAand that⊴_F is a pre-partial ordering on^<ωA. Our definitions of≤_F and⊴_F are equivalent to a special case of the ones given in [2], where the collection of operations contains all projections.

Lemma 2.1. Supposea,⃗⃗b are infinite sequences in A. Thena⃗≤_F⃗b if and only if every initial segment ofa is a reduction of some initial segment of⃗ ⃗b.

Proof. The only if direction is immediate from the definition of≤_F. The if direction is proved in Lemma 4.3 of [2].

Definition 2.4. Suppose⃗b is an infinite sequence in A. An element a of A is afinite reduction of⃗b with respect toFiff a is equal to f(⃗b0)for some orderly term f overFand some finite subsequence⃗b0of⃗b. DefineFRF(⃗b)to be the set of all finite reductions of⃗b with respect to F.

Note that ifa⃗≤_Fb, then FR_F( ⃗a) ⊆FR_F(⃗b).

Definition 2.5. We say that(A,F )is Ramsey iff for everya⃗∈^ωA and every X⊆A, there exists⃗b≤_Fa such that⃗ FR_F(⃗b)is either contained in or disjoint from X .

It is a consequence of Hindman’s Theorem that every semigroup is a Ramsey algebra (Corollary 5.15 in [10]). There are examples of Ramsey algebras which are not semigroups (see [14]).

Every subalgebra of a Ramsey algebra is Ramsey. In fact, it is easy to see that assuming F is countable,(A,F )is a Ramsey algebra if and only if every countable subalgebra is Ramsey.

Definition 2.6. Suppose U is an ultrafilter on A. We say that U isstrongly reductiblefor Fiff for every X∈U , there existsa⃗∈^ωA such thatFR_F( ⃗a) ⊆X andFR_F( ⃗a−n) ∈U for all n∈ω.

Remark 2.1. By Lemma 2.2 in [8],U is a strongly summable ultrafilter if and only if for everyX∈U, there existsa⃗∈^ωNsuch that FS( ⃗a) ⊆Xand FS( ⃗a−n) ∈Ufor alln∈ω. Hence, strongly reductible ultrafilters are indeed generalizations of strongly summable ultrafilters.

Suppose(A,F )is an algebra such that for everya⃗∈^ωA, there exists⃗b≤_F a⃗such that

∣FR_F(⃗b)∣ =1. Then(A,F )is trivially Ramsey, and we say that it is adegenerate Ramsey algebra.

Lemma 2.2. Suppose(A,F )is a nondegenerate Ramsey algebra. Then there existsa⃗∈^ωA such thatFR_F(⃗b)is infinite whenever⃗b≤_Fa.⃗

Proof. First, we will show the following: if FR_F( ⃗a)is finite, then there exists⃗b≤_Fa⃗such that∣FR_F(⃗b)∣ =1. Choose⃗b≤_Fa⃗such that∣FR_F(⃗b)∣ ≤ ∣FR_F(⃗c)∣for allc⃗≤_Fa. We claim⃗ that ∣FR_F(⃗b)∣ =1. Suppose not. LetX be a nonempty proper subset of FR_F(⃗b). Since (A,F ) is a Ramsey algebra, choose c⃗≤_F ⃗b such that FR_F(⃗c)is either contained in or disjoint fromX. In either case, FR_F(⃗c)is a proper subset of FR_F(⃗b), contradicting the minimality of⃗b, as⃗cis also a reduction ofa.⃗

(4)

To prove the lemma, we argue by contradiction. Fixa⃗∈^ωA. Then there exists⃗b≤_F a⃗ such that FR_F(⃗b)is finite. By the previous claim, there exists a reductionc⃗of⃗b(and thus ofa) such that⃗ ∣FR_F(⃗c)∣ =1. Sincea⃗is arbitrary,(A,F )is degenerate, contradicting the hypothesis.

To say thata∈Ais anidempotentelement for an algebra(A,F )means thatf(a, . . . ,a) =a for every f ∈ F. Note that if FR_F( ⃗a) = {c}, thencis anidempotent element for(A,F ).

Suppose(A,F )is a degenerate Ramsey algebra. Then clearly every principal ultrafilter on Agenerated by an idempotent element of(A,F )is strongly reductible forF. The following example shows that a nonprincipal ultrafilter strongly reductible forFneed not exist.

Example 2.1. Suppose f is a constant binary operation onω, say f(x,y) =cfor allx,y∈ω. Trivially,(ω,{f})is a degenerate Ramsey algebra. Nevertheless, there is no nonprincipal ultrafilter onω strongly reductible for{f}. To see this, simply consider the cofinite set ω/{c}.

3. The main results

Suppose(A,F )is an algebra. We will restrict our attention to the case where the underlying setAis countable. We will address the general case at the end of this section. Without loss of generality, we may assumeAis equal toω.

From now on, fixFto be a collection of operations onωuntil we say otherwise. Hence, we will say “a strongly reductible ultrafilter” to mean an ultrafilter onωstrongly reductible forF. We will show under special set theoretic axioms that if(ω,F )is a nontrivial Ramsey algebra, then there exists a strongly reductible ultrafilter. We will follow Hindman’s foot- steps by first proving this result under the Continuum Hypothesis and then under Martin’s Axiom. In doing so, we can highlight how Martin’s axiom is used to prove a main lemma when the Continuum Hypothesis is absent.

Definition 3.1. Supposea,⃗⃗b∈^ωω. We say thata is⃗ eventually a reductionof⃗b, and write a⃗≤^∗_F⃗b iffa⃗−n≤_F⃗b for some n∈ω.

SinceF is fixed, to improve readability, we will simply write≤^∗,≤and FR( ⃗a)for≤^∗_F,

≤_F and FR_F( ⃗a)respectively.

Note that≤^∗is a pre-partial ordering on^ωω. Transitivity of≤^∗follows easily from the transitivity of≤.

For convenience, when we say that a finite sequencea⃗is a reduction of an infinite se- quence⃗b, it is understood thata⃗is a reduction of some initial segment of⃗b.

Lemma 3.1. Suppose⟨ ⃗a_n⟩_n∈ωis a sequence in^ωω such thata⃗_n+1≤^∗a⃗_nfor all n∈ω. Then there exists⃗b∈^ωωsuch that⃗b−n≤ ⃗a_nfor all n∈ω.

Proof. Suppose⟨ ⃗a_n⟩_n∈ωis as stated. We will define a sequence⟨M_n⟩_n∈ωof natural numbers inductively as follows. LetM₀=0. SupposeM_nhas been chosen. Sincea⃗_n+1≤^∗a⃗_n, we can choose M_n+1>M_n such thata⃗_n+1−M_n+1≤ ⃗a_n− (M_n+1). Take ⃗b to be the sequence

⟨ ⃗a_n(M_n)⟩_n∈ω. We will show that⃗b−nis in fact a reduction ofa⃗_n−M_n for alln∈ω. By Lemma 2.1, it suffices to show that every initial segment of⃗b−nis a reduction ofa⃗_n−M_n. This follows from the following claim.

Claim.Supposem∈ω. For each 0≤n≤m, the sequence⟨ ⃗a_n(M_n), . . . ,a⃗_m(M_m) ⟩is a reduction ofa⃗_n−M_n.

(5)

Fixm∈ω. Proceed by inverse induction on n. For the base stepn=m, it is clear that

⟨ ⃗a_m(M_m) ⟩is a reduction ofa⃗_m−M_m. For the inductive step, suppose⟨ ⃗a_n(M_n), . . . ,a⃗_m(M_m) ⟩ is a reduction ofa⃗_n−M_n. Sincea⃗_n−M_n≤ ⃗an−1− (Mn−1+1)by our construction,⟨ ⃗a_n(M_n), . . ., a⃗_m(M_m) ⟩is a reduction ofa⃗n−1− (Mn−1+1). It follows that⟨ ⃗an−1(Mn−1), . . . ,a⃗_m(M_m) ⟩is a reduction ofa⃗n−1−Mn−1. The claim is proved.

Lemma 3.2. Assumeλ is a limit ordinal such that cof(λ) =ω. Suppose⟨ ⃗a_α⟩_α∈λ is a transfinite sequence in^ωω such thata⃗_α≤^∗a⃗_β wheneverβ <α. Then there exists⃗b∈^ωω such that⃗b≤^∗a⃗_α for allα<λ.

Proof. Suppose ⟨ ⃗a_α⟩_α∈λ is as stated. Choose a strictly increasing sequence of ordinals γ0,γ1, . . . cofinal inλ. Clearlya⃗_γ_n+1≤^∗a⃗_γ_n whenevern∈ω. By Lemma 3.1, we can find a sequence⃗bsuch that⃗b−nis a reduction ofa⃗_γ_n for alln∈ω. We claim that this⃗bworks. Fix anyα<λ. Choosensuch thatγn>α. By the hypothesis,a⃗_γ_n is eventually a reduction of a⃗_α. Since⃗b−nis a reduction ofa⃗_γ_n, it follows that⃗b−nis eventually a reduction ofa⃗_αby transitivity.

Theorem 3.1. Assume the continuum hypothesis. Suppose(ω,F )is a nondegenerate Ram- sey algebra. Then there exists a nonprincipal strongly reductible ultrafilter.

Proof. By Lemma 2.2, we can choose a sequencea⃗such that FR(⃗b)is infinite whenever

⃗b≤ ⃗a. SupposeXα(α<ω1)enumerates all subsets ofω. By transfinite recursion, for each α<ω1we will constructa⃗α∈^ωωsuch that

● FR( ⃗aα)is infinite;

● either FR( ⃗aα) ⊆Xαor FR( ⃗aα) ⊆ω/Xα;

● a⃗_α≤^∗a⃗_β wheneverβ<α.

We will use the Ramsey property of(ω,F )repeatedly in the construction. Firstly, choose a⃗₀to be a reduction ofa⃗such that either FR( ⃗a₀) ⊆X₀or FR( ⃗a₀) ⊆ω/X₀. Supposeλ<ω₁ anda⃗_αfor eachα<λ have been constructed. There are two cases. Ifλ=β+1 for someβ, then we can choosea⃗_λto be any reduction ofa⃗_β such that FR( ⃗a_λ) ⊆X_λ or FR( ⃗a_λ) ⊆ω/X_λ. Now suppose λ is a limit ordinal. Sinceλ <ω1, we have cof(λ) =ω. Therefore, by Lemma 3.2 we can choose a sequence⃗bsuch that⃗b≤^∗a⃗_α for everyα<λ. Choosea⃗_λ to be any reduction of⃗bsuch that FR( ⃗a_λ) ⊆X_λ or FR( ⃗a_λ) ⊆ω/X_λ. By transitivity,a⃗_λ≤^∗a⃗_α for everyα<λ. By the transitivity of≤^∗and the choice ofa⃗₀, we havea⃗_λ−N≤ ⃗afor some N∈ω. By the hypothesis, FR( ⃗a_λ−N)is infinite, and so is FR( ⃗a_λ).

Now, for eachα<ω1letFαbe the filter generated by the sets FR( ⃗aα−n), meaning F_α= {X⊆ω∣FR( ⃗a_α−n) ⊆Xfor somen∈ω}.

Supposeβ <α<ω1. By our construction,a⃗_α−N≤ ⃗a_β for someN∈ω. This implies that a⃗_α− (N+n) ≤ ⃗a_β−nand hence FR( ⃗a_α− (N+n)) ⊆FR( ⃗a_β−n)for eachn∈ω. It follows easily thatF_β ⊆F_α.

TakeUto be⋃_α<ω₁F_α. It is a standard routine argument to show thatUis an ultrafilter.

SupposeX∈U, sayX=X_αfor someα<ω1. Then it must be the case that FR( ⃗a_α) ⊆X. By our construction, FR( ⃗a_α)is infinite, and so isX. Furthermore, FR( ⃗a_α−n) ∈F_α⊆Ufor all n∈ω. Therefore,Uis nonprincipal and strongly reductible.

Without the continuum hypothesis,cof(λ)need not beωfor every limit ordinalλ<c.

Hence, we need Lemma 3.2 to hold without the assumption thatcof(λ) =ω. Martin’s axiom is sufficient for this.

(6)

Before we prove the main lemma, let us remind the reader of the version of Martin’s Axiom that we shall use. Suppose(Q,≼)is a pre-partially ordered set. A subsetDofQis said to be anantichainiff for every distincta,b∈D, there does not existc∈Qsuch thatc≼a andc≼b. We say that(Q,≼)satisfies thecountable chain conditioniff every antichain inQ is countable. A subsetDofQis said to bedenseinQiff for everya∈Q, there existsd∈D such thatd≼a. A non-empty subsetGofQis called afilteriff

(1) for everya∈Gandb∈Q, ifa≼bthenb∈G;

(2) for everya,b∈G, there existsc∈Gsuch thatc≼aandc≼b.

Supposeκ is an infinite cardinal. MA(κ)asserts that if Qis a pre-partially ordered set satisfying the countable chain condition andFis a family of dense subsets ofQfor which

∣F ∣ <κ, then there exists a filter inQwhich intersects every set inF. Martin’s Axiom states thatMA(κ)holds for all infinite cardinalsκ<c. SinceMA(ω)is true, Martin’s Axiom is a consequence of the continuum hypothesis.

Lemma 3.3. Supposeλ <cis a limit ordinal and assumeMA(∣λ∣). If⟨ ⃗a_α⟩_α∈λ is a transfinite sequence in^ωωsuch thata⃗_α≤^∗a⃗_β wheneverβ<α, then there exists⃗b∈^ωω such that

⃗b≤^∗a⃗αfor allα<λ.

Proof. In this proof,a⃗=^∗⃗bmeans there existm,n∈ωsuch thata⃗−m= ⃗b−n. (The motivation for this is that the filter generated by the sets FR( ⃗a−n)is the same as the filter generated by the sets FR(⃗b−n)whenevera⃗=^∗⃗b.)

Suppose⟨ ⃗a_α⟩_α∈λ is given as stated. LetS= { ⃗a∈^ωω∣ ⃗a=^∗a⃗_αfor someα<λ}. We will need the observation thata⃗≤^∗⃗bor⃗b≤^∗a⃗whenevera,⃗⃗b∈S. Let

Q= { (n,a) ∣⃗ n∈ω,a⃗∈S} and define for every(m,a),⃗ (n,⃗b) ∈Q,

(m,a) ≼ (n,⃗ ⃗b)if and only ifm≥n,a⃗↾n= ⃗b↾nanda⃗≤ ⃗b.

Claim.(Q,≼)is a pre-partial ordering with the countable chain condition.

It is easy to check that≼is reflexive and transitive. Suppose(n,a)⃗ and(n,⃗b)are elements of an antichain such thata⃗↾n= ⃗b↾n. We will show that(n,a) = (n,⃗ ⃗b). The countable chain condition will then follow as this induces a one-to-one map from the antichain into the set of finite sequences in ω. We may assume thata⃗≤^∗⃗b. Then we can chooseN≥n such thata⃗−N≤ ⃗b−n. Letc⃗= ⃗a↾n∗ ( ⃗a−N). It is clear that(n,c) ∈⃗ Qand(n,c) ≼ (n,⃗ a). Since⃗ a⃗↾n= ⃗b↾n, we havea⃗↾n∗ ( ⃗a−N) ≤ ⃗b↾n∗ (⃗b−n)implying that⃗c≤ ⃗b. Hence,(n,c) ≼ (n,⃗ ⃗b) as well. Since(n,a)⃗ and(n,⃗b)belong to an antichain,(n,a)⃗ and(n,⃗b)cannot be distinct.

The claim is proved.

Now, consider the following subsets ofQ.

D(α) = { (n,a) ∈⃗ Q∣ ⃗a−n≤ ⃗a_α}, α<λ E(m) = { (n,a) ∈⃗ Q∣n≥m}, m∈ω Claim.D(α)andE(m)are dense subsets ofQ.

Suppose(n,a) ∈⃗ Q. Then(max{m,n},a) ≼ (n,⃗ a)⃗ and(max{m,n},a) ∈⃗ E(m). Hence, E(m)is dense inQ.

Fixα<λ. To see thatD(α)is dense inQ, suppose(n,a) ∈⃗ Q. Sincea⃗_α,a⃗∈S, either a⃗_α≤^∗a⃗ora⃗≤^∗a⃗_α. Assumea⃗_α≤^∗a. Then we can choose⃗ N≥nsuch thata⃗_α−N≤ ⃗a−n.

(7)

Letc⃗= ⃗a↾n∗ ( ⃗a_α−N). Otherwise, assumea⃗≤^∗a⃗_α. Then we can chooseN≥nsuch that a⃗−N≤ ⃗aα. Letc⃗= ⃗a↾n∗ ( ⃗a−N). In either case, we can easily verify that(n,c) ≼ (n,⃗ a)⃗ and (n,⃗c) ∈D(α). The claim is proved.

Therefore,{D(α) ∣α<λ} ∪ {E(m) ∣m∈ω}is a family of dense subsets ofQof size

∣λ∣. ByMA(∣λ∣), choose a filterGonQthat intersects all these subsets. Let

⃗b= ⋃{ ⃗a↾n∣ (n,a) ∈⃗ G}.

We claim that⃗bis a function onω. Suppose(n,a),(n⃗ ^′,a⃗^′) ∈G. SinceGis a filter, choose (n^′′,a⃗^′′) ∈Gsuch that(n^′′,a⃗^′′) ≼ (n,a)⃗ and(n^′′,a⃗^′′) ≼ (n^′,a⃗^′). This means thata⃗^′′↾n= ⃗a↾n anda⃗^′′↾n^′= ⃗a^′↾n^′, implying thata⃗↾nanda⃗^′↾n^′are compatible. It follows that⃗b is a function. To see that the domain of⃗bisω, supposem∈ω. SinceG∩E(m+1) ≠ ∅, choose (n,a) ∈⃗ Gsuch thatn≥m+1. Thena⃗↾nis an initial segment of⃗b, so thatmis in the domain of⃗b.

It remains to prove that⃗b≤^∗a⃗_αfor allα<λ. Fixα<λ. Suppose(n,a) ∈⃗ G∩D(α). We claim that⃗b−n≤ ⃗a_α. By Lemma 2.1, it suffices to show that every initial segment of⃗b−n is a reduction ofa⃗_α. Fixm>n. SinceG∩E(m) ≠ ∅, choose(m^′,c) ∈⃗ Gwithm^′≥m. By the definition of⃗b, it suffices to show that⟨⃗c(n), . . . ,c(m⃗ ^′−1)⟩is a reduction ofa⃗_α. Choose (m^′′,d⃗) ∈Gsuch that (m^′′,d) ≼ (n,⃗ a)⃗ and(m^′′,d⃗) ≼ (m^′,c). Since⃗ d⃗↾m^′= ⃗c↾m^′, the sequence⟨⃗c(n), . . . ,c(m⃗ ^′−1)⟩is equal to⟨ ⃗d(n), . . . ,d⃗(m^′−1)⟩. Meanwhile,d⃗≤ ⃗aimplies thatd⃗−nis a reduction ofa⃗−n, which in turn is a reduction ofa⃗_α because(n,a) ∈⃗ D(α).

Therefore,⟨ ⃗d(n), . . . ,d(m⃗ ^′−1)⟩is a reduction ofa⃗_α, and so is⟨⃗c(n), . . . ,c(m⃗ ^′−1)⟩. This completes the proof of the theorem.

Theorem 3.2. Assume Martin’s Axiom. Suppose(ω,F )is a nondegenerate Ramsey algebra. Then there exists a nonprincipal strongly reductible ultrafilter.

Proof. This is similar to the proof of Theorem 3.1. At the limit stage, to get a sequence⃗b such that⃗b≤^∗a⃗_αfor allα<λ, use Lemma 3.3 instead of Lemma 3.2.

Now, we will address the case where the underlying set is not assumed to be countable.

Theorem 3.3. Assume Martin’s axiom. Suppose(A,F )is a nondegenerate Ramsey algebra and thatF is countable. Then there exists a nonprincipal ultrafilter U on A strongly reductible forF.

Proof. Let(B,G )be the smallest subalgebra of(A,F )generated by{ ⃗a(i) ∣i∈ω}, where G = {f↾B∣ f ∈ F }. SinceF is countable,(B,G )is a countable Ramsey algebra. Apply- ing Theorem 3.2 withBidentified asω, choose a nonprincipal ultrafilterU onBstrongly reductible forG. LetV be{X⊆A∣X∩B∈U}. ThenV is a nonprincipal ultrafilter onA.

Furthermore, strongly reductibility ofUforGeasily implies strongly reductibility ofV for F.

4. Concluding remarks and open problems

Suppose(A,F )is an algebra and supposeUis an ultrafilter onA. Consider the property for eachX∈U, there existsa⃗∈^ωAsuch that FR_F( ⃗a) ⊆Xand FR_F( ⃗a) ∈U.(∗) Property∗is weaker than strongly reductible. It seems natural to have definedUwith the property∗ to be strongly reductible. In fact, various results for strongly summable ultrafilters have been generalized in [9] and [11] to infinite abelian groups, where the analogue

(8)

of a strongly summable ultrafilter is defined to be the one having property∗. We do not know whether the two possible definitions are equivalent in general and for abelian groups in particular. Our choice of definition is partially motivated by the following observation:

an ultrafilter strongly reductible forFis immediately an ultrafilter idempotent forF, analogous to the fact that a strongly summable ultrafilter is an idempotent ultrafilter. Because a general Ramsey algebra lacks a certain algebraic property, like that enjoyed by abelian groups, our choice of definition is plausible.

Meanwhile, the analogue of the independence result for strongly summable ultrafilters does not hold in general for Ramsey algebras. It follows from [9] that the existence of nonprincipal strongly reductible ultrafilters for an infinite abelian group cannot be proven inZFC. On the other hand, supposeP(x,y) =xfor allx,y∈ω. Then(ω,{P})is trivially a Ramsey algebra and every nonprincipal ultrafilter onω is strongly reductible for{P}.

Therefore, it is natural to ask for a subclass of Ramsey algebras properly containing the class of infinite abelian groups such that the existence of the corresponding strongly reductible ultrafilters is independent ofZFC.

Acknowledgement. This paper grows out of the author’s thesis submitted as a partial ful- filment for the award of PhD to the Ohio State University under the supervision of Timothy Carlson. The definition of Ramsey algebras is due to Carlson. The author would like to thank Carlson for introducing the concept of Ramsey algebras and for his critical insights that lead to the generation of this paper. Furthermore, the author appreciates the comments provided on the draft, which have helped to polish the paper in its present form.

References

[1] A. Blass and N. Hindman, On strongly summable ultrafilters and union ultrafilters,Trans. Amer. Math. Soc.

304(1987), no. 1, 83–97.

[2] T. J. Carlson, Some unifying principles in Ramsey theory,Discrete Math.68(1988), no. 2-3, 117–169.

[3] W. W. Comfort, Ultrafilters: some old and some new results,Bull. Amer. Math. Soc.83(1977), no. 4, 417–

455.

[4] E. Ellentuck, A new proof that analytic sets are Ramsey,J. Symbolic Logic39(1974), 163–165.

[5] N. Hindman, The existence of certain ultra-filters onNand a conjecture of Graham and Rothschild,Proc.

Amer. Math. Soc.36(1972), 341–346.

[6] N. Hindman, Finite sums from sequences within cells of a partition ofN,J. Combinatorial Theory Ser. A17 (1974), 1–11.

[7] N. Hindman, Ultrafilters and combinatorial number theory, inNumber Theory, Carbondale 1979 (Proc.

Southern Illinois Conf., Southern Illinois Univ., Carbondale, Ill., 1979), 119–184, Lecture Notes in Math., 751, Springer, Berlin.

[8] N. Hindman, Summable ultrafilters and finite sums, inLogic and combinatorics (Arcata, Calif., 1985), 263–

274, Contemp. Math., 65, Amer. Math. Soc., Providence, RI.

[9] N. Hindman, I. Protasov and D. Strauss, Strongly summable ultrafilters on abelian groups,Mat. Stud.10 (1998), no. 2, 121–132.

[10] N. Hindman and D. Strauss,Algebra in the Stone- ˇCech Compactification, second revised and extended edition [of MR1642231], de Gruyter Textbook, de Gruyter, Berlin, 2012.

[11] P. Krautzberger, On strongly summable ultrafilters,New York J. Math.16(2010), 629–649.

[12] S. Shelah,Proper and Improper Forcing, second edition, Perspectives in Mathematical Logic, Springer, Berlin, 1998.

[13] W. C. Teh, Ramsey algebras, (submitted).

[14] W. C. Teh, Ramsey algebras and formal orderly terms,Notre Dame J. Form. Log.(to appear).