1. ## 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}).

2. Originally Posted by shaoen01
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?

3. Originally Posted by shaoen01
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$.

4. Hi,

But i didn't quite understand what you mean by "
$\displaystyle T = N\backslash S$".

Thanks

Originally Posted by Plato
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?

5. 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

Originally Posted by ThePerfectHacker
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$.