Prove that recursively defined function is injective and equal to subset

Question

This is my question from one of the past paper exams, I am solving it it but I am not sure. The question is following:
A certain subset A of the set {0,1}* is defined recursively as follows:

Base case: λ ∈ A.
Constructor case 1: If s ∈ A then 0s ∈ A.
Constructor case 2: If s ∈ A then 10s ∈ A.
Constructor case 3: If s ∈ A then 11s ∈ A.
A certain function f : {x,y,z}* --> {0,1}* is defined recursively as follows:

Base case: f(λ) = λ.
Constructor case 1: f(xs) = 0f(s) = <0, f(s)>
Constructor case 2: f(ys) = 10f(s) = <1, <0, f(s)>>
Constructor case 3: f(zs) = 11f(s) = <1, <1, f(s)>>

Prove that f is injective.
Prove that f({x,y,z}*) = A.

This is my solution:

1. 
   

In injective function if f(x)=f(y), then x=y.

Let's define a predicate P(s) ---> {0,1}* Where for every t ∈ {x,y,z}*
If we can prove that s=t when f(s)=f(t) Then we can conclude that function f is injective.
Base Case:
In Base case λ ∈ A As well as f(λ) = λ, therefore f(s) = f(t) as both equal to λ
Constructor Case:
Case 1;
f(xs) = 0f(s) = <0, f(s)>
f(xt) = 0f(t) = <0, f(t)>
f(xs)=f(xt) => s = t
Case 2 and 3 the same way. Therefore, we conclude that the function f is injective.

2. I do not understand how to do this

Answer 1

Actually, surjectivity is easier: We need to show that

• $f(s)=\lambda$ for some $s\in \{x,y,z\}^*$
• If $s\in f(\{x,y,z\}^*)$ then $0s\in f(\{x,y,z\}^*)$.
• If $s\in f(\{x,y,z\}^*)$ then $10s\in f(\{x,y,z\}^*)$.
• If $s\in f(\{x,y,z\}^*)$ then $11s\in f(\{x,y,z\}^*)$.

The first is clear because $f(\lambda)=\lambda$. For the other three parts, note that $s\in f(\{x,y,z\}^*)$ means $s=f(t)$ for some $t\in \{x,y,z\}^*$. But then $0s=f(xt)$, $10s=f(yt)$, $11s=f(zt)$. $\square$

For injectivity, you may need to be a bit more careful. As you suggest, we let $$ P(s)\equiv \forall t\in\{x,y,z\}^*\colon f(s)=f(t)\to s=t$$

• We have $P(\lambda)$ because if $t\ne \lambda$ then $t$ begins with $x$, $y$, or $z$, hence $f(t)$ begins with $0$, $10$, or $11$. At any rate $f(t)\ne \lambda= f(\lambda)$.
• If $s=xs'$ and $f(s)=f(t)$ then $t=\lambda$ or $t=xt'$ or $t=yt'$ or $t=zt'$. As $f(s)$ begins with $0$, we can exclude $t=\lambda$, $t=yt'$, and $t=zt'$. Hence $t=xt'$ and $0f(s')=f(s)=f(t)=0f(t')$ implies $f(s')=f(t')$. By induction hypothesis, $s'=t'$ and ultimately $s=xs'=xt'=t$.
• If $s=ys'$ and $f(s)=f(t)$ then $t=\lambda$ or $t=xt'$ or $t=yt'$ or $t=zt'$. As $f(s)$ begins with $10$, we can exclude $t=\lambda$, $t=xt'$, and $t=zt'$. Hence $t=yt'$ and $10f(s')=f(s)=f(t)=10f(t')$ implies $f(s')=f(t')$. By induction hypothesis, $s'=t'$ and ultimately $s=ys'=yt'=t$.
• If $s=zs'$ and $f(s)=f(t)$ then $t=\lambda$ or $t=xt'$ or $t=yt'$ or $t=zt'$. As $f(s)$ begins with $11$, we can exclude $t=\lambda$, $t=xt'$, and $t=yt'$. Hence $t=zt'$ and $11f(s')=f(s)=f(t)=11f(t')$ implies $f(s')=f(t')$. By induction hypothesis, $s'=t'$ and ultimately $s=zs'=zt'=t$.