Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable

Question

I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable. I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ by described in follows.

First note $\Sigma_1$ = the language of the form $\{x | \exists y R(x,y)\}$, where $R(x,y)$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t [M \text{ accept $w$ in $t$ steps}]\}$, where $M \text{ accept $w$ in $t$ steps}$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t T(\big \langle M \big \rangle, w, t)\}$

So we show that $A_{TM} \in \Sigma_1$, but does it sufficient to show that $\Sigma_1$ is in r.e.? Any suggestion?

Answer 1

Suppose that $L = \{x \mid \exists y R(x,y)\}$, where $R(x,y)$ is a decidable predicate.

To recognize $L$, given an input $x$, enumerate all possible $y$, and check whether $R(x,y)$ holds for at least one of them. This will halt iff $x \in L$.