## Mathematical Birdwatching (and Combinatory Logic)

By David K. Zhang

## 1. The Enchanted Forest

Imagine that you wake up one day in an enchanted forest populated by talking birds. The birds love talking about each other if you walk up to a bird and say the name of a bird then will say the name of a bird in response, which we designate by If you instead approach and say 's name, will respond with another name which is not necessarily the same as

The birds always behave in a consistent and predictable manner, in the sense that 's response to hearing is always the same bird regardless of the weather or time of day. This means that the operation of saying 's name to can be regarded as a mathematical function.

Definition: A forest is a set equipped with a binary operation , denoted by juxtaposition. The elements of are called birds. If , then we interpret as 's response to hearing the name of .

Example: Consider the set equipped with the following binary operation:

(We use a dot to separate bird names when they are spelled out.) In this two-element forest, the parrot simply repeats back the name of whatever bird it hears, while the cardinal only talks about itself.

Whenever we have three birds, and we must be careful to distinguish between the names and The first is 's response to , while the second is 's response to these are not necessarily the same! Thus, the operation of “multiplying” two birds is in general neither commutative nor associative. We will use parentheses throughout to indicate the order in which birds are spoken to.

We will begin our study of ornithology by describing some special types of relationships between birds.

Definition: Let be a forest, and let be any three birds.

• We say that is fond of if responds to 's name by repeating it. In symbols, is fond of if .
• We say that is normal if it is fond of some bird in (including possibly itself). Otherwise, if is not fond of any bird in (not even itself), it is abnormal.
• We say that composes with if for all birds , we have that . This means that 's response to is the same as 's response to 's response to .

Note that a given forest might not contain a composition for every pair of birds. Moreover, when a composition exists, it might not be unique! For this reason, composing birds is subtly different from composing mathematical functions.

Warning! Note that does not mean that composes with