Extension of Rice's theorem

Question

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable")

Answer 1

Any property $P$ of a pair of RE sets becomes a property $P_{1,B_0}$ of the first component alone, if we fix the second RE set to a set $B_0$. As such, by Rice theorem, the property $P_{1,B_0}$ must be trivial or undecidable. If it is undecidable, then the property $P$ is undecidable for $\{(A,B_0)\mid A\in RE\}$, and is thus also undecidable for $\{(A,B)\mid A,B\in RE\}$. If it is trivial, it is either true or false for all $A\in RE$, and thus $P$ is either true for all pairs in $\{(A,B_0)\mid A\in RE\}$, or false for all of them.

We assume that it is trivial, and without loss of generality that it is true for all pairs $(A,B_0)$.

There are then two possibilities:

• There is some RE set $A_0$ such that the property is undecidable for the set of pairs $\{(A_0,B)\mid B\in RE\}$, where $B$ is any RE language. This implies, as before, that it is a fortiori undecidable for the set of all pairs of RE languages.

• For any choice of $A_0$, the property $P$ is decidable over $\{(A_0,B)\mid B\in RE\}$. Since $A_0$ is fixed, it can be viewed as a decidable property $P_{2,A_0}$ on the second component alone, which may be any RE set. Hence by Rice theorem, it is trivial. So $P_{2,A_0}(B)$ is either true, or false, for all choices of $B\in RE$. Hence the property $P$ is trivial, either true or false, over the set $\{(A_0,B)\mid B\in RE\}$. Since it is true for all pairs $(A,B_0)$, it must be true for $(A_0,B_0)$, and since it is trivial for $\{(A_0,B)\mid B\in RE\}$, it must be true for all pairs $P(A_0,B)$. And since that reasonning is valid for any choice of $A_0$ in RE, the property must be true for all pairs of RE sets.

Hence we see that the property is either undecidable or trivial (true for all pairs or false for all pairs).

Answer 2

Let $C$ be the collection of all c.e. sets. One way to understand Rice's theorem is to say that every computable map $f : C \to \mathsf{bool}$ which preserves equality of sets is constant. (By "respects equality of sets" we mean that $f$ actually accepts codes of c.e. sets, but it maps any two codes for the same set to equal values).

Let's answer your question. Suppose we have a computable map $g : C \times C \to \mathsf{bool}$ which respects equality of sets. We want to prove it is constant. Then for every $y \in C$, the map $x \mapsto g(x,y)$ is constant by Rice's theorem. Likewise, for every $x \in C$, the map $y \mapsto g(x,y)$ is constant by Rice's theorem. But a map $g$ which is constant in each argument separately is constant.