The Division Algorithm: need proof for "f(x) = q(x)g(x)+r(x) where r(x) is either..."

Aion

New member
Joined
May 8, 2018
Messages
39
The Division Algorithm: need proof for "f(x) = q(x)g(x)+r(x) where r(x) is either..."

Is it possible to prove the Division Algorithm without using the Well-Ordering Principle? According to what I've read the Well-ordering principle is equivalent to the statement of the principle of mathematical induction. The well-ordered property says that any set of non-negative integers has a least element. And you can use this fact for an inductive proof of the division algorithm. But the thing is, to prove that this property is true, you need set theory; which I don't understand. Should I just accept this statement, namely that "any set of non-negative integers has a least element" as an axiom and simply move on? The reason I'm asking this is since I'm currently trying to understand a proof for the division algorithm, and I don't know any set theory. Or should I learn some basic set theory before I continue with polynomial long division?

I need a proof for:

\(\displaystyle f(x) = q(x)g(x) + r(x)\) where \(\displaystyle r(x)\) is either a zeropolynomial or deg \(\displaystyle r<\) deg \(\displaystyle g\)

 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,242
Is it possible to prove the Division Algorithm without using the Well-Ordering Principle? According to what I've read the Well-ordering principle is equivalent to the statement of the principle of mathematical induction.
The reason I'm asking this is since I'm trying to understand a proof for the division algorithm, and I don't know any set theory. Is it necessary for me to learn some basic set theory before I continue with polynomial long division?

Since I need to proof that:

\(\displaystyle f(x) = q(x)g(x) + r(x))\) where \(\displaystyle r(x))\) is either a zeropolynomial or deg \(\displaystyle r< deg \(\displaystyle g\)

\)
\(\displaystyle
The principle behind a proof by induction is highly intuitive.

We prove that some proposition is true for the integer 1.

That proves that the proposition is true for at least one integer. We now say that k is any number for which the proposition is true. Then we prove that it is true for k + 1.

At that point, we have proved the proposition for all positive integers by weak mathematical induction.

What is the intuition?

We proved it for 1 directly, but that means it is also true for 1 + 1 = 2, which means that it is true for 2 + 1 = 3, which means it is true for 3 + 1 = 4, and so on forever.

To use weak mathematical induction effectively and confidently, all you need to understand is the structure of such a proof and the intuition behind it.\)
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,050
Is it possible to prove the Division Algorithm without using the Well-Ordering Principle? According to what I've read the Well-ordering principle is equivalent to the statement of the principle of mathematical induction. The well-ordered property says that any set of non-negative integers has a least element. And you can use this fact for an inductive proof of the division algorithm. But the thing is, to prove that this property is true, you need set theory; which I don't understand. Should I just accept this statement, namely that "any set of non-negative integers has a least element" as an axiom and simply move on? The reason I'm asking this is since I'm currently trying to understand a proof for the division algorithm, and I don't know any set theory. Or should I learn some basic set theory before I continue with polynomial long division?

I need a proof for:

\(\displaystyle f(x) = q(x)g(x) + r(x)\) where \(\displaystyle r(x)\) is either a zeropolynomial or deg \(\displaystyle r<\) deg \(\displaystyle g\)

I sent you a link (via a previous post) to a youtube video that someone posted that shows this proof. What part do you not understand? In your response please include the link to the video and the time period you are not understanding. Personally I think that the video is low level but I could be wrong about that.
 

Aion

New member
Joined
May 8, 2018
Messages
39
I sent you a link (via a previous post) to a youtube video that someone posted that shows this proof. What part do you not understand? In your response please include the link to the video and the time period you are not understanding. Personally, I think that the video is low level but I could be wrong about that.
Ok. I don't understand the part at 5:30. I have don't I have a clue what a bounded set is: and after reading on Wikipedia about it a little, it seems a bit hard with no prior set theory knowledge.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,050
Ok. I don't understand the part at 5:30. I have don't I have a clue what a bounded set is: and after reading on Wikipedia about it a little, it seems a bit hard with no prior set theory knowledge.
I think that you can get by with this definition for now. A set S of numbers is bounded from above if there is a number T that is greater than every number in S. For example, if S = {2, 7.5, pi/2, e}, then this set is bounded above by 11 (or 7.9 or e^3 or ...) because 11 is greater than every number in S. We define a Set of numbers bounded below in a similar way.

I'll look at the video to see if this definition is sufficient. I wish that you posted the link to the video as now I have to find it again.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,050
Ok. I don't understand the part at 5:30. I have don't I have a clue what a bounded set is: and after reading on Wikipedia about it a little, it seems a bit hard with no prior set theory knowledge.
OK, I viewed the video and I have no idea why he talks about line segments.

What he is trying to say is very simple. He says that b<a (this is given). Then he says that you can multiply b by an integer m such that b*m> a. In fact there is a smallest integer m to do this. So if you try (m-1) (or smaller than (m-1)), then b(m-1) is NOT greater than a

For example: 5< 32. can we find the smallest integer m such that 5m>32. Lets try!
5*1 is NOT greater than 32.
5*2 is NOT greater than 32.
5*3 is NOT greater than 32.
5*4 is NOT greater than 32.
5*5 is NOT greater than 32.
5*6 is NOT greater than 32.
But 5*7 is greater than 32. So in this case m would be 7.

Not too complicated correct?!
 
Last edited:
Top