Predicate logic: "Everybody knows somebody who knows Alice"

Question

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?

Answer 1

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

Answer 2

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