Use predicates and quantifiers to express this statement.

1.7k Views Asked by At

“Some students in this class grew up in the same town as exactly one other student in this class."

I'm thinking there is a relation T(x,y) where the student x grew up the same town as student y. And "some student" would imply ∃x. But my conclusion of ∃x(T(x,y)) seems too easy. Would there be a variable for the town? For specifying "exactly one student"? Thanks ahead.

1

There are 1 best solutions below

0
On BEST ANSWER

You're on the right track, but we need to tighten our conditions.

Let $T(x,y)$ represent "$x$ grew up in the same town as $y$."

We're discussing two students, so we have $\exists x \exists y(T(x,y))$. However, we need to make sure person $x$ is not the same person as $y$, since every person grows up in the same town as themselves. So, we have $\exists x \exists y (T(x,y) \land x\not=y)$. Now we want for there to be exactly one $y$. This involves the uniqueness quantifier, so we can just write $\exists x \exists! y (T(x,y) \land x\not=y)$ and be done with it. However, we can rewrite this using the reduction formulas in the link. So, one possible answer is: $$\exists x \exists y [T(x,y) \land (x\not=y) \land \forall z(T(x,z)\rightarrow (z=y)].$$

This says that there are distinct persons $x$ and $y$ such that $x$ lives in the same town as $y$; AND if $x$ happens to live in the same town as any person $z$, then $z$ in fact, better be the same person as $y$.