Negation and quantifiers

Question

To write the expression: "there does not exist any person such that... " In first-order formula, would we have to use either ∀ or ∃. My question is would you have to negate one of the quantifiers or the variable P? I am also unsure about what the quantifiers mean when negated..

Here variable P stands for person..

I think that it would be (∃(¬P)) or ((¬∃)P) but I am not sure at all..

EDIT: To clarify what I really mean I can come with an example..

The only relevant part of the signature that we need here is the two relations Dog and Cat, they have an arity of 2. What I want to say with a first-order formula in text is "There is no one that is both dog and a cat"

Answer 1

If it says "there does not exist any person such that...", you can directly infer that negation of the existential quantifier is needed, thus

$\neg \exists x (P(x) \land\ ...)$

An equivalent statement would be

$\forall x\neg (P(x) \to\ ...)$

because "There is no $x$ for which it is true that..." is the same as saying "For all $x$ it is not true that...".

---

If you would formalise it as

$\exists x (\neg (P(x) \land \ ...))$

or, equivalently,

$\neg \forall x (P(x) \to \ ...)$

this would mean "There is one $x$ which is not a person and ..." or "Not all $x$ are persons and ...", which is a weaker statement and not what you want to say, because these formulas can be true if one or even most persons are indeed $P(x) \land ...$, as long as there is at least one who doesn't fulfill the requirement.
Instead, you want to say that it applies to none, meaning that you must negate the existence for the positive statement or univerally quantify over the negated statement.

---

Generally, when saying "There is no $x$ for which ...", this will have the form $\neg \exists x (...)$, i.e. the existential quantifier is negated.

In your example, this will reult in

$\neg \exists x (P(x) \land (Dog(x) \land Cat(x)))$          "There is no person which is a dog and a cat"
$\Leftrightarrow \forall x \neg (P(x) \to (Dog(x) \land Cat(x)))$  "For all persons it holds that they are not a dog and a cat"

Answer 2

You have that

$$\lnot(\exists x:P)\iff \nexists x:P\iff\forall x:\lnot P$$

where $P$ is any logically valid statement.

---

Answering to the edit of the question we can say something like

$$\nexists \langle x,y\rangle\in X^2: \langle x,y\rangle\in R \land \langle x,y\rangle\in S$$

what is equivalent to write

$$\forall \langle x,y\rangle\in X^2: \langle x,y\rangle\notin R \lor \langle x,y\rangle\notin S$$

where $R$ and $S$ are relations of arity $2$ on $X$, i.e. $R\subseteq X^2$ and $S\subseteq X^2$, and the symbol $\land$ means "logic AND" and the symbol $\lor$ is the "logical OR".

In the last statement we used the DeMorgan law

$$\lnot(A\land B)\iff (\lnot A) \lor (\lnot B)$$

Answer 3

Still working on this?

Generally speaking, you're going to negate whole sentences, or quantifiers, or predicates; you don't negate your variables. Think about how you would translate that back into English: "There is a not-thing, such that ..."

You can usually read the negation of a whole sentence as "It is not the case that ..."

So $\neg \exists x(Fx)$ can be read "It is not the case that there is some $x$ that is $F$." Since there's only the one quantifier here, you can also read it "There is no $x$ that is $F$."

If you negate a predicate rather than a quantifier or a whole sentence, you're doing something different: $\exists x(\neg Fx)$ is "There is some $x$ that is not $F$." Whole different deal.

It's worth noticing that $\neg\exists$ can be expressed otherwise using $\forall$, which you should be learning right about now. There's a whole little musical chairs $\exists$ and $\forall$ and $\neg$ play that you'll want to get really comfortable with.