# Does it always exist an infinite subset of sequences that satisfy this property?

Let $E = \left\lbrace u \in \mathbb{N}^{\mathbb{N}} : u_{n+1} \geq u_n \right\rbrace$ be the set of increasing sequences. It's know that $\text{card}(E) = 2^{\aleph_0}$

The question is : for all $S\subset E$ with $\text{card}(S) = 2^{\aleph_0}$, does it exist a an infinite subset $B$ of $S$ such as :

• $\text{card}(B) \geq \aleph_0$
• $\forall k \in \mathbb{N}, \: \sup \lbrace u_k : u \in B \rbrace < +\infty$

If this property is false, how can we construct such a set $S$ that doesn't verify it?

• Your first condition is redundant: all infinite sets have $|X|\ge\aleph_0$. – Adam Hughes Feb 26 '15 at 0:53
• Is the second condition the same as saying all sequences in $B$ are eventually constant? – David P Feb 26 '15 at 0:56
• @AdamHughes: yes, I know. it's purely a question of clarity that I repeated it. You think it would be less confusing if I removed the "infinite"? – Tryss Feb 26 '15 at 0:57
• @DavidP : No, it isn't. It means that there exist a sequence that bound the set of sequences (this bounding sequence is not necessary in the set). – Tryss Feb 26 '15 at 0:59
• @Tryss Monotone + bounded + discrete topology on $\Bbb N$ means eventually constant, no? The last condition says that the largest coordinate of anything in $B$ is finite, so that should force it. Perhaps you can clarify how this is not so. – Adam Hughes Feb 26 '15 at 1:02

Sure, this is an argument similar to the proof of Ramsey's theorem.

Let $S$ be the set of sequences, and let $E$ be some uncountable (need not be size continuum) subset of $S$. I'll define a sequence (heh) of sequences $f_i\in E$ with the desired properties; at the same time I'll define an auxiliary sequence $U_0\supseteq U_1\supseteq . . .$ of subsets of $E$.

The idea is that, at stage $k$ of the construction, the set $U_k$ will represent the collection of sequences which we might, at some future stage, throw into the $B$ we're building. As the construction goes along, the $U_k$s shrink, as we impose more and more requirements of the form "The $j$th bit of every sequence we throw into $B$ must be small!"

To begin, define $X_{k, n}=\{g\in E: g(k)\le n\}.$ Now onto the construction:

• First, set $U_0=E$, and pick any sequence in $U_0$ to be $f_0$.

• Now, since $E$ is uncountable, there is a least $n_0>f_0(0)$ such that $X_{0, n_0}$ is uncountable. Set $U_1=U_0\cap X_{0, n_0}$; note that $U_1$ is uncountable.

• Pick any sequence in $U_1$ to be $f_1$.

• Now since $U_1$ is uncountable, there is a least $n_1>g(1)$ such that $X_{1, n_1}\cap U_1$ is uncountable. Let $U_2=U_1\cap X_{1, n_1}$ for the least such $m$.

• Pick any sequence in $U_2$ to be $f_2$.

In general, having defined $U_k$ and $f_k$, we set $U_{k+1}$ to be $X_{k, n_k}\cap U_k$ where $n_k$ is the least number such that $X_{k, n_k}\cap U_k$ is uncountable.

The resulting set $B=\{f_i: i\in\omega\}$ has the desired property, as witnessed by the $n_i$s: $\sup\{u_k: u\in B\}\le n_k$.

Note that it is not enough just to take $\bigcap Y_i$, where $Y_i=X_{i, n}$ for $n$ least number such that $X_{i, n}$ is uncountable: consider the family $F$ of functions $f$ satisfying the property $$\exists i[(\forall j<i, f(j)=j)\text{ but } (\forall j\ge i, f(j)\ge j+1)].$$ This set is uncountable, and we can check easily that in this case $Y_i$ will be $\{f\in F: f(i)\le i\},$ but the intersection of the $Y_i$s is disjoint from $F$!

(If you're of a topological bent, similar issues come up when consider games played on topological spaces, such as Banach-Mazur and Choquet games . . .)

ASIDE: Note that we keep saying "Pick any . . ." in the above argument. This seems to require the axiom of choice! (Well, not the full axiom of choice, but some amount of choice.) A reasonable question, at this point, is: can we answer your question in $ZF$ alone? I don't know what the answer is, but I strongly suspect it's "no" . . .

• Thanks ! What I was missing was the idea to extract an element at each step... – Tryss Feb 26 '15 at 1:55
• Yeah, that's an important trick. It comes up with annoying frequency. :P – Noah Schweber Feb 26 '15 at 1:57