another question here to see if I'm on the right track. Here is the problem that I have been proposed.

Determine if the set $H$ of all functions $f:Z_+\rightarrow Z_+$ that are eventually constant is countable.

Here is my solution.

I claim the set $H$ is countable. By definition, we say that $f$ is eventually constant if there is a positive integer $N$ such that $f(n)=c,\textrm{c a constant,}\ \forall\ n\ge N.$ Let $F$ be a set containing some $f:Z_+\rightarrow Z_+.$ Let $$H=\bigcup_{n\in\mathbb{Z_+}}F_n=\{f:Z_+ \rightarrow Z_+ |f\in F_n\ \textrm{for at least one}\ n\in Z_+\}.$$ Since $H$ is an arbitary union of sets, we can define a function $g:Z_+\rightarrow H$, where $g$ is an indexing function of $H$ and $Z_+$ is the index set given. Since $g$ is an indexing function, this implies that $g$ is surjective. By Theorem 7.1, which states if $H$ is a nonempty set and there is a surjective function $f:Z_+ \rightarrow H$ then $H$ is countable, we have that $H$ is countable as claimed.

  • 5
    $\begingroup$ What is $F_n$? What is Theorem $7.1$? I can guess at both based on the context but at least for posting online to people not using your resources they should be spelled out. $\endgroup$ – John Habert Feb 12 '14 at 1:38
  • $\begingroup$ You never defined $F_n$ ... $\endgroup$ – Sergio Parreiras Feb 12 '14 at 1:40
  • 1
    $\begingroup$ Ah, I meant $F_n$ as a set containing some function $f:Z_+\rightarrow Z_+.$ $\endgroup$ – Pubbie Feb 12 '14 at 1:41
  • 1
    $\begingroup$ Similar question: math.stackexchange.com/questions/411225/… $\endgroup$ – Martin Sleziak Feb 12 '14 at 6:32

Alternatively, consider the following:

For a function $f:Z_+\rightarrow Z_+ $ such that $\exists N \in Z_+ : \forall n > N, f(n) = f(N) $

Let $M = min\{ N : \forall n > N, f(n) = f(N) \}$

and $S(f) = \sum_{i=1}^{M} f(i) + M$

Then for any value $k$, there are only finitely many such functions with $S(f) = k$. List all $f$ with $S(f)=1$ then all $f$ with $S(f)=2$ etc.


For each such function you have a polynomial p(x) in $\mathbb{Z}[x]$ with nth coefficient given by $a_n = f(n+1) - f(n)$ and $a_0 = f(1)$. Clearly f can be recovered from p and this correspondence is injective. So your set is countable.


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.