8
$\begingroup$

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,

  • 0
    BTW this is in fact part of [this question](http://math.stackexchange.com/questions/31147/sum-and-product-of-ultrafilters).2012-06-20

1 Answers 1

5

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.

  • 0
    @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.2011-12-02