# Prove that all combinators must fulfill A x = x for some x, given that M x = x x and composability of any two combinators

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.

-
What does 'fond' mean in the context of these birds? – Ted Jan 2 '13 at 5:46
The usual proof that every bird is fond of at least one other bird, involves constructing such a bird, not a proof by contradiction. The Mockingbird is indeed a key element in such a construction. I don't really know how to give a hint without giving it away though (many constructions exist, but none is very intuitive to me and I have to look it up each time). – Ted Jan 2 '13 at 6:14
ryu jin deleted his comment about the definition of 'fond' but I think it was correct (based on searching the web): B is fond of A if BA=A. – Ted Jan 2 '13 at 6:25
Yes, that's the definition of fond. I can't believe I neglected to add that. – Josh Infiesto Jan 2 '13 at 6:54

Hint: Consider an arbitrary bird $A$ from the forest. Try to prove the existence of a bird $B$ such that $A(BB) = BB$ (so that $A$ is fond of $BB$).