# Addition on ultrafilters is non-commutative

I'm reading a book on ultrafilters and it tells me that showing addition on ultrafilters over the naturals (addition on the set of ultrafilters '$\beta \mathbb{N}$', defined in the standard way) is not commutative is a 'nice exercise'. I am curious to see a proof: however, this result isn't particularly important for what I need ultrafilters for, I don't really want to spend a long time trying to obtain the result.

I have seen that addition is left-continuous, so I suppose the equivalent statement is that addition is not right-continuous (as it would be if $+$ was commutative) though I suspect non-right-continuous and non-commutative immediately follow from one another; could anyone perhaps direct me to a source with a proof that addition is not commutative on $\beta \mathbb{N}$, if they know one? (Or perhaps if the proof is short and it's no more trouble, you could explain the proof yourself - I am happy with either).

Many thanks,

-
You might check Theorem 4.27 in Hindman, Strauss: Algebra in the Stone-Cech compactification, p.81. – Martin Sleziak Nov 30 '11 at 18:25
Just out of curiosity: What book on ultrafilters are you reading? – Martin Sleziak Mar 19 '12 at 8:48
BTW this is in fact part of this question. – Martin Sleziak Jun 20 '12 at 15:37

Added: After giving this some more thought, I realized that if one just wishes to show that ultrafilter addition is not commutative, the argument can be greatly simplified.

For $n\in\omega$ let $t(n)=\max\{k\in\omega:2^k\mid n\}$. For $k\in\omega$ let $D_k=\{n\in\omega:t(n)=k\}$. Let $$E=\bigcup_{k\in\omega}D_{2k}\text{ and }O=\bigcup_{k\in\omega}D_{2k+1}\;,$$ and for $n\in\omega$ let $\displaystyle R_n=\bigcup_{k\ge n}D_k$. The families $$\{R_n:n\in\omega\}\cup\{E\}\text{ and }\{R_n:n\in\omega\}\cup\{O\}$$ are centred and have empty intersection, so they can be extended to $p,q\in\beta\omega \setminus\omega$, respectively. Let $A=\{n\in\omega:t(n)\text{ is even}\}$; I’ll show that $A\in(q+p)\setminus(p+q)$ and hence that $p+q\ne q+p$.

To show that $A\in q+p$, let $n\in E$, so that $n\in D_{2k}$ for some $k\in\omega$. For each $m\in R_{2k+1}$, $t(m)>2k$, while $t(n)=2k$, so $t(m+n)=2k$, and $m+n\in A$. Thus, $A-n\supseteq R_{2k+1}\in q$ for each $n\in E$, so $\{n\in\omega:A-n\in q\}\supseteq E\in p$, and hence $A\in q+p$.

Now let $n\in O$, so that $n\in D_{2k+1}$ for some $k\in\omega$. For each $m\in R_{2k+2}$, $t(m)>2k+1$, while $t(n)=2k+1$, so $t(m+n)=2k+1$, and $m+n\notin A$. Thus, $(A-n)\cap R_{2k+2}=\varnothing$ for each $n\in O$. $R_{2k+2}\in p$, so $\{n\in\omega:A-n\notin p\}\in q$, which of course implies that $\{n\in\omega:A-n\in p\}\notin q$ and hence that $A\notin p+q$.

The original argument, showing that no free ultrafilter is in the centre of $\langle\beta\omega,+\rangle$:

I was digging around in some old notes and found this; I believe that the argument is due to Neil Hindman.

For $p,q\in\beta\omega$ define $p+q\in\beta\omega$ by $A\in p+q$ iff $\{n\in\omega: A-n\in p\}\in q$. (Some authors reverse the definition.) Fix $p\in\beta\omega\setminus\omega$; I’ll construct $q\in\beta\omega\setminus\omega$ such that $p+q\ne q+p$.

For each $k\in\omega$, the residue classes modulo $2^k$ are a finite partition of $\omega$, so exactly one of them belongs to $p$, say $R_k\triangleq\{2^kn+r_k:n\in\omega\}$, where $0\le r_k<2^k$. Note that $R_{k+1}\subseteq R_k$, since otherwise $R_{k+1}$ and $R_k$ would be disjoint elements of $p$. It follows that either $r_{k+1}=r_k$, or $r_{k+1}=r_k+2^k$. For $k\in\omega$ let $D_k=R_k\setminus R_{k+1}$. Let $$E=\bigcup_{k\in\omega}D_{2k}\text{ and }O=\bigcup\limits_{k\in\omega}D_{2k+1}\;;$$ clearly $E$ and $O$ are disjoint, so at most one of them belongs to $p$.

Now $$E\cup O=R_0\setminus\bigcap_{k\in\omega}R_k=\omega\setminus\bigcap_{k\in\omega}R_k\;,$$ so if $r\in\omega\setminus(E\cup O)$, $r\equiv r_k\pmod{2^k}$ for every $k\in\omega$, and hence $r_k=r$ for all $k$ such that $2^k>n$. Thus, either $\langle r_k:k\in\omega\rangle$ is unbounded, in which case $E\cup O=\omega$, or there is some $r\in\omega$ such that $r_k=r$ for all sufficiently large $k$, in which case $E\cup O=\omega\setminus\{r\}$. In either case $E\cup O\in p$, and therefore exactly one of $E$ and $O$ belongs to $p$.

Clearly $\{R_k:k\in\omega\}\cup\{E\}$ and $\{R_k:k\in\omega\}\cup\{O\}$ are both centred families, so both can be extended to ultrafilters on $\omega$. Choose $q\in\beta\omega\setminus\omega$ so that

$$\begin{array}{ll} \{R_k:k\in\omega\}\cup\{O\}\subseteq q,&\text{ if }E\in p,\text{ and}\\ \{R_k:k\in\omega\}\cup\{E\}\subseteq q,&\text{ if }O\in p\;. \end{array}$$

Now let

$$A=\{2^{2k}(2m+1)+2r_{2k}:k,m\in\omega\};$$

I’ll show that if $E\in p$ and $O\in q$, $A\in(q+p)\setminus(p+q)$. (In the other case, of course, $A\in(p+q)\setminus(q+p)$.)

To show that $A\in q+p$, let $n\in E$, so that $n\in D_{2k}=R_{2k}\setminus R_{2k+1}$ for some $k\in\omega$; I claim that $R_{2k+1}\subseteq A-n$. To see this, let $m\in R_{2k+1}$, so that $m=2^{2k+1}j+r_{2k+1}$ for some $j\in\omega$. Since $n\in R_{2k}\setminus R_{2k+1}$, $n\equiv r_{2k}\pmod{2^{2k}}$, but $n\not\equiv r_{2k+1}\pmod{2^{2k+1}}$. Recall that either $r_{2k+1}=r_{2k}$, or $r_{2k+1}=r_{2k}+2^{2k}$.

Suppose first that $r_{2k+1}=r_{2k}$. Then $2^{2k}\mid n-r_{2k}$, but $2^{2k+1}\nmid n-r_{2k}$, so $$n=2^{2k}(2i+1)+r_{2k}=2^{2k+1}i+r_{2k}+2^{2k}$$ for some $i\in\omega$ and $$m=2^{2k+1}j+r_{2k+1}=2^{2k+1}j+r_{2k}\;.$$

Now suppose that $r_{2k+1}=r_{2k}+2^{2k}$. Then $2^{2k}\mid n-r_{2k}$, but $2^{2k+1}\nmid n-r_{2k}-2^{2k}$, so $2^{2k+1}\mid n-r_{2k}$, and hence $$n=2^{2k+1}i+r_{2k}$$ for some $i\in\omega$, while $$m=2^{2k+1}j+r_{2k}+2^{2k}\;.$$

In either case \begin{align*} n+m&=2^{2k+1}(i+j)+2^{2k}+2r_{2k}\\ &=2^{2k}\big(2(i+j)+1\big)+2r_{2k}\in A\;, \end{align*}

so $m\in A-n$, and since $n\in E$ and $m\in R_{2k+1}$ were arbitrary, $R_{2k+1}\subseteq A-n$ for each $n\in E$. But $R_{2k+1}\in q$, so $A-n\in q$ for each $n\in E$, and $E\in p$, so by definition $A\in q+p$.

To show that $A\notin p+q$, let $n\in O$, so that $n\in D_{2k+1}$ for some $k\in\omega$. Let $m\in R_{2k+2}$; it suffices to show that $m+n\notin A$, since we will then have $R_{2k+2}\cap (A-n)=\varnothing$ for all $n\in O$ and hence $A-n\notin p$ for any $n\in O$ (since $R_{2k+2}\in p$). That is, we’ll have $$O\cap\{n\in\omega:A-n\in p\}=\varnothing\;,$$ where $O\in q$, and hence $$\{n\in\omega:A-n\in p\}\notin q$$ and $A\notin p+q$.

Much as before we can write $m=2^{2k+2}j+r_{2k+2}$ for some $j\in\omega$, and we can observe that since $n\in R_{2k+1}\setminus R_{2k+2}$, $n\equiv r_{2k+1}\pmod{2^{2k+1}}$, but $n\not\equiv r_{2k+2}\pmod{2^{2k+2}}$.

If $r_{2k+2}=r_{2k+1}$, then, again much as before, $n = 2^{2k+2}i + r_{2k+1} + 2^{2k+1}$ for some $i\in\omega$, and $m=2^{2k+2}j+r_{2k+1}$. If $r_{2k+2}=r_{2k+1}+2^{2k+1}$, then $n=2^{2k+2}i+r_{2k+1}$ for some $i\in\omega$, and $m=2^{2k+2}j+r_{2k+1}+2^{2k+1}$. In either case

\begin{align*} m+n&=2^{2k+2}(i+j)+2^{2k+1}+2r_{2k+1}\\ &=2^{2k+1}\big(2(i+j)+1\big)+2r_{2k+1}\;. \end{align*}

Let $s=i+j$, and suppose that $m+n=2^{2k+1}(2s+1)+2r_{2k+1}\in A$. Then there are $t,\ell\in\omega$ such that $$2^{2k+1}(2s+1)+2r_{2k+1} = 2^{2\ell}(2t+1) + 2r_{2\ell}\;.$$

If $r_{2k+1}=r_{2\ell}$, then $2^{2k+1}(2s+1)=2^{2\ell}(2t+1)$, so $2k+1=2\ell$, which is absurd. If $2k+1<2\ell$, then $$r_{2\ell}=r_{2k+1}+\sum_{e\in F}2^e$$ for some $F\subseteq\{2k+1,\dots,2\ell-1\}$, and $$2^{2k+1}(2s+1)+2r_{2k+1} = 2^{2\ell}(2t+1) + 2\left(r_{2k+1}+\sum_{e\in F}2^e\right)$$ i.e.,

\begin{align*} 2^{2k+1}(2s+1) &= 2^{2\ell}(2t+1) + 2\sum_{e\in F}2^e\\ &=2^{2k+2}\left(2^{2\ell-2k-2}(2t+1)+\sum_{e\in F}2^{e-2k-1}\right), \end{align*} in which every exponent is non-negative. This is clearly impossible, since the righthand side is divisible by $2^{2k+2}$, and the lefthand side is not.

A similar contradiction arises if $2k+1>2\ell$, so $m+n\notin A$, and as we’ve already seen, this implies that $A\notin p+q$ and hence that $p+q\ne q+p$, and the proof is complete.

-
A 'nice exercise', indeed. – Thomas Klimpel Dec 2 '11 at 22:34
@Thomas: Yes, I thought that just a wee bit optimistic. To be fair, the argument could be simplified a little if we just wanted to construct a single non-commuting pair. – Brian M. Scott Dec 2 '11 at 23:22