Results 1 to 5 of 5

Math Help - Well Ordering Principle

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    15

    Well Ordering Principle

    I need help for the question below, i simply do not know where to start.

    In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    Quote Originally Posted by shaoen01 View Post
    In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).
    We know that 1 belongs to S, so S is not empty.
    We also know that \exists J \in N\left[ {n < J} \right] so J does not belong to S.
    If T = N\backslash S then J \in T; thus T is not empty.
    By well ordering, there is a first element, t, in T.
    Now t-1 is not in T so t-1 belongs to S.
    Can you complete the proof?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by shaoen01 View Post
    I need help for the question below, i simply do not know where to start.

    In the proof of the quotient remainder theorem, we have "if n>=0 and 0<d<=n, then there is a largest integer q such that qd<=n". Use the well ordering principle to justify the existence of q. (Consider the set S={i element of Natural numbers: id<=n}).
    Given a,b\in \mathbb{Z} with b>0 we want to show there exists q,r so that a = qb+r where 0\leq r < b. Define the set \{ a - sb \geq 0 | s\in \mathbb{Z} \}. This set is non-empty (why?) and so by Well-Order it means there is a r that is the least element. Thus, a - qb = r for some q. We will show 0\leq r < b, because if not then r = b+r' where r' < r. And then a - qb = b + r' \implies a - (q+1)b = r' which is impossible since r is the least element and r' < r.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Hi,

    But i didn't quite understand what you mean by "
    <br />
T = N\backslash S<br />
".

    Thanks

    Quote Originally Posted by Plato View Post
    We know that 1 belongs to S, so S is not empty.
    We also know that \exists J \in N\left[ {n < J} \right] so J does not belong to S.
    If T = N\backslash S then J \in T; thus T is not empty.
    By well ordering, there is a first element, t, in T.
    Now t-1 is not in T so t-1 belongs to S.
    Can you complete the proof?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Hi,

    I understand your explanation but when it comes down to trying to do it by myself i am always lost. Do you have any tips or certain methods to determine how to do this? Thanks

    Quote Originally Posted by ThePerfectHacker View Post
    Given a,b\in \mathbb{Z} with b>0 we want to show there exists q,r so that a = qb+r where 0\leq r < b. Define the set \{ a - sb \geq 0 | s\in \mathbb{Z} \}. This set is non-empty (why?) and so by Well-Order it means there is a r that is the least element. Thus, a - qb = r for some q. We will show 0\leq r < b, because if not then r = b+r' where r' < r. And then a - qb = b + r' \implies a - (q+1)b = r' which is impossible since r is the least element and r' < r.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 08:31 AM
  2. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 18th 2009, 02:18 PM
  3. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2009, 10:59 AM
  4. well-ordering principle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2007, 08:09 PM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 14th 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum