I'm working through Raymond Smullyan's "To Mock a Mockingbird" and I'm stuck on the first problem in the combinatory logic section. I'd appreciate hints, but no spoilers please. The problem is basically as follows:
There exists a forest of magical talking birds. If you call out the name of the bird $B$ to the bird $A$, it will call out the name of another bird, We'll use the notation $AB$ to designate the bird that $A$ calls when the name of $B$ is called to $A$. Our forest has two conditions.
Condition 1: Given any two birds $A$ and $B$, there exists a bird $y$ such that $y x = A (B x)$ for any $x$. That is, if you call $x$ to $B$, and then call the name of that bird to $A$, there is such a bird $y$ that will call the name of the bird that $A$ would call after being called the name of the bird that $B$ calls after being called $x$.
Condition 2: In the forest, there is a Mockingbird, a bird such that $M x = x x$ for any $x$. That is, after calling $x$ to the Mockingbird, the Mockingbird calls out the name of the bird that $x$ would have called out after having its own name called to it.
A bird $A$ is said to be fond a bird $B$ if $AB = B$. One rumor has it that every bird in the forest is fond of at least another bird. Another rumor has it that there is at least one bird that is fond of no bird. Which rumor is true?
My approach so far has been to assume that there is a bird that is fond of no bird and then break either of the conditions. That is, show that assuming $C$ is a bird that is fond of no bird that there is some problem with $y x = M (C x)$. I'm using the Mockingbird since that's the only other bird I know anything about. Alternatively, I've tried to show that $C$ somehow breaks the Mockingbird, that is $M C = C C$ is somehow nonsensical. Neither of these approaches have panned out.
As an aside, is $M M$ possible? It seems like the existence of the Mockingbird is somewhat problematic in the first place. What happens if we call the name of the Mockingbird to itself? In symbols, I guess I might say that it would call out $(M M)$, but that's not very satisfactory.
I've been attempting proof by contradiction since I can't conceive of any approach not involving contradiction that seems to go anywhere. Some direction would be appreciated, though no spoilers please.