# Countable set of sequences - is there a sequence where every element is greater or equal?

I'm looking at this question:

$$\mathrm { N } ^ { \mathrm { N } } : = \{ f : f : \mathrm { N } \rightarrow \mathrm { N } \}$$ is the set of all sequences of natural numbers. Let $$A= \left\{ f _ { n } \in \mathbb { N } ^ { \mathrm { N } } : n \in \mathrm { N } \right\}$$ be any countable subset (finite or infinite) of $$\mathrm { N } ^ { \mathrm { N } }$$. Is there a sequence $$f \in \mathrm { N } ^ { \mathrm { N } }$$ where $$f _ { n } \leq ^ { * } f\quad \forall n \in \mathrm { N }$$?

My assumption would be that the answer is yes, however I have no idea how to even begin to prove it. I'm guessing the fact that $$A$$ is countable is important. My only idea would be that, because it is countable, you can possibly order the sequences for each n and then let $$f(n)$$ be the element of the sequence which is ranked highest, but I really don't know.

I would be thankful for any suggestions!

Edit:

Definition of $$f\leq ^ { * } g$$ : $$\exists m \in \mathbb { N } : \forall n \in \mathbb { N } \text { where } n \geq m \Longrightarrow f ( n ) \leq g ( n )$$

• By $f\leq^*g$ do you mean $f(n) \leq g(n) \forall n\in \mathbb{N}$? – Jakob B. Jan 20 at 21:20
• Yes, sorry, that was defined elsewhere. – j.lnhrt Jan 20 at 21:21
• That is not the usual definition of $\le^*$. Please check what definition you are actually using. – Andrés E. Caicedo Jan 20 at 21:22
• Sorry again... It was only vaguely defined in two sentences ahead of the question. I did however find this definition in my lecturer's notes later on: $\exists m \in \mathbb { N } \text { : } \forall n \in \mathbb { N } \text { where } n \geq m \implies f ( n ) \leq g ( n )$ – j.lnhrt Jan 20 at 21:35
• Please edit that definition into your question. It is the more common definition. It ruins the answer you have gotten. – Ross Millikan Jan 20 at 22:14

Yes, given a countable $$A$$ there is a sequence $$f$$ where all of them are $$\le^*$$ than $$f$$. We set $$f(1)=f_1(1)+1\\ f(2)=\max(f_1(2),f_2(2))+1\\ f(3)=\max(f_1(3),f_2(3),f_3(3))+1\\ f(n)=\max_{i=1}^n(f_i(n))+1$$ This is greater than the first sequence starting at $$1$$, greater than the second starting by $$2$$, greater than the $$n^{th}$$ starting by $$n$$. Each of the $$\max$$ functions has a finite list of arguments, so is well defined. Diagonalization wins again.
• To the proposer: Alternatively let $f(n)=1+\sum_{j=1}^n f_j(n)$. – DanielWainfleet Jan 21 at 8:24