Expressing statements in predicate logic

Question

I'm having trouble explaining no.s 2 and 4.

    Consider the predicate logic language with the natural numbers {0, 1, 2, 3, . . .} as 
constants; the predicates < (x < y means x is smaller than y); =
    (x = y means x is equal to y); and prime (prime(x) means x is a
    prime number); and the usual logical connectives.

    Express each of the following (if possible). If not explain why not.
    1. y is a prime number
    2. there exists a first element
    3. 0 is smaller than everything
    4. the predicate < is transitive
    5. there is no greatest number

Here's what I got:

i) prime(y)
ii) impossible: predicate is undefined (not sure about this explanation)
iii) ∀x(x≠0 -> 0<x)
iv) impossible I think: (not sure why)
v) ∀x∃y(x<y)

I believe that no.s 2 and 4 can't be expressed since the predicates for those statements are undefined (or can't be defined) - is this correct?

Answer 1

I believe these are all expressible, if the connectives you are using include $\{\neg, \rightarrow, \wedge, \vee, \forall, \exists\}$, where $\neg$ is the negation symbol.

The three questions you have answered seem fine to me, I'd just point out a slight error with (iii). You don't have the $\neq$ symbol in your language, so instead of writing $x\neq 0$, try using only $=$ and $\neg$.

For the remaining questions:

ii) This is similar to (iii); by `first' they simply mean a least element, something smaller than everything else. You first need to assert the existence of the element. Once you know there exists an $x$ with the same property as you gave $0$ in (iii), you're done.

iv) This requires understanding transitivity pretty clearly, and is a statement about all triples of numbers. So you begin with $\forall x(\forall y(\forall z\ldots)))$, and then need to find some way to express the idea that, if $x<y$ and $y<z$, it must be the case that $x<z$...

I hope that makes things clearer!

Note: You might also want to adjust (v), as your sentence isn't quite a direct translation, although it is equivalent. You want something more like $\neg(\exists x(\forall y((\neg(x=y))\rightarrow (y<x))))$.

Answer 2

I think that 2) and 4) can easily be expressed in your language:

2) $\exists x \forall y (x < y \lor x = y)$

4) $\forall x \forall y \forall z ((x < y \land y < z) \to x < z)$