Limits of Logic #2: Undecidable Sets

15 Jul, 2024

1.5.5 Exercise: Undecidable Sets

Let $S$ be a set of strings. Let $P$ be a set of programs. Each program is a string in $S$ i.e. $P \subseteq S$ .

We can run any given program with a string input and it may or may not "succeed" (for example, by eventually printing a result True). So we have a two place relation program $A$ succeeds with input string s.

Say a string $X$ is decidable if and only if there is some program $A$ that succeeds for all and only the strings in $X$ . If there is no program $A$ like this then $X$ is undecidable.

Show that there is at least one undecidable set of strings.

Let's try to rephrase this exercise, and thus, this notion of undecidability in a more generic manner.

Although programs are relevant to undecidability as it is discusssed in Limits Of Logic, I find it is clarifying to notice how the notion of undecidability itself has no hard relation with this magical entity of "programs".

Also, the exercise is a bit of a word salad. Let's try:

Let $S$ be a non-empty set and $P \subseteq S$ .

We have a relation $R \subseteq P \times S$ .

A set $X \subseteq S$ is decidable iff there is some $s \in P$ such that $s R d$ for all and only $d \in X$ .

If there is no such $s \in P$ for some $X \subseteq S$ , then $X$ is undecidable.

Show there is at least one undecidable set $X \subseteq S$ .

I believe this is a correct generic restatement of the exercise. A subset is decidable if it's the image of an element under some relation. So, a set being "undecidable" simply means that the relation we're considering does not pick out that subset as an image of any of its inputs.

We'll see how this understanding of decidability holds as we move along the text and encounter what's meant to be the rigorous notion of decidability.

For now, the proof.

Proof:

Consider the function $f : P \to P S$ taking a program $s \in P$ to the set of all strings (inputs) $X \subseteq S$ that it succeeds with.

If the function $f$ is onto, it means that for any $X \subseteq S$ , there is at least one program $s \in P$ such that $f (s) = X$ .

But given Cantor's theorem, a function $f$ from the set of programs $P \subseteq S$ to the power set $P S$ cannot be onto. Therefore, there is at least one $X \subseteq S$ that is not in the range of $f$ .

This means there is at least one $X \subseteq S$ such that no program $s \in P$ succeeds with all and only the strings (input) in $X$ . And so, there is at least one undecidable set. $∎$

How should we understand the relation "program $A$ succeeds with input $s$ " and, as a result, what does the exercise really tell us (when it says there is an undecidable set)?

We can imagine appending a print statement (printing True) at the end of every possible program, such that the print statement always runs as long as the program does not run into an infinite loop.

This means we don't really care about whether a program suceeds in the way we'd expect a test case to succeed i.e. "the program is giving the intended output for whatever input." As long as the program terminates -- even as a result of "erroring out" -- we'll take it to print True and consider that it succeeds for its input.

So, we can rephrase the relation "program $A$ succeeds with input $s$ " as "program $A$ terminates for input $s$ ". In this way, we've interpreted any given program as an identifier, or a procedure that tells us the exhaustive and exclusive set of strings (inputs) it terminates for.

What then does the exercise tell us when it says there is an undecidable set.

A set $X$ is undecidable if there is no program which terminates for all and only those inputs in that set. That means, there is no "program" i.e. systematic procedure that can tell us whether a given string is a member of $X$ .

To see the higher level consequences of the result, note that there may be sets that we may be interested in (as we uncover later, sets like "the set of all true statements in a language / mathematics"), and there may be no program that can simply churn out the members of that set.