# How to prove a set has infinite cardinality?

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.

• This seems to be a pure mathematics question; I wonder why you got migrated here. (Update: I checked with the responsible SO mod; a mistake happend.) – Raphael Nov 9 '15 at 19:29

A general way of showing this is proof by contradiction.

1. Assume (towards a contradiction) that the given set $S$ is finite, i.e.

$\qquad S = \{s_1, \dots, s_n\}$.

2. 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.

3. 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$.

### Example

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.

• Note that this method scaled to "higher" notions of "size": you can show uncountability of sets in exactly the same way. – Raphael Nov 9 '15 at 19:36

You can prove that a set is infinite simply by demonstrating two things:

• For a given n, it has at least one element of length n.
• If it has an element of maximum finite length, then you can construct a longer element (thereby disproving that an element of maximum finite length).

In essence, this demonstrates that the a subset, consisting of a, aa, aaa, . . . is infinite. This latter clearly maps to the integers.

• Your method is tied to the objects having a "length" or, more generally speaking, a "size". While that's true here, it may not always be. – Raphael Nov 9 '15 at 19:30

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$.

### Example

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.$$