Can any function be written as a composition of other functions?

Question

Can any function be written as a composition of other functions? For example, can a polynomial $h(x)$ be written as $k(g(x))$?

Answer 1

Every function can be written as a composition, using the identity function: $h = h \circ \text{id} = \text{id} \circ h$

Your particular example will only work for some polynomials. E.g. $h(x) = 2x - 42$ can not be composed using your given functions. $$ h = k \circ g \Rightarrow \\ k = h \circ g^{-1} $$ Thus $k(x) = 2\sqrt{x} - 42 $ which is not a polynomial.

Answer 2

This is called the "extension problem" or the "lifting problem" depending on which one you fix ($f$ or $g$, where $h = g \circ f$). Its answer depends on what field or ring your polynomials are over (or more generally, what category you are working in). For a nice introductory treatment see Lawvere and Schanuel's "Conceptual Mathematics" page 45.