Page 1 of 2 12 LastLast
Results 1 to 15 of 19
Like Tree5Thanks

Math Help - From a structure, define 0, 1 and the successor relation

  1. #1
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    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.
    Last edited by Zhai; May 7th 2012 at 02:14 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

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

    Quote Originally Posted by Zhai View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    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...
    Last edited by Zhai; May 7th 2012 at 02:41 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

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

    Quote Originally Posted by Zhai View Post
    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).
    Thanks from Zhai
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

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

    Quote Originally Posted by Zhai View Post
    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\}
    Thanks from Zhai
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    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?
    Last edited by Zhai; May 7th 2012 at 04:49 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

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

    1. But then n can be more than 0? :S
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

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

    Quote Originally Posted by Plato View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1

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

    Quote Originally Posted by Zhai View Post
    1. But then n can be more than 0? :S
    NO! It means that n\ge 0~.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

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

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

    Quote Originally Posted by Zhai View Post
    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).
    Thanks from Zhai
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

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

    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

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

    Quote Originally Posted by Plato View Post
    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..
    Last edited by Zhai; May 8th 2012 at 08:24 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

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

    Quote Originally Posted by Zhai View Post
    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).

    Quote Originally Posted by Zhai View Post
    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?
    Quote Originally Posted by emakarov View Post
    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.
    Thanks from Zhai
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    May 2012
    From
    Europe
    Posts
    15

    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...)
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    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?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 11
    Last Post: December 5th 2011, 08:30 PM
  2. Replies: 2
    Last Post: November 13th 2010, 08:27 AM
  3. Define a relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 27th 2010, 09:17 AM
  4. Replies: 1
    Last Post: March 13th 2010, 01:13 PM
  5. define a relation...
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: December 3rd 2008, 12:21 PM

Search Tags


/mathhelpforum @mathhelpforum