3

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

Community
  • 1
Gigili
  • 5,503
  • 8
  • 41
  • 62
  • 2
    I think in general when using an abbreviation it is a good idea to provide the full word at least once as not everyone may know what "r.e." stands for. Just a small suggestion. –  May 15 '13 at 12:41
  • 1
    Bryan's suggestion is very important. Don't burden the reader with the task of puzzling out what you mean. A lot of people who read this, possibly even people who know the answer, are going to glance at this and say "Ok, NEXT question..." I guess we are speculating this is "recursively enumerable" sets. – rschwieb May 15 '13 at 12:47
  • When showing that $A$ is r.e., you should assume that $B$ is nonempty; otherwise the result can fail. – Andreas Blass May 15 '13 at 12:52
  • @Bryan Urízar: the abbreviation "r.e." is just as standard and fundamental in computability as the term "group" in abstract algebra. Given the "computability" tag, anyone likely to answer the question would have no confusion about what is being asked. At the same time, I have removed the "linear-algebra" tag that is unrelated to this question. – Carl Mummert May 15 '13 at 13:24
  • @Gigili: what have you tried? Imagine someone enumerates $A \times B$ for you - how could you turn that into an enumeration of $A$? – Carl Mummert May 15 '13 at 13:25
  • @Gigili: please do not tag these questions as "computer science"; just the computability tag is fine. The questions are not particularly related to computer science any more than to mathematics. – Carl Mummert May 15 '13 at 13:28
  • @CarlMummert: I've removed the tag, but I thought it was more related to computer science than mathematics. – Gigili May 15 '13 at 13:53

4 Answers4

3

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

A.Schulz
  • 3,768
3

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.

Asaf Karagila
  • 393,674
3

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.

Carl Mummert
  • 81,604
  • Thank you, could you define the numeral for number x? – Gigili May 18 '13 at 06:55
  • 1
    @Gigili: the numeral for a number $n$ is the term $1+1+\cdots + 1$ ($n$ ones). The only things that can appear in formulas are terms, so to substitute a number it is necessary to use the term for the number. This is one of the basic techniques in formal arithmetic. – Carl Mummert May 18 '13 at 20:38
2

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.

William
  • 19,935