2

How do I interpret these claims in order to translate them into plain English. They seem a bit ambiguous in their meaning to me.

$$1) \quad \forall x\in\mathbb{N}: \exists y\in\mathbb{N}: (x+y=0)$$

$$2) \quad \forall x\in\mathbb{Z}: \exists y\in\mathbb{Z}: (x+y=0)$$

$$3) \quad \exists y\in\mathbb{N}: \forall x\in\mathbb{N}: (x+y=0)$$

$$4) \quad \exists y\in\mathbb{Q}: \forall x\in\mathbb{Q}: (x+y=0)$$

My interpretation of these claims is that the first means "For all $x$ that are natural numbers, there exists a $y$ in the set of natural numbers such that $x+y=0$.

However, this is where I stop understanding the meaning of this expression. Does this mean that there is one $y$ for all existing $x$'s that makes $x+y=0$? Or is it trying to say that There is a specific $y$ for all $x$ which makes $x+y=0$?

So basically is it saying that $y$ is a master key? Or is it saying that there is a specific key ($y$) for each $x$?

I hope my question makes sense.

Michael Angelo
  • 1,087
Cherry_Developer
  • 4,239
  • 1
    As @AndréNicolas indicates, your first "interpretation of these claims" anyway 1) and 2), is correct: for each $x$, there is a $y$ (choice of $y$ depending on $x$), such that $x+y=0$. Your "However, ..." paragraph is going off the rails: no, not that, forget about it, with respect to 1) and 2). BUT, 3) and 4) do make such claims: they say, there is some "master" $y$ which is the additive inverse of every $x$. This is a much stronger claim, which of course is false. In general, $\exists y \forall x$ is a stronger assertion than $\forall x\exists y$ (stronger: less likely to be true) – BrianO Oct 31 '15 at 07:42

3 Answers3

8

The symbolic expressions are there precisely to make those distinctions unambiguous. It is good that you have noticed the possibility of ambiguity, because then you're more than halfway to learning how the notation resolves that ambiguity.

It may help a bit to write down the claim with more parentheses: $$ \forall x\in\mathbb N \Big( \exists y\in\mathbb N (x+y=0)\Big)$$ This extra set of brackets doesn't change the meaning; it is how chained quantifiers are always interpreted. Then we can unravel the quantifiers one my one.

For every natural number $x$ it is true that $$ \exists y \in\mathbb N (x+y=0) $$

The symbolic formula $\exists y\in\mathbb N(x+y)=0$ contains the variable $x$ but does not bind that variable -- so it is an open formula that denotes a property that some specific $x$ can have or not have. Namely, the property "you can add something to it to make it zero".

In other words, the formula $\exists y\in\mathbb N(x+y=0)$ only becomes true or false when we select a value for $x$. Once we do so, it turns into one of $$ \exists y\in\mathbb N(0+y=0) \\ \exists y\in\mathbb N(1+y=0) \\ \exists y\in\mathbb N(2+y=0) \\ \cdots $$ And the truth values of each of those doesn't care about how we produced it. Each of them can be evaluated by itself, and the $\exists y$ in one of them is independent of the fact that there's another $\exists y$ somewhere else on the paper.

Here we see that $\exists y\in\mathbb N(0+y=0)$ is true (we can take $y=0$), but the other formulas are false (there is no $y\in\mathbb N$ that becomes 0 when you add 1 or 2).

Now we can go back to the $\forall x$. It asserted that all of the different $\exists y$ formulas are true, which is not the case, and therefore the entire $\forall x\exists y\ldots$ formula is false.

What this all works out to when the dust settles is that

  • When a $\exists$ appears to the right of $\forall$, the $\exists$-bound variable is allowed to depend on the $\forall$-bound variable.
  • When the $\exists$ appears to the left of $\forall$, there must be a single value for the $\exists$-bound variable that works for all choices of $\forall$.

Typically you would just be asked to memorize these two shortcut rules. But I think it is easier to know how the rules arise -- namely by putting in the parentheses and treating one quantifier at a time.

