# Model theory - definiable sets 2

Printable View

• Nov 16th 2010, 11:05 AM
Arczi1984
Model theory - definiable sets 2
Here is more difficult exercise (for me of course) from definiable sets:

Let $A$ be the partial ordering (in a signature with $\leq$) whose elements are the positive integers, with $m \leq ^A$ iff $m$ divides $n$.
Show that the set $\{1\}$ and the set of primes are both $\emptyset$-definable in $A$.

I don't have any idea how can I solve it. Could You give me some advices?
Any help will be highly appreciated.
• Nov 16th 2010, 12:40 PM
emakarov
Well, 1 is the only positive integer that divides all other positive integers. And a number other than 1 is prime if its divisors are 1 and itself. It's easy to write these properties as formulas.
• Nov 16th 2010, 12:58 PM
Arczi1984
Could You show me how can I do this, for example in second case (set of primes)?
This is probably easy but I'm really newbie in this subject so I'll be glad if You write some more details. Thanks.
• Nov 16th 2010, 01:08 PM
emakarov
$\mathrm{prime}(x)$ is $\neg\mathrm{one}(x)\land\forall y.\,y\le x\leftrightarrow(\mathrm{one}(y)\lor y=x)$. Here $\mathrm{one}(y)$ means $y=1$ (the first part of the problem). I also assume that = is in the language and is interpreted as identity.