# Unbounded family of functions from $\mathbb{N}$ to $\mathbb{N}$

Definitions:

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.

Question:

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

Thank you for any help!

-
Is there a reason you posted the same question again? math.stackexchange.com/questions/243044/… – Asaf Karagila Nov 23 '12 at 22:17
I don't think this question is really a duplicate of the other question. See also my post in the meta thread for reopen request to see more details. – Martin Sleziak Dec 28 '14 at 10:07
Another way to reformulate this question: It is asking for the proof that the $\mathfrak b\ge\aleph_1$, where $\mathfrak b$ denotes the bounding number. – Martin Sleziak Dec 28 '14 at 10:25

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$