Here is the statement of the problem
Set RAF of rational functions is defined recursively in this manner:
Base Case :
- Identity function id(r) ::= r for $r \in R$ (the real numbers), is an RAF
- Any constant function on R is an RAF
Constructor cases: If f,g are RAF's, then so are $f \star g$, where $\star$ is one of the operations +,*, or /
Prove by structural induction that RAF is closed under composition. That is, using induction hypothesis, $$P(h) = \forall g \in RAF. h \circ g \in RAF$$
Prove that $P(h)$ is true $\forall h \in RAF$
Where I am getting stuck
I decide to do induction on h. Proving the base cases was easy. The function returned g and k in the case of identity function and constant function respectively. However, I am a bit confused about the inductive step. I decided to assume that $h \circ g \in RAF$, and tried to prove it for $h \circ (h \circ g)$, which followed from the fact that if $h \circ g$ is rational, then $h \circ (h \circ g)$ should be rational because h of any rational function is rational (Our assumption in the inductive step). However, I am still unsettled and confused about it because I didn't use the $f \star g$ part anywhere in my proof, and can't think of where to accomodate it. I also feel like I'm missing some other important part here, but I can't say what.
Best Answer
You seem to be confusing what you need to show for the inductive case. The number of compositions is not relevant, since you are not doing induction on the number of $\circ$'s.
You are performing induction on $h$, so you need to consider all possible cases for $h$. The base cases are $h=\mathrm{id}$ or $h=\mathrm{constant}$, which when composed with another rational function clearly result in a rational function.
Then you need to consider the "constructor" cases where $h=\phi+\psi$, $h=\phi\psi$, and $h=\frac\phi\psi$ (where $\phi,\psi\in\mathrm{RAF}$).
So for example, in the first case, if $h=\phi+\psi$, then we have $$h\circ g = (\phi+\psi)\circ g = (\phi\circ g) + (\psi\circ g),$$ where these two are now in $\mathrm{RAF}$ by the hypothesis (since $\phi$ and $\psi$ are substructures of $h$) and thus their sum is in $\mathrm{RAF}$.