# Can we write programs for all functions if we have an infinite alphabet?

If we have a finite alphabet, then the set of programs we can write is countably infinite (aleph naught). The set of all functions is uncountably infinite (cardinality of real numbers).

If we have an infinite alphabet, does that change the cardinality of the set of programs we can write? Can we write programs for all functions then?

Intuitively, if I tried to count the number of such programs, I would get stuck at the first character and never progress to the second character. That seems to suggest that it's uncountably infinite, but then I remember Cantor's trick of presenting rational numbers in diagonal rows, so I'm not sure if there is a (perhaps similar) way of presenting the programs in a countable way as well.

If by "infinite" you mean "countably infinite", and by "program" you mean "finite program", then the answer is no. The set of all finite sequences from a countably infinite set is countable.

If you allow infinite programs too, then you can of course write each function. Even if you have an alphabet containing just two letters.

If you mean an uncountable alphabet, then it depends whether or not the number of characters is smaller or not from the size of the continuum (something which is undecidable from the standard axioms of set theory). If no, and a program is finite, then the answer is still no; and if yes, then you can write many programs, so theoretically you can encode each and every function from $\Bbb N$ to itself by a single character, but how you will decode it is another story.

If your alphabet is countably infinite then no, you will still only be able to write programs for countably many functions.

Your program will consist of countably many characters. And each character can take on countably many values. So you can map the $i$-th character of the alphabet to the $j$-th character of the program, i.e. $(i,j)$ or "$i/j$". And then, as you suspect, apply Cantor's trick...

• Is it just the cartesian product set of the characters in the alphabet and the positions in the program string? – guest Jul 25 '14 at 19:05
• @guest: It is the Cartesian product with one factor for each position in the string. – Ross Millikan Jul 25 '14 at 19:10

If the programs are finite strings from a countably infinite alphabet, there are still only countably many of them. If you know the proof that $|\Bbb N\times \Bbb N|=\aleph_0$, you can extend it to any finite string. The one character strings are $\Bbb N$, the two character strings are $\Bbb N\times \Bbb N$ and so on. Then you have a countable union of countable sets. If you allow the programs to be infinite in length, you get uncountably many, even with a finite alphabet-just think of decimal expansions of real numbers.

Suppose we are assuming programs from the uncountable alphabet can be any subset of that alphabet (i.e. can themselves be uncountable). Assume we can assign one letter from our alphabet onto each program in a one to one fashion.

Consider the subset $X$ of letters (i.e. the program) in the uncountable alphabet consisting of those elements not used in their corresponding program. For instance, if $y$ is in $X$, and you have assigned $y$ to program $f_y$, then that means the letter $y$ was not used in the program $f_y$.

Has the program $X$ been mapped onto? If it has, say by letter $x$, then if $x$ is a member of $X$, it's used in its corresponding program - the program consisting of elements not used in its corresponding program! That's a contradiction, so $x$ must not be a member of $X$.

But wait - if $x$ is not a member of $X$, then $x$ is not used by its corresponding program. That means it must be a member of $X$. Another contradiction!

Therefore, it must be the case that the cardinality of our uncountable alphabet cannot match the cardinality of programs of our uncountable alphabet. The latter must be greater.

Sources: Cantor's Theorem (http://www.math.ucla.edu/~hbe/resource/general/131a.3.06w/cantor.pdf)