1
$\begingroup$

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 )$

$\endgroup$
  • $\begingroup$ By $f\leq^*g$ do you mean $f(n) \leq g(n) \forall n\in \mathbb{N}$? $\endgroup$ – Jakob B. Jan 20 at 21:20
  • $\begingroup$ Yes, sorry, that was defined elsewhere. $\endgroup$ – j.lnhrt Jan 20 at 21:21
  • 1
    $\begingroup$ That is not the usual definition of $\le^*$. Please check what definition you are actually using. $\endgroup$ – Andrés E. Caicedo Jan 20 at 21:22
  • $\begingroup$ 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 )$ $\endgroup$ – j.lnhrt Jan 20 at 21:35
  • $\begingroup$ Please edit that definition into your question. It is the more common definition. It ruins the answer you have gotten. $\endgroup$ – Ross Millikan Jan 20 at 22:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! Got it now :) $\endgroup$ – j.lnhrt Jan 21 at 7:01
  • $\begingroup$ To the proposer: Alternatively let $f(n)=1+\sum_{j=1}^n f_j(n)$. $\endgroup$ – DanielWainfleet Jan 21 at 8:24

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.