-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Then you also need that $B$ (or $A$) is non-empty. $\endgroup$ – Hendrik Jan May 12 '13 at 10:07
  • $\begingroup$ @HendrikJan: Right, I forgot to mention that condition. Thanks. $\endgroup$ – Gigili May 12 '13 at 10:08
  • 1
    $\begingroup$ @HendrikJan If $A$ or $B$ is empty then $A$ or $B$ is r.e. $\endgroup$ – Pål GD May 12 '13 at 10:56
  • 1
    $\begingroup$ Gigili, What do you mean "formula"? If your task is to show what the post asks, then surely @HendrikJan answers the question. $\endgroup$ – Pål GD May 12 '13 at 10:57
  • 1
    $\begingroup$ @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. $\endgroup$ – Hendrik Jan May 12 '13 at 17:48
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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