Thread: 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?

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.

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?

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.

So if I suppose A is empty then it implies r=0. But then I don't understand why it contains at least 0.

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:



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



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,



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 since that would leave r having to fill the remainder to 5, which violates its constraints. Thus, for the ordered pair we have the unique solution for the ordered pair , and we can express the statement thus:



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,



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:



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?

Originally Posted by Sneaky

So, since I have showed 0<=r<=m-(qm)/n

To repeat what I said above:

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.

Originally Posted by Sneaky

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

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.

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.

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.

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.

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.

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?

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.

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.