Problem 4. [18 points] You are a lonely logician in desperate need of a friend. However, knowing that it would be impossible to make one, you decide to focus your time on something much more achievable: creating a general AI (artificial intelligence) who will then be your friend!

Amazingly, you succeed! You make yourself a friend whom you name Alan. Now all you need to do is teach Alan what friendship is. You decide to model friendship as a relation on a set of people. Rather than explicitly define the relation, you decide to explain some rules that any relation modelling friendship must follow. These are your three laws of robotic friendships:

Not everyone is friends with everyone (as you harshly know from your lack of human friends).

The enemy of my enemy is my friend (this is a good saying youve heard before! For simplicity, you tell Alan enemy just means not friend).

The enemy of my friend is my enemy.

With these three laws defining friendship, what will Alan learn?

a) [6 points] Draw the directed graph of a relation on a set of 3 people which satisfies the three properties above (i.e. a dot for each person and an arrow from person a to person b if friend(a, b)). Explain how you arrived at your relation.

b) [12 points] Does Alan think friendship is an equivalence relation? Explain why or why not. If it is, how many equivalence classes does it define on a set of 100 people? Explain in English how you arrived at your answer.