3
$\begingroup$

There is a problem I have that says to translate the sentence into logic "None of my friends are perfect." where $F(x)$ is my friends and $P(x)$ is them being perfect. I initially wanted to choose $\neg\forall x(F(x)\wedge P(x))$ but my mind is telling me to choose $\exists x(F(x)\wedge\neg P(x))$. All I want to know is what is the inverse of $\forall$ to help me choose the right answer.

$\endgroup$
3
  • 2
    $\begingroup$ If it is false that for all $x$ $P(x)$ is true, then there exists at least one element $x$ such that $P(x)$ is false, hence the negation of "for all" is "there exists" $\endgroup$
    – en3trix
    Jul 29 at 19:29
  • $\begingroup$ $\forall x (F(x) \land P(x))$ means "Everyone/everything is my friend, and everyone/everything is perfect". $\lnot\forall x (F(x) \land P(x))$ means "Not everyone/thing is my perfect friend". It could be that some people are your friends, that some of these friends even could be perfect. $\endgroup$ Jul 29 at 19:29
  • 2
    $\begingroup$ Try rewriting as: "there does not exist a friend of mine who is perfect". Note also that if I have no friends at all, it is vacuously true that all my friends are perfect (which does not imply the existence of a friend) and also that none of my friends are perfect (because I don't have any friends to be perfect). If you are not careful with the existence quantifier you can accidentally exclude cases involving the empty set. $\endgroup$ Jul 29 at 19:37
11
$\begingroup$

Neither of the sentences you've written does the job.

First of all, "$\forall x(F(x)\wedge P(x))$" is absurdly strong: forgetting the $P$-part it implies that everyone is your friend, which is probably not true. Consequently the expression $$\neg\forall x(F(x)\wedge P(x))$$ which you've written is absurdly weak - it's automatically true as soon as there is someone who isn't your friend, regardless of the perfectness of your friends.

Your second example $$\exists x(F(x)\wedge\neg P(x))$$ is similarly flawed, although less so: it says that you have some non-perfect friend, but "(at least) one of my friends isn't perfect" is much weaker than "none of my friends are perfect."

To express "none of my friends are perfect" you want to say that there does not exist someone who is a perfect friend of yours:

$\neg \exists x(F(x)\wedge P(x))$.

Alternatively, you could say that everyone who is your friend is not perfect:

$\forall x(F(x)\rightarrow \neg P(x))$.


As a coda, let me mention two points to take away from the above.

First, and this gets to your last sentence, there's a duality between "none" and "some". Put another way, "$\forall x\neg$" is the opposite of "$\exists x$" - or if you prefer, "$\exists x\neg$" is the opposite of "$\forall x$."

Second, bounded quantification is a bit weird: "some $A$ is $B$" is "$\exists x(A(x)\wedge B(x))$," but "all $A$ are $B$" is "$\forall x(A(x)\rightarrow B(x))$." See e.g. here for more on this latter point, which is a common source of confusion early on.

$\endgroup$
3
  • 4
    $\begingroup$ +1 Particularly like the way in which you describe the strength of the various statements in relation to what is intended - that helps to build useful intuition: and have also just seen the additional remarks. [There is a tendency on the site to assume that abstract formulations which contain the mathematical content form an adequate answer to a real question posed by a real person - I tend to err on what has become the "wrong" side - I think this answer achieves an excellent balance.] $\endgroup$ Jul 29 at 20:03
  • $\begingroup$ It might be easier to see the duality between the two solutions remembering $F(x)\to\neg P(x)$ is the same as $\neg F(x)\vee \neg P(x)$, which is the same as $\neg(F(x)\wedge P(x))$, so the inside of the forall is the negation of the foreach. $\endgroup$ Jul 30 at 3:38
  • $\begingroup$ Out of curiosity, why the downvote? $\endgroup$ Jul 30 at 17:37
0
$\begingroup$

One tool that will help you translate from natural language into formal logic is a bounded quantifier.

$\forall x \in S \mathop. P(x)$ asserts that, for all x satisfying $S(x)$, $P$ holds.

The idea is that you specify an explicit domain for the quantifier, rather than letting it range over everything in the universe.

All of my friends are prefect would then be:

$$ \forall x \in F \mathop. P(x) $$

I have at least one perfect friend would then be:

$$ \exists x \in F \mathop. P(x) $$

Bounded quantifiers, however, are not part of the core notation of first-order logic, so we have to define them in terms of what we do have, the unbounded quantifiers.

I have at least one perfect friend is equivalent to

$$ \exists x \mathop. F(x) \land P(x) $$

Translating the above back into natural langauge we get at least one entity is my friend and is perfect, which has the same meaning.

All of my friends are perfect is equivalent to the following:

$$ \forall x \mathop. F(x) \to P(x) $$

This is equivalent to for every entity it is the case that that entity is not my friend or that entity is perfect. This has the same meaning as all my friends are perfect. The body of the statement is vacuously true for all the entities out there that aren't my friends.

Let's translate none of my friends are perfect step by step.

Let's start with a slightly informal bounded quantifier.

$$ \not\exists x \in F \mathop. P(x) $$

Replace $\not\exists$ with negation.

$$ \lnot (\exists x \in F \mathop. P(x)) $$

Bounded quantifiers satisfy the same duality property that unbounded quantifiers do.

$$ \forall x \in F \mathop. \lnot P(x) $$

Remove the bounded quantifier.

$$ \forall x \mathop. F(x) \to \lnot P(x) $$

We can also rewrite the body as follows.

$$ \forall x \mathop. \lnot (F(x) \land P(x)) $$

This is equivalent to for all entities, it is not the case that that entity is both perfect and my friend, which has the same meaning as none of my friends are perfect.

$\endgroup$

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.