2. Applied

The hit new social media site FOL-owo Me involves users following users' posts.

This social media site can be represented as the tuple (S,F) where S denotes the

set of all the users in the site and F denotes the set of ordered pairs for who follows

who. Meaning we can think of S as a unary predicate and F as a binary predicate.

For example, (Mac, Excellent Elf) = F means Mac follows Excellent Elf.

In FOL-owo Me, the follow restriction holds: Vavy(Fry → (Sx ^ Sy)).

Users can follow as many users (including themselves) as they wish.

(a) Draw out a sample instance of FOL-owo Me with at least 4 users and at

least 5 ordered pairs in F. Give the users family-friendly names.

(b) Assume the worst-case scenario for the servers - Everyone is following everyone

(including themselves!). Prove by mathematical induction on the amount of

users S, that |F|≤|S|².

Hint: Think of the smallest number of users in the system, and think of how

many more follows are added when we add a new user following everyone.