If $x_n$ is a 0,1 sequence such that $\text{p-lim}(x_n) = 1$, then any 0,1 sequence $y_n \supset x_n$ has $\text{p-lim}(y_n) = \text{p-lim}(x_n) = 1$.

Question

I am working through this post from Terry Tao's blog.

Problem: Prove that if a binary (i.e. consisting of $0$ and $1$, or $\top$ and $\bot$) sequence $x_n$ is such that $\text{p-lim}(x_n) = 1$, then any sequence $y_n$ containing $x_n$ has $\text{p-lim}(y_n) = \text{p-lim}(x_n) = 1$.

My attempt at a proof. We know the following facts regarding $\text{p-lim}$:

• homomorphic: $\text{p-lim}(1) = 1$, $\text{p-lim}(Cx_n) = C\text{p-lim}(x_n)$ (for some $C \in \{0, 1\}$), $\text{p-lim}(x_n \oplus y_n) = \text{p-lim}(x_n) \oplus \text{p-lim}(y_n)$ (where $\oplus$ is the "or" operator), and $\text{p-lim}(x_n \otimes y_n) = \text{p-lim}(x_n) \otimes \text{p-lim}(y_n)$ (where $\otimes$ is the "and" operator)
• bounded: $\text{p-inf}(x_n) \leq \text{p-lim}(x_n) \leq \text{p-sup}(x_n)$
• non-principality: deletion of a finite number of elements from $x_n$ should not change its $\text{p-lim}$.

We do not know anything else about $\text{p-lim}$, so a combination of these facts must be used to prove the required.

Note that $x_n$ will never be finite, since it is an indicator sequence which runs over all the natural numbers, hence $y_n$ will never be finite either. So non-principality is unlikely to be a useful tool. The supremum and infimum of every sequence of binary numbers which is not $1, 1, 1, 1, 1, 1 \dots$ or $0, 0, 0, 0, 0, 0, \dots$ is trivially $0$ and $1$ respectively, so it is unlikely that boundedness can be used as a tool.

Let us try to use the fact that $\text{p-lim}$ is a homomorphism. Note that $y_n \oplus x_n = y_n$, since $x_n \subset y_n$ (in other words, $x_k = 1 \Rightarrow y_k = 1$, while $x_k = 0 \Rightarrow (y_k = 1 \vee y_k = 0)$). Then:

\begin{align*} &\quad\;\; x_n \oplus y_n = y_n \\ &\Rightarrow \text{p-lim}(x_n \oplus y_n) = \text{p-lim}(y_n) \\ &\Rightarrow \text{p-lim}(x_n) \oplus \text{p-lim}(y_n) = \text{p-lim}(y_n) \\ &\Rightarrow 1 \oplus \text{p-lim}(y_n) = \text{p-lim}(y_n) \\ &\{\text{1 is the zero of $\oplus$}\} \\ &\Rightarrow 1 = \text{p-lim}(y_n) \end{align*}

---

Is this proof correct? The following assumptions, I think, will need confirmation:

• On the space of binary numbers, is it okay to assume that $\oplus, \otimes$ are the analogues of $+, \times$, for the homomorphism property? I think it should be okay, because: 1) it makes things work out nicely (I think I can use similar logic to show that some of the other ultrafilter properties hold for the $\text{p-lim}$ over the binary numbers), and connects nicely to classical "predicate calculus" stuff; 2) $\oplus, \otimes$ can also be thought of as "addition/multiplication $\mathbb{Z}/2$")

Answer 1

You can go about it in two ways, which come down to the same thing. If we have a $p$-lim for sequences with values $0$ and $1$ we can identify a sequence $x=(x_n)$ with a subset $A(x) \subseteq \omega$ where $n \in A(x)$ iff $x_n =1$ (using characteristic functions, in other words, or indicator sequences as Tao calls them). As $p$-$\lim(x_n) \in \{0,1\}$ as well, as he also shows, we have that a $p$-lim defines a non-principal ultrafilter $\mathcal{F}$ on the powerset of $\omega$: $A \in \mathcal{F}$ iff the indicator sequence $\chi_A$ has $p$-$\lim(\chi_A)=1$. The monotonicity property you mention follows immediately from Tao's monotonicity principle: if two Boolean sequences $x,y$ obey: $\forall k: x_k =1 \implies y_k=1$, we see that $A(x) \subseteq A(y)$ and as $p$-$\lim(x)=1$ so $A(x) \in \mathcal{F}$ we have $A(y) \in \mathcal{F}$ by monotonicity of ultrafilters, and so $p$-$\lim(y)=1$ as well.

To see the monotonicity of the ultrafilter (which Tao doesn't show) is to use the homomorphism properties. "$x$ is contained in $y$" (or $A(x) \subseteq A(y)$) in your definition is equivalent to the identity $1-x+xy=1$ or $xy-x=x(y-1)=0$ (i.e. this holds for all $k$, as reals). This identity is preserved by $p$-$\lim$ by its homomorphism property:

$$p\text{ -}\lim(x)\left(1-p\text{ -}\lim(y)\right) = 0$$

from which it follows that $p\text{ -}\lim(x)=1$ implies $p\text{-}\lim(y)=1$ which is what we needed.