Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

During a lecture today the prof. posed the question of how we could write "There is exactly one person whom everybody loves." without using the uniqueness quantifier.

The first part we wrote as a logical expression was "There is one person whom everybody loves.", ignoring the 'exactly one' part of the question initially. From this he wrote

$L(x,y): x$ loves $y$; domain for $x$ and $y$: $\{\text{people}\}$

$\exists x\forall y: L(y,x)$

Which I understand to mean 'There is a person $x$ such that for all $y$, $x$ is loved by $y$' AKA 'There is a person who is loved by everyone'. I get that part.

The part I don't get is how the expression of 'exactly one'.

$\forall z(\forall y(L(y,z))\to x =z)$

which then creates the joint expression

$\exists x\forall y(L(y,x))\land \forall z(\forall y(L(y,z))\to x=z)$

I just can't seem to understand how $\forall z(\forall y(L(y,z))\to x =z)$ means exactly one here. I suppose you can take $\forall z$ here to mean 'for any given person', which means the $\forall z$ is considering every person in the world. This would translate the second expression block to something like, "For any given person $z$, if everybody loves $z$ then $z$ is the same person as $x$".

To me though $\forall z$ generally means for every element in the domain which I see as meaning every person in the world simultaneously, as it seems to for $y$. Is that just plain wrong? How can I tell when $\forall$ means 'all' and when it means 'for any (one)'? In the previous English translation the only reason I was able to translate it (if it's even right) is because I already knew what the statement was suppose to mean.

Is it just that $\forall z$ means that this statement could be true for any element, and if so what's the difference between $\forall z$ and $\exists z$? Someone told me that $\exists z$ would be redundant because the expression says $x=z$ but how do I know that $x$ and $z$ are automatically the same person if $\exists$ is used for both?

Sorry if this is a bit long with too many questions. I just wanted to try to make the cause of my confusion as clear as possible so you can help me figure this out.

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

Is it just that $\forall z$ means that this statement could be true for any element,

Yes, exactly.

...and if so what's the difference between $\forall z$ and $\exists z$?

If we only asserted the existence of some particular $z$ such that if $y$ loves $z$, then that particular person $z$ would thus be $x$. But then we are not ruling out that there might be another person, different from $x$, that is also loved by everyone. And we have already asserted the existence of someone (namely, x) who is loved by all. So in that sense, $\exists z$ such that... is reduntant.

We need the universal quantifier for $z$ (to assert a statement $\forall z$) in the second clause to indicate that if there is any $z$ (which means that the claim that follows - as it relates to $z$, is true for every z) $z$ such that $L(y, z)$, then any/every such $z$ must be $x$, since there is exactly one person, namely $x$, who is loved by all $y$. I.e., for every $z,$ if every y loves z, then z must be x: i.e., that $z$ is not anyone other than $x$. This gives us that $x$ (whose existence we asserted at the start) is therefore the one unique person loved by all.


Now, just one oversight to "clean up" your expression, which you state as:

$$∃x(\forall y L(y,x))\land ∀z(∀y(L(y,z))⟹x=z)$$

But here we have two independent clauses that creates a problem, because in your second clause, you have $x$ appear outside the scope of its quantifier. I.e., it is a free, unquantified varible.

So we want the scope of $\exists x$ to persist over the entire statement, hence the square brackets below.

That is, $$\exists x \big[\forall y(L(yx))\land \forall z(\forall y(L(y, z) \rightarrow z = x)\big]$$


share|improve this answer
1  
This simplification, eliminating the second $\forall y$, doesn't work. Since $\forall y$ distributes over conjunctions, the simplified formula says that there is an $x$ with two properties: First, everybody loves $x$ (so far, so good). Second, for every $y$ and $z$, if $y$ loves $z$ then $x=z$. So the second clause not only prevents any $z$ other than $x$ from being universally loved (as $x$ is) but prevents any $z$ other than $x$ from being loved at all. –  Andreas Blass May 17 '13 at 15:52
    
On the other hand, I agree that the formula in the question needs to be rewritten so that the scope of the quantifier $\exists x$ extends to the final $x=z$. –  Andreas Blass May 17 '13 at 15:54
    
So if I'm getting this right then ∃x∀y(L(y,x))⋀$\exists z$(∀y(L(y,z))⟹x=z) means 'There is a person who is loved by everyone $\bigwedge$ there is a person z(at least 1 person) who, if loved by everyone, is person x. This is redundant because it's not eliminating any more potential people because it's saying that there could be other people who are loved by everyone. If we use the ∀z instead, it means that if you find a person z who is loved by everyone, that person is THE person who is loved by everyone; the only 1. –  BustedZen May 17 '13 at 19:00
    
@BustedZen Exactly!! You're correct. –  amWhy May 17 '13 at 19:06
    
@amWhy: Andreas is right. When you try to clean up the formula, you've incorrectly 'factored' $\forall y$ out of the antecedent of the conditional. It is a "rule of passage" that $((\forall x Fx)\to p)$ is equivalent to $\exists x(Fx\to p)$ when $p$ is free of $x$. In other words, you can factor out a universal quantifier from the antecedent of a conditional to get an existential quantifier over the whole conditional (provided the consequent is free of the variable being quantified over) -- not a universal quantifier, as you think. –  symplectomorphic May 17 '13 at 19:12
show 5 more comments

The idea behind the formula is that, to say exactly one person is loved by everybody, you first say that there is such a person $x$ (this is the part you said you understood), and then you say that there isn't a second such person. That second part is expressed here as saying, if any other $z$ shows up who is also (like $x$) loved by everybody, then this wasn't really another $z$ but just the same $x$.

share|improve this answer
add comment

The simplest definition for $\langle \exists! x :: P(x) \rangle$ I know, which I've probably learned from Dijkstra et al.'s works, is $$\langle \exists y :: \langle \forall x :: P(x) \equiv x = y \rangle \rangle$$ which does only use $P(x)$ once.

Note how we have the following nice symmetry: $$ \begin{array} \\ \langle \exists! x :: P(x) \rangle & \;\equiv\; & \langle \exists y :: \langle \forall x :: P(x) & \equiv & x = y \rangle \rangle \\ \langle \exists\phantom! x :: P(x) \rangle & \;\equiv\; & \langle \exists y :: \langle \forall x :: P(x) & \Leftarrow & x = y \rangle \rangle \\ \langle \phantom\exists! x :: P(x) \rangle & \;\equiv\; & \langle \exists y :: \langle \forall x :: P(x) & \Rightarrow & x = y \rangle \rangle \\ \end{array} $$ where $\langle ! x :: P(x) \rangle$ means "there is at most one $x$ such that $P(x)$".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.