0
$\begingroup$

I am reading a textbook on computer science, and now the author explains a proof of existence of non-recursively enumerable language (he calls it $L_{diag}$) by diagonalization method, that is very reminiscent of Cantor's diagonalization and is the same in principle as this one - http://www.pmshiva.elementfx.com/cs530/rep2/G17.ppt .

So far so good.

However, then he asks a question as an excercise: "Generalize diagonalization by using permutations." And I have no clue what he means by that.

  • 0
    I realize$d$ that, an$d$ I a$d$$d$ed a link to some prezentation using exactly the same proof2012-01-08

1 Answers 1

1

I don’t know whether what follows is the desired generalization, but it’s the one that seems most natural to me.

In ordinary diagonalization you have a doubly infinite matrix of objects $m(i,j)$ for $i,j\in\omega$. The $i$-th row of this matrix can be thought of as a sequence $\rho_i=\langle m(i,j):j\in\omega\rangle$, and the point of the diagonalization procedure is to build a sequence that is different from every $\rho_i$ for $i\in\omega$. This is done by starting with the diagonal sequence $\delta=\langle m(i,i):i\in\omega\rangle$ and for each $i\in\omega$ choosing an object $\bar \delta(i)\ne m(i,i)$ to form the sequence $\bar\delta=\langle\bar \delta(i):i\in\omega\rangle$. Then for each $i\in \omega$ we have $\bar\delta(i)\ne m(i,i)=\rho_i(i)$, so $\bar\delta\ne\rho_i$. In other words, the $i$-th term of $\bar\delta$ ‘kills off’ the sequence $\rho_i$.

Now let $\pi$ be any permutation of $\omega$; that simply means that $\pi:\omega\to\omega$ is a bijection. Instead of ‘killing off’ $\rho_i$ with the $i$-th term of $\bar\delta$, we could try to ‘kill off’ $\rho_{\pi(i)}$. Equivalently, we could try to make the $\pi^{-1}(i)$-th term of $\bar\delta$ ‘kill off’ the $i$-th row, $\rho_i$. This requires only a small modification of the previous procedure: instead of taking $\delta$ to be the true diagonal sequence, let it be a ‘fake’ diagonal sequence determined by $\pi$: $\delta=\left\langle m\big(i,\pi(i)\big):i\in\omega\right\rangle$. Now for each $i\in\omega$ let $\bar \delta(i)$ be any suitable object different from $m\big(i,\pi(i)\big)$, and proceed as before.

The standard diagonalization is simply the special case in which $\pi$ is the identity permutation.