Problem 11813
(American Mathematical Monthly, Vol.122, January 2015) Proposed by G. Oman (USA).
Let X be a set, and let ∗ be a binary operation on X (that is, a function from X × X to X). Prove or disprove: there exists an uncountable set X and a binary operation ∗ on X such that for any subsets Y and Z of X that are closed under ∗, either Y ⊆ Z or Z ⊆ Y .
Solution proposed by Carlo Pagano, Mathematical Institute, Leiden University, The Netherlands, and Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, Italy.
We will show that there exists an uncountable set X with a non-associative binary operation which satisfy the required property. Moroever we will prove that if the binary operation is associative then a set X with that property can not be uncountable.
The non-associative case.
Let X be the first uncountable ordinal space, an uncountable well-ordered set such that for any y ∈ X the set
Iy := {x ∈ X : x < y}
is countable. Let x0be the smallest element of X. Note that each x ∈ X has a successor s(x) := min(X \ (Ix∪ {x})).
If y 6∈ s(X) and y 6= x0 then Iy is infinite countable and there is an infinite strictly increasing sequence {xk}k≥1 ⊆ Iy such that limk→∞xk = y (i. e. for all z ∈ Iy there is n > 0, such that z < xk< y for k > n). Now we define the function f : X × X → X as follows.
i) If y ∈ s(X) then y = s(x) for some x ∈ Iy. Let f (y, y) = x.
ii) If y 6∈ s(X) and y 6= x0 then limk→∞xk = y for some sequence. Let f (y, y) = x1 and let f (y, xk) = xk+1for k ≥ 1.
iii) Otherwise, let f (y, z) = x0.
Note that the corresponding binary operation ∗ is not associative because if y 6∈ s(X) and y 6= x0
then
y ∗ (y ∗ x1) = f (y, f (y, x1)) = f (y, x2) = x3> f (x1, x1) = f (f (y, y), x1) = (y ∗ y) ∗ x1. Let Z be a subset closed under ∗. It suffices to show that
[
x∈Z
Ix⊆ Z,
because if Y is another set closed under ∗ and z ∈ Z \ Y then Y ⊆ Iz⊆ Z (otherwise there is y ∈ Y such that y > z and z ∈ Iy⊆ Y whereas z 6∈ Y ).
Let Z0:= {x ∈ Z : Ix6⊆ Z} and assume by contradiction that Z0 is not empty. Let z = min(Z0) (X is well-ordered) then z 6= x0 and finally we distinguish two cases.
i) If z ∈ s(X) then z = s(x) for some x ∈ Iz. and f (z, z) = x ∈ Z. Hence, by the minimality of z, Ix⊆ Z and Iz= Ix∪ {x} ⊆ Z which is a contradiction.
ii) If z 6∈ s(X) then f (z, z) = x1 ∈ Z, f (y, xk) = xk+1∈ Z for k ≥ 1. Hence, by the minimality of z, Ixk ⊆ Z for k ≥ 1 and limk→∞xk = z implies that Iz = S
k≥1Ixk ⊆ Z which is a contradiction.
The associative case.
Assume that X is uncountable. For x ∈ X, let P (x) = {xn : n ≥ 1} where xn := x ∗ x ∗ · · · ∗ x (n times). Then P (x) is countable and closed under ∗.
Let a0∈ X then there is a1∈ X \ P (a0) because X is uncountable. Since the subsets of X which are closed under ∗ are totally ordered by inclusion and a16∈ P (a0), it follows that P (a0) ( P (a1).
Continuing in this way, we obtain a sequence {an: n ≥ 0} such that
P (a0) ( P (a1) ( P (a2) ( · · · with an6∈ P (an−1) for n ≥ 1.
Now the set
A = [
n≥0
P (an)
is countable and closed under ∗. As before, there is b ∈ X \ A and A ( P (b).
Hence a0= bmfor some m ≥ 1, which implies that
P (b) =b, b2, . . . , bm−1 ∪ P (a0) ∪ b ∗ P (a0) ∪ b2∗ P (a0) ∪ · · · ∪ bm−1∗ P (a0).
Sinceb, b2, . . . , bm−1 is finite and an 6∈ P (a0) for n > 0 there is 0 < k < m such that bk∗ P (a0) contains infinite elements of {an: n ≥ 1}. Let an1 be one of them
an1= bk∗ aj01 for some j1≥ 1.
Among the other infinite elements, there is an2 with n2> n1 such that an2 = bk∗ aj02 for some j2> j1. Since a0∈ P (an1), it follows that a0= arn1 for some r ≥ 1 and therefore
an2 = bk∗ aj02 = an1∗ a0j2−j1= a1+r(jn1 2−j1)
which contradicts an26∈ P (an1).
Note that there exists (X, ∗) where X is countably infinite: take X = {exp(2πik/pn) | k ∈ Z, n ∈ Z+}.
where p is a prime and the binary operation ∗ is the multiplication of complex numbers. It is easy to see that its subgroups are totally ordered by inclusion.
