10
$\begingroup$

I was wondering if a sequence that has every element of $\mathbb N$ infinite number of times exists ($\mathbb N$ includes $0$). It feels like it should, but I just have a few doubts.

Like, assume that $(a_n)$ is such a sequence. Find the first $a_i \not = 1$ and the next $a_j, \ \ j > i, \ \ a_j = 1$. Swap $a_j$ and $a_i$. This can be done infinitely many times and the resulting sequence has $1$ at position $M \in \mathbb N$, no matter how large $M$ is. Thus $(a_n) = (1_n)$.

Also, consider powerset of $\mathbb N, \ \ 2^{\mathbb N}$. Then form any permutation of these sets, $(b_{n_{\{N\}}})$. Now simply flatten this, take first element $b_1$ and make it first element of $a$ and continue till you come to end of the first set and then the next element in $a$ is the first element of $b_2$... But again, if you start with set $\{1 | k \in \mathbb N\}$ (infinite sequence of ones), you will get the same as in the first case...

You would not be able to form a bijection between this sequence and a sequence that lists every natural number once, for if you started $(a_n)$ with listing every natural number once, you would be able to map only the first $\aleph_0$ elements of $(a_n)$ to $\mathbb N$.

But consider decimal expansion of $\pi$. Does it contain every natural number infinitely many times?

What am I not getting here?

What would the cardinality of such a sequence, if interpreted as a set, be?

$\endgroup$
22
$\begingroup$

$$\langle \underbrace{0}_{1\text{ term}},\underbrace{0,1}_{2\text{ terms}},\underbrace{0,1,2}_{3\text{ terms}},\underbrace{0,1,2,3}_{4\text{ terms}},\underbrace{0,1,2,3,4}_{5\text{ terms}},\dots\rangle$$

Each $n\in\Bbb N$ appears in all but the first $n$ blocks, hence infinitely often.

$\endgroup$
  • $\begingroup$ Oh dear, I was over thinking (or under thinking) again... $\endgroup$ – Valtteri Mar 12 '13 at 21:21
  • $\begingroup$ My powerset example is wrong, because every subset has every number just once and the first example was dubious to begin with. $\endgroup$ – Valtteri Mar 12 '13 at 21:26
9
$\begingroup$

Let $f\colon\Bbb{N\to N\times N}$ be a bijection, and let $a_n$ be the right coordinate of $f(n)$, then $\langle a_n\mid n\in\Bbb N\rangle$ is a sequence covering all the elements of $\Bbb N$, and each appearing infinitely many times.

$\endgroup$
  • 1
    $\begingroup$ Indeed, the existence of such a bijection is equivalent to this statement. $\endgroup$ – Thomas Andrews Mar 12 '13 at 21:22
8
$\begingroup$

Let $a_n$ be the largest natural number, $k$ such that $2^k$ divides $n+1$

$\endgroup$
  • $\begingroup$ This is my favorite example, partly because of the short but complete description. It has an alternative (longer) description as: Put 0 in every second position; put 1 in every second of the positions that are still vacant; put 2 in every second of the positions that are still vacant; etc. $\endgroup$ – Andreas Blass Nov 21 '18 at 15:57

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.