Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - help with well ordering principle

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    help with well ordering principle

    Division Algorithm - For every pair of natural numbers m,n in N with n!=0, there is a unique q,r in N, such that m=qn+r and r<n.

    Consider the Set A of natural numbers that might be suitable candidates for r, in other words, A={r' in N: r' = m - nq' >=0 for some q' in N}. Show that A must be non empty and use the Well-ordering principle to show that there in an element r in A that satisfies r<n.

    I am trying to show that A must be non empty and use the Well-ordering principle to show that there in an element r in A that satisfies r<n.

    This is my incomplete informal attempt:
    1.
    m,n in N
    m/n <= n [since n!=0]
    2.
    q,r in N
    m=qn+r
    (m-r)/q=n

    m/n <= (m-r)/q [combining 1 and 2]
    qm/n<=m-r
    r<=m-(qm)/n
    0<=r<=m-(qm)/n [since r in N]
    Does this show that there is at least 1 element in A?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I believe you are going in the wrong direction. First, there is no reason why m/n <= n should be the case. More importantly, the problem seems to be about proving that the division operation is well-defined. Therefore, in the proof you still can't use division.

    I suggest taking several pairs of small m and n and write the set A explicitly for those m and n. Then form a hypothesis about which element is always in A.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    So, since I have showed 0<=r<=m-(qm)/n

    Then if

    m=0, n=1
    A={0}

    m=1, n=2
    A={0,...,1-(q/2)}

    1-(q/2) >= 0
    1>=q/2
    2>=q

    m=2, n=3
    A={0,...,2-(2q/3)}

    2-(2q/3) >= 0
    2>=2q/3
    6>=2
    3>=q

    m=10, n=1
    A={0,...,10-(10q)}

    10-(10q)>=0
    10>=10q
    1>=q

    where r is in A
    So if q <= n, then |A|>=1, and 0 is always in A, or rather m-(qm)/n is always in A

    Is this better?
    Last edited by Sneaky; May 22nd 2011 at 03:42 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2011
    Posts
    3
    if I understood A is the set of all possible r for all possible n?
    if so
    u can suppose that A is empty
    then you would have m=qn but this implies that r=0 if m|n so in any case A contains at least 0.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    So if I suppose A is empty then it implies r=0. But then I don't understand why it contains at least 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    You don't really want to use division in your proof as often that comes as undefined in discussing the division algorithm. It is sort of like talking about a number being less than another when you don't have any way of speaking about orderings. How can we say 3 is less than 5? We use a statement like:

    \exists (k>0) (m = n + k)

    Here we let m = 5, n = 3 and we can uniquely identify k. Thus, we can say

    \exists (k>0) (5 = 3 + k) \Rightarrow 3 \le 5

    Of course, the analogous proof would be to show that k exists and is unique. You are in a similar position with division. How do we talk about something being a divisor of another thing without the use of division? Well, we can express it in terms of multiples (quotients) and remainders. That is what the division algorithm states. As emakarov suggested, you should write out a few cases to develop your intuition of this formulation of division. That intuition will help you perceive the proof.

    Let m = 5, n = 3. Then,

     5 = q3 + r

    By definition 'r' must be less than 3, and q cannot be greater than 2 since 'q3' would "overtake" 5. We can also see that q\neq 0 since that would leave r having to fill the remainder to 5, which violates its constraints. Thus, for the ordered pair (m, n) = (5, 3) we have the unique solution for the ordered pair (q, r) = (1, 2), and we can express the statement thus:

    5 = 1 \times 3 + 2

    In similar fashion we can find many such ordered pairs. I'm unsure, but I think you define A to basically be all the possible numbers r can be. But this would just be all the natural numbers in the interval [0, n). Then we might as well say,

    A = \{r : \forall (m, n \in N)\exists (q\in N)(m = qn + r \wedge r < n)\}

    This almost seems too obvious, but what the condition states is that there are some numbers m, n, and q that let us define r such that r has to be less than n. I take it for granted that the universe of discourse for these letters is over the natural numbers. Thus, the condition says r is in the interval of natural numbers [0, n) defined by there existing m, n, and q such that m = qn + r. This just means for every instance there is an n such that B = {0, ... n}. If we take the intersection of all these B's we end up with what is in common with all possible candidates for r in an instance of the division algorithm. I would hope the solution here is obvious: zero is the only thing that can be in common.

    The outline of my proof would go something like this. First, the division algorithm says something like this:

    \forall m \forall n ((m, n \in N \wedge n \ne 0) \Rightarrow \exists q \exists r(q, r \in N \wedge m = q\times n + r \wedge r < n))

    I would let m and n be any arbitrary natural numbers with n > 0. We argue that we can fix q and define A as above. There are two cases. The easier case is when r = 0. Then we're saying that m is a multiple of n (i.e., m = qn). Put differently, n divides m evenly. The other case is when n does not divide m evenly. In that case, r > 0 but it will turn out that r < n. If r were not less than n, then we could have another multiple, say (q+1)n or for some k, (q+k)n, that would then put r in the correct range. However, the point of our selection of q is to fix r into that specified range.

    The way A is defined is just saying that for any m, n in N with n > 0, we can pick a q that defines r in such and such a way. So if you can do that under the above scenario I outline, then A is nonempty. This amounts to showing that there is a unique solution for r in m = qn + r. Of course, r = m - qn. But do we have subtraction in our discussion? Maybe not, in which case you'll have to go in a roundabout way to show something equivalent. Of course, we do know there is a unique solution. Thus, A is nonempty. The well-ordering principle says any nonempty set of natural numbers has a least element. Thus, if A consists of all the numbers in [0, n), then 0 is that least element.

    I have only seen this come up in context to abstract algebra, so I don't recall the need for using the well-ordering principle. Maybe it is because q can range over an infinite number of choices, unless both q and r are fixed at the same time, and so A has to be a set for all possible q's. Then we still know A is nonempty as long as it works for one choice of q, or that there is a choice of q that defines an r. Then the well-ordering principle could establish that 0 is in A, and from that we can build up to saying each element between 0 and n is in A. I assume this problem arose within some context. That might give more clarity as to the approach one might expect to have to this problem?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Quote Originally Posted by Sneaky View Post
    So, since I have showed 0<=r<=m-(qm)/n
    To repeat what I said above:
    Quote Originally Posted by emakarov
    More importantly, the problem seems to be about proving that the division operation is well-defined. Therefore, in the proof you still can't use division.
    Quote Originally Posted by Sneaky View Post
    m=2, n=3
    A={0,...,2-(2q/3)}
    By writing the set A explicitly I meant writing every element of A as a number, not as a formula. In any case, 0 is not an element of A for m = 2 and n = 3.

    I suggest writing A explicitly for the following values of m, n:

    m = 3, n = 2
    m = 2, n = 3
    m = 3, n = 3
    m = 6, n = 2
    m = 6, n = 4
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    m = 3, n = 2 A={1}
    m = 2, n = 3 A={2}
    m = 3, n = 3 A={0}
    m = 6, n = 2 A={0}
    m = 6, n = 4 A={2}

    m=qn+r and r<n

    I get these sets since r < n, and m, q, r, n is an element of N.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    To recall the definition:
    A={r' in N: r' = m - nq' >=0 for some q' in N}
    The possible values of q' in N are 0, 1, 2, ... Therefore, A = {m - n*0, m - n*1, m - n*2, ...} as long as these numbers are nonnegative.

    m = 3, n = 2 A={1}
    A should be {3 - 2*0, 3 - 2*1}, i.e., A = {3, 1}. The next number 3 - 2*2 < 0, so it is not in A.

    m = 2, n = 3 A={2}
    Correct.

    m = 3, n = 3 A={0}
    No, A = {3, 0} because q' is allowed to be 0.

    m = 6, n = 2 A={0}
    No, A = {6, 4, 2, 0}.

    m = 6, n = 4 A={2}
    A = {6, 2}.

    As you see in these examples, m is always in A.

    I get these sets since r < n, and m, q, r, n is an element of N.
    The definition of the set A does not say that r must be < n.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Oh ok, but how do you prove that m is always in A? I don't think its enough, by showing some examples, to prove m is always in A.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    By definition, A contains all numbers of the form m - q'n for all possible q', as long as m - q'n >= 0. In particular, q' can equal 0, which means that m is in A (by assumption, m is a natural number and thus nonnegative).

    You need to make sure you understand the set builder notation like {r' in N: r' = m - nq' >=0 for some q' in N}. If you have an explanation or a definition of it, it may be a good idea to review it.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    So if m is in A, then A is non empty, then by well ordering principle A contains a smallest integer.
    But I still don't see how r is always smaller than n.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    So, A contains numbers that you get from m by successively subtracting n. As long as you get positive numbers, you can keep subtracting n.

    Suppose the smallest element of A is >= n. What does this mean in light of the previous paragraph?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    So if the smallest element is >=n, then wouldn't that mean there is only one element in A, where the q for that is equal to 0 or 1(if n=smallest element in A), thus making the element equal to 0?

    or does it mean that A will always be equal to {0}, defying the rule about m is always in A.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    So if the smallest element is >=n, then wouldn't that mean there is only one element in A, where the q for that is equal to 0 or 1(if n=smallest element in A), thus making the element equal to 0?
    I don't understand your reasoning. The number n, as long as it is positive (which it is, by assumption in the first post), cannot be the smallest element in A.

    I think everybody understand the concept of taking something repeatedly until there is not enough to take.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

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 Discrete Math Forum
    Replies: 3
    Last Post: June 11th 2010, 06:57 AM
  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