I'm a professional philosopher, not a mathematician, so I got myself stumped and hope somebody here will be kind enough to help me.
When I'm explaining the universal and existential quantifiers to undergraduates, I like to help motivate the semantics by telling a story and drawing a diagram.
Let the domain of discourse be five high school students: Annie, Bobby, Charlie, Dani, Eddie. I write the letters a, b, c, d, and e in a ring on the board. Then I draw an arrow to represent the "loves(x,y)" relation. [Let's assume the love relation isn't necessarily symmetric or reflexive, so the situation where A loves B is distinct from the situation where B loves A and from where (A loves B and B loves A).] This is an easy way to get the students to see there's a big difference between
- $\forall x \forall y [L(x,y)]$ ("Everybody loves everybody.")
- $\exists x \forall y [L(x,y)]$ ("Somebody loves everybody.")
- $\forall x \exists y [L(x,y)]$ ("Everybody loves somebody.")
- $\exists x \exists y [L(x,y)]$ ("Somebody loves somebody.")
Obviously there's only one diagram that would make the first sentence true. There are a bunch more diagrams that would make two and three true though. And it's clear that the fourth sentence must have the most possible diagrams that make it true.
Is there some nice technique to show exactly how many diagrams make each sentence true, given a domain of discourse with $n$ elements?
So far, all I've been able to figure out are the following:
- The number of possible diagrams should be a function of the number of elements $n$ in the domain of discourse.
- The total number of diagrams that can be drawn for $n$ elements $=$ the total number of ways to make $\exists x \exists y [L(x,y)]$ true for $n$ elements + 1 (for the null diagram)
- $f(0) =$ undefined, $f(1) = 2$, $f(2) = 12$
- This looks like a generalization of the handshake problem. Shaking hands is the special case where the relation is both irreflexive and symmetric. In general for $n$ many handshakers, you have $f(n) = n(n-1)/2$ handshakes. The division by two accounts for the symmetry of the handshake relation. (My shaking your hand is the same handshake as your shaking my hand.) But if the relation isn't symmetric, then we have three distinct possibilities, not two--I can love you, you can love me, or we can love each other.
- And now I can't figure out how to proceed.
Any help is greatly appreciated!