Let's consider the following definition (I'm not an expert, so let me know if this is not the usual one!).
Let $I\subset \mathbb{R}$ be an open interval. A function $f:I\to \mathbb{R}$ is said to be algebraic on $I$ if there is a nonzero polynomial $p\in \mathbb{R}[x,y]$ such that $p(x,f(x)) = 0$, for every $x\in I$.
Remark: Even if this is not usual, it is what I have in the situation I'm studying.
My question is: Given two algebraic functions $f,g$ on $I$, is there a nonzero polynomial $P\in \mathbb{R}[x,y]$ such that $P(f(x),g(x))=0$ for every $x\in I$?
What I've tried: Let $p$ and $q$ be polynomials on $\mathbb{R}[x,y]$ such that $p(x,f(x))=q(x,g(x))=0$, for every $x\in I$. Write $$p(x,y)=\sum_{j=0}^n a_j(y) x^j,$$ $$ q(x,y)=\sum_{j=0}^m b_j(y) x^j,$$ with $a_j, b_j\in \mathbb{R}[y]$ and $a_n$, $b_m$ both not identically zero.
Whithout loss of generality, suppose $m\leq n$. Then we have $$b_m(g(x)) x^m =-\sum_{j=0}^{m-1}b_j(g(x)) x^j,\quad \forall x\in I.$$
Then, multiplying the equation $0=p(x,f(x))$ by $b_m(g(x))$ as many times as needed, allows us to decrease the degree of $x$ in this equation to, at most, $m-1$. More precisely, this yields an equation of the form $$Q(x,f(x),g(x))=0,\quad \forall x\in I,$$ for a certain polynomial $Q\in \mathbb{R}[x,y,z]$, with degree at most $m-1$ on $x$.
Collecting again on $x$ and isolating its leading term, allows us again to decrease the degree of $x$ by multiplying the equation $q(x,g(x))=0$ by its coefficient (again, as many times as needed - and this complicates matters, since we're talking about powering polynomials).
So eventually, we're going to have an equation "free of $x$", i.e. $P(f(x),g(x))=0$, for some $P\in \mathbb{R}[x,y]$.
Example: Consider $n=2$, $m=n-1$. For the sake of simplicity, let's write $a_j(f(x))$ and $b_j(g(x))$ just as $a_j$, $b_j$. Then we have $$a_2x^2+a_1x+a_0=0,$$ $$b_1x=-b_0.$$ Multiplying the first equation by $b_1^2$, we get the relation $$a_2b_0^2-a_1b_0b_1+a_0b_1^2=0.$$ The case $n=3$, $m=n-1$ will require two steps and yields a considerably more complicated relation...
This seems a very promising algorithm, at least in theory (although computationally expensive). But is there any hope to pose conditions on $f$ and $g$ in order to guarantee that $P$ is nonzero? Actually, what $P\equiv 0$ would mean for $f$ and $g$? (this seems very unlikely in general).
The answer is yes, and we don't necessarily have to construct an explicit $P$. If $f$ is constant, say equal to $r\in\Bbb R$, then $P=x-r$ suffices. Now suppose $f,g$ are nonconstant. Consider the tower of fields $\Bbb R(f)\subset \Bbb R(f,g)\subset\Bbb R(x)$. As $\Bbb R(f)\subset\Bbb R(x)$ is algebraic, the extension $\Bbb R(f)\subset\Bbb R(f,g)$ is algebraic, so there is a nonzero polynomial in $\Bbb R(f)[t]$ satisfied by $g$. Clearing denominators, we obtain a nonzero polynomial $P$ which vanishes on $f$ and $g$.
There are other ways to see this, too. One is to consider the ideal $J=(p(x,y),q(x,z))\subset\Bbb R[x,y,z]$ and note that $J\cap \Bbb R[y,z]$ will contain a $P$ if it's nonzero. But $f,g$ nonconstant imply $p,q$ nonzero imply $J$ of height two, so the intersection $J\cap \Bbb R[y,z]$ cannot be zero (algebro-geometrically, this is the statement that an [algebraic] curve in 3-space cannot project down to cover the whole plane).
If you do want to construct an explicit $P$, one way to do this is to write $p=p'd$ and $q=q'd$ for $d$ the GCD of $p,q$, then take the resultant of $p$ and $q'$ - this is guaranteed to not vanish as they're coprime, and it can actually (kind of) be calculated.