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.

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!

share|improve this question
    
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

1 Answer 1

up vote 5 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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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