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?

  • $\begingroup$ Your first condition is redundant: all infinite sets have $|X|\ge\aleph_0$. $\endgroup$ – Adam Hughes Feb 26 '15 at 0:53
  • $\begingroup$ Is the second condition the same as saying all sequences in $B$ are eventually constant? $\endgroup$ – David P Feb 26 '15 at 0:56
  • $\begingroup$ @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"? $\endgroup$ – Tryss Feb 26 '15 at 0:57
  • $\begingroup$ @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). $\endgroup$ – Tryss Feb 26 '15 at 0:59
  • $\begingroup$ @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. $\endgroup$ – 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" . . .

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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