The power of Closure Properties.

Question

Here is the question:

Also, we will use the notation $p_{n}: \mathbb{R} \rightarrow \mathbb{R}$ given by $p_{n}(x) = x^n$ for $n \in \mathbb{N}$ where we take $0 \in \mathbb{N}.$ Now, since $p_{1} = id_{\mathbb{R}},$ where I worked this problem:

My questions are:

1- Is, in the 6th line of problem 6, it should be $\mathcal{C}$(actually I do not know how to write this type of C that is in the picture) instead of $C$?

2-Could anyone help me in solving problem 6?

Answer 1

1. It is most definitely a typo and should be $\mathcal{C}$. It tells us that constant functions are a part of the collection.
2. A polynomial can be written as $P(x)=\sum_{k=1}^n a_k x^k$, and since it is closed under sums, you have to show that each $a_k x^k$ is in $\mathcal{C}$. $a_k \in \mathcal{C}$ by assumption 2, and $x^n \in \mathcal{C}$ by assumption 1 and 4. Thus $a_k x^k \in \mathcal{C}$ again by assumption 4, then by assumption 3, $P(x) \in \mathcal{C}$.

Answer 2

As far as I can see, line six does say $\mathcal{C}$, the set of functions under discussion. Anything else would be strange after the intro.

Note that $p_1(x)=x$, and closedness under products gives that $p_1 \cdot p_1 \in \mathcal{C}$ and this map is just $x \to x \cdot x=x^2$ so $p_2 \in \mathcal{C}$.

By induction $p_n(x) \in \mathcal{C}$ as $p_{n+1}=p_1 \cdot p_n$ for all $n$. As $\text{const}_c$ is in $\mathcal{C}$ as well, all functions of the form $x \to cx^n$ are in $\mathcal{C}$ too, by the product requirement.

Also show that $\mathcal{C}$ is closed under all finite sums (not just sums of two), by induction; a standard argument.

Then any polynomial $f$ can be written as $f(x)=c_0 + c_1x + c_2x^2 + \ldots + c_n x^n$ a finite sum of functions that we've already shown to be in $\mathcal{C}$ and so is in $\mathcal{C}$ by the sum condition and its finite sum extension.

Answer 3

$(6)$ has a natural rigorous proof by induction on degree. For the base case all zero degree polynomials (constants) are in $\cal C$ by hypothesis. Else $\deg f \ge 1$ hence by the polynomial division algorithm $\,f = q\, x + c\,$, with $\deg q < \deg f\,$ so $\,q\in\cal C\,$ by induction, hence $\,x = p_1\in\cal C\,$ and constant $\,c\in\cal C\,$ implies $\,q\,x+c = f\in\cal C,\,$ by $\,\cal C\,$ closed under multiplication and addition.

Remark $ $ Unwinding the induction essentially writes $f(x)$ in Horner form

$$ f(x) \,=\, f_0 + x (f_1 + x(f_2 + x(\cdots)))$$

It deserves to be better known that exponentiation by repeated squaring is simply a multiplicative analog.

One more general perspective that may prove instructive is structural induction and recursion.