Here are three example sentences:
- Everything Anna knows, Bob also knows.
∀y(Knows(alice, y) -> Knows(Bob, y))
- There are things Anna knows, that bob does not.
∃y(Knows(Anna, y) ^ ¬(Knows(Bob, y))
- Alice knows only one thing.
∀x∃y(¬(Knows(Anna, x)) v Knows(Anna, y))
I think I got the first two right. But I'm not sure on the third. Can anyone confirm that I'm right or push me in the right direction?
I'm also trying to prove:
∀x∃y(x = y), ∃x¬P(x) $\vdash$ ¬∀x¬P(x)
I really can't find a counterexample to disprove it, but I also can't find any way to prove it. So any help to help me along here would be very appreciated.
Edit: Is this a solution? If my structure is only allows for {1}, and P = {∅}. Then ∀x∃y(x = y) is true. ∃x¬P(x) is also true but ¬∀x¬P(x) is not, since ¬∀x¬P(x) = ∃xP(x) and there is no x which satisfies P?
Thanks!
You indeed got 1 and 2 right. And, as you feared, 3 is not right.
To do 3, think about it this way: there is something that Anna knows, but that is the only thing she knows. So: there is something she knows, and there isn't anything other than that thing she knows. So:
$$\exists x (Knows(Anna,x) \land \neg \exists y (y \not = x \land Knows(Anna, y)))$$
Another intuitive paraphrasing would be: there is something she knows, and everything she knows is that very thing. So then you get:
$$\exists x (Knows(Anna,x) \land \forall y (Knows(Anna, y) \to y = x))$$
In the comments, Mauro offered a third one: there is something she knows, and anything else she doesn't know:
$$\exists x (Knows(Anna,x) \land \forall y (y \not = x \to \neg Knows(Anna, y)))$$
Note that the last two are equivalent, since the difference is a simple contraposition between $Knows(Anna, y) \to y = x$ and $y \not = x \to \neg Knows(Anna, y)$
And to see that the first one is equivalent as well:
$$\exists x (Knows(Anna,x) \land \neg \exists y (y \not = x \land Knows(Anna, y))) \Leftrightarrow \text{ (Quantifier Negation)}$$
$$\exists x (Knows(Anna,x) \land \forall y \neg (y \not = x \land Knows(Anna, y))) \Leftrightarrow \text{ (DeMorgan)}$$
$$\exists x (Knows(Anna,x) \land \forall y (\neg y \not = x \lor \neg Knows(Anna, y))) \Leftrightarrow \text{ (Implication)}$$
$$\exists x (Knows(Anna,x) \land \forall y (y \not = x \to \neg Knows(Anna, y)))$$
You also asked about:
$$\forall x \exists y (x = y), \exists x \neg P(x) \vdash \neg \forall x \neg P(x)$$
Well, that is actually not provable at all! If you think about it, $\forall x \exists y (x = y)$ is a tautology (since for $y$ we can always pick $x$), so that doesn't add any information or constraints, and just because there is something that does not have property $P$ does not mean that there is something that has property $P$ (which is what the purported conclusion says, since $\neg \forall x \neg P(x) \Leftrightarrow \exists x P(x)$.
Indeed, the counterexample is easy: simply choose a (non-empty, but classical logic typically assumes that) domain where nothing has property $P$: then $\forall x \exists y (x = y)$ is true (of course, it is a tautology!), $\exists x \neg P(x) $ is true, but $\neg \forall x \neg P(x)$ is false, since domain $\neg \forall x \neg P(x)$ is true.