Model theory - definiable sets

Printable View

November 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 $\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
November 17th 2010, 01: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.
November 19th 2010, 08:19 AM
Arczi1984

The structure of natural numbers is following:

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

One more definition:

"The quantifiers $\forall (x<y)$ and $\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 $\sum_0^0$ in $\mathbb{N}$ ? What formulas should I use?
November 19th 2010, 09: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.

All times are GMT -8. The time now is 11:20 PM.