Here is a problem I thought was easy and straightforward but
found out that it was more difficult that I thought:
In the structure < N, < >, define
a) 0 (i.e the unary relation x = 0)
b) 1
c) The relation "y is the successor of x"
(N in the structure is the "natural numbers")
The reason why I thought it was easy was because
I thought I could use 0,1,+ in my answer, but seems like I cant use them
because it's not in the defined structure.
I dont really see how I can do this with only the symbol < .
Any kind of help here would be most appreciated.
To be precise: 0,1,+ aren't constants or functionsymbols in the structure.
That makes a bit sense, because then I could obviously define 0 like this: x < 1, then x has to be 0.
But the structure is only defined like I wrote: < N, < > ,
which makes this a bit harder...
But I think connectives and quantifiers are allowed though, dont know
if that makes the matter any better...
Thanks for the replies so far
But "There is no number less than 0" means that there are numbers that are more than 0...
and that wont exactly define 0...
And since the structure only contains natural numbers, then I dont think we needed
to worry about numbers less than 0.
But I was thinking about something like this though in First Order: "There is one and only x less than every y"
Then x has to be 0 because its less than every number. Could this be it? Or can someone think of something better?
By the phrase "There is no number less than 0" I did not mean a proposition that has to be evaluated to be true or false. I gave this phrase as a hint for defining a predicate which is true of zero only. Namely, n is zero if there is no number less than n. Thus, the formula ¬∃m m < n with one free variable n defines a unary relation n = 0.
This does not exactly work because < is irreflexive. You could use ≤, but I am not sure if you have = in the language. The problem statement seems to say you don't. Of course, you can define x ≤ y as ¬(y < x).
1. Defining 0 without using 0 itself in the definition since it's not in the language,
I ended up with this: ∀y (x ≤ y) , then x has to be 0, correct?
( Seems like the ' = ' is actually in the language)
2. As for defining 1, how can this be done without using the successor function S(n) as you described?
3. Here too, can't use 1 and S(0) because it's not in the language..
If you define x ≤ y as x < y ∨ x = y, then yes. Let's denote ∀y (x ≤ y) by zero(x).
Does the following hint help you?
I.e., 1 is a number x such that... First write the required formula with one free variable x and a constant 0. Then we have to remove 0.
Actually, as far as removing 0 goes, it is easier to use the following characteristic of 1: x is 1 iff ∀z (z < x ↔ z = 0). Here we can replace z = 0 by zero(z) to get a formula in the language of < only.
If 0 occurs in any context other than t = 0 for some term t, then we need a systematic way of eliminating constants whose definition is given as a formula. The first suggestion above includes the part 0 < x. We replace it by ∀z (zero(z) → z < x). We do this with every atomic formula containing 0. The resulting formula is equivalent to the original one. This process is described here in Wikipedia.