Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Family of unbounded functions is uncountable.


  1. For functions $f,g:\mathbb{N}\to \mathbb{N}$, we say $f\leq ^{*} g$ if there exist $n\in\mathbb{N}$ such that for $n\leq m$ we have $f(m)\leq g(m)$

  2. Family $F$ of functions from $\mathbb{N}$ to $\mathbb{N}$ is unbounded if for every function $g:\mathbb{N}\to \mathbb{N}$, exist $f\in F$ such that $f\leq ^{*} g$ isn't holds.


Show that an unbounded family $F$ of functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable.

Thank you for any help!

share|improve this question

marked as duplicate by Andres Caicedo, Asaf Karagila, Micah, Marvis, Cameron Buie Nov 24 '12 at 0:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Is there a reason you posted the same question again? math.stackexchange.com/questions/243044/… –  Asaf Karagila Nov 23 '12 at 22:17

1 Answer 1

up vote 3 down vote accepted

Instead of showing that every unbounded family is uncountable, let's try the (equivalent) contraposition: Show that every countable family fails to be unbounded. Let $F$ be a countable family of functions $\mathbb N\to \mathbb N$. That is, there exists a bijection $\mathbb N\to F$, or simply put, we can enumerate the elements of $F$ like this: $$\tag1F=\{f_n\mid n\in\mathbb N\}.$$ This $F$ would be unbounded if for every $g\colon\mathbb N\to \mathbb N$ there exists an $f\in F$ such that $f\le^* g$ is false. Thus we have to show that there exists $g\colon\mathbb N\to \mathbb N$ such that for all $f\in F$ the statement $f\le^* g$ is true.

Simply define $$\tag2g(n)=\max\{f_k(n)\mid k\le n\}.$$ Now let $f$ be an arbitrary element of $F$. We have to show $f\le^* g$. By $(1)$, we have $f=f_n$ for some $n$. Then using $(2)$ $$\tag3g(m)=\max\{f_k(m)\mid k\le m\}\ge f(m)\quad \text{for }m\ge n$$ because $f$ occurs among the $f_k$ with $k\le m$. But $(3)$ is just the definition of $f\le^* g$. $_\square$

share|improve this answer
Can you elaborate, because what you wrote appears as a hint to the problem? –  17SI.34SA Nov 23 '12 at 21:59
I thought I was very verbose!? –  Hagen von Eitzen Nov 23 '12 at 22:01
Thank you so much, Gold medalist! :) –  17SI.34SA Nov 23 '12 at 23:45

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