# Thread: From a structure, define 0, 1 and the successor relation

1. ## From a structure, define 0, 1 and the successor relation

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.

2. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
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.
You say "I cant use them because it's not in the defined structure."
So why not tell what is defined in the structure?

This sort of thing is done differently in almost every textbook in which it is considered.

3. ## Re: From a structure, define 0, 1 and the successor relation

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...

4. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
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"
The following can be expressed using < only.

a) There is no number less than 0.

b) 1 is greater than 0 and there are no numbers between 0 and 1.

c) Similar to b).

5. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
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 hn as to be 0.
But the structure is only defined like I wrote: < N, < >
Following reply #4, here is adaption of James Henle's work in his An Outline of Set Theory.
1. $\neg \left( {\exists n} \right)\left[ {n < 0} \right]$
2. $\left( {\forall n} \right)\left[ {n < S(n)} \right] \wedge \neg \left( {\exists m} \right)\left[ {n < m < S(n)} \right]$
3. $1 = S(0)$

Note there is a reversal in the order of statements.

BTW: $S(n)$ stands for successor of n.
Henle defines $S(n)$ as:
For any set $n,~$ $S(n)=n\cup\{n\}$

6. ## Re: From a structure, define 0, 1 and the successor relation

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?

7. ## Re: From a structure, define 0, 1 and the successor relation

1. But then n can be more than 0? :S

8. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Plato
Following reply #4, here is adaption of James Henle's work in his An Outline of Set Theory.
1. $\neg \left( {\exists n} \right)\left[ {n < 0} \right]$
2. $\left( {\forall n} \right)\left[ {n < S(n)} \right] \wedge \neg \left( {\exists m} \right)\left[ {n < m < S(n)} \right]$
3. $1 = S(0)$

Note there is a reversal in the order of statements.

BTW: $S(n)$ stands for successor of n.
Henle defines $S(n)$ as:
For any set $n,~$ $S(n)=n\cup\{n\}$
1. But then n can be more than 0? :S

9. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
1. But then n can be more than 0? :S
NO! It means that $n\ge 0~.$

10. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
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.
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.

Originally Posted by Zhai
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?
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).

11. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by emakarov
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).
Thanks for the details, really needed that.
I will need some time to study all of your helpful words.
Hope you guys are still sticking around in case I get stuck

12. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Plato
Following reply #4, here is adaption of James Henle's work in his An Outline of Set Theory.
1. $\neg \left( {\exists n} \right)\left[ {n < 0} \right]$
2. $\left( {\forall n} \right)\left[ {n < S(n)} \right] \wedge \neg \left( {\exists m} \right)\left[ {n < m < S(n)} \right]$
3. $1 = S(0)$

Note there is a reversal in the order of statements.

BTW: $S(n)$ stands for successor of n.
Henle defines $S(n)$ as:
For any set $n,~$ $S(n)=n\cup\{n\}$
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..

13. ## Re: From a structure, define 0, 1 and the successor relation

Originally Posted by Zhai
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)
If you define x ≤ y as x < y ∨ x = y, then yes. Let's denote ∀y (x ≤ y) by zero(x).

Originally Posted by Zhai
2. As for defining 1, how can this be done without using the successor function S(n) as you described?
Does the following hint help you?
Originally Posted by emakarov
b) 1 is greater than 0 and there are no numbers between 0 and 1.
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.

14. ## Re: From a structure, define 0, 1 and the successor relation

When you say "x is 1 iff ∀z (z < x ↔ z = 0)", cant x be other numbers than 1?
Won't the sentence still hold if x is 2, 3, 4....and so on ?
(awkward question...)

15. ## Re: From a structure, define 0, 1 and the successor relation

So, you think that ∀z (z < 2 → z = 0) is true on natural numbers?

Page 1 of 2 12 Last