"More than two" in First Order Logic

126 Views Asked by At

I'm trying to express the following statement which has "More than two" in first order logic.

More than two people work at Google

Using the following:

Name: Google

Property: People

Relation: WorksAt

Here's my attempt however, I am unsure of it

$$\exists x \exists y[People(x) \land People(y) \land WorksAt(y,Google) \land WorksAt(x,Google) \land -(x=y)]$$

1

There are 1 best solutions below

0
On

As stated in the comments, your

$$\exists x \exists y[People(x) \land People(y) \land WorksAt(y,Google) \land WorksAt(x,Google) \land \neg(x=y)]$$

expresses that there are at least 2 people working at Google, but you need to express that there are at least 3. You have the right idea though, and it's easy to just add one more person:

$$\exists x \exists y \exists z [People(x) \land People(y) \land People(z) \land WorksAt(y,Google) \land WorksAt(x,Google) \land WorksAt(z,Google) \land \neg(x=y) \land \neg(x=z) \land \neg (y=x)]$$

Notice how you need to repeat all the predicates though, and this becomes a pretty bothersome. Is there a more efficient way to do this? Yes, there is. Consider:

$$\forall x \forall y \exists z (People(z) \land WorksAt(z,Google) \land \neg((z = x) \lor (z=y))$$

This will force for there to be at at least 3 people working at Google, because if there would only be two (or less), then you can cover those with your $x$ and $y$, and you wouldn't be able to pick a $z$ other than those $x$ and $y$ that works at Google. So, since no matter how we pick $x$ and $y$ we always can find such a $z$, we must have at least three people working at Google.

Notice that we could have used this trick as well if the statement really would have asked for 'at least two', for then we could do:

$$\forall x \exists y (People(y) \land WorksAt(y,Google) \land \neg(y = x) )$$

And, in general, we can do 'for at least $n$ objects the formula $\phi(x)$' is true as:

$$\forall x_1 ... \forall x_{n-1} \exists y (\phi(y) \land \neg(y = x_1 \lor ... \lor y = x_{n-1}))$$