0
$\begingroup$

I'm having problem in getting the underlined statement from Gallian text:

enter image description here

Shouldn't the induction hypothesis be taken only on $n?$ But here the author also assumed the case for arbitrary field in induction hypothesis.

$\endgroup$
2
  • $\begingroup$ Note that the $n=1$ case is "the statement is true for all fields and all polynomials of degree $1$" $\endgroup$
    – Umberto P.
    Apr 2, 2014 at 17:26
  • $\begingroup$ The induction hypothesis $\,P(n)\,$ is the quoted statement restricted to polynomials of degree $\,n < \deg f.\ \ $ $\endgroup$ Apr 2, 2014 at 17:30

2 Answers 2

1
$\begingroup$

This is called Strong Induction. Assume for $P_1, \ldots P_n$ to be true and prove $P_{n+1}$ is true as well.

His assumption is for all fields and polynomials of degree less than $f(x)$.

$\endgroup$
0
$\begingroup$

If you want to use the Peano Postulates for the natural numbers as a foundation for your idea of induction, you need $n$ to be there somewhere. However, there are other basic foundations for induction - e.g. in set theory, within which we can build a model of the natural numbers.

Pure induction assumes a statement true for $n$ and shows that it follows for $n+1$ - then you need to establish the base case.

"Strong induction" assumes the truth of the statement for $1,2 \dots n$ and then proves it is true for $n+1$. Provided you have a way of talking about appropriate sets of numbers, this can be recast as follows. Let the proposition you are trying to prove be $P(n)$. Let $Q(n)$ be the proposition that $P(1), P(2) \dots P(n)$ are all true. If we can prove a base case and that $Q(n+1)$ follows from $Q(n)$ we have $Q(n)$ true, and this in turn implies that $P(n)$ is true.

In the case you cite, the induction is on the degree of the polynomial. It is a $Q$-type strong induction (all degrees less than or equal to $n$, where $f(x)$ has degree $n+1$). The hypothesis involves polynomials over "all fields" - but that is not a problem, provided we can deal with all fields at once in the proof. It doesn't impinge on the induction, which isn't on the size or nature of the field.

$\endgroup$
1
  • $\begingroup$ I note that your instinct that there might be a problem with "all fields" is a good one - there is a foundational question as with the "set of all sets". But the proof here goes through for the cases which matter for the kind of algebra being contemplated here. $\endgroup$ Apr 2, 2014 at 17:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .