How to take more than two in logical quantifiers

823 Views Asked by At

Let the universe of discourse be all humans. Let $F(x,y)$ denote $x$ is a friend of $y$.

Stating the following logically: No one has more than two friends.

$$ \neg ( \exists x \exists y \exists z((Fx \land Fx) \land (Fy \land Fy)) \land (Fz \land Fz)) \land (x \neq y) \land (y \neq z) \land (x \neq z))$$

Is the above statement I derived correct? I used some other answer to mash this one up, could you explain each part of this statement if correct please?

2

There are 2 best solutions below

2
On BEST ANSWER

Your expression clearly cannot be right, because the relation $F$ takes two arguments, and in your expression you’ve given it only one. Let’s start over from scratch. First we write a logical expression $\varphi(x)$ that says ‘$x$ has more than two friends’; once we have that, the desired sentence will be $\forall x\big(\neg\varphi(x)\big)$ or, equivalently, $\neg\exists x\big(\varphi(x)\big)$.

To say that $x$ has more than two friends is to say that $x$ has at least three friends; that means that there are $y_1,y_2$, and $y_3$ such that $x$ is a friend of each of them, and no two of them are the same person. It’s easy to say that $x$ is a friend of $y_1$: that’s just $F(x,y_1)$. To say that $x$ is a friend of each of the three is therefore

$$F(x,y_1)\land F(x,y_2)\land F(x,y_3)\;.$$

We also have to specify that $y_1,y_2$, and $y_3$ are three different people:

$$y_1\ne y_2\land y_1\ne y_3\land y_2\ne y_3\;.$$

A formula $\varphi(x)$ that says ‘$x$ has more than two friends’ is therefore

$$\exists y_1\exists y_2\exists y_3\Big(F(x,y_1)\land F(x,y_2)\land F(x,y_3)\land y_1\ne y_2\land y_1\ne y_3\land y_2\ne y_3\Big)\;.$$

0
On

I would say it in words, but if you like symbols: $$\forall x,a,b,c \ (F(x,a) \wedge F(x,b) \wedge F(x,c)) \implies (a = b \vee a = c \vee b = c)$$ or, perhaps more readable: $$\forall x \ |\{y : F(x,y)\}| \le 2$$