# Determining the negation of a logical statement?

I'm currently working on some first order logic questions as a brush up for a discrete mathematics course and I'm having a bit of trouble remembering exactly how to find the negation of a logical statment. Precisely, how do I rewrite certain statements as the negated versions of themselves? I've had luck with a couple but right now I'm stumped on the following:

At the moment I'm working on an assignment for a discrete mathematics course and I've run into a question that seems deceptively simple based on how it is asked but I feel like the instructor is asking for more. The question goes as follows:

Give the negation of the statement
∃! x ∈ U [P(x)].


But to negate this statement could I not just put a ¬ in front of the equation and be done? I only ask because on this assignment most questions are worth 4-6 marks and this particular question is worth 10 so I feel like there must be more to it. Any help is greatly appreciated.

• You are very likely asked to provide a more detailed version of the answer. So in this case, you want the negation of "there exists a unique $x$ in $U$ such that P(x)". To negate this you can think about what would make this statement fail, i.e., either there is no such $x$ in $U$ of there are actually multiple distinct elements of $U$ that verify it. So you would need to write that in a formal way. – Alexandre548 Jan 13 '15 at 17:11
• We have already discussed it here; if it is not enough to put $\lnot$ in front, you have to "unwind" it and then negate it. As per previous comment, $∃!x∈U[P(x)]$ is $∃x∈U[P(x)∧∀y∈U(P(y) \to y=x)]$; to negate it, you have to move from $\lnot \exists$ to $\forall \lnot$ and then "move in" the negation sign with De Morgan and so on ... – Mauro ALLEGRANZA Jan 13 '15 at 17:13

## 1 Answer

In a trivial sense, yes you could just stick a $\neg$ at the beginning, but, similarly to saying that the solutions to $x^5+x^4+2x^2+3 = 0$ are those $x$ for which it is true, you probably aren't going to get any points.

So, the statement says, "there is a unique element of $U$ with property $P$". There are two ways in which this is false, either no element of $U$ has the property, or more than one does. We can express the first as $$\forall x (x \in U \rightarrow (\neg P(X)))$$ and of course there are many other ways, and the second can be parsed as $$\exists x \exists y (x\in U \land y \in U \land x \neq y \land P(x) \land P(y))$$ so, one form of the statement we want is $$(\forall x (x \in U \rightarrow (\neg P(X)))) \lor (\exists x \exists y (x\in U \land y \in U \land x \neq y \land P(x) \land P(y))).$$

• You can "shorten" it as : $\forall x[P(x) \rightarrow \exists y (P(y) \land y \ne x)]$ avoiding all the cumbersome $\in U$ that add nothing to the meaning of the formula. – Mauro ALLEGRANZA Jan 13 '15 at 17:20
• @MauroALLEGRANZA Oh certainly, I just thought that this way was more pedagogically sound. – James Jan 13 '15 at 17:21