Existential vs Universal Quantification

Question

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.

Answer 1

The second statement is saying that 'there exists a pidgeon who lives in more than one hole" unless you actually meant to write pidgeons.

Answer 2

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.

Answer 3

Not in every hole lives a pigeon.

Negate "in every hole lives a pigeon".

$$\neg \;\forall x\;\exists y\; \Big(\operatorname{Hole}(x) \,\to\, \big(\operatorname{Pigeon}(y)\wedge\operatorname{LivesIn}(y, x)\big)\Big)$$

Remember: use implication to restrict a universe and conjugation to restrict an existence.

Then use the law of dual negation to 'flip' the quantifiers to the required state, such as:

$$\exists x\;\neg \;\exists y\; \Big(\operatorname{Hole}(x) \,\to\, \big(\operatorname{Pigeon}(y)\wedge\operatorname{LivesIn}(y, x)\big)\Big)$$

Some pigeon lives in more than one hole.

Declare the existence of (at least) two entities which are not the same thing, … and other stuff.

$$\exists x\,\exists y\,\exists z\;\Big(y\neq z\wedge\ldots\Big)$$

Answer 4

Not in every hole lives a pigeon.

$\neg \forall x:[Hole(x)\implies \exists y:[Pigeon(y) \land LivesIn(y,x)]]$

Or equivalently:

$\exists x: [Hole(x) \land \forall y: [Pigeon(y)\implies \neg LivesIn(y,x)]]$

Some pigeon lives in more than one hole.

$\exists x,y,z: [Pigeon(x) \land Hole(y) \land Hole(z) \land [LivesIn(x,y) \land Lives(x,z) \land y\neq z]]$