hmakholm left over Monica
  • 286,031
  • I'm trying to understand, but at a certain point you lost me... So, if I take the expression $\quad \forall x\in\mathbb{N}: \exists y\in\mathbb{N}: (x+y=0)$, this asserts that for every $x$, there are several $y$'s that make this expression hold? Or does it assert that for every $x$, there is one, unique $y$ that makes this expression hold? – Cherry_Developer Oct 31 '15 at 08:05
  • 1
    @Cherry_Developer: It asserts that for every $x$ there is at least one $y$ that makes $x+y=0$ hold for that particular $x$. – hmakholm left over Monica Oct 31 '15 at 08:09
  • 3
    @Cherry_Developer: Another way to think of it is a game: Your opponent starts by revealing a $x$ -- if you can then play an $y$ such that $x+y=0$, you win that round of the game. It doesn't matter whether there are more than one $y$ you can play, as long as there is one. The entire $\forall\exists$ formula is then true if you have a winning strategy that the opponent cannot beat by choosing his $x$ cleverly. On the other hand, in an $\exists y\forall x$ game, you start by writing down an $y$, and your opponent then chooses and $x$ and you win the round if $x+y=0$ turns out to be true. – hmakholm left over Monica Oct 31 '15 at 08:14
  • So, the first claim two claims I originally posted are then true? – Cherry_Developer Oct 31 '15 at 08:21
  • 1
    @Cherry_Developer: No, the first claim is false: When $x=1$ there is no $y\in\mathbb N$ such that $x+y=0$. But the claim asserts that such an $y$ can be found no matter what $x$ is, which is not the case. – hmakholm left over Monica Oct 31 '15 at 08:26
  • Ok. That's a mistake on my part for being too hasty and not paying attention to details. I just want to clarify these meanings with you one last time in layman terms so that I know that I have it down.

    So, $\quad \forall x\in\mathbb{N}: \exists y\in\mathbb{N}: (x+y=0)$ basically means that given any $x$ in the natural numbers, there is a $y$ in the natural numbers that will make the expression (is it called the predicate?) hold. So if you give me some random $x$ in the natural numbers, I will be able to give you a $y$ that makes the expression hold.

     – Cherry_Developer Oct 31 '15 at 08:31
  • On the other hand, $\quad \exists y\in\mathbb{N}: \forall x\in\mathbb{N}: (x+y=0)$ means that given one specific $y$, and every $x$ in the natural numbers, the expression will hold. (Which is impossible). – Cherry_Developer Oct 31 '15 at 08:33
  • 1
    @Cherry_Developer: Yes, that sounds right. – hmakholm left over Monica Oct 31 '15 at 09:35
4

It means that for any $x$ (in the set), there is at least one $y$ (in the set) such that $x+y=0$.

Informally, given an $x$ in the set, we can find a suitable $y=y(x)$ in the set, such that the relation holds.

"The" $y$ is specific to $x$, in the sense that different $x$ may require different $y$. When we assert $\forall x\exists yP(x,y)$, we are not claiming that given $x$ there is a unique $y$ (dependent on $x$) such that $P(x,y)$ holds. There may be several.

Contrast this with the very different sentence $\exists y\forall xP(x,y)$. This means that there is a $y$ that works uniformly for every $x$, what you called a master key.

André Nicolas
  • 507,029
1

Let $P(x, y)$ be some sentence involving variables $x$ and $y$.

Then $\forall x\ \exists y\ P(x, y)$ means that for any $x$, there is at least one $y$ such that $P(x, y)$ is true. The $y$ is allowed to be different for each $x$. For example:

$$(\forall x\in\text{Humanity}\ \exists y\in\text{Humanity})\ \text{$y$ is $x$'s father}$$

Notice that $y$ is not the same for all $x$. If we wanted to say there was one $y$ that worked for everyone, we would say:

$$\exists y\ \forall x\ P(x, y)$$

Jack M
  • 27,819
  • 7
  • 63
  • 129