1 Introduction
In [Reference Milliken1], Carlson introduced the notion of a Ramsey space, now called a topological Ramsey space following Todorocevic’s extension of the work [Reference Teoh21]. When the Ramsey space is generated by an algebra, Carlson has suggested that a purely combinatorial approach might be possible. In his doctoral work, Teh pursued this theme and the study has since been known as Ramsey algebra [Reference Teh12].
An algebra is a structure consisting of a family of sets, called the domains of the algebra, and a family of operations on these sets. For instance, groups
$(G, \circ )$
are algebras, as are rings and fields
$(R, +, \times )$
. Groups, rings, and fields are what we refer to as homogeneous algebras. Such algebras have only one type of domain, G or R as indicated above. These are contrasted with heterogeneous algebras, a typical example which is a vector space, where its domains consist of the set of vectors as well as the set of scalars. Of course, homogeneous algebras are special cases of heterogeneous algebras.
Our concern in this paper is solely on homogeneous algebras. Arguably, Ramsey theory in algebras has roots in Hindman’s theorem. It states that, for each positive integer r and each coloring
$c:\mathbb {Z}^+\to \{1, \ldots , r\}$
, there exists an infinite
$S\subseteq \mathbb {Z}^+$
such that c is constant on the set
$\text {FS}=\left \{\sum _{i\in F} i:F\subseteq S, F\:\text {is finite}\right \}$
. The same theorem can be cast in terms of finite subsets of the natural numbers [Reference Sankappanavar and Burris8]. On the other hand, Erdös–Rado [Reference Ellentuck4] showed that the corresponding property for arbitrary colorings of infinite sets of natural numbers is false. The counterexample considered by Erdős–Rado made use of the Axiom of Choice and is hence non-constructive. On the contrary, Galvin–Prikry [Reference Erdos and Rado5] showed that Borel colorings possess Ramsey property and, using the method of forcing, Silver [Reference Teh11] showed that analytic colorings also do.
Ellentuck [Reference Chang and Keisler3] came into the scene by showing that the result of Silver could also be proved using a topological formulation without having to appeal to metamathematical methods. In his proof, Ellentuck introduced what is to be called the Ellentuck topology. Seeing the potential in such an argument, Carlson [Reference Milliken1] arrived at a generalization, the notion of a (topological) Ramsey space. The power of Ramsey spaces lies in the ability to derive as corollaries classical results such as the Hales–Jewett theorem and Hindman’s theorem, which Carlson showed in that same paper.
If one is to ask whether a given structure is a Ramsey space, the definition requires that one checks some topological properties of the space. However, Carlson’s abstract version of Ellentuck’s theorem turns a topological question into a combinatorial one (cf. [Reference Milliken1] and [Reference Todorcevic19]). Some early works on Ramsey algberas include [Reference Silver9, Reference Teh13–Reference Teh and Teoh15]. Two articles on heterogeneous Ramsey algebras can be found in [Reference Todorcevic19, Reference Teh20]. The two doctoral theses [Reference Teh12, Reference Rajah, Teh and Teoh18] may also be of interest.
In this paper, we investigate some structural questions pertaining to Ramsey algebras. In particular, we study the property of being Ramsey under the notions of elementary equivalence and elementary extension. The direct limit of a family of Ramsey algebras is also investigated. We also give a partial answer to a question that has been asked since the inception of Ramsey algebras, namely the question of whether the Cartesian product of arbitrarily many Ramsey algebras is also Ramsey (cf. [Reference Rajah, Teh and Teoh18], p. 116 and Section 7—Open Problems of [Reference Teoh and Teh14]).
We fix some symbols and conventions.
$\omega $
will denote the set of natural numbers
$0, 1, 2, \ldots $
If D is a set, then
$\operatorname {\mathrm {id}}_D$
denotes the identity function on D. If
$\sigma $
is a finite sequence or an n-tuple, then
$|\sigma |$
denotes the length n of the sequence or n-tuple. If A is a nonempty set, an infinite sequence of A is an element of
${^\omega }A$
. A sequence, finite or infinite, will be denoted by an arrow over a Roman alphabet such as
$\vec {b}$
. If
$\mathcal {A}$
is a model of a first order language, its universe will either be denoted by the associated unscripted capital alphabet A or by
$|\mathcal {A}|$
. Finally, we denote the concatenation operation by
$\ast $
in this paper.
We assume the Axiom of Choice throughout.
2 Ramsey algebras
As mentioned in the previous section, we will only be concerned with homogeneous algebras in this paper, hence we will circumvent the more general notions pertaining to heterogeneous algebras. The interested reader can find the more general treatment in Carlson’s original paper [Reference Milliken1] as well as in [Reference Todorcevic19, Reference Teh20].
We assume that the reader is familiar with first-order logic. In particular, we will not give the precise definitions of elementary equivalence, elementary extension, and direct limit. Now, from a logical point of view, an algebra is a structure interpreting a purely functional language. That is, an algebra
$\mathcal {A}$
consists of a universe A and a family
$\mathcal {F}$
of finitary operations (i.e., functions)Footnote
1
on A, i.e., each
$f\in \mathcal {F}$
has as domain some finite Cartesian product
$A^n$
and codomain A. We write
$\mathcal {A}=(A, \mathcal {F})$
for the algebra just described. An algebra is said to be infinite if its universe is infinite; it is finite otherwise. An algebra whose family of operations consist only of unary functions will be called a unary system or unary algebra.
Our first formal definition deals with a certain type of composition of operations. The definition here is a slight modification of the original one given in Definition 3.6 by Carlson [Reference Milliken1].
Definition 2.1 (Orderly Composition & Orderly Terms).
Let
$\mathcal {F}$
be a family of operations on A. An n-ary function f is called an orderly composition of
$\mathcal {F}$
if there exists
$h_1, h_2, \ldots , h_k, g\in \mathcal {F}$
such that
-
(1) g is a k-ary function,
-
(2)
$h_j$
is an
$n_j$
-ary function for each
$j\in \{1, 2, \ldots , k\}$
, -
(3)
$\sum _{j=1}^k n_j=n$
, and -
(4) if
$\vec {x}_1=(x_1, x_2, \ldots , x_{n_1})$
and for each
$j\in \{2$
,
$\ldots $
,
$k\}$
we have
$\vec {x}_j=\left (x_{\left (\sum _{i=1}^{j-1}n_i\right )+1}, x_{\left (\sum _{i=1}^{j-1}n_i\right )+2}, \ldots , x_{\sum _{i=1}^jn_i}\right )$
, then
$f(x_1, \ldots , x_n)=g(h_1(\vec {x}_1), h_2(\vec {x}_2),\ldots , h_k(\vec {x}_k))$
.
The collection
$\operatorname {\mathrm {OT}}(\mathcal {F})$
of orderly terms over
$\mathcal {F}$
is the smallest collection of operations containing
$\mathcal {F}\cup \left \{\operatorname {\mathrm {id}}_A\right \}$
and is closed under orderly composition.
The collection of orderly terms over
$\mathcal {F}$
is in fact the collection of operations on A which can be generated by an application of finitely many of the following more lucid rules:
-
(1)
$\text {id}_A$
is an orderly term, -
(2) every operation in
$\mathcal {F}$
is an orderly term, -
(3) if f is an operation on A given by
$f(\vec {x}_1, \vec {x}_2, \ldots , \vec {x}_k)=g(h_1(\vec {x}_1)$
,
$h_2(\vec {x}_2)$
,
$\ldots $
,
$h_k(\vec {x}_k))$
for some
$g\in \mathcal {F}$
and some orderly terms
$h_1$
,
$h_2$
,
$\ldots $
,
$h_k$
, then f is an orderly term.
In formal terms, suppose a function symbol is associated with each element of
$\mathcal {F}$
. The orderly terms over
$\mathcal {F}$
are defined by formal terms in which each variable in the term occurs exactly once and the variables appear “in order.”
Definition 2.2 (Reduction
$\leq _{\mathcal {F}}$
).
Let
$(A, \mathcal {F})$
be an algebra and let
$\vec {a}$
and
$\vec {b}$
be members of
${^\omega }A$
. Then
$\vec {a}$
is said to be a reduction of
$\vec {b}$
if there exist orderly terms
$f_j$
over
$\mathcal {F}$
and finite subsequences
$\vec {b}_j$
of
$\vec {b}$
such that
-
(1)
$\vec {a}(j)=f_j(\vec {b}_j)$
for each
$j\in \omega $
and -
(2)
$\vec {b}_0\ast \vec {b}_1\ast \cdots $
forms a subsequence of
$\vec {b}$
.
We write
$\vec {a}\leq _{\mathcal {F}}\vec {b}$
to mean
$\vec {a}$
is a reduction of
$\vec {b}$
.
The relation
$\leq _{\mathcal {F}}$
is a preorderFootnote
2
on
${^\omega }A$
. Note that the inclusion of the identity functions in the set of orderly terms is necessary to ensure that the relation
$\leq _{\mathcal {F}}$
is reflexive.
We pause to illustrate the two definitions above using the algebra
$(\mathbb {Z}^+, +)$
. (According to our notation above, the exact notation for this algebra should be written as
$(\mathbb {Z}^+, \{+\})$
. However, from this point onwards, we will drop the curly brackets encompassing the operations when the list is short.) Examples of orderly terms over
$\{+\}$
include
$+(x_0, +(x_1, x_2))$
and
$+(+(x_1, x_2), +(x_3, +(x_4, x_5)))$
. Note that the variables appear in order from left to right and no repetition occurs. Also from this point onward, we will write orderly terms involving common operations such as
$+$
is the more suggestive manner such as
$x_0+(x_1+x_2)$
and
$(x_1+x_2)+(x_3+(x_4+x_5))$
for the orderly terms above. Of course, since addition on
$\mathbb {Z}^+$
is associative, the bracketing does not matter, and we will even be omitting them and write
$x_0+x_1+x_2$
and
$x_1+x_2+x_3+x_4+x_5$
. We will revert to conventional notations whenever possible.
As for reduction, let
$\vec {b}=\langle 1, 3, 5, 7, \ldots \rangle $
. Then an example of a reduction of
$\vec {b}$
is
$\langle 6, 16, 53, 23, \ldots \rangle $
with the associated finite sequences and orderly terms given respectively by
$x_1+x_2$
on
$\langle 1, 5\rangle $
,
$x_1+x_2$
again but on
$\langle 7, 9\rangle $
,
$x_1+x_2+x_3$
on
$\langle 15, 17, 21\rangle $
, and
$\operatorname {\mathrm {id}}_{\mathbb {Z}^+}(x)$
on
$23$
, and so on.
For families consisting of unary operations, the orderly terms coincide with the familiar composite functions:
Remark 2.3. If
$\mathcal {F}$
is a family of unary operations on A, then
$\operatorname {\mathrm {OT}}(\mathcal {F})$
coincides with the set of all composites of functions in
$\mathcal {F}\cup \{\operatorname {\mathrm {id}}_A\}$
.
We continue with more definitions for Ramsey algebras. The next one is the generalization of the sets analogous to
$\text {FS}$
in the introductory section and are precisely those sets
$\text {FS}(\langle x_n\rangle _{n=1}^\infty )$
appearing in Chapter 5 of [Reference Galvin and Prikry6] in the context of the algebra
$(\mathbb {Z}^+, +)$
.
Definition 2.4. If
$\vec {b}$
is an an infinite sequence of A, then
$$ \begin{align*} \operatorname{\mathrm{FR}}_{\mathcal{F}}(\vec{b}) &= \{\vec{a}(0):\vec{a}\leq_{\mathcal{F}}\vec{b}\} \\ &= \{f(\sigma):f\in\operatorname{\mathrm{OT}}(\mathcal{F}), \sigma\;\text{ is a finite sequence of }\:\vec{b}\}. \end{align*} $$
We now arrive at the central notion of the paper.
Definition 2.5 (Ramsey algebra).
An algebra
$(A, \mathcal {F})$
is said to be a Ramsey algebra if, for each infinite sequence
$\vec {b}$
and each
$X\subseteq A$
, there exists
$\vec {a}\leq _{\mathcal {F}}\vec {b}$
such that
$\operatorname {\mathrm {FR}}_{\mathcal {F}}(\vec {a})$
is either contained in or disjoint from X. Such a sequence
$\vec {a}$
is said to be homogeneous for X (with respect to
$\mathcal {F}$
).
In the language of Ramsey algebras, Hindman’s theorem takes the following form (see Corollary 5.9 of [Reference Galvin and Prikry6]).
Theorem 2.6 (Hindman).
Every semigroup is a Ramsey algebra.
As mentioned earlier, the origin of Ramsey algebras has its roots in the notion a Ramsey space introduced by Carlson [Reference Milliken1]. Although implicit in Carlson’s original paper, readers who are interested in the exact connection between (topological) Ramsey spaces and Ramsey algebras may refer to Section 4 of [Reference Todorcevic19], which gives the explicit proof that every Ramsey algebra with some finitary properties yields a (topological) Ramsey space.
Carlson’s theorem on variable words, from which he derived many of the classical combinatorial theorems mentioned in the introduction, can be stated in terms of Ramsey algebras:
Theorem 2.7 (Carlson).
The algebra of variable words with finite alphabets equipped with the operations of “substitution” and “evaluation” is a Ramsey algebra.
Before we embark on an investigation of new questions, we state a few more results from past works.
Theorem 2.8. No infinite integral domain is a Ramsey algebra. In particular, no infinite division ring is a Ramsey algebra.
Corollary 2.9. No infinite ring with multiplicative identity having characteristic zero is a Ramsey algebra.
The theorem and its corollary above can be found in [Reference Teoh and Teh14]. The next theorem, which is found in the same paper, will play an important role in Section 4.
Theorem 2.10 (Characterization of Unary Ramsey algebras).
Let
$\mathcal {A}=(A, \mathcal {F})$
be a unary system. Then
$\mathcal {A}$
is a Ramsey algebra if and only if for each
$a\in A$
, there exists an
$F\in \operatorname {\mathrm {OT}}(\mathcal {F})$
such that
$F(a)\in \{x\in A:f(x)=x\;\text {for all}\;f\in \mathcal {F}\}$
.
This theorem will be used in conjunction with the predecessor function in Section 4. Points in the set
$\{x\in A:f(x)=x\;\text {for all}\;f\in \mathcal {F}\}$
will be called fixed points of
$\mathcal {F}$
and
$\operatorname {\mathrm {OT}}(\mathcal {F})$
coincides with the smallest set of composite functions containing
$\mathcal {F}$
. Thus, when applying the theorem above, we will often speak of a point being able to be sent to the set of fixed points by finitely many applications of the functions in
$\mathcal {F}$
.
3 Homomorphic algebras and quotients
Recall that the notion of homomorphism only applies to algebras with the same language. For the convenience of writing proofs, we give the definition of the notion of a homomorphism. If
$\mathcal {L}$
is a family of function symbols and
$\mathcal {A}_0=(A_0, \mathcal {F}_0), \mathcal {A}_1=(A_1, \mathcal {F}_1)$
are algebras of the language
$\mathcal {L}$
, then
$\pi :A_1\to A_0$
is said to be a homomorphism from
$A_1$
into
$A_0$
if
$$ \begin{align} \pi(f^{\mathcal{A}_1}(b_1, \ldots, b_n))=f^{\mathcal{A}_0}(\pi(b_1), \ldots, \pi(b_n)) \end{align} $$
for each
$f\in \mathcal {L}$
and each
$b_1, \ldots , b_n\in A_1$
. It follows that, if t is an
$\mathcal {L}$
-term and
$b_1, \ldots , b_n\in A_1$
, then
$$ \begin{align} \pi(t^{\mathcal{A}_1}(b_1, \ldots, b_n))=t^{\mathcal{A}_0}(\pi(b_1), \ldots, \pi(b_n)). \end{align} $$
In particular, Equation 2 holds for
$\mathcal {L}$
-terms interpreting orderly terms. The main result of this section is the fact that an epimorphism, i.e., a surjective homomorphism, preserves the property of being a Ramsey algebra.
Theorem 3.1. If
$\pi :A_1\to A_0$
is an epimorphism and
$(A_1, \mathcal {F}_1)$
is a Ramsey algebra, then
$(A_0, \mathcal {F}_0)$
is a Ramsey algebra.
Proof. Suppose
$\pi :A_1\to A_0$
is an epimorphism and
$(A_1, \mathcal {F}_1)$
a Ramsey algebra; let
$\vec {b}$
be an infinite sequence
$A_0$
and
$X\subseteq A_0$
. Set
$\vec {\beta }$
to be such that, for each
$i\in \omega $
,
$\vec {\beta }(i)$
is a representative of the preimage of
$\vec {b}(i)$
under
$\pi $
, the exact representative which is immaterial, and let
$Y=\{\alpha \in A_1:\pi (\alpha )\in X\}$
. We may now choose an
$\vec {\alpha }\leq _{\mathcal {F}_1}\vec {\beta }$
homogeneous for Y.
We claim that
$\vec {a}=\langle \pi (\vec {\alpha }(i)):i\in \omega \rangle $
is the desired reduction of
$\vec {b}$
. To see this, first note that
$\vec {a}$
is indeed a reduction of
$\vec {b}$
by appealing to Equation 2. Secondly, let
$c\in \operatorname {\mathrm {FR}}_{\mathcal {F}_0}(\vec {a})$
; thus, let t be a term of the language of the algebras interpreting an orderly term over
$\mathcal {F}_0$
and let
$n_1<\cdots <n_N$
be indices such that
$c=t^{\mathcal {A}_0}(\pi (\vec {\alpha }(n_1)), \ldots , \pi (\vec {\alpha }(n_N)))$
. By Equation 2, we obtain
$c=\pi (t^{\mathcal {A}_1}(\vec {\alpha }(n_1), \ldots , \vec {\alpha }(n_N)))$
. Thus, we see that c is the image of an element of
$\operatorname {\mathrm {FR}}_{\mathcal {F}_1}(\vec {\alpha })$
under
$\pi $
.
Therefore,
$\operatorname {\mathrm {FR}}_{\mathcal {F}_0}(\vec {a})\subseteq X$
or
$\operatorname {\mathrm {FR}}_{\mathcal {F}_0}(\vec {a})\subseteq A_0\setminus X$
depending respectively on whether
$\operatorname {\mathrm {FR}}_{\mathcal {F}_1}(\vec {\alpha })\subseteq Y$
or
$\operatorname {\mathrm {FR}}_{\mathcal {F}_1}(\vec {\alpha })\subseteq A_1\setminus Y$
. Thus, the homogeneity of
$\vec {a}$
for X is established.⊣
Corollary 3.2. The property of being a Ramsey algebra is an invariant under isomorphism.
The fact that isomorphic algebras have the same Ramsey algebraic property does not come as a surprise. In the next section, we will see that, on the other hand, elementary equivalence is not sufficient to warrant such invariance.
We end this section with quotient algebras. We learn from group theory and ring theory that being an equivalence relation on the elements of a group or ring itself does not warrant a well-defined quotient. In the case of groups, the condition on the relation is for the associated subgroup to be normal. In general, we need the equivalence relation to be a congruence. A congruence relation E on an algebra is one where every operation in the algebra is compatible with it:
Definition 3.3 (Compatible Relation & Congruence).
Let
$\mathcal {A}=(A, \mathcal {F})$
be an algebra, let E be an equivalence relation on
$|\mathcal {A}|$
, and let
$f\in \mathcal {F}$
. We say that E is compatible with f if
$f(a_1, a_2, \ldots , a_{|f|})Ef(b_1, b_2, \ldots , b_{|f|})$
whenever
$a_iEb_i$
for each
$i\in \{1, 2, \ldots , |f|\}$
. We say that E is a congruence relation on
$\mathcal {A}$
if E is compatible with every
$f\in \mathcal {F}$
.
A congruence relation E partitions the universe of an algebra
$\mathcal {A}$
in such a way that the operations on
$\mathcal {A}$
are well-defined on the resulting classes. To be precise, a congruence relation E ensures that the quotient map
$\rho :a\mapsto [a]$
from
$\mathcal {A}$
onto its quotient by E is a homomorphism (see the paragraph immediately following Definition 5.2 on p. 36 of [Reference Teh10]). Since such a homomorphism is epimorphic, we have the following:
Corollary 3.4. The quotient of a Ramsey algebra by a congruence relation is Ramsey.
An example of a congruence relation on an algebra is furnished by an ultrafilter, which we will have a chance to see in the next section.
4 Cartesian products, ultrapowers, and first-order properties
The predecessor function p on
$\omega $
plays an important role in this section and it is defined by
$$ \begin{align*} p(n) = \left\{ \begin{array}{lr} 0, & \text{if}\; n=0; \\ n-1, & \text{otherwise}. \end{array} \right. \end{align*} $$
p has exactly one fixed point, namely
$0$
. Theorem 2.10 in essence states that algebras whose families of operations are unary admit a simple characterization in terms of fixed points. Applying this characterization, we see that
$\mathcal {A}=(\omega , p)$
is a Ramsey algebra. We will call this algebra the predecessor algebra and we will denote it by
$\mathcal {A}$
throughout this section. The predecessor algebra allows us to show that the following three conjectures, desirable as they may be, are not true:
-
(1) Cartesian products of Ramsey algebras are Ramsey algebras.
-
(2) Ultrapowers of Ramsey algebras are Ramsey.
-
(3) Algebras that are elementarily equivalent have the same Ramsey algebraic property.
We will show that these statements are false in this section.
The question of whether Cartesian products of Ramsey algebras are Ramsey is a question that has been asked since the inception of the subject. Surprisingly, this question can be easily answered by the predecessor algebra. We state the definition of a Cartesian product of algebras for convenience:
Given a family of algebras
$\mathcal {A}_\xi =(A_\xi , \mathcal {F}_\xi )$
(with
$\xi \in \kappa $
,
$\kappa $
some cardinal) of the same language
$\mathcal {L}$
, the Cartesian product
$\mathcal {A}=(A, \mathcal {F})$
of this family is such that
-
a. the domain of
$\mathcal {A}$
is the Cartesian product
$\prod _{\xi <\kappa }A_\xi $
and -
b. for each operation
$f\in \mathcal {F}$
, if f interprets the function symbol
$F\in \mathcal {L}$
, then f acts coordinate-wise and each coordinate, say the
$\xi $
th coordinate, is acted by the corresponding operation
$f_\xi $
, which also interprets F.
Theorem 4.1. The infinite Cartesian product
$\mathcal {B}=\prod _{i\in \omega }\mathcal {A}$
of
$\mathcal {A}=(\omega , p)$
is not a Ramsey algebra. Hence, infinite Cartesian products of Ramsey algebras need not be Ramsey.
Proof. We again exploit the characterization given by Theorem 2.10. Consider the element
$\Omega =\langle 0, 1, 2, \ldots \rangle \in \prod _{i\in \omega }\omega $
of the Cartesian product. It can not be sent to the fixed point
$\varphi =\langle 0, 0, \ldots \rangle $
by any composition of the sole operation f in the algebra
$\mathcal {B}$
since each orderly term has the form
$f^n$
and
$f^n(\Omega )=\langle 0, 0, \ldots , 0, 1, 2, 3, \ldots \rangle $
, where the initial segment consisting of
$0$
’s has length
$n+1$
.⊣
It is essential that we are taking an infinite product of the predecessor algebra here. The general case when the product is finite remains open and any counterexample cannot be found in the Cartesian product of unary algebras. For, consider the product
$\mathcal {A}=\mathcal {A}_1\times \mathcal {A}_2$
of two Ramsey algebras consisting only of unary operations. The idea is that, using the characterization theorem of such algebras, we can send any point of the Cartesian product to a fixed point by operating on one component after another.
We can now take the quotient of the Cartesian product
$\mathcal {B}$
above by a nonprincipal ultrafilter on
$\omega $
to show that the resulting ultrapower is not Ramsey. This also establishes the fact that an algebra elementarily equivalent to a Ramsey algebra need not be Ramsey.
Theorem 4.2. No ultrapower of the predecessor algebra induced by a nonprincipal ultrafilter on
$\omega $
is Ramsey.
Proof. We begin by noting a few facts:
-
(1) Being a fixed point is a first-order property when the family of functions is finite (a singleton in our case here). It being unique is also a first-order property.
-
(2) That every point can be sent to a fixed point (
$0$
in particular) by finitely many applications of p is not a priori a first-order property. The statement “finitely-many” does not specify the exact number and it has infinitely many possibilities. We will need countably many disjunctions to express this fact. (This also allows us to give a compactness proof of the theorem, which we will give in the next corollary.) -
(3) That the point c can be sent to a fixed point by exactly n applications of p is a first-order property, and so is being the unique point that can be sent to the unique fixed point by exactly n applications of p. This statement differs from the one above by the fact that the finite number n is specified and so a finite number of disjunctions is sufficient to express it.
We will now make use of the first-order properties above. Let j be the canonical embedding of
$\mathcal {A}$
into its ultrapower
$\operatorname {\mathrm {Ult}}(\mathcal {A}, \mathcal {U})=\left (\prod _{i\in \omega }\omega \right )/\mathcal {U}$
along a nonprincipal ultrafilter
$\mathcal {U}$
on
$\omega $
. We will call the associated predecessor function in the ultrapower P. Firstly, since
$0$
is the unique fixed point of the predecessor function p, we see that
$[j(0)]$
is the unique class that is fixed by P. Furthermore,
$[j(n)]$
is the unique class that can be sent to
$[j(0)]$
by exactly n applications of P.
Given
$\vec {b}\in \prod _{i\in \omega }\omega $
, if
$\vec {b}$
can be sent to the unique fixed point
$[j(0)]$
, then
$[\vec {b}]$
must be
$\mathcal {U}$
-equivalent to
$[j(n)]$
for some
$n\in \omega $
by the uniqueness we just saw above. Thus,
$\vec {b}$
can be an unbounded sequence, but it must be equal to n on a
$\mathcal {U}$
-measure one set, i.e.,
$\{i\in \omega :\vec {b}(i)=n\}\in \mathcal {U}$
. Now, the sequence
$\omega =\langle 0, 1, 2, \ldots \rangle $
, which is a member of
$\prod _{i\in \omega }\omega $
, cannot be
$\mathcal {U}$
-equivalent to any
$[j(n)]$
, for that would require the set
$$ \begin{align*} \left\{i\in\omega:\omega(i)=n\right\}=\{n\}\in\mathcal{U}, \end{align*} $$
which cannot happen since
$\mathcal {U}$
is nonprincipal. This shows that
$\omega $
cannot be sent to the unique fixed point
$j[0]$
by an iterate of P. Therefore, the ultrapower
$\operatorname {\mathrm {Ult}}(\mathcal {A}, \mathcal {U})$
is not Ramsey by the characterization in Theorem 2.10. Since
$\mathcal {U}$
is an arbitrary nonprincipal ultrafilter, the statement is true for any ultrapower along a nonprincipal ultrafilter
$\mathcal {U}$
on
$\omega $
.⊣
By restricting to the
$\omega $
initial segment of larger cardinals, the same reasoning should also establish similar results for larger Cartesian products and ultraproducts. Now, as a consequence of the preceding theorem, we now know that the notion of a Ramsey algebra is not first-order characterizable:
Corollary 4.3. The notion of a Ramsey algebra is not necessarily preserved under elementary equivalence.
Proof. The corollary follows immediately from the elementary equivalence of an ultrapower. However, we provide an alternative proof using the compactness theorem here. This will also illustrate the point made in Fact 2 of the preceding proof. We will construct an elementarily equivalent algebra
$\mathcal {B}$
for which some points of its universe cannot be sent to some fixed points of its associated operation
$\phi $
.
Let
$\mathcal {L}=\{F\}$
be the language of the algebra
$\mathcal {A}$
. Augment
$\mathcal {L}$
with the constant symbol
$\zeta , c$
and call the language
$\mathcal {L}^*$
. Consider the
$\mathcal {L}^*$
-theory
$T=\operatorname {\mathrm {Th}}(\mathcal {A})\cup \{F(\zeta )=\zeta \}\cup \{F^i(c)\neq \zeta :i\in \omega \}$
. Note that we immediately have
$T\models c\neq \zeta $
.
Let
$\Delta $
be a finite subset of T. If
$\Delta \cap \{F^i(c)\neq \zeta :i\in \omega \}\neq \varnothing $
, let
$n\in \omega $
be greatest such that
$F^n(c)\neq \zeta \in \Delta $
. Clearly, interpreting
$\zeta $
by
$0$
and interpreting c by
$n+1$
, the expansion
$\mathcal {A}_n$
of
$\mathcal {A}$
to the expanded language
$\mathcal {L}^*$
is a model of
$\Delta $
. Hence, by compactness, T is satisfiable. Fix one such model and call it
$\mathcal {B}^*$
.
Now,
$\mathcal {A}\models \exists !x(F(x)=x)$
, so
$\exists !x(F(x)=x)\in T$
, whereby
$\mathcal {B}^*\models \exists !x(F(x)=x)$
. In particular, this implies that
$T\models \forall x(F(x)=x\rightarrow x=\zeta )$
. Now, according to
$\Delta $
, the point
$c^{\mathcal {B}^*}\in B$
is such that
$\phi ^i(c^{\mathcal {B}^*})\neq \zeta ^{\mathcal {B}^*}$
for each
$i\in \omega $
. This says that
$c^{\mathcal {B}^*}$
cannot be sent to the only fixed point
$\zeta ^{\mathcal {B}^*}$
by finitely many applications of
$\phi $
. As such, the reduct
$\mathcal {B}=(B, \phi )$
of
$\mathcal {B}^*$
to
$\mathcal {L}$
is clearly an algebra in which
$\mathcal {B}\equiv \mathcal {A}$
and
$\phi ^i(c^{\mathcal {B}^*})\neq \zeta ^{\mathcal {B}^*}$
for each
$i\in \omega $
, so
$\mathcal {B}$
is not a Ramsey algebra by Theorem 2.10.⊣
Before we end this section, we state two propositions about two special cases of Cartesian products. These special cases deal primarily with finite Ramsey algebras and they can be found in Section 6 of the thesis [Reference Rajah, Teh and Teoh18]. The following theorem, which is part of Theorem 3.9 of [Reference Teoh and Teh14], will be applied. It should be reminded that Cartesian products are only defined for algebras modeling the same language
$\mathcal {L}$
.
Theorem 4.4. Suppose that
$(A, \mathcal {F})$
is a finite algebra. Then it is Ramsey if and only if for each
$\vec {b}\in {^\omega }A$
, there exists
$\vec {a}\in {^\omega }A$
such that
$\vec {a}\leq _{\mathcal {F}}\vec {b}$
and
$\operatorname {\mathrm {FR}}_{\mathcal {F}}(\vec {a})$
is a singleton.
Proposition 4.5. The Cartesian product of finitely many finite Ramsey algebras is a Ramsey algebra.
Proof. It suffices to show that the statement holds for the Cartesian product of two Ramsey algebras.
Assume that
$\mathcal {A}_1=(A_1, \mathcal {F})$
and
$\mathcal {A}_2=(A_2, \mathcal {G})$
are finite Ramsey algebras. Denote by
$\leq $
the reduction relation relation with respect to
$\mathcal {F}\times \mathcal {G}$
.
Given
$X\subseteq A_1\times A_2$
and
$\vec {b}\in {^\omega }(A_1\times A_2)$
, we obtain a homogeneous reduction in two steps. First, we operate on the first coordinates by applying Theorem 4.4 and then we apply the same theorem to the second coordinates of the resulting sequence. To be precise, Theorem 4.4 furnishes a sequence
$f_0, f_1, f_2, \ldots $
of orderly terms of
$\mathcal {F}$
and a desired sequence
$\vec {\beta }_0, \vec {\beta }_1, \vec {\beta }_2, \ldots $
of finite sequences of the first coordinates of
$\vec {b}$
such that
$\vec {\beta }'=\langle f_0(\vec {\beta }_0), f_1(\vec {\beta }_1), f_2(\vec {\beta }_2), \ldots \rangle $
has the property
$\operatorname {\mathrm {FR}}_{\mathcal {F}}(\vec {\beta }')=\{\phi \}$
for some
$\phi \in A_1$
. Applying
$(f_0, \operatorname {\mathrm {id}}_{A_2})$
,
$(f_1, \operatorname {\mathrm {id}}_{A_2})$
,
$(f_2, \operatorname {\mathrm {id}}_{A_2}), \ldots $
to the terms of
$\vec {b}$
corresponding to
$\vec {\beta }_0, \vec {\beta }_1, \vec {\beta }_2, \ldots $
, we obtain a
$\vec {b}'\leq \vec {b}$
for which
$\operatorname {\mathrm {FR}}_{\mathcal {F}\times \mathcal {G}}(\vec {b}')$
consist of ordered pairs whose first coordinates are all equal to
$\phi $
.
Furnished by Theorem 4.4, we may again obtain a sequence
$(\operatorname {\mathrm {id}}_{A_1}, g_0)$
,
$(\operatorname {\mathrm {id}}_{A_1}, g_1)$
,
$(\operatorname {\mathrm {id}}_{A_1}, g_2), \ldots $
for
$\vec {b}'$
to obtain
$\vec {a}\leq \vec {b}'\leq \vec {b}$
such that
$\operatorname {\mathrm {FR}}_{\mathcal {F}\times \mathcal {G}}(\vec {a})$
is now a singleton
$\{(\phi , \gamma )\}$
for some
$\gamma \in A_2$
. Consequently,
$\mathcal {A}_1\times \mathcal {A}_2$
is also a (finite) Ramsey algebra by the same theorem again.⊣
Using Theorem 4.4 on the finite part and then focusing on the infinite part, we obtain the following corollary.
Corollary 4.6. The Cartesian product of an infinite Ramsey algebra with a finite number of finite Ramsey algebras is a Ramsey algebra.
5 Subalgebras and extensions
A subalgebra of a given algebra is a subset of the universe of the algebra closed under the associated operations. To be precise, let
$\mathcal {A}=(A, \mathcal {F})$
be an algebra, let
$A'\subseteq A$
, and let
$\mathcal {F}'=\{f':f'=f\upharpoonright A', f\in \mathcal {F}\}$
. Then
$\mathcal {A}'=(A', \mathcal {F}')$
is said to be a subalgebra of
$\mathcal {A}$
if
$A'$
is closed under all operations
$f'\in \mathcal {F}'$
. In what follows, the subalgebra relation will be invariably denoted by the subset relation
$\subseteq $
, e.g.,
$\mathcal {A}'\subseteq \mathcal {A}$
. If
$(A', \mathcal {F}')$
is a subalgebra and
$(A\setminus A', \{f\upharpoonright (A\setminus A'):f\in \mathcal {F}\})$
happens to be a subalgebra as well, then we express this subalgebra as
$\mathcal {A}\setminus \mathcal {A}'$
. A subalgebra of an algebra is said to be proper if the universe of the former is a proper subset of the latter; a subalgebra of an algebra
$\mathcal {A}$
is nontrivial if it is not the empty algebra nor is it
$\mathcal {A}$
itself.
It is intuitively clear that, if an algebra is Ramsey, any subalgebra of it is also Ramsey. Such is indeed the case (cf. [Reference Teh20]):
Theorem 5.1. Every proper subalgebra
$\mathcal {A}'$
of a Ramsey algebra
$\mathcal {A}$
is a Ramsey algebra.
Obviously, by the theorem, every subalgebra of a Ramsey algebra is Ramsey. Whether the converse of the theorem is true remains an open question. If
$\mathcal {A}=(A, \mathcal {F})$
is an algebra and
$\mathcal {A}'$
is a proper subalgebra of
$\mathcal {A}$
, it is not necessarily true that
$\mathcal {A}\setminus \mathcal {A}'$
is a subalgebra. Some functions in
$\mathcal {F}$
may send tuples of elements of
$A\setminus A'$
into
$A'$
.
Let us look at two sufficient conditions to ensure that an algebra is Ramsey whenever its nontrivial subalgebras are Ramsey. These sufficient conditions can be stated in some topological terms.
Definition 5.2. Let
$\mathcal {A}=(A, \mathcal {F})$
be an algebra. We define a topology
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
on A by specifying the basic open sets to be precisely those subsets of A that are the universes of the subalgebras of
$\mathcal {A}$
. Denote by
$\mathfrak {B}(\mathcal {A})$
the set of basic open sets.
Indeed,
$\mathfrak {B}(\mathcal {A})$
forms a basis and it is in fact a Moore collection of subsets of
$|\mathcal {A}|$
; its members are closed under arbitrary intersections. As such,
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
is Alexandroff.
Proposition 5.3. Let
$\mathcal {A}=(A, \mathcal {F})$
be an algebra such that all of its proper subalgebras are Ramsey. Then
$\mathcal {A}$
is Ramsey if there exists a clopen
$A'\in \mathfrak {B}(\mathcal {A})\setminus \{A, \varnothing \}$
.
Proof. Let
$\vec {b}\in {^\omega }A$
,
$X\subseteq A$
, and let
$A'\in \mathfrak {B}(\mathcal {A})\setminus \{A, \varnothing \}$
be clopen. Therefore,
$A'$
and
$A\setminus A'$
are Ramsey algebras.
As the terms of
$\vec {b}$
are either members of
$A'$
or otherwise, we may pick, by the piegonhole principle, a subsequence
$\vec {b}'$
of
$\vec {b}$
all of whose terms are either members of
$A'$
or all of whose terms are members of
$A\setminus A'$
. That is,
$\vec {b}'(i)\in A'$
for each
$i\in \omega $
or
$\vec {b}'(i)\in A\setminus A'$
for each
$i\in \omega $
. In either case, a reduction
$\vec {a}$
of
$\vec {b}'$
that is homogeneous to X can be found. Hence, since
$\vec {b}$
and X are arbitrary, it follows that
$\mathcal {A}$
is a Ramsey algebra.⊣
Proposition 5.4. Suppose that
$\mathcal {A}=(A, \mathcal {F})$
is an algebra such that all of its proper subalgebras are Ramsey and
$\bigcup _{A'\in \mathfrak {B}(\mathcal {A})\setminus \{A\}}A'=A$
. If
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
is compact, then
$\mathcal {A}$
is a Ramsey algebra.
Proof. Let
$\vec {b}\in {^\omega }A$
and
$X\subseteq A$
. Let
$A_1, \ldots , A_n$
be a finite subcover of
$\bigcup _{A'\in \mathfrak {B}(\mathcal {A})\setminus \{A\}}A'=A$
. Then there exists a subsequence
$\vec {b}'$
of
$\vec {b}$
all of whose terms belong in
$A_k$
for some
$k\in \{1, \ldots , n\}$
. Then by the fact that
$A_k$
along with the restricted functions form a Ramsey algebra, the sequence
$\vec {b}'$
has a reduction
$\vec {a}$
homogeneous for X. Therefore,
$\vec {b}$
has a reduction homogeneous for X. Since
$\vec {b}$
and X are arbitrary, it follows that
$\mathcal {A}$
is a Ramsey algebra.⊣
Example 5.5. Let us take a look at the topology
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
for the predecessor algebra
$\mathcal {A}$
. The topology is very coarse because the only subalgebras are the empty algebra, the algebra
$\mathcal {A}$
itself, and the algebra
$(\{0\}, p)$
. The topology does not have nontrivial clopen sets, but it is trivially compact. In contrast, let us also take a look at the topology
$\operatorname {\mathrm {Sub}}(\mathcal {B})$
for
$\mathcal {B}$
constructed in the proof of Corollary 4.3. The empty algebra, the subalgebras
$\mathcal {A}$
,
$\mathcal {B}$
itself, and
$\mathcal {B}\setminus \mathcal {A}$
are all members of
$\mathfrak {B}(\mathcal {B})$
. The open sets
$\mathcal {A}, \mathcal {B}\setminus \mathcal {A}$
are a pair of nontrivial clopen basis sets that is dual to each other, but note that
$\mathcal {A}$
is Ramsey but
$\mathcal {B}\setminus \mathcal {A}$
is not. There is nothing much we can say about compactness unless we delve into the specifics of
$\mathcal {B}$
, considering the types it can realize, but we will not do so here.
We end our discussion of the topology with a few observations about
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
in the case when
$\mathcal {A}$
is a unary system. For any such algebra, the set
$$ \begin{align*} S=\{c\in A:f(c)=c\;\text{for each}\;f\in\mathcal{F}\} \end{align*} $$
of fixed points for
$\mathcal {F}$
is a subalgebra of
$\mathcal {A}$
, i.e.,
$S\in \mathfrak {B}(\mathcal {A})$
. In fact, the subspace topology on S induced by the topology
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
is discrete. When
$\mathcal {A}$
is Ramsey, we can say even more about S; this is in fact a reformulation of Theorem 2.10:
Theorem 5.6 (Characterization of Ramsey Unary algebras, topological formulation).
Let
$\mathcal {A}=(A, \mathcal {F})$
be a unary system equipped with the topology
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
. Then
$\mathcal {A}$
is a Ramsey algebra if and only if the set S of fixed points is dense in A.
Proof. Our reference theorem is again Theorem 2.10. Suppose
$\mathcal {A}$
is Ramsey and let
$a\in A$
. Then any open set containing a will have a nonempty intersection with S. This is because every open set will contain the smallest open set containing a, which is the subalgebra generated by a. But since a can be sent into S by finitely many applications of the members of
$\mathcal {F}$
, the subalgebra generated by a has a nonempty intersection with S.
Conversely, suppose that S is dense in
$\operatorname {\mathrm {Sub}}(\mathcal {A})$
. Let
$a\in A$
and let U be the subalgebra generated by a. Then, by
$U\in \operatorname {\mathrm {Sub}}(\mathcal {A})$
and density, we have
$U\cap S\neq \varnothing $
. Thus, if
$c\in U\cap S$
, then there is a way to send a to
$c\in S$
using finitely many members of
$\mathcal {F}$
.⊣
We continue to explore the question about the converse to Theorem 5.1, now with a specific example that is somewhere “in between” a theorem that we are after. There is some triviality involved and it is the reason we considered the smaller collection
$\bigcup _{A'\in \mathfrak {B}(\mathcal {A})\setminus \{A\}}A'=A$
in Proposition 5.4 above. Consider the algebra
$\mathcal {Z}=(\mathbb {Z}, f, g)$
, where
$f(x)=x+1$
and
$g(x)=x-1$
.Footnote
3
Then it is easy to check that the only subalgebras of
$\mathcal {Z}$
are trivial and that
$\mathcal {Z}$
is not a Ramsey algebra by Theorem 2.10. Thus, the relevant question is whether an algebra must be Ramsey if nontrivial subalgebras of it exist and if all of them are Ramsey. This question still seems to be elusive. The algebra
$\mathcal {D}$
that we will now study is not Ramsey, has countably many isomorphic copies of itself embedded in within, and these isomorphic subalgebras are, therefore, not Ramsey by the isomorphism theorem above. Nevertheless,
$\mathcal {D}$
is an algebra for which all other subalgebras are Ramsey. We begin the construction of
$\mathcal {D}$
by looking at one-point extensions of Ramsey algebras.
Suppose that
$\mathcal {A}=(A, \mathcal {F})$
is a Ramsey algebra. Consider the new universe
$A'=A\cup \{\alpha \}$
augmented by a new symbol
$\alpha $
; let
$\mathcal {F}'$
be a family of operations on A, each member
$f'$
being a fixed arbitrary extension of some member
$f\in \mathcal {F}$
to
$A'$
. We claim that the new algebra
$\mathcal {A}'=(A', \mathcal {F}')$
is also a Ramsey algebra.
To see this, let
$\vec {b}\in {^\omega }A'$
and
$X\subseteq A'$
. If
$\alpha $
appears only finitely many times in the terms of
$\vec {b}$
, we may drop those terms to obtain
$\vec {b}'$
and, clearly,
$\vec {b}'\leq _{\mathcal {F}'}\vec {b}$
. Since
$\vec {b}'$
consists of terms belonging in A and
$\mathcal {A}$
is a Ramsey algebra,
$\vec {b}'$
clearly has a reduction
$\vec {a}\leq \vec {b}'$
homogeneous for X and so
$\vec {b}$
has a reduction
$\vec {a}\leq _{\mathcal {F}'}\vec {b}$
homogeneous for X.
On the other hand, suppose that
$\alpha $
occurs infinitely many times in
$\vec {b}$
. We drop the other terms and obtain the subsequence
$\vec {b}'$
, which is a constant sequence all of whose terms are
$\alpha $
. As usual,
$\vec {b}'\leq _{\mathcal {F}'}\vec {b}$
, so it suffices to show the existence of a reduction of
$\vec {b}'$
homogeneous for X. There are two possibilities to consider:
-
(1) All
$F'\in \operatorname {\mathrm {OT}}(\mathcal {F}')$
yield the value
$\alpha $
when given input
$(\alpha , \ldots , \alpha )$
. -
(2) There exists an
$F'\in \operatorname {\mathrm {OT}}(\mathcal {F}')$
such that
$F'(\alpha , \ldots , \alpha )\neq \alpha $
, thus
$F'(\alpha , \ldots , \alpha )\in A$
.
In the former case,
$\vec {b}'$
itself is homogeneous for X; in fact,
$\operatorname {\mathrm {FR}}_{\mathcal {F}'}(\vec {b}')=\{\alpha \}$
, and so
$\vec {b}'$
is clearly homogeneous for X. In the latter case, apply
$F'$
on consecutive blocks of
$\langle \alpha , \ldots , \alpha \rangle $
(of length the arity of
$F'$
) in
$\vec {b}'$
so that we obtain the reduction
$\vec {a}'\leq _{\mathcal {F}'}\vec {b}'$
all of whose terms lie in A. Since
$\vec {a}'\in {^\omega }A$
and
$\mathcal {A}$
is a Ramsey algebra, we have a reduction
$\vec {a}\leq _{\mathcal {F}'}\vec {a}'$
that is homogeneous for X.
Dovetailing the observations above, we obtain the following lemma:
Lemma 5.7. Any one-point extension of a Ramsey algebra also results in a Ramsey algebra.
The notion of a direct limit is one that is familiar from model theory (cf. [Reference Carlson2]) and we will not give it here.
Theorem 5.8. The direct limit of a sequence of Ramsey algebras need not be a Ramsey algebra.
Proof. We recursively construct a
$\subseteq $
-chain of algebras. Begin with
$\mathcal {A}_0=(A_0, f)=(\{0\}, f_0)$
, where
$f_0$
is a binary function; it is clearly a Ramsey algebra. By recursion, we let
$\mathcal {A}_{n+1}=(A_{n+1}, f_{n+1})=(A_n\cup \{n+1\}, f_n)$
, where
$f_{n+1}$
denotes the extension of
$f_n$
from
$A_n$
to
$A_{n+1}$
given by
$$ \begin{align*} f_{n+1}(a, b) = \left\{ \begin{array}{ll} n+1, & a=b=n+1; \\ n, & a\neq b \text{ while either one equals } n+1. \end{array} \right. \end{align*} $$
We denote the direct limit of these algebras by
$\mathcal {D}$
, the universe of the algebra being
$\omega $
and the operation we denote by f. Note that each natural number is an idempotent element of
$\mathcal {D}$
, i.e.,
$f(n, n)=n$
for each
$n\in \omega $
.
Note that f so defined on
$\omega $
is not associative; for instance, we have
$f(f(0, 0), 3)=2\neq 1=f(0, f(0, 3))$
. Hence
$\mathcal {D}$
is not a semigroup, whence Hindman’s theorem clearly does not apply. In fact, we now show that, while each
$\mathcal {A}_n$
is a Ramsey algebra because each is a one-point extension of the previous Ramsey algebra, the direct limit
$\mathcal {D}$
is not Ramsey. We will show that
$\vec {b}=\langle 0, 1, 2, \ldots \rangle $
does not have a reduction homogeneous for the set X of even numbers. We first need the following claim.
Claim. If
$F\in \operatorname {\mathrm {OT}}(\{f\})$
,
$\sigma $
is a finite subsequence of
$\vec {b}=\langle 0, 1, \ldots \rangle $
, the first and last terms of
$\sigma $
is N and M, respectively, then
$N\leq F(\sigma )<M$
.
Proof of Claim. By induction on the complexity of F. For the atomic case, we have
$F=f$
. Let
$\sigma =(N, M)$
be a finite subsequence of
$\vec {b}$
; we have
$0\leq N<M$
. Then we have
$0\leq F(\sigma )=f(N, M)=M-1<M$
. Now, suppose that the claim is true for the orderly terms
$F_1, F_2$
the finite subsequences
$\sigma _1, \sigma _2$
with first and last term pairs equaling
$(N_1, M_1)$
and
$(N_2, M_2)$
, respectively, and with
$M_1<N_2$
. We want to show that the orderly term next up in complexity, namely
$F(\vec {x}_1\ast \vec {x}_2)=f(F_1(\vec {x}_1), F_2(\vec {x}_2))$
, also satisfies the statement of the claim. Indeed, by induction hypothesis, we have
$N_1\leq F_1(\sigma _1)<M_1$
and
$N_2\leq F_2(\sigma _2)<M_2$
. Now, since
$M_1<N_2$
, we have
$F_1(\sigma _1)<F_2(\sigma _2)$
, whence
$N_1\leq f(F_1(\sigma _1), F_2(\sigma _2))=F_2(\sigma _2)-1<M_2$
as desired.
The claim states that any application of an
$F\in \operatorname {\mathrm {OT}}(\{f\})$
on a finite subsequence
$\sigma $
of
$\vec {b}$
picks out a natural number between the values of the first term N and the last term M of
$\sigma $
. As a reduction
$\vec {a}\leq \vec {b}$
does not allow applying orderly terms on overlapping finite subsequences of
$\vec {b}$
(see Definition 2.2), it follows from the claim that every reduction
$\vec {a}\leq \vec {b}$
is an infinite subsequence of
$\vec {b}$
. In particular, this implies that, for each of these reductions
$\vec {a}$
, we have
$\vec {a}(1), f(\vec {a}(0), \vec {a}(1))\in \operatorname {\mathrm {FR}}(\{f\})$
, but these two numbers have different parity, whence
$\vec {a}$
cannot be homogeneous for the set X of even numbers. This concludes the proof of the theorem.⊣
In the spirit of the converse question above, let us inspect the subalgebras of
$\mathcal {D}$
:
Proposition 5.9. Every nontrivial subalgebra of the direct limit
$\mathcal {D}$
is some
$\mathcal {A}_n$
, some
$\mathcal {D}\setminus \mathcal {A}_n$
, or some
$\mathcal {A}_n\setminus \mathcal {A}_m$
.
Proof. We first note that structures of the forms
$\mathcal {A}_n$
,
$\mathcal {D}\setminus \mathcal {A}_n$
, and
$\mathcal {A}_n\setminus \mathcal {A}_m$
are subalgebras of
$\mathcal {D}$
. We now show that these are the only proper subalgebras.
Let
$W\subsetneq \omega $
be nonempty and let
$w_0$
be least in W; we claim that W has one of the stipulated forms. If W is a singleton, then W generates the algebra
$(\{w_0\}, f)$
, but
$(\{w_0\}, f)$
is precisely
$\mathcal {A}_{w_0}\setminus \mathcal {A}_{w_0-1}$
in the case
$w_0>0$
or
$\mathcal {A}_0$
in the case
$w_0=0$
.
On the other hand, suppose that W is not a singleton. Let w be a nonzero member of W distinct from
$w_0$
. It is easy to see from the definition of f that
$\{w_0, w_0+1, \ldots , w\}\subseteq W$
, whence it follows by induction that
$\mathcal {A}_w\setminus \mathcal {A}_{w_0}$
is a subalgebra of the algebra generated by W. (In fact, the induction begins with the observation that
$f(w, w_0)=w-1$
and the induction step takes the form
$f(w-k-1, w_0)=w-k-2$
, terminating when we hit
$w_0$
.) But w is arbitrary, hence if the algebra generated by W is nontrivial, then it must have the form
$\mathcal {D}\setminus \mathcal {A}_n$
or
$\mathcal {A}_n\setminus \mathcal {A}_{w_0}$
in the case
$w_0>0$
or
$\mathcal {A}_n$
in the case
$w_0=0$
. This concludes the proof that every nontrivial subalgebra of
$\mathcal {D}$
assumes one of the stipulated forms.⊣
In the proof of Theorem 5.8, we have seen that
$\mathcal {D}$
is not a Ramsey algebra. Now note that each
$\mathcal {D}\setminus \mathcal {A}_n$
is isomorphic to
$\mathcal {D}$
, so these subalgebras are not Ramsey either by Corollary 3.2. For the other subalgebras, note that each
$\mathcal {A}_n$
and each
$\mathcal {A}_n\setminus \mathcal {A}_m$
is a finite algebra. The following theorem on finite algebras, appearing as part of Theorem 3.9 in [Reference Teoh and Teh14] and which is related to Theorem 4.4, will show that the finite subalgebras
$\mathcal {A}_n$
and
$\mathcal {A}_n\setminus \mathcal {A}_m$
are, in fact, Ramsey.
Theorem 5.10. A finite algebra
$(A, \mathcal {F})$
is a Ramsey algebra if and only if every nonempty subalgebra contains an idempotent element a of
$(A, \mathcal {F})$
, i.e.,
$f(a, a, \ldots , a)=a$
for all
$f\in \mathcal {F}$
.
Each
$\mathcal {A}_n$
as well as each
$\mathcal {A}_n\setminus \mathcal {A}_m$
is Ramsey because every natural number is idempotent for
$\mathcal {D}$
. As such, we have seen that the direct limit
$\mathcal {D}$
is not a Ramsey algebra, so neither are the subalgebras
$\mathcal {D}\setminus \mathcal {A}_n$
that are isomorphic copies of it, but the remaining subalgebras
$\mathcal {A}_n$
and
$\mathcal {A}_n\setminus \mathcal {A}_m$
are Ramsey algebras. In summary, we have seen that the ring
$\mathbb {Z}$
, interpreted as a model
$(\mathbb {Z}, f, g)$
of a purely functional language, is not Ramsey because it has no nontrivial subalgebras that are Ramsey, and
$\mathcal {D}$
is not Ramsey despite of the fact that all of its subalgebras that are not isomorphic to it are Ramsey. One final example from octonions to show that if an algebra fails to be Ramsey, then it must already have subalgebras that are not Ramsey. It is shown in [Reference Silver9] that the real octonions
$(\mathbb {O}, \cdot )$
is not a Ramsey algebra under multiplication because it has a subalgebra that is not a Ramsey algebra. As such, the question posed at the beginning of this section remains open, but we yet see another evidence that the answer could be in the affirmative.
6 Conclusion
The results above answer a number of structural questions pertaining to Ramsey algebras. Since isomorphic algebras are essentially the same algebra, it came as no surprise that isomorphic algebras have the same Ramsey algebraic property. On the other hand, elementary equivalence is a first-order property and the invariance of Ramsey property breaks down in the face of the stronger third-order property of being a Ramsey algebra. This also suggests another line of investigation, namely when does a Ramsey algebra have a first-order characterization? Hindman’s theorem states that semigroups are Ramsey algebra and being a semigroup is a first-order property. On the contrary, the characterization theorem, Theorem 2.10, is not a first-order statement as we saw by means of an example, which is contained in the proof of Theorem 4.3.
We also answered a question since the inception of the subject as to whether Cartesian products of Ramsey algebras must be Ramsey and the answer turns out to be in the negative, something expected in hindsight. It will now be interesting to investigate if one can always reduce an infinite product to yield a reduced product that is Ramsey, an investigation towards a characterization of the filters that would do the job. The result above on the ultrapowers of the predecessor algebra somehow show that this might not come by easy.
Apart from our results on subalgebras, most of the other theorems we considered involved enlarging a given algebra. Cartesian products are enlargements, so are direct limits. Answering the question about elementarily equivalent algebras, we constructed the ultrapower; alternatively, we also constructed, by way of the compactness theorem, an extension of the given Ramsey algebra. As we have seen, the enlargements that accompany these results do not exhibit Ramsey property. In summary, going from a Ramsey algebra to a larger algebra does not necessarily preserve Ramseyness. This runs in stark contrast with the usual Ramseyan theme, where larger domains of a structure that exhibits Ramseyan properties would remain Ramsey. A remedy, if we would, is to shift perspective from the universe of the algebra to the countable sequences of its universe as they pertain to the definition of a Ramsey algebra. To be precise, consider a sequence
$\vec {b}$
for which one is interested to find a homomgeneous reduction
$\vec {a}$
. If
$\vec {b}$
admits a homogeneous reduction
$\vec {a}$
, then any “enlarged” sequence
$\vec {b}'$
that contains
$\vec {b}$
as a subsequence will have
$\vec {a}$
as a homogeneous reduction. Thus, the proper “domain” of enlargement lies in sequences rather than the domain of the algebra in question. At any rate, a further understanding of this issue would be illuminating.
Finally, one nagging question remains: For algebras with an abundance of nontrivial subalgebras, if every subalgebra is Ramsey, must the algebra be Ramsey? One is free to interpret the term “abundance” in this question.
Acknowledgment
This work was done at Universiti Sains Malaysia and at Xiamen University Malaysia under the grant XMUMRF/2020-C5/IMAT/0014 in its later stage. I would like to thank Xianghui Shi for raising the question as to whether whether enlargements of a Ramsey algebra will remain Ramsey. I also extend my utmost gratitude to Wen Chean Teh for constantly suggesting improvements on writing proofs. The painstaking effort taken by Noor Atinah Ahmad, Kai Lin Ong, and Azhana Ahmad in reading the manuscript and providing valuable feedback is an aspect in the preparation of the manuscript that I truly cherish. Special thanks goes to Qiaochu Yuan for giving the example algebra
$\mathcal {Z}$
above. Also thanking Lai Yeng Kuan for being at my side while I worked late hours on this paper. Finally, I dedicate this paper to my late father Chin Seng Teoh, forever in fond memories.
