What is the cardinal number of all strictly increasing sequences? I was able to find an injection from $(0,1)$ into the set of all strictly increasing sequnces by defining $i(a)=(a,1,2,3,4,\dots)$, where $a\in (0,1)$(Am I correct?). But I think that its cardinality is bigger than continuum. How do I prove that?
[Math] the cardinal number of all strictly increasing sequences
cardinalselementary-set-theorysequences-and-series
Related Solutions
The set you are talking about is sometimes written as $\def\N{\Bbb N}\binom\N2$ in combinatorics: the set of all $2$-element subsets of$~\Bbb N$. It has the same cardinality as$~\N$. An explicit bijection is given by the combinatorial number system system for $k=2$: map the subset $\{a,b\}$ with $a<b$ to $\binom a1+\binom b2=a+\frac{b(b-1)}2$.
A similar bijection holds for $k$-element subsets for any fixed finite$~k$ (see the linked page). Even the union of all those sets is in bijection with$~\N$; in this case a slightly different bijection works: interpret the subset as a binary number, with the bit in position$~i$ indicating whether $i$ is present in the subset (value $1$) or not (value $0$).
In order to get an uncountable collection of subsets of$~\N$, your collection must contain some subsets that are infinite, and moreover need infinite information to describe (a necessary but not sufficient condition). As long as each element can be specified, using some fixed and definite encoding, by a finite amount of data, one can order the elements by size of those data first, and then for a fixed size by some total ordering of the encoding data (lexicographically for instance); this produces a well-ordering in which each element occurs in a position corresponding to a natural number. The above bijections are in fact inspired by fairly simple such ordering schemes, but using "largest element" in the place of "data size" (but that would no longer work for collections containing infinite subsets with finite descriptions).
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.
Best Answer
Fix a strictly increasing sequence whose limit is $1$, for example: $$a_n=\frac{n}{n+1}$$
Now for every $c\in (0,1)$ the sequence $c_n=c\cdot a_n$ is strictly increasing and converges to $c$. Thus we easily obtain that there are at least $2^{\aleph_0}$ many strictly increasing sequences.
On the other hand every sequence is a function from $\mathbb N$ into $\mathbb R$. Since $\left|\mathbb R\right|=\left|\{0,1\}^\mathbb N\right|$ we have that $\left|\mathbb R^\mathbb N\right|=\left|\left(\{0,1\}^\mathbb N\right)^\mathbb N\right|$.
From How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers? we deduce that this set, therefore, has the same cardinality as $\{0,1\}^{\mathbb N\times\mathbb N}$. Using Cantor's pairing function (or a different method) we have that $|\mathbb N|=|\mathbb N\times\mathbb N|$, thus obtaining: $$\left|\mathbb R^\mathbb N\right|=\left|\{0,1\}^{\mathbb N\times\mathbb N}\right|=\left|\{0,1\}^\mathbb N\right|=|\mathbb R|$$
So we have that the set of all strictly increasing sequences is a subset of $\mathbb R^\mathbb N$, so it cannot be more than $2^{\aleph_0}$ but on the other hand we have at least $2^{\aleph_0}$ many sequences in this set.
By Cantor-Bernstein we therefore have that this set has $2^{\aleph_0}$ many elements.