Uniformness, and the Halting problem

Uniformness#

The usual story#

Given a countable pair of socks, are there countable socks?

If we substitute "shoes" for "socks", then it is obvious. Every pair of shoes has a left shoe and a right shoe. Choose the left shoe from each pair and send them to the even numbers, choose the right shoe from each pair and send them to the odd numbers.

But if it is "socks", we can't really uniformly decide which sock in a pair to be sent to the even numbers and which to the odd numbers. We don't have a choice function.

Problem with the usual story#

The problem might be this. If we cannot distinguish between a left and a right sock, what does it mean that they are different? After all a set consists of distinguished elements.

Fix#

We can say that every pair of socks consists of different socks, in that their colors are different. But the pairs of socks are not uniform: pair 1 might be red and blue, pair 2 might be green and yellow, etc. And there's a continuum of color for us to pick, hence the color cannot be exhausted.

There still can be some means to uniformly pick one of the sock in a pair out. E.g. if the color is described in terms of RGB, pick the one with the larger R out, if Rs are equal, then pick the one with the larger G, etc. But let's say that there's no this sort of ordering given.

Nevertheless, what needs to be stressed is that the choice function requires the presence of a uniform way to choose between the elements of the sets \(x\in X\). So, say, a perfect binary tree, without an injection into the plane, is not guarenteed to possess an infinite path, since there's no way to choose, as usual, the leftmost path. Because it is indeed a perfect binary tree, at each node there must be a way to choose between the two branch, since the two branches are distinguished, but the way the infinitely many pairs of branches associated to their corresponding nodes are distinguished need not be uniform.

The Halting Problem#

We have stressed that what's problematic for the choice function is that it must uniformly chose an element \(f(x) \in x\) for every \(x\in X\). This is very similar to what's forbidden by the undecidability of Halting problem.

The Halting problem asks whether there's a single general method, i.e., a uniform method, that determines for arbitrary \(x\in \mathbb{N}\) whether the program \(P_x\), whose Goedel number is \(x\), halts, when the input is some \(y\), which is again arbitrary.

It is by means of showing that whether the computation \(P_x(x)\) halts, for every \(x\), is undecidable with a uniform method that the Halting problem is finally settled down to be undecidable. So here, a particular choice made is analogues to a computation \(P_a(a)\) that actually can be shown to halt, but it is unclear whether for general \(x\), \(P_x(x)\) halts, and similarly the choice function for arbitrary \(X\) cannot be shown to exist.

The notational similarity between \(P_x(x)\) and \(f(x)\in x\) may really be a coincidence. Or maybe not. Forcing \(f(x)\) to be in \(x\) is strangely similar to diagonalization.