Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set.
I have tried proving set S as one to one corresponding to natural number set in binary form. like a = 0, b = 1. However, I am stuck in proving it since there are more than one "1", "01" = "1", same as other numbers.
A general way of showing this is proof by contradiction.
Assume (towards a contradiction) that the given set $S$ is finite, i.e.
$\qquad S = \{s_1, \dots, s_n\}$.
Show that there is an element $s \in S$ but for which $s \neq s_i$ for all $i \in [1..n]$.
One way to do this is to construct $s$ from $s_1, \dots, s_n$ explicity; that would be an instance of a diagonal argument.
Above step provides a contradiction, hence the assumption must be false: $S$ does not have this form.
Important: This only works if you make no assumptions whatsoever about the $s_i$ and $n$ (beyond what you know about $S$ already). If you do, you have not argued against all finite candidates for $S$.
Show that $\mathbb{N}$ is infinite.
Assume the opposite. Then, $\mathbb{N} = \{n_1, \dots, n_N\}$ for some $N$. Let $n = \max \mathbb{N}$. Then, by the definition of the natural numbers, $n+1 \in \mathbb{N}$ as well. But that contradicts that $n$ is the largest number in $\mathbb{N}$; the assumption must be false.
You can prove that a set is infinite simply by demonstrating two things:
In essence, this demonstrates that the a subset, consisting of a, aa, aaa, . . . is infinite. This latter clearly maps to the integers.
A general method is to show that $S$ has an infinite subset.
That is, you show that there is $A \subseteq S$ for which you already know that $|A| = \infty$.
Show that $\mathbb{Z}$ (or $\mathbb{Q}$, $\mathbb{R}$, ...) is infinite.
We already know that $\mathbb{N}$ is infinite (see my other answer). Hence, $\mathbb{Z} \supsetneq \mathbb{N}$ is also infinite.
A general way of showing that a set $S$ is infinite is giving a one-to-one map from $S$ to a proper subset of $S$. For example, the map $f(n) = 2n$, mapping the integers bijectively to the even integers, shows that there are infinitely many integers.
There is a nice bijection between finite strings over the alphabet $\{1,2\}$ and the non-negative integers. The mapping is $$ f(x_{n-1} \ldots x_0) = \sum_{i=0}^{n-1} x_i 2^i. $$ The first few strings according to this bijection are $$ \epsilon, 1, 2, 11, 12, 21, 22, 111, \ldots $$ The same idea works for the alphabet $\{1,\ldots,d\}$: $$ f_d(x_{n-1} \ldots x_0) = \sum_{i=0}^{n-1} x_i d^i. $$
