Predicate logic: “Everybody knows somebody who knows Alice”

I'm stuck on an undergraduate CS exercise: I am to translate "Everybody knows somebody who knows Alice" into predicate logic.

I'm having trouble bending my head around it (being a complete beginner), but this is what I'm thinking:

$x,y \in$ "the set of all people"
$A(y) = y$ knows Alice

$\forall x \exists !y A(y)$

However, this feels too cumbersome (if it's even valid), and I'm sure there must be a better, simpler way of doing it. Can anybody offer any suggestions?

• You need a binary predicate symbol $K(x,y)$, to be read "$x$ knows $y$." – André Nicolas Nov 17 '13 at 21:13

You need a binary predicate (two-place), let's say, $K(x, y)\,$ to denote "$\;x\,$ knows $\,y$", and then we can simply use the constant $\,a\,$ to denote Alice.

You used the uniqueness quantifier $\exists!$, which is not appropriate here.

What we want is to say "For all $x$, there is some $y$ such that $x$ knows $y$, and $y$ knows Alice."

$$\forall x \,\exists y\,\Big(K(x, y) \land K(y, a)\Big)$$

• I didn't realise I could do it that way! Thanks a lot! Out of interest, why is the uniqueness identifier inappropriate? Is it because "somebody" could mean more than one person? – Jacob Nov 17 '13 at 21:18
• You're welcome, Jacob! – Namaste Nov 17 '13 at 21:24
• @Jacob : Yes, somebody means "any number greater or equal than 1". – Fezvez Nov 17 '13 at 22:44
• @Jacob Yes, "exists someone" means "there is at least one person". If the problem made explicit that there is one and only one person that x knows, or stated "Everyone knows exactly one person that knows Alice"...then we would need the uniqueness quantifier. – Namaste Nov 17 '13 at 22:48
• @amWhy: Right up your alley! +1 – Amzoti Nov 18 '13 at 0:09

You need a two-place predicate $K(x,y)$ that means ‘$x$ knows $y$’. You want

$$\forall x\,\exists y\Big(K(x,y)\land\text{something}\Big)\;,$$

where I’ve left $\text{something}$ for you to fill in. So far it just says that each person $x$ knows someone ($y$). You’ll need a constant, $\text{Alice}$, as well as the predicate $K$.

• Thanks! I've accepted @amWhy's answer because it's more complete, but I do appreciate you leaving something to work out. – Jacob Nov 17 '13 at 21:24
• @Jacob: You’re welcome. – Brian M. Scott Nov 17 '13 at 21:28