6
$\begingroup$

$\exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y)$

I was told they were not, but I don't see how it can be true.

  • 0
    [Confused between nested quantifiers](http://math.stackexchange.com/questions/64500/confused-between-nested-quantifiers), [Is the order of universal/existential quantifiers important?](http://math.stackexchange.com/questions/201051/is-the-order-of-universal-existential-quantifiers-important)2012-11-04

3 Answers 3

6

Let $ P(x,y) $ be the statement '$ x $ loves $ y $', where $ x $ and $ y $ are variables ranging over all individuals from a selected group of people. The LHS reads 'there is someone who loves everyone'. The RHS reads 'everyone is loved by someone'. The LHS can be made false while the RHS made true, if the group of people is carefully chosen.

It is a theorem of the predicate calculus, though, that $ (\exists x)(\forall y)P(x,y) \rightarrow (\forall y)(\exists x)P(x,y) $. The formal proof of this, using the Hilbert Deduction System, is as follows:

  1. $ \quad (\exists x)(\forall y)P(x,y) \quad $ (Assumption)
  2. $ \quad \quad (\forall y)P(x,y) \quad $ (Rule C with variable $ x $; assumption)
  3. $ \quad \quad P(x,y) \quad $ (Rule of Specification)
  4. $ \quad \quad (\exists x)P(x,y) \quad $ ($ \exists $-Rule)
  5. $ \quad \quad (\forall y)(\exists x)P(x,y) \quad $ (Rule of Generalization)
  6. $ \quad (\forall y)(\exists x)P(x,y) \quad $ (Rule C; Assumption 2 is discharged)
  7. $ (\exists x)(\forall y)P(x,y) \rightarrow (\forall y)(\exists x)P(x,y) \quad $ (Deduction Theorem, 1 - 6)

Notice that the theorem does not contradict what I said earlier about $ (\exists x)(\forall y)P(x,y) $ being false and $ (\forall y)(\exists x)P(x,y) $ being true. As $ \text{False} \rightarrow \text{True} $ is true, there is no contradiction.

If you try to prove the converse of the theorem, namely $ (\forall y)(\exists x)P(x,y) \rightarrow (\exists x)(\forall y)P(x,y) $, you will realize that no amount of fiddling with the rules of the Hilbert Deduction System will get you anywhere. Therefore, $ (\forall y)(\exists x)P(x,y) $ is generally weaker than $ (\exists x)(\forall y)P(x,y) $.

Finally, the difference between the concepts of 'continuity' and 'uniform continuity' is due precisely to the fact that $ (\forall y)(\exists x)P(x,y) $ can be weaker than $ (\exists x)(\forall y)P(x,y) $. Let $ f $ be a real-valued function on $ \mathbb{R} $. Expressing the continuity of $ f $ in symbols, we get $ (\forall \epsilon)(\forall x)(\exists \delta)(\forall y)(|x - y| < \delta \rightarrow |f(x) - f(y)| < \epsilon). $ Expressing the uniform continuity of $ f $ in symbols, we get $ (\forall \epsilon)(\exists \delta)(\forall x)(\forall y)(|x - y| < \delta \rightarrow |f(x) - f(y)| < \epsilon). $ Notice the swap in the middle-two quantifiers from $ (\forall x)(\exists \delta) $ to $ (\exists \delta)(\forall x) $. Hence, by the theorem, we expect uniform continuity to imply continuity. However, continuity does not imply uniform continuity. For example, the exponential function is continuous but not uniformly continuous.

  • 1
    @MathildaPitt: You can also read the RHS as 'for every person, there is so$m$eone who loves that person'.2012-10-31
2

Take the more concrete statements: $\forall {n \in \mathbb{N}}\ \exists {m \in \mathbb{N}}: m > n$ versus $\exists {m \in \mathbb{N}}\ \forall {n \in \mathbb{N}}: m > n$. Now the first statement reads: For every natural number there's a bigger one. The second statement reads: There's a biggest natural number.

Quantifiers of different type don't commute. However, quantifiers of the same type do: $\exists x \ \exists y \equiv \exists y \ \exists x$ and $\forall x \ \forall y \equiv \forall y \ \forall x$.

2

Not the same. Compare

(RHS) "Every person has some father or other"

with

(LHS) "There's some guy who fathered every person in the human race"

  • 1
    The intent was to offer something intuitive and simple for a beginner to understand. It's hard for me to believe that the top voted answer, with its Hilbert deduction systems, continuity definitions, etc. would make sense to a person asking this sort of question. It may not add much info for somebody who TA'ed logic courses. As to real world analogies--every intro logic book I have uses them to explain semantics involving multiple quantifiers.2013-09-22