properties of recursively enumerable sets

Question

$A \times B$ is an r.e.(recursively enumerable) set, I want to show that $A$ (or $B$) is r.e. ($A$ and $B$ are nonempty)

I need to find a formula. I've got an idea that I should use the symbolic definition of an r.e. set. That is, writing a formula for the function that specifies $A$ or $B$, assuming a formula exists for $A \times B$. I guess I must use Gödel number somewhere.

I should've mentioned that I asked this question over there (Computer Science) but since I am more interested in mathematical arguments and looking for formulas, I'd ask it here as well.

Answer 1

If $A\times B$ is recursively enumerable then there exists a bounded formula $\varphi(x,y,z)$ such that $\langle a,b\rangle\in A\times B$ if and only if $\exists z\varphi(a,b,z)$ is true.

Then we have that $a\in A$ if and only if $\exists b\exists z\varphi(a,b,z)$.

Therefore $A$ is definable by a $\Sigma_1$ formula, and therefore recursively enumerable.

Answer 2

I don't know why you request some formula.

Just take a Turing machine $M$ that enumerates $A\times B$, but instead of outputting some tuple $(a,b)$, it only outputs $a$, resp. $b$. This modified machine $M'$ enumerates $A$, resp. $B$.

Answer 3

The notion of computable or c.e. is usually defined on $\omega$. To understand what $A \times B$ being computable or c.e., you should identify order pairs $(x,y)$ with the natural number under a bijective pairing function. Any of the usual standard pairing function, the projection maps $\pi_1$ and $\pi_2$ are computable.

First note that $\emptyset \times B = \emptyset$. So the result does not hold if one of the sets is empty.

Suppose $A$ and $B$ are not empty. Suppose $A \times B$ is c.e. Then there is a total computable function $f$ with range $A \times B$. Then $\pi_1 \circ f$ and $\pi_2 \circ f$ are total computable functions with range $A$ and $B$, respectively. So $A$ and $B$ are c.e.

Answer 4

Here is a formalization or detailed exposition of Asaf Karagila's answer.

Because $A \times B$ is r.e., there is an $e$ such that for all $n$ and $m$, $$ (n,m) \in A \times B \Leftrightarrow (\exists s)T(\underline{e},\underline{\langle n,m\rangle},s). $$ Here $T$ is Kleene's $T$ predicate, $\underline{x}$ is the numeral for a number $x$, and $\langle \cdot,\cdot\rangle$ is a fixed effective pairing operation, e.g. $\langle n,m \rangle = 2^n3^m$.

Given $e$, we can define a unary computable function $f(n)$ which does the following: search for an $m$ and $s$ such that $T(\underline{e},\underline{\langle n,m\rangle},\underline{s})$ holds. If such an $m$ and $s$ are found, immediately halt and return $1$, otherwise keep searching forever.

Because $f$ is computable, it has an index $e'$. Then we have, for all $n$, $$ n \in A \leftrightarrow (\exists s) T(\underline{e'},\underline{n},s) $$ and so the formula on the right side of that equivalence is the desired formula. In particular, we can effectively produce $e'$ from $e$.

As a historical note, this argument is reminiscent of the way that arguments in computability were written in the earliest stages of the field, in the 1940s and 1950s. As the field progressed, we have stopped using this sort of argument - which needlessly brings up technical devices such as the $T$ predicate - and have moved to more intuitive arguments like the ones William and A.Schulz provided, which do not explicitly mention formulas. It is occasionally necessary to work with the $T$ predicate, especially when studying formal theories of arithmetic, but for pure computability theory it is not typical to write arguments in this style.