3
$\begingroup$

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.

$\endgroup$
4
  • 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$ Commented Feb 12, 2014 at 1:38
  • $\begingroup$ You never defined $F_n$ ... $\endgroup$ Commented Feb 12, 2014 at 1:40
  • 1
    $\begingroup$ Ah, I meant $F_n$ as a set containing some function $f:Z_+\rightarrow Z_+.$ $\endgroup$
    – Pubbie
    Commented Feb 12, 2014 at 1:41
  • 1
    $\begingroup$ Similar question: math.stackexchange.com/questions/411225/… $\endgroup$ Commented Feb 12, 2014 at 6:32

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .