what is the relevance of computability when applying diagonallization?

Question

When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter?

Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?

Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?

Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable? Something seems wrong here.

In general, what are the catches when doing diagonalization pertaining to computability?

Answer 1

There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove:

• that there is no surjection from a set to its powerset
• that the real numbers cannot be enumerated
• that the computable real numbers cannot be computably enumerated
• that the Halting oracle does not exist
• etc.

In its most general form it is known as Lawvere's fixed-point theorem.

You ask what happens if you diagonalize against the rational numbers. You did not specify in what form the rationals are given, I am assuming you mean their decimal expansions. The diagonalization will produce a real number which is not a member of the enumeration (this real may be rational or irrational, depending on what enumeration you started with). If you start with a non-computable enumeration, the result may be non-computable. If you start with a computable enumeration, you will get a computable result, because diagonalization preserves computability.

Likewise, if you take a computable enumeration of computable real numbers (given as infinite sequences of digits), the result of diagonalization will be a computable real number which is not a member of the starting enumeration.

Answer 2

I am not sure how to answer the general question, but for the specific ones:

Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?

Why not just an irrational number?

Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?

For the set of all computable numbers yes.

Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable?

It's clearly computable thus proving you can't have a computable enumeration of all computable real numbers.