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:
-
Unconditionally computable: for any bijection \(\sigma: S \to \mathbb{N}\), \(\sigma(R)\) is computable.
-
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.
-
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
\[R = \{(a,y) \mid y \in S\}.\]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
\[R = \{(x,0) \mid x \text{ is even}\} \cup \{(x,1) \mid x \text{ is odd}\}.\]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
\[R = \{(x,y) \mid x < y\}.\]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.