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.

  • $\begingroup$ 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. $\endgroup$ – Alexandre548 Jan 13 '15 at 17:11
  • 1
    $\begingroup$ 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 ... $\endgroup$ – Mauro ALLEGRANZA Jan 13 '15 at 17:13

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))). $$

  • 1
    $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Jan 13 '15 at 17:20
  • 2
    $\begingroup$ @MauroALLEGRANZA Oh certainly, I just thought that this way was more pedagogically sound. $\endgroup$ – James Jan 13 '15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.