Logic: Problem 3b

Solution for straightforward answer to (a)

We start by putting the negation on the outside of the whole expression: $$\neg (\ (\exists x \in A,\ P(x)) \ \text{ and } \ (\neg \exists y,z \in A, \ P(y)\ \wedge P(z)\ \wedge\ y \not = z )\ )$$

We then push the negation into the top-level operation, which is the "and." $$(\forall x \in A,\ \neg P(x)) \ \text{ or } \ \neg(\neg \exists y,z \in A, \ P(y)\ \wedge P(z)\ \wedge\ y \not = z )$$

There's nothing more to do to the first half of the statement. For the second half of the statement, we just cancel the negations, to get $$(\forall x \in A,\ \neg P(x)) \ \text{ or } \ (\exists y,z \in A, \ P(y)\ \wedge P(z)\ \wedge\ y \not = z )$$

That is, when unique existence doesn't hold, there's two possibilities. It could be that no value makes P() true. Or it could be that (at least) two distinct values make P() true.

Solution for hardcore answer to (a)

We start by putting the negation on the outside of the whole expression: $$\neg\ ( \ \exists x \in A, \ P(x)\ \text{ and } \ ( \forall y \in A,\ P(y) \rightarrow x = y )\ )$$

Then push the negation into the top-level operator, which is the first quantifier (since it has scope over the entire rest of the statement) $$\forall x \in A,\ \neg( \ P(x)\ \text{ and } \ ( \forall y \in A,\ P(y) \rightarrow x = y )\ )$$

Now we need to push the negation into the new top-level operator, the "and." $$\forall x \in A,\ \neg P(x)\ \text{ or } \ \neg (\forall y \in A,\ P(y) \rightarrow x = y )$$

Now we deal with the second quantifier: $$\forall x \in A,\ \neg P(x)\ \text{ or } \ (\exists y \in A,\ \neg (P(y) \rightarrow x = y) )$$

And finally we need to negate the if/then statement: $$\forall x \in A,\ \neg P(x)\ \text{ or } \ (\exists y \in A,\ P(y) \wedge x \not = y) $$

This is equivalent to the negation for the straightforward answer (above), but you may reasonably feel this isn't obvious. Also, this version is less helpful to the reader, in terms of understanding what happens when unique existence fails.