2
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Nov 9 '15 at 18:39

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael Nov 9 '15 at 19:29
4
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Nov 9 '15 at 19:30
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.