4

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:

  1. The number of possible diagrams should be a function of the number of elements $n$ in the domain of discourse.
  2. 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)
  3. $f(0) =$ undefined, $f(1) = 2$, $f(2) = 12$
  4. 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.
  5. And now I can't figure out how to proceed.

Any help is greatly appreciated!

Thomas Andrews
  • 177,126
shane
  • 143
  • 1
    Not sure how you get $f(2)=12$. Also, are we allowing self-love? – Thomas Andrews Feb 10 '16 at 14:12
  • I just tried to enumerate the cases-but it seems I missed one. (i) nobody loves anybody, (ii) A loves himself, (iii) B loves himself, (iv) A loves B, (v) A loves himself and B, (vi)A loves himself, B loves himself and A loves B, (vii) B loves A, (viii) B loves himself and A, (ix) B loves himself, A loves himself and B loves A, (x) A and B love each other, (xi) A and B love each other, and A loves himself. (xii) A and B love each other, and B loves himself, (xiii) A and B love themselves and each other. – shane Feb 10 '16 at 14:16
  • yes, permitting self love. – shane Feb 10 '16 at 14:16
  • 1
    There should be $2^{4}$ total, and $15$ worlds with love. – Thomas Andrews Feb 10 '16 at 14:17
  • Ok, so I've probably just missed some. – shane Feb 10 '16 at 14:19
  • Basically, it should be like enumerating a truth table where $p,q,r,s$ are each of the cases A loves A, A loves B, B loves A, B loves B. – Thomas Andrews Feb 10 '16 at 14:19
  • @ThomasAndrews What about the other universally-quantified sentences? Is there a similarly simple way to calculate the number of worlds that satisfy them? – shane Feb 10 '16 at 14:28
  • Added the other counts to my answer. – Thomas Andrews Feb 10 '16 at 14:35

1 Answers1

2

There are a total of 25 possible arrows in your "directed graph," assuming self-love is allowed. So the number of possible graphs is $2^{25}$.

Then we want to remove the one case with zero edges. So the total is $2^{25}-1$.

If love is symmetric and no self-love, there are $10$ possible edges, and the total is $2^{10}-1$.

Basically, any non-empty subset of the arrows is allowed.

The case of "everybody loves somebody," the total is, for $n$ people: $(2^n-1)^n$.

The case of "somebody loves everybody" is: $2^{n^2}-(2^n-1)^n$, which is just subtracting the cases where "nobody loves everybody" from all possible graphs.

Thomas Andrews
  • 177,126