How to iterate through all the possibilities in with this quantifier?

389 Views Asked by At

This is a problem from Discrete Mathematics and its Applications enter image description here

My question is on 9g. Here is my work so far enter image description here

I am struggling with the exactly one person part. The one person whom everybody loves is pretty straight forward ( ∃ x∀y(L(y,x)). I am trying to apply the method that Alan gave in How to express exact quantifier in this situation? from my other question. From what I have, if I know that x is a possibility(one, exists), I have to iterate over all the rest of the domain to ensure that there are no other possibilities(check against x) That's what I tried doing with the conjunction. However, this doesn't work because in my diagram, A is the exact one person whom everybody loves. I also showed that C loves C. Once q and w take up C and C (go through all the values in the domain) w, which is C, is not A, which means the whole expression is false because the implication is false but the expression shouldn't be false(A is the only one in the diagram whom everybody loves. C loving C should not have an effect) Is there any way else I can restructure the nested quantifier so i can still iterate through and see if there are any others that everybody loves?

2

There are 2 best solutions below

2
On BEST ANSWER

The statement $\exists x \Big(P(x) \wedge \forall y \big(P(y)\to y=x\big)\Big)$ is the assertion of uniqueness.

"There exists a something for which the predicate is true and if the predicate is true for anything it must be that something."

So for "There is exactly one person whom everyone loves" we replace $P(\cdot)$ with $(\forall z\, L(z, \cdot))$

$$\exists x \Big((\forall z\, L(z,x))\wedge \forall y\big((\forall z\, L(z,y))\to y=x\big)\Big)$$

Note: this says "everyone loves a unique person". You may also interpret the statement as "everyone uniquely loves someone", which would be:

$$\forall w \exists x \Big(L(w,x)\wedge \forall y\big(L(w,y)\to y=x\big)\Big)$$


Equivalently:

The statement $\exists x \forall y \big(P(y)\leftrightarrow y=x\big)$ is another assertion of uniqueness.

"There exists a something such that if the predicate is true for anything it must be that something."

So for "There is exactly one person whom everyone loves" we replace $P(\cdot)$ with $(\forall z\, L(z, \cdot))$

$$\exists x \forall y\big((\forall z\, L(z,y))\leftrightarrow y=x\big)$$

Note: this says "everyone loves a unique person". You may also interpret the statement as "everyone uniquely loves someone", which would be:

$$\forall w \exists x \forall y\big(L(w,y)\leftrightarrow y=x\big)$$



Now can you do $(h)$ "there are exactly two people whom Lynn loves"?

13
On

Following the approach in the link, you would write $\forall y L(y,x) \wedge \forall z L(z,w) \implies w=x$