[Math] Existential vs Universal Quantification


What is the difference and how can I write these two statements in both forms?

Not in every hole lives a pigeon.

Some pigeon lives in more than one hole.

For the first statement I have $∀h∀p [LivesIn(p, h)]$ but I am not sure how to express this in the universal form.

I am not sure how to express the second statement, because it says "more than one", so a for all wouldn't make sense (at least from what I understand (which is very little))

Also, if you combine a for all and a there exists then what is it, existential or universal? If anybody can help clear the air on these problems for me I would be extremely grateful.

Best Answer

For the first, "Not in every hole lives a pigeon", start from the positive assertion, "In every hole lives a pigeon." The one which you're trying to represent is just the negation of that. "In every hole lives a pigeon" is a universal-existential sentence: "for every hole, there's a pigeon that lives in it", or symbolically, $\forall h \exists p\,(Hole(h) \to (Pigeon(p) \wedge LivesIn(p, h)))$. Negating this, moving the negation across the quantifiers and transforming the propositional matrix of the sentence gives the following: $$ \begin{align} &\neg \forall h \exists p\,(Hole(h) \to (Pigeon(p) \wedge LivesIn(p, h))) \\ \iff &\exists h \forall p\,\neg(Hole(h) \to (Pigeon(p) \wedge LivesIn(p, h))) \\ \iff &\exists h \forall p\,(Hole(h) \wedge \neg (Pigeon(p) \wedge LivesIn(p, h))) \\ \iff &\exists h \forall p\,(Hole(h) \wedge (Pigeon(p) \to \neg LivesIn(p, h))) \\ \end{align} $$ In other words, "There's a hole in which no pigeon lives."

For the second sentence, "Some pigeon lives in more than one hole": "some" should signal "existential quantifier" to you. In order to express "more than one", just (in)equality. Like so: $$ \exists p\,(Pigeon(p) \wedge \exists h_1 \exists h_2\, (Hole(h_1) \wedge Hole(h_2) \wedge h_1 \neq h_2 \wedge LivesIn(p, h_1) \wedge LivesIn(p, h_2)) $$ That is, "There is a pigeon $p$, and there are distinct holes $h_1, h_2$ such that $p$ lives in both $h_1$ and $h_2$."

Note that combining existential and universal quantifiers gives a new thing: the meaning is in general distinct from the meaning of any purely existential or purely universal sentence. Furthermore, order matters: $\forall \exists$ is very different from $\exists \forall$. Three alternating quantifiers is yet another level of complexity, not reducible two-quantifier forms. And so on.

Related Question