The question is simple, and the answer may be obvious, but it eludes me... Does it exist a countable set of sequences $S \subset \mathbb{N}^\mathbb{N}$ such that

$$\forall v \in \mathbb{N}^{\mathbb{N}}, \exists u \in S, v \leq u$$

  • $\begingroup$ What is your ordering $\leq$ on $\mathbb N^{\mathbb N}$? $\endgroup$ – William Stagner Mar 1 '15 at 22:05
  • $\begingroup$ The usual ordering, $$v \leq u \Leftrightarrow \forall n \in \mathbb{N}, v_n \leq u_n $$ $\endgroup$ – Tryss Mar 1 '15 at 22:06

No, by a diagonalization argument. Let $S=\{s^{(n)}:n\in\Bbb N\}$, where $s^{(n)}=\left\langle s_k^{(n)}:k\in\Bbb N\right\rangle$. For each $k\in\Bbb N$ let

$$s_k=1+\max\left\{s_k^{(n)}:n\le k\right\}\;,$$

and let $s=\langle s_k:k\in\Bbb N\rangle$. Then for each $n\in\Bbb N$ we have $s^{(n)}\not\le s$.

  • $\begingroup$ Thanks ! I should have think of this... :( $\endgroup$ – Tryss Mar 1 '15 at 22:13
  • $\begingroup$ @Tryss: You’re welcome! (I know that feeling all too well myself.) $\endgroup$ – Brian M. Scott Mar 1 '15 at 22:13

This is an example of a 'diagonalization' argument. Since your sequences are countable you can list them as $S_N $ for natural numbers $N $ and then construct a sequence that is greater than $S_n (N) $ for all $n$ less than or equal to $N $. Then no sequence in your set will dominate the construcTed sequence.


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.