nested quantifiers (exactly one questions)

2.4k Views Asked by At

Express this statement using quantifiers, without using the uniqueness quantifier."There is exactly one student in this class who has taken exactly one mathematics class at this school" T (x, y):means that student x has taken class y and the domain is all students in this class

The correct answer says : ∃x∀z((∃y∀w(T (z, w) ↔ w = y)) ↔ z = x)

My answer is: ∃x∃y,(T(x,y)∧ (∀m,∀n, T(m,n)∧((x=m)∧(y=n))))

What's wrong with my answer?

2

There are 2 best solutions below

2
On BEST ANSWER

One difference is that your answer implies that $\forall m, \forall n, T(m,n)$. That should only be true when $m = x$ and $n = y$.

Does that help?

0
On

First you should know how to convert between "there exists 1 object such that..." and the primitive $\exists,\forall$ quantifiers. Saying that there is exactly $1$ object with property $P$ is the same as saying that there is at least $1$ object with property $P$, and every other object doesn't have that property.

$$\exists_1 x ~ P(x)$$ is the same as

$$\underbrace{\exists x ~ \bigg( P(x)}_{\text{There is an object with the property}} \land \underbrace{\forall y ~ y \ne x \implies \lnot P(y)\bigg)}_{\text{and nothing else has that property}}$$

By contrapositive that is

$$\exists x ~ \bigg( P(x) \land \forall y ~ P(y) \implies y = x \bigg)$$

From here your author is making a (misleading, poor choice for teaching, but not incorrect) transformation to convert that into:

$$\exists x \forall y ~ \bigg( P(x) \iff y = x \bigg)$$

So in summary, the author is using the transform $\exists_1 x ~ P(x) \quad \equiv \quad \exists x \forall y ~ P(x) \iff x = y$.

So work backwards from the solution to see how the author obtained it:

$$\exists x \forall z \left(\begin{array} {c} \bigg(\exists y \forall w ~ T(z, w) \leftrightarrow w = y\bigg) \\ \updownarrow \\ z = x \end{array}\right)$$

Apply the transform to $x$ and $z$:

$$\exists_1 x (\exists y \forall w) ~ T(x, w) \leftrightarrow (w = y)$$

And apply the transform again to $y$ and $w$:

$$\exists_1 x \exists_1 y ~ T(x, y)$$

So the book's solution is "there is exactly 1 student $x$ and exactly 1 student $y$ such that student $x$ is taking $y$ as a class."

The truth is that this problem has no solution given your constraints. If the universe is all students in a class (and not even all students), then how can you talk about all classes? It's not possible. So I suggest that either you badly misread the question, or you need to find someone else to learn logic from.