Let $T$ be a family of finite binary trees under the signature contains two realational symbols: $$ l(y,x) \iff \text{ y is left son of x }$$ $$ r(y,x) \iff \text{ y is right son of x }$$ Prove that for every $n \in \mathbb{N} $ there exists a such FO two-varviables-sentence $\phi_n$ that for every finite tree $t$ it is true: $$ t \models \phi_n \iff t \text { is complete and its height equals to n}$$.
My solution: Induction by height of tree:
Let $\phi_1 = \exists x [ (\exists y l(y,x) \wedge (\neg \exists x l(x,y) \vee r(x,y))) \wedge (\exists y r(y,x) \wedge (\neg \exists x l(x,y) \vee r(x,y))) ]$. It means that $x$ is a root of complete tree where its height = 1.
Induction step: Let $\phi_n(x) $ will be a such two-variable-sentence that: $$ t \models \phi_n(x) \iff \text{ t is a complete tree. Its height = n}$$
Now, we define the $$\phi_{n+1}(x) = (\exists y l(y,x) \wedge \phi_n[y/x]) ) \wedge (\exists y r(y,x) \wedge \phi_n[y/x])$$
Now, $phi_{n+1}(x) $ has no free variables.
Now, we can note that if $t \models \phi_{n+1}(x)$ then $t$ is a complete tree, its height = $n+1$. $\phi_{n+1}(x)$ is still 2-variables because the induction step doesnt introduce new variables.
Ok?
First of all, note that $\varphi_1$ isn't a sentence; it has a free variable $x$. So you need to tweak it.
Even then, you're not quite done: $\varphi_1$ (when fixed) will say that $t$ extends a complete tree of height $1$. How do you know, for instance, that $t$ isn't a complete tree of height $17$? Intuitively, your formulas need to do two things: say that $t$ is at least a complete tree of height $n$, and also say that $t$ isn't more than that. (Your inductive step is fine, after you fix the base case.)