How Does Nicholson Apply Induction in Theorem 12 Proof?

In summary, Nicholson is discussing how to use the Principle of Mathematical Induction in a proof. He assumes that every polynomial of degree $d<n$ has a unique factorization, and then proves that a polynomial of degree $n$ also has a unique factorization.
  • #1
Math Amateur
Gold Member
MHB
3,998
48
I am reading W. Keith Nicholson's book: Introduction to Abstract Algebra (Third Edition) ...

I am focused on Section 4.2:Factorization of Polynomials over a Field.

I need some help with the proof of Part 1 of Theorem 12 on page 218

The relevant text from Nicholson's book is as follows:https://www.physicsforums.com/attachments/4596I do not follow how Nicholson is using the Principle of Mathematical Induction in Part (1) of the above proof ... ... indeed I find his proof strategy quite puzzling.

Nicholson seems to me to proceed as follows:

He proves the case for \(\displaystyle n\) = deg \(\displaystyle f = 1\) ... well and good ...

Now, according to my understanding of the Principle of Mathematical Induction he should assume (1) is true for deg \(\displaystyle f = n\) and then prove it true for deg \(\displaystyle f = n + 1\).

... ... BUT ... Nicholson does not seem to do this ... ?Can someone please explain exactly how Nicholson is using the Principle of Mathematical Induction ...

Help will be appreciated ...

Peter
 
Physics news on Phys.org
  • #2
Hi Peter,

There is a difference between using simple or strong induction.

Suppose we want to prove some property $P$ for all natural numbers.

If we use simple induction then we will do what you expect, assume $P(n)$ is true and then prove $P(n+1)$.

But, if we use strong induction we will assume $P(i)$ true for all $i<n$ and then prove $P(n)$, and that's what Nicholson is doing here.

He assumes that every polynomial of degree $d<n$ has a unique factorization, and then proves that a polynomial of degree $n$ also has a unique factorization.
 
  • #3
Fallen Angel said:
Hi Peter,

There is a difference between using simple or strong induction.

Suppose we want to prove some property $P$ for all natural numbers.

If we use simple induction then we will do what you expect, assume $P(n)$ is true and then prove $P(n+1)$.

But, if we use strong induction we will assume $P(i)$ true for all $i<n$ and then prove $P(n)$, and that's what Nicholson is doing here.

He assumes that every polynomial of degree $d<n$ has a unique factorization, and then proves that a polynomial of degree $n$ also has a unique factorization.
Thanks for the help, Fallen Angel ...

Reflecting on on this now ...

Thanks again,

Peter
 
  • #4
This is somewhat off-topic, but "strong" induction and "weak" (regular) induction are actually equivalent.

It is (hopefully) clear that strong induction certainly implies regular induction: if we assume something is true for all:

$n_0 \leq k < n$

then it is certainly true for $k = n-1$ (as long as $n \geq n_0 + 1$, of course).

Of course, it is *not* as clear that weak induction implies strong induction.

Suppose the statement we wish to prove (for all $n \geq n_0$) is $P(n)$. We then consider:

$Q(n) \stackrel{\text{def}}{=} \forall (n_0 < m < n): P(m)$

and apply weak induction to $Q$, proving strong induction for $P$.

This is especially useful in using induction on "divisibility orderings", where it may be hard to get a statement $P(n)$ into the form $P(n-1)$ and "something else" (a tactic that works very well on SUMS, typically), but it is easy to get a statement on FACTORS of $n$.
 
  • #5
Deveno said:
This is somewhat off-topic, but "strong" induction and "weak" (regular) induction are actually equivalent.

It is (hopefully) clear that strong induction certainly implies regular induction: if we assume something is true for all:

$n_0 \leq k < n$

then it is certainly true for $k = n-1$ (as long as $n \geq n_0 + 1$, of course).

Of course, it is *not* as clear that weak induction implies strong induction.

Suppose the statement we wish to prove (for all $n \geq n_0$) is $P(n)$. We then consider:

$Q(n) \stackrel{\text{def}}{=} \forall (n_0 < m < n): P(m)$

and apply weak induction to $Q$, proving strong induction for $P$.

This is especially useful in using induction on "divisibility orderings", where it may be hard to get a statement $P(n)$ into the form $P(n-1)$ and "something else" (a tactic that works very well on SUMS, typically), but it is easy to get a statement on FACTORS of $n$.
Thanks for for the help Deveno ...

Just by the way ... I am so happy to see you back!

Peter
 

FAQ: How Does Nicholson Apply Induction in Theorem 12 Proof?

1. What is the Unique Factorization Theorem for polynomials over a field?

The Unique Factorization Theorem, also known as Nicholson Theorem 12, states that every polynomial over a field can be factored in a unique way as a product of irreducible polynomials.

2. What is the significance of Unique Factorization Theorem in mathematics?

The Unique Factorization Theorem is an important result in mathematics as it allows us to simplify and manipulate polynomials in a systematic way. It also has applications in algebraic geometry, number theory, and algebraic coding theory.

3. How does the Unique Factorization Theorem differ from the Fundamental Theorem of Algebra?

The Fundamental Theorem of Algebra states that every polynomial with complex coefficients can be factored into linear factors. However, the Unique Factorization Theorem applies to polynomials over any field, not just the complex numbers, and allows for factoring into irreducible polynomials, which cannot be further factored.

4. Can the Unique Factorization Theorem be extended to polynomials with coefficients in a ring?

No, the Unique Factorization Theorem only applies to polynomials over a field. In a ring, there may be zero divisors, which would break the uniqueness of the factorization.

5. Are there any conditions or restrictions for the Unique Factorization Theorem to hold?

Yes, in order for the Unique Factorization Theorem to hold, the field must be a unique factorization domain (UFD). This means that every nonzero element in the field can be factored into irreducible elements in a unique way.

Similar threads

Back
Top