# Model theory - definiable sets

• Nov 16th 2010, 09: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 $\displaystyle \sum_0^0$ set in $\displaystyle \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, 01:44 PM
emakarov
What relations and functions are available in the language?

I understand that $\displaystyle \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 $\displaystyle n\ne 1$ and for all m < n, if m divides n, then m = 1.
• Nov 19th 2010, 08:19 AM
Arczi1984
The structure of natural numbers is following:

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

One more definition:

"The quantifiers $\displaystyle \forall (x<y)$ and $\displaystyle \exists (x<y)$ 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 $\displaystyle \sum_0^0$ in $\displaystyle \mathbb{N}$? What formulas should I use?
• Nov 19th 2010, 09:12 AM
emakarov
Replace "there exists an x such that" with "$\displaystyle \exists x$", "and" with "$\displaystyle \land$", and "if P, then Q" with "$\displaystyle 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.