# Caleb Stanford

## Uncomputable binary relations

math computability model-theory

Consider a binary relation $R$ on a countable set $S$, i.e. $R \subseteq S \times S$. Equivalently, this is a directed graph where $S$ is the set of vertices and $R$ is the edge relation. We might be interested in whether $R$ is computable: given vertices $x, y \in S$, is it decidable whether $xRy$?

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

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

1. Unconditionally computable: for any bijection $\sigma: S \to \mathbb{N}$, $\sigma(R)$ is computable.

2. Conditionally computable: there exist bijections $\sigma_1, \sigma_2: S \to \mathbb{N}$ such that $\sigma_1(R)$ is computable but $\sigma_2(R)$ is not.

3. Uncomputable: for any bijection $\sigma: S \to \mathbb{N}$, $\sigma(R)$ is uncomputable.

Some examples should make this classification more clear:

• Suppose $(S,R)$ is a directed graph with a specific vertex $a \in S$, and

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

• Let $S = \mathbb{N}$, with

If $\sigma$ is the identity function $\mathbb{N} \to \mathbb{N}$, then this is certainly computable. However, we can instead have $\sigma$ 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 $R$ becomes uncomputable. So this relation is of type (2).

• Let $S = \mathbb{N}$ again, with

This is again computable if $\sigma$ 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 $(n,n+1) \in \sigma(R)$ for every odd $n$ representing a halting Turing machine, and $(n+1,n) \in \sigma(R)$ for every odd $n$ 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 $R$ to consist of a cycle of length $BB(n)$, for each natural number $n$, where $BB$ 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. $R$ has type (1) if and only if there exists a finite subset $S_0 \subseteq S$ such that for all $x \in S$ and for all $y, y' \in S \setminus S_0$, $xRy$ if and only if $xRy'$ and $yRx$ if and only if $y'Rx$. In other words, all vertices outside of $S_0$ are indistinguishable from each other; any vertex is either connected to all of $S \setminus S_0$, or none of $S \setminus S_0$.

An equivalent way of saying the above condition is that there is a quantifier-free formula $\varphi(x,y)$ over the language of equality and allowing constants from $S$, that defines $R$. I.e., $xRy$ if and only if $\varphi(x,y)$.

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 $2^{\aleph_0}$, 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 $S$ is the underlying set of the model, and $R$ 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 .