# Each of the two sets is recursively enumerable given their cartesian product is

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

• Then you also need that $B$ (or $A$) is non-empty. – Hendrik Jan May 12 '13 at 10:07
• @HendrikJan: Right, I forgot to mention that condition. Thanks. – Gigili May 12 '13 at 10:08
• @HendrikJan If $A$ or $B$ is empty then $A$ or $B$ is r.e. – Pål GD May 12 '13 at 10:56
• Gigili, What do you mean "formula"? If your task is to show what the post asks, then surely @HendrikJan answers the question. – Pål GD May 12 '13 at 10:57
• @PålGD The point is that when $A$ is empty (and RE), then $A\times B$ is empty (and RE) while $B$ might not be RE. So the implication (for $B$) is not valid. – Hendrik Jan May 12 '13 at 17:48

Not sure if that's what you want: with the same idea as @HendrikJan and with a function:

$A\times B$ is r.e. hence, there is a partial recursive function $f$ such that: $$f(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x \in A\times B \\ \mbox{undefined/does not halt}\ &\mbox{if}\ x \notin A\times B \end{matrix}\right.$$

$A$ is not empty let $a$ be an element of $A$ ($a\in A$).

Let $g$ be the partial recursive function defined as $g(x)=f(a,x)$.

$g(x)=0$ iff $f(a,x)=0$ iff $(a,x)\in A\times B$ iff $x\in B$. Hence $B$ is r.e.

We assume both $A$ and $B$ are nonempty.

If $A\times B$ is r.e., then it is definable by a $\Sigma^{0}_{1}$ formula: $$(a,b) \in A\times B \Longleftrightarrow \exists x \, R(a,b,x),$$ where $R$ is a recursive predicate. Thus $$a\in A \Longleftrightarrow \exists x \, \exists \, b R(a,b,x),$$ so $A$ is definable by a $\Sigma^{0}_{1}$ formula and hence r.e. Similarly for $B$.