Question

Show that the set of all finite bit strings is countable.

Short answer

The set of all finite bit strings is countable.

Step-by-step solution

Step 1:

DEFINITIONS:

A set is countable if it is finite or countably infinite.

A set is finite if it contains a limited number of elements.

A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

The function f is one-to-one if and only if f (a) = f (b) implies that for all a and b in the domain.

X is a subset of Y if every element of X is also and element of Y. Notation: .

Definition (2): There is a one-to-one function from A to B if and only if $\left|A\right|\le \left|B\right|$.

Difference A - B : All elements in A that are NOT in B.

Step 2:

To proof: The set S of all finite bit strings is countable.

PROOF:

Let us definite the function f as:

$f:S\to Z^{+},f\left(s\right)=$decimal representation.

Thus, translates each string to its decimal representation.

Check that f is one-to-one: If f (s) = f (t), then the decimal representation of s and f are the same. Thus, and represent the same positive integer and then the binary representations also have to be the same.

s = t

By the definition of one-to-one, we have then shown that f is a one-to-one function.

By definition (2):

$\left|S\right|\le \left|Z^{+}\right|$

A set A is countable if and only if $\left|A\right|\le \left|Z^{+}\right|$. Thus, we have then shown that S is countable.