# Is this diagonalization argument correct?

Consider a countably infinite vector, where each component is a rational number between 0 and 1 (inclusive). We say that an ordering $\preceq$ is Pareto if it obeys the following rule: If there is some index $i$ such that $x_i\leq y_i$, and for all other $j\not = i$, $x_j = y_j$, then $x\preceq y$.

I was wondering if any Pareto ordering's are computable in this set that I mentioned. I suspect the answer is no, but someone told me proof which I don't understand: One confusion I have is that this seems to prove that the rational numbers themselves cannot be computably ordered, a contradiction.

What am I misunderstanding?

You are right, this argument is not correct. Indeed, let $A(x,y) = \begin{cases} 1 & x \le y \\ 0 &\text{ otherwise} \end{cases}$ for two rational $x$ and $y$. Then we want to consider such $a$ that $a = A(a,0.5)$. If $a = 1$ then $A(a,0.5)=0$ and if $a = 0$ then $A(a,0.5)=1$. Well, we've proved that such $a$ does not exist. But that doesn't imply that we can not compare rational numbers.
Let me prove that this is not computable by reducing the halting problem to the comparator, I think that this proof is easier to follow. Let $A(X,Y) = 1 \iff \{X(i)\}_{i=1}^{\infty}$. Let $M$ be an arbitrary algorithm. $G_{M,x} (n) = 1$ iff $M(x) \text{ stops after exactly } n \text{ steps}$. Thus if $M(x)$ ever stops then $H_{M,x} = \{G_{M,x}(n)\}_{n=1}^{\infty} = (0, \ldots, 0, 1, 0, \ldots)$. Otherwise $H_{M,x} = (0, 0, 0, \ldots)$. Therefore $M(x)$ stops iff $H_{M,x} \neq (0, 0, \ldots)$. Notice that $H_{M,x} = (0,0,\ldots) \iff (H_{M,x} \leq (0,0,\ldots)) \land ((0,0,\ldots) \leq H_{M,x})$. Let $\mathbf{0}(n)$ be an algorithm which always prints zero. $M(x)$ stops iff $A(\mathbf{0}, G_{M,x}) = 1 \land A(G_{M,x}, \mathbf{0}) = 1$. Since the halting problem is not computable, so is $A$. The crucial idea here is that $G_{M,x}(n)$ always stops by the definition and hence $H_{M,x}$ is computable and defined for every positive integer.