Question

Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]

Short answer

Proof that the set of all computer programs is countable by showing that the set of all computer programs is a subset of the countable set ${\cup }_{i=1}^{\infty }{A}_i$with $A_i=A\cup \left\{\lambda \right\}$.

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 (thus it is possible to list every single element in the set).

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

A set is uncountable if the set is not finite or countably infinite.

The function f is onto if and only if for every element $b\in B$there exist an element $a\in A$such thatdata-custom-editor="chemistry" $f\left(a\right)=b$ .

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

f is a one-to-one correspondence if and only if f is one-to-one and onto.

Step 2:

To proof: The set of all computer programs in a particular programming language is countable.

PROOF

Each computer program is a string of symbols from a finite alphabet. Let us call the finite alphabet A. Thus A is a finite set and thus A is also countable.

Since the computer program is a (finite) string of symbols from the finite alphabet, the computer program is an element of the union $U_{i=1}^{\infty }{A}_{i}with{A}_i=A\cup \left\{\lambda \right\}$ (where $\lambda$is the empty string).

Since A is countable, $A_i$is also countable (as contains only one more element compare to A).

However, the union of a countable number of countable sets is countable and thus $U_{i=1}^{\infty }{A}_i$is countable.

As all computer programs are elements in $U_{i=1}^{\infty }{A}_i$, the set of all computer programs is a subset of the countable set $U_{i=1}^{\infty }{A}_i$.

Since the subset of a countable set is also countable, the set of all computer programs is countable.