3

Here I have the following definition of $\exists ! (x,y) P(x,y)$:

$$\exists x \exists y[P(x,y) \land \lnot \exists u \exists v (P (u,v) \land (u \neq x \lor v \neq y))]$$

Are that formula equivalent to $\exists ! x \exists ! yP(x,y)$ ?

I'm using that $\exists ! xP(x)$ is equivalent to:

$$\exists x (P(x) \land \lnot \exists u (P(u) \land u \neq x)$$

I could not prove them equivalent, but don't know how to prove that it's not equivalent.

49328481
  • 109

4 Answers4

12

Nope, they are not equivalent.

Consider $x,y\in\{0,1\}$ and the condition $xy=0$. Then

  • $\exists! (x,y):xy=0$ is false (there are three such points),

  • $\exists! x:\exists! y:xy=0$ is true (for $x=0$, there are two points such that the condition holds, and for $x=1$, only one, so a single $x$ fits).

7

Let $P(x,y)$ be defined by $y^2 = x$.

Then $\exists!(x,y)P(x,y)$ is false, since there are infinitely many pairs $(x,y)$ that solve the equation.

However, $\exists!x(\exists!yP(x,y))$ is true, since if and only if $x=0$, there is only one $y$ that solves the equation ($y=0$ obviously).

molarmass
  • 2,014
  • 13
  • 16
4

"There is exactly one pair of people $x$ and $y$ at this party such that $x$ is friends with $y$.

is not the same as

"There is exactly one person $x$ at this party such that there is exactly one person $y$ at this party such that $x$ is friends with $y$.

At the first party, $x$ is the only person with a friend. At the second party, poor $x$ only has one friend, but everybody else is free to have lots of friends (or no friends).

For this "real life" example to work, the "friends with" relation must not be symmetric. But I think that's not too unrealistic.

Alex Kruckman
  • 76,357
  • Ah, your explanation/example is so much clearer than mine! – Barry Cipra Feb 11 '21 at 15:07
  • It's maybe even more obvious with this situation: a club of single people and $P$ is married relation. First proposition is that nobody is married, which is trivially true. In the second one we consider that given a person $x$ no $y$ is married to him/her. This is true for all $x$ making the proposition false. In fact $\exists !(x,y)$ is closer to $\forall x\exists !y$ than to $\exists !x\exists !y$. – zwim Feb 11 '21 at 15:42
2

They are different. $\exists!x\exists!y$ allows for the possibility that $P(x,y)$ is true for all $x$ and $y$ except for one particular value of $x$, for which it's $P(x,y)$ is true for one particular value of $y$ but false for all other values.

Added later: As an example, picture a set of keys (on a keyring, say) and a set of doors (along a hallway, say). The proposition $P(x,y)$ says that key $x$ unlocks door $y$. The statement $\exists!(x,y)P(x,y)$ then says that there's one key that unlocks one (and only one) door while the rest of the keys are useless (i.e., don't unlock any of the doors). The statement $\exists!x\exists!yP(x,y)$, on the other hand, says that there's one key that unlocks one (and only one) door while the other keys are either useless or unlock multiple doors.

Barry Cipra
  • 79,832