Let $L(x,y)$ be the statement, "$x$ loves $y$."

If the universe U is the set of all people,

can the statement, "There is exactly one person whom everybody loves."

or, equivalently (according to my textbook): $∃x[∀y(L(y,x)) ∧ ∀z(∀y(L(y,z) → z=x)]$

be written as (my answer):

[($∃x∀yL(y,x)) ∧ (∀z∃y¬L(y,z))] \mbox∣~ x≠z, z∈U$ ?

The original statement is the answer from my textbook, which I think seems pretty weird. That's why I'm trying to rewrite it.
So, if my answer is not a 'better' way to write "There is exactly one person whom everybody loves.", what is the most logical way to write this statement?

  • $\begingroup$ what is s.t? and what is the set U which you refer to? $\endgroup$ – Daniel Jun 3 '17 at 18:36
  • $\begingroup$ @Daniel: s.t. = "such that", U is the universal set. $\endgroup$ – md2perpe Jun 3 '17 at 18:37
  • $\begingroup$ Make sure that you write the second statement in correct logic notation and that it's clear what belongs together. $\endgroup$ – md2perpe Jun 3 '17 at 18:40
  • 1
    $\begingroup$ No, the vertical bar is used in set construction, not in logic. Also, if everything before $|$ belongs together, then $x$ after $|$ is not bound to anything. $\endgroup$ – md2perpe Jun 3 '17 at 19:23
  • 1
    $\begingroup$ You can use "such that" in text in other contexts than set building, but now we're dealing with logics and then everything should be written in correct logic language. $\endgroup$ – md2perpe Jun 3 '17 at 19:34

The statement from the book $$\exists x [ \forall y L(y,x) \land \forall z ( \forall y L(y,z) \rightarrow z = x ) ]$$

is a good way to express this. To see this you might write the property of a person to be loved by everyone as $$P(x) := \forall y L(y,x)$$

Then the statement becomes $$\exists x [ P(x) \land \forall z ( P(z) \rightarrow z = x ) ]$$

which means that there is a person $x$ with property $P$, and for any person $y$ with property $P$, that person $y$ must already be $x$.

This might further be abbreviated $$\exists! x P(x)$$


I would suggest: ∃x∀yL(y,x) ∧ ∀z((x≠z)→(∃y¬L(y,z)))

sounds right?

  • 1
    $\begingroup$ This is almost the same as the textbook answer that the OP already has -- and does nothing to help with his actual problems with understanding. $\endgroup$ – hmakholm left over Monica Jun 3 '17 at 19:31

$$\color{red}(\exists \color{red}x~\forall y~ Lyx\color{red}) \land (\forall z~\exists y \lnot Lyz) \text{ s.t. } \color{red}x \ne z$$

Look at the red parts. The first $x$ is inside the parenthesis (quantified), the second is outside (unquantified). The second $x$, grammatically, refers to a different variable than the first due to how you wrote it.

(Btw ignore the complaints about s.t., it is well understood and fine to use if done grammatically correctly).

Here are some ways to transform the formula:

$$\exists x~\bigg( (\forall y ~ Lyx) \land (\forall z~\forall y ~Lyz \to z = x)\bigg)$$

First it would appear you'd like to use the contrapositive:

$$\exists x~\bigg( (\forall y ~ Lyx) \land (\forall z~\forall y ~ z \ne x \to \lnot Lyz )\bigg)$$

Since $x \ne z$ doesn't reference $y$, the $\forall y$ can be moved (this is a formula from the prenex technique):

$$\exists x~\bigg( (\forall y ~ Lyx) \land (\forall z~z \ne x \to \forall y ~ \lnot Lyz )\bigg)$$

One thing you can also notice is that you have a formula of the form $\forall a Pa \land \forall b Qb$, which can be written $\forall c Pc \land Qc$ :

$$\exists x~\bigg( (\forall w ~ Lwx) \land (\forall w~w \ne x \to \forall y ~ \lnot Lyw )\bigg)$$

$$\exists x~\bigg( \forall w ~ (Lwx \land (w \ne x \to \forall y ~ \lnot Lyw ))\bigg)$$

There's other manipulations you can do, but more big picture, there are a lot of ways to write "the predicate $P$ is inhabited exactly once". One way attributed to Dijkstra is as $\exists x (\forall y~P(y) \text{ iff } x = y)$, which in your case becomes:

$$\exists x (\forall y~(\forall z ~ Lzy) \text{ iff } y = x)$$

  • 2
    $\begingroup$ I want to upvote this for the nice explanation -- but I can't, because of the assertion that it is fine to mix things like "s.t." or "iff" together with symbolic quantifiers. $\endgroup$ – hmakholm left over Monica Jun 3 '17 at 19:29
  • 1
    $\begingroup$ It is quite common (even in logic) to write things like $\{x \text{ s.t. } P(x)\}$ or $\exists y \text{ s.t. } Qy$. Using s.t. doesn't change the abstract syntax tree represented by the expression, so yes, using "s.t." instead of "$|$" or "$:$" or empty space as well as using $\text{ iff }$ instead of $\iff$ is not only fine, it is good style. Insisting that beginners in logic use things like $\land$ instead of $\text{ and }$ seems to me to be very inconsiderate. $\endgroup$ – DanielV Jun 3 '17 at 19:40
  • $\begingroup$ Given the quoted textbook answer, I think it's safe to assume that the OP is studying a formal language, namely standard first order logic. (If that's not the case, I'd invite the OP to clarify this point.) And the fact is $\wedge$ is a connective in this language while "and" is not. It's like you're saying, "It's inconsiderate to insist that beginners in Spanish use 'y' instead of 'and.'" $\endgroup$ – grndl Jun 3 '17 at 20:08
  • $\begingroup$ The "formal" in formal logic doesn't mean "pedantic notation". It means "characterized to the degree that it could be represented by a program (on whatever computing model)". The divide between formal and informal logic isn't that the author is being mechanical, it is that formal logic demonstrates how things could be done mechanically. Humans are not turing machines, but we use (approximations of) them quite well. $\endgroup$ – DanielV Jun 3 '17 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy