Results 1 to 5 of 5

Thread: 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
    21,742
    Thanks
    2814
    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 $\displaystyle \exists J \in N\left[ {n < J} \right]$ so J does not belong to S.
    If $\displaystyle T = N\backslash S$ then $\displaystyle 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
    10
    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 $\displaystyle a,b\in \mathbb{Z}$ with $\displaystyle b>0$ we want to show there exists $\displaystyle q,r$ so that $\displaystyle a = qb+r$ where $\displaystyle 0\leq r < b$. Define the set $\displaystyle \{ a - sb \geq 0 | s\in \mathbb{Z} \}$. This set is non-empty (why?) and so by Well-Order it means there is a $\displaystyle r$ that is the least element. Thus, $\displaystyle a - qb = r$ for some $\displaystyle q$. We will show $\displaystyle 0\leq r < b$, because if not then $\displaystyle r = b+r'$ where $\displaystyle r' < r$. And then $\displaystyle a - qb = b + r' \implies a - (q+1)b = r'$ which is impossible since $\displaystyle r$ is the least element and $\displaystyle 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 "
    $\displaystyle
    T = N\backslash S
    $".

    Thanks

    Quote Originally Posted by Plato View Post
    We know that 1 belongs to S, so S is not empty.
    We also know that $\displaystyle \exists J \in N\left[ {n < J} \right]$ so J does not belong to S.
    If $\displaystyle T = N\backslash S$ then $\displaystyle 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 $\displaystyle a,b\in \mathbb{Z}$ with $\displaystyle b>0$ we want to show there exists $\displaystyle q,r$ so that $\displaystyle a = qb+r$ where $\displaystyle 0\leq r < b$. Define the set $\displaystyle \{ a - sb \geq 0 | s\in \mathbb{Z} \}$. This set is non-empty (why?) and so by Well-Order it means there is a $\displaystyle r$ that is the least element. Thus, $\displaystyle a - qb = r$ for some $\displaystyle q$. We will show $\displaystyle 0\leq r < b$, because if not then $\displaystyle r = b+r'$ where $\displaystyle r' < r$. And then $\displaystyle a - qb = b + r' \implies a - (q+1)b = r'$ which is impossible since $\displaystyle r$ is the least element and $\displaystyle 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: Aug 3rd 2010, 08:31 AM
  2. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Aug 18th 2009, 02:18 PM
  3. Well-Ordering Principle
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 20th 2009, 10:59 AM
  4. well-ordering principle
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 10th 2007, 08:09 PM
  5. Well ordering principle
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Oct 14th 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum