# Model theory - definiable sets

• Nov 16th 2010, 10:53 AM
Arczi1984
Model theory - definiable sets
Hi,
I'm newbie in logic and model theory. I've the following task:

By exhibiting suitable formulas, show that the set of even numbers is a $\sum_0^0$ set in $\mathbb{N}$.
Show the same for the set of prime numbers.

How can I solve this? Any advices?
I'll be grateful for help
• Nov 17th 2010, 02:44 PM
emakarov
What relations and functions are available in the language?

I understand that $\Sigma_0^0$ means a set definable by a formula with bounded quantifiers only. A number n is even iff there exists an m <= n such that 2m = n. A number n is prime iff $n\ne 1$ and for all m < n, if m divides n, then m = 1.
• Nov 19th 2010, 09:19 AM
Arczi1984
The structure of natural numbers is following:

$\mathbb{N}=(\omega, 0, 1, +, \cdot, <)$

One more definition:

"The quantifiers $\forall (x and $\exists (x are said to be bounded"

Your definitions of even and prime numbers are clear but how can I use this facts to show that mentioned sets are $\sum_0^0$ in $\mathbb{N}$? What formulas should I use?
• Nov 19th 2010, 10:12 AM
emakarov
Replace "there exists an x such that" with " $\exists x$", "and" with " $\land$", and "if P, then Q" with " $P\to Q$". Also, you can express 2 as 1 + 1, and "m divides n", since it is not in the language, has to be written using an existential quantifier: there exists k such that m * k = n.

To be honest, I don't see where your difficulty is. I wrote English sentences as close as possible to symbolic formulas, so a mechanical search/replace can turn one into the other.