lambda calculus type assigned problem

Question

we have $\lambda xabc.xa(xbc)$ and we should give a type for it can we assign $a$ and $b$ to the same symbol ? like here $a$ and $b$ should be same type for example $\alpha$ so we can continue ? $a,b = \alpha$ $c=\beta$ $x = \alpha \rightarrow \beta \rightarrow \beta$ is it correct this way ?

Answer 1

I am not sure what you are saying, but from context it seems like you are asking what the type of $\lambda x a b c.x~a~(x~b~c)$ should be, and in particular, if we can show $a, b : \alpha$, $c : \beta$, and $x : \alpha \to \beta \to \beta$. You are correct, and I'll explain in detail how we can figure this out:

We have a term $\lambda x a b c . x ~ a ~(x~b~c)$. Let's start by saying $a : \alpha$, $b : \beta$, $c : \gamma$, $x:\chi$. Let's see if we can figure out constraints on our types in order to make the above term well-typed.

The first thing to notice is that $x$ is a function of 2 arguments. If we look at $x~b~c$, we know that $x : \beta \to \gamma \to \tau$. This is because $b : \beta$ and $c : \gamma$, but we cannot constrain our output type (yet).

Now we see we also need $x~a~(x~b~c)$ to be well typed. So $a$ must have type $\beta$ (since that is the type of $x$'s first argument) and $(x~b~c)$ must have type $\gamma$ (since that is the type of $x$'s second argument).

So now we have also constrained the output type of $x$. We must have $x : \beta \to \gamma \to \gamma$, and this is where we can stop.

$a,b : \beta$, $c : \gamma$, and $x : \beta \to \gamma \to \gamma$ is consistent with our constraints, and there is no extra information to use. Of course, we can clean this up a little bit (renaming our type variables to be closer to the front of the alphabet) and write the final answer (which you correctly gave):

$a,b : \alpha$, $c : \beta$, and $x : \alpha \to \beta \to \beta$.

Keep in mind that this $\alpha$ is different from the $\alpha$ we were using before! We have renamed everything in sight, and I've known some students who get confused by this step.

---

I hope this helps ^_^