Let $(E, \mathcal B(E))$ be a Polish space and $X_0$ be a random variable with values in $E$.
Let $Y_0,Y_1,\ldots$ be independent random variables with values in $(F,\mathcal F)$ and assume that $X_0$ is independent from the $Y_i$'s.
Let $\phi_n:E\times F \to E$ be a sequence of measurable functions.
Define inductively $X_{n+1} = \phi_{n+1}(X_n, Y_{n+1})$. Prove that $(X_n)$ is a Markov chain.
I'm using the following definition of Markov chain: $(X_n)$ is a Markov chain if $$\forall n\geq 1,\forall A\in \mathcal B(E),P(X_{n+1}\in A |X_n, \ldots, X_0)=P(X_{n+1}\in A |X_n)$$
I have noticed that each $X_n$ is a measurable function of $X_0,Y_1,\ldots, Y_n$, hence $X_n$ is independent of $Y_{n+1}$
I have tried using regular conditional distribution: $$P(X_{n+1}\in A |X_n=x_n, \ldots, X_0=x_0) = P(\phi_{n+1}(x_n,Y_{n+1})\in A|X_n=x_n, \ldots, X_0=x_0) $$
But I don't know what to do next.