4
$\begingroup$

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!

  • 0
    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](http://en.wikipedia.org/wiki/Cardinal_characteristic_of_the_continuum).2014-12-28

1 Answers 1

5

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$

  • 0
    Thank you so much, Gold medalist! :)2012-11-23