Caleb Stanford


math random-facts

The current year, translated to various systems for your convenience:

Fun fact: All of these number systems have a unique representation theorem of some kind. However, the only which offer a unique representation for all integers, and not just for all nonnegative integers, are negabinary and offset base 3. For traditional decimal or binary numbers, you either only have representations for nonnegative integers, or you allow a possible minus sign in front at which point you get two representations of zero.

For uniqueness of Zeckendorf representation, one requires that there are no two adjacent 1s.

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.

"I'm moving to Canada"

politics random-facts

“If Donald Trump wins this election, I’m moving to Canada.”

According to a recent poll, Democrats are three times as likely to say they would leave the country if their candidate loses.

Sanity check: Google searches for moving to canada do seem to have strong political correlation – the huge spikes occur at Bush’s reelection in 2004, and at Super Tuesday in the 2016 primaries. But the consensus from articles on the subject is that that actual moves to Canada do not really go up.

« Newer Posts Older Posts »