Caleb Stanford

Uncomputable binary relations

math computability model-theory

Consider a binary relation on a countable set , i.e. . Equivalently, this is a directed graph where is the set of vertices and is the edge relation. We might be interested in whether is computable: given vertices , is it decidable whether ?

However, this doesn’t make sense, because we haven’t picked a representation of the elements of – we need to first assign elements of to natural numbers (alternatively, to binary strings). Given any bijection , we can then ask if ( applied to each coordinate of each pair in the relation) is a computable relation on .

We might split all binary relations / directed graphs on , then, into three types:

  1. Unconditionally computable: for any bijection , is computable.

  2. Conditionally computable: there exist bijections such that is computable but is not.

  3. Uncomputable: for any bijection , is uncomputable.

Some examples should make this classification more clear:

  • Suppose is a directed graph with a specific vertex , and

    This is a relation of type (1), because no matter how we represent vertices as natural numbers, is some particular number, and we can decide if by just checking if .

  • Let , with

    If is the identity function , then this is certainly computable. However, we can instead have send all odd numbers to halting turing machines, and even numbers to non-halting turing machines (where turing machines are represented as natural numbers in a standard way). If so, then becomes uncomputable. So this relation is of type (2).

  • Let again, with

    This is again computable if is the identity bijection, because is a computable relation on natural numbers. But once again using a general bijection we can cause it to be uncomputable. For example, we can arrange so that for every odd representing a halting Turing machine, and for every odd representing a non-halting Turing machine. So this is another example of type (2).

I’m told I’m not supposed to put exercises in a blog post, but here I go:

Exercise. Construct a relation of type (3).

(Hint: One approach is for to consist of a cycle of length , for each natural number , where is the busy beaver function. Then you have to prove that this works.)

Some observations

There are only countably many relations of type (1), and they are of a very particular kind. Here is a classification theorem:

Theorem. has type (1) if and only if there exists a finite subset such that for all and for all , if and only if and if and only if . In other words, all vertices outside of are indistinguishable from each other; any vertex is either connected to all of , or none of .

An equivalent way of saying the above condition is that there is a quantifier-free formula over the language of equality and allowing constants from , that defines . I.e., if and only if .

On the other hand, there are uncountably many relations of type (2) (for silly reasons), but there are only countably many non-isomorphic relations of type (2). Since the number of non-isomorphic countable graphs is , this means “most” relations are of type (3).

Although we can’t construct one explicitly, it turns out that any countable model of ZFC is of type (3). (In this case is the underlying set of the model, and is the “is an element of” binary relation.) In contrast, the standard model of Peano Arithmetic is entirely computable – successor, addition, and multiplication are all computable relations (or computable functions, it doesn’t matter) on the natural numbers – so PA has a model of type (2). This is one way that ZFC is measurably more complex than a theory like PA.

Edited on .