Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You should outline the original proof you want to modify in the exercise, to allow more people to contribute to an answer. –  gnometorule Jan 8 '12 at 14:21
    
I realized that, and I added a link to some prezentation using exactly the same proof –  Karel Bílek Jan 8 '12 at 14:24

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.