[Math] Strictly monotonically increasing sequences of natural numbers

elementary-set-theorynatural numberssequences-and-series

I have several questions with regards to these sequences:

  1. What is the cardinality of the set of all such sequences?

    I assume that it is equal to the cardinality of $\mathbb{R}$, is that correct?

  2. Consider those sequences which can be expressed with a finite formula.

    Is the cardinality of the set of those sequences equal to the cardinality of $\mathbb{R}$?

  3. Are there any other sequences which cannot be expressed with a finite formula?

    I have a feeling that this question might lead to a paradox, hence cannot be answered.

    Nevertheless, my intuition tells me that there have to be infinitely many such sequences.

    How can we prove that, and how can we find the cardinality of the set of those sequences?

Examples of a finite formula:

  1. $A_n=n$

  2. $An=2n$

  3. $An=$ the $n$th prime

  4. $A_1=1,A_2=2,A_n=A_{n-1}+A_{n-2}$

  5. $A_n=\begin{cases}
    n+1&\text{$ 1\leq{n}\leq 10$}\\
    n+2&\text{$ 11\leq{n}\leq 100$}\\
    n+3&\text{$ 111\leq{n}\leq 1000$}\\
    n+4&\text{$1111\leq{n}\leq10000$}\\
    n+5&\text{ otherwise }\\
    \end{cases}$

Best Answer

Yes, you are correct that there are $2^{\aleph_0}$ strictly increasing sequences. An easy way of seeing this is to note that given a set $A\subseteq\Bbb N$ you can define a function $f$ such that $f(0)=0$ and $\chi_A(n)=f(n+1)-f(n)-1$.

For the second question, and simultaneously the third, "finite formula" is a very ambiguous term. What is the language in which we are allowed to express this formula? If the language only includes $+$ and $\cdot$ and $\leq$, or any countable number of symbols, then there are only countably many finite formulas in that language to begin with, not all even define functions or increasing functions.

But if you don't specify the language, why not take the language which includes a function symbol for every possible function from $\Bbb N$ to itself? And axioms which describe the behavior of these functions on every natural number completely. In that case, each function can be described using a very short formula.

So the second and third questions, which are tied together, cannot be fully answered without specifying what a "finite formula" means exactly. If we play the naive assumption game, then the answer is that there are only countably many finite formulas, so "almost" all functions are undefinable.

EDIT:

In the comments the OP points out that every real number can be used as part of the language. This means that in fact every function from $\Bbb N$ to itself can be defined with a finite formula, and a real number as a parameter.

To see this, just consider real numbers $r$ whose expansion in a fixed basis includes only $1$ and $0$ (which exist in all bases, but there are other tricks to use here). Now use the $0$ as delimiters for the blocks of $1$, and just "read off" the length of the $n$-th block as the value for $f_r(n)$.

Other wonderful ways of encoding and decoding exist. For example continued fractions.

Related Question