Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

share|cite|improve this question
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


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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.