Is there a proof that the observations of a hidden Markov chain is not itself a Markov chain? Suppose $\{X_n\}$ is the hidden Markov chain, and $\{Y_n\}$ is the series of observations, where $\mathbb{P}\{Y_n = j| X_n = i\}$ is the same for all $n$ (please correct me if I have not stated the definition of hidden Markov models correctly). How does one show rigorously that $\{Y_n\}$ does not have the Markov property?
Thank you in advance.

You cannot show that for every $X_n$ and $Y_n$. For some $X_n$ and $Y_n$, the process $Y_n$ is a Markov process. For instance if $Y_n = X_n$ and $X_n$ is an arbitrary Markov process then $Y_n$ is a Markov process. 
On the other hand, if $X_n$ is a random walk on a path $u_1 \to u_2 \to u_3 \to u_4$ of length 4, and
$$
Y_n = \begin{cases} 0, & \text{if } X_n = u_1\\ 1, & \text{if } X_n \in\{ u_2, u_3\} \\ 2, &\text{if }  X_n = u_4\end{cases}
$$
then $Y_n$ is not a Markov chain (hint: prove that $\Pr[Y_n = 0 \wedge Y_{n+1} = 1 \wedge Y_{n+2} = 2] = 0$).
