Question

Prove that if it is possible to label each element of an infinite set S with a finite string of keyboard characters, from a finite list characters, where no two elements of S have the same level, then S is a countably infinite set.

Short answer

Proved using that the countable union of finite sets is countable and that all infinite subsets of a countable set are countable.

Step-by-step solution

Step 1:

Given,

Let K be the finite set of characters which we are using to label S.

Let $\sum s$be the set of finite strings of keyboard.

Characters from K assigned to each element of S.

Each element of $\sum s$can be given by an ordered tuple of elements of K.

Then, there is a one-to-one correspondence between $\sum s$and S.

Step 2:

Let $\sum =\underset{n=0}{\overset{\mathrm{\infty }}{\cup }} K^n$.

Then,$\sum _{}$ is a countable set.

Step 3:

$\sum s\subseteq \sum$

$\sum s$is a set which comprises of ordered n-tuples of elements of K for some positive integers n.

Since $\sum$is the set of all such finite tuples, the subset relation holds.

Step 4:

$\sum s$is countable.

All infinite subsets of a countable set are countable.

Therefore, S is countable by the given one-to-one correspondence between S and $\sum s$.