2
$\begingroup$

According to Rosen, an infinite set A is countable if $|A|= |\mathbb{Z}^+|$ which in turn can be established by finding a bijection from A to $\mathbb{Z}^+$.

Also, a sequence is defined as a function from $\mathbb{Z}^+$ (or $\{0\} \cup \mathbb{Z}^+$) to some set.

With the above, a sequence is certainly enumerable. However, it need not be a bijection, e.g. Fibonacci(1) = Fibonacci(2) = 1.

This implies that not every sequence is countable which seems counterintuitive. Are there any results in this regard? Is there a mistake in the reasoning above?

$\endgroup$
6
  • $\begingroup$ Is the sequence $1,1,1,...$ countable? $\endgroup$
    – Yanko
    Feb 7, 2018 at 17:30
  • $\begingroup$ I suppose you mean the values taken by the sequence, that is, given a sequence $(a_n)_{n \in \mathbb N}$ (or $\mathbb Z^+$) then you're asking if the set $\{a_n : n \in \mathbb N\}$ is countable, right? $\endgroup$
    – amrsa
    Feb 7, 2018 at 17:34
  • 2
    $\begingroup$ "This implies that not every sequence is countable" ... um, i'm not following. Why does it imply that? A function from a countable set must be countable whether it is a bijection or not. $\endgroup$
    – fleablood
    Feb 7, 2018 at 17:35
  • $\begingroup$ @amrsa Yes, that is the question. $\endgroup$
    – wsaleem
    Feb 7, 2018 at 18:05
  • $\begingroup$ @Yanko The set of terms is {1} which is finite, thus countable. $\endgroup$
    – wsaleem
    Feb 20, 2018 at 21:59

3 Answers 3

2
$\begingroup$

Every sequence has a countable or a finite set of values.

Besides, you are mixing two ideas : a sequence $(u_n)_n$ is a function $n\mapsto u_n\in F$ ($F$ being any possible set) and almost never a bijection, but the set of all its values are finite or countable.

$\endgroup$
1
  • $\begingroup$ Yes, I made a more precise statement. $\endgroup$
    – Netchaiev
    Feb 7, 2018 at 17:36
2
$\begingroup$

"However, it need not be a bijection"

No, it doesn't.

"This implies that not every sequence is countable"

Why do you say that?

$f: \mathbb Z^+ \to B$. If $f$ is not surjective then there are points of $B$ that are not in the image. Those to not matter. We can restrict ourselves to $f: \mathbb Z^+ \to Im(B)$.

This must be surjective.

It doesn't need to be injective however and your Fibinocci example shows.

But... so what? Than means $|Im(B)| \le |\mathbb Z^+|$.

Hence it MUST be countable (or countably finite).

Anyway, as the terms of a sequence, as opposed to a set, need not be distinct it is possible, indeed common, for a sequence to have a finite number of distinct terms infinitely repeated.

$\endgroup$
10
  • $\begingroup$ A bijection is invertible. Consider the bijection from $\mathbb{Z}^+$ to the terms of the Fibonacci sequence. If the set of terms of the Fibonacci sequence is countably infinite, then, as per definition, such a bijection must exist. Let us call it $f$. What is $f^{-1}(1)$? $\endgroup$
    – wsaleem
    Feb 7, 2018 at 18:10
  • $\begingroup$ @wsaleem The bijection need not be given by the sequence itself ... $\endgroup$ Feb 7, 2018 at 18:13
  • $\begingroup$ Agreed. But no matter the function, we will have 2 distinct elements in the domain ($\mathbb{Z}^+$) mapping to the element, 1, in the co-domain. This function is not injective and therefore not a bijection. Thus, it seems that no bijection exists from $\mathbb{Z}^+$ to the set of terms of the Fibonacci sequence. $\endgroup$
    – wsaleem
    Feb 7, 2018 at 18:17
  • $\begingroup$ Wsaleem. I honestly fail to see your point. $\endgroup$
    – fleablood
    Feb 8, 2018 at 0:25
  • $\begingroup$ f (1)=13,f(2)=8;f (3)=1;f (4)=21;f (5)=3 etc. Is a bijection. $\endgroup$
    – fleablood
    Feb 8, 2018 at 0:31
0
$\begingroup$

As a sequence is a set indexed by the natural numbers, there exists a surjection from the naturals to the set. Let $A$ be the set and g: $\mathbb{N}\rightarrow A$ the surjection. Then we can define a map $f:A \rightarrow \mathbb{N}$ as $f(a)=$ the minimum natural number n such that $g(n)=a$. Then f is injective and thus A must be countably infinite or finite. Further, you can similarly show that every set indexed by a countably infinite set is either finite or countably infinite.

$\endgroup$

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.