# 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$.

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$$")
• What do you mean by $(y_n)$ "containing" $(x_n)$? Sequences are functions, not sets.. It seems you mean $y_n \le x_n$ for all $n$? – Henno Brandsma Jan 30 '19 at 5:34
• It seems that you mean by "$x_n \subset y_n$" that $y_k \le x_k$ for all $k$; is that true? In the subset interpretation Tao gives the latter means that the subset of $\omega$ associated with $y$ is a subset of the one asssociated with $x$, so inclusion the other way around.... You seem confused. – Henno Brandsma Jan 30 '19 at 23:07
• @HennoBrandsma by $x_n$ being contained in $y_n$, I mean: $x_k = 1 \Rightarrow y_k = 1$ – user89 Jan 31 '19 at 18:45

## 1 Answer

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.

• Can you comment on whether my proof approach was okay or not? – user89 Feb 1 '19 at 3:47
• @user89 You have to prove separately that $\oplus$ is preserved. I do think it's true, as it can be defined in terms of $+,\cdot$ on the reals, when restricted to Boolean sequences, so do that. And you need to justify too that $x$ contained in $y$ iff $x \oplus y = y$. I think the equivalence is not true. – Henno Brandsma Feb 1 '19 at 5:28