2
$\begingroup$

I was looking at the following question: which is the stronger logic statement

The original poster provides two statements with the only difference being the order of the quantifiers as follows:

$\forall a \exists b \forall c \; Sport(a,b,c)$ (1)

&

$\forall a \forall c \exists b \;Sport(a,b,c)$ (2) where a,b represent people.

My question is, why exactly is there a difference in the "strength" of a statement due to the order of the quantifiers? I have read the answer on the aforementioned question, but I am looking for something which is a bit more concrete.

My interpretation of (1) in English is as follows:

For each person $a$, there is a sport $b$, which is shared by every other person $c$

Similarly, my interpretation of (2) in English is as follows:

For every person $a$ and $c$, there is a sport $b$ which they share

Are these two statements not equivalent? Could someone prove this?

$\endgroup$
1
$\begingroup$

They certainly are not equivalent. The first statement $$ \forall a\, \exists b\, \forall c\, Sport(a, b, c) \tag{1} $$ is true when and only when everybody "shares" a single sport. The second, $$ \forall a\, \forall c\, \exists b\, Sport(a, b, c) \tag{2} $$ is true only when any pair of people share some sport. This is a weaker statement than (1), because (2) applies to a broader range of states of the world than (1) does. (1) implies (2), in short, but not conversely.

Imagine a universe with three sports: basketball, polo and curling. In this universe there are 3 people: Tom, Dick and Harry. Tom and Dick share basketball; Tom and Harry share polo; Dick and Harry share curling.

Then (2) is true in this universe: any two people share a sport.

But (1) is false in this universe. (Suppose it's true. In (1), let $a$ be Tom. Then there is some sport $b$ such that $\forall c \, Sport(Tom, b, c)$. But whichever sport $b$ is taken as, there's some $c$ with whom Tom does not share that sport.)

$\endgroup$
  • $\begingroup$ I don't quite understand your explanation for the first statement where you say "is true when and only one everybody "shares" a single sport". Could you rephrase this please? $\endgroup$ – user141834 Oct 20 '15 at 6:16
  • $\begingroup$ Also, would you say that my english interpretation of the statements is correct? $\endgroup$ – user141834 Oct 20 '15 at 6:20
  • $\begingroup$ @user141834 Sorry "when and only one" should have been "when and only when" -- fixed. Yes your English versions of the statements are correct, they're very faithful to the first order sentences. $\endgroup$ – BrianO Oct 20 '15 at 6:23
  • $\begingroup$ If (2) applies to a broader range of states, wouldn't that make it a stronger statement as opposed to weaker? $\endgroup$ – user141834 Oct 20 '15 at 6:47
  • 2
    $\begingroup$ Just the reverse, as @NoahSchweber points out in his answer. Stronger = less chance of being true , more restrictive, harder to satisfy, true of fewer states of affairs; weaker = more chance of being true, easier to satisfy, true of more states of affairs. Stronger implies weaker — red is a color, but not all colors are red. The weakest statements are tautologies and logical validities (and thought-stopping cliches, e.g. "it is what it is"). They're always true and don't impart any new information. $\endgroup$ – BrianO Oct 20 '15 at 6:55
1
$\begingroup$

A simpler example that might be easier to start with:

  • The sentence "$\forall x\exists y(y>x)$" is certainly true (of the natural numbers, say): there is no biggest natural number.

  • The sentence we get by switching the order of the quantifiers, though - "$\exists y\forall x(y>x)$" - is false, for exactly the reason that the former was true!

So this shows that altering the order of quantifiers can effect the truth value. If you think about this example, it should become clear that moving existential $\exists$ quantifiers to the left, outside of universal $\forall$ quantifiers, will always make a sentence$^*$ stronger (=less likely to be true).


$^*$I'm assuming our sentence is in prenex normal form, so all the quantifiers are already on the outside.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.