This section in the book is about quantifiers, and in particular nested quantifiers. The idea is to understand the precise meaning of commonly used English phrases, such as "for all" and "there exists". The differences between two statements in written English can sometimes seem subtle, but the mathematical meaning can be drastically different.
This exercise is quite good at teasing out and surfacing these differences.
Exercise A.5.1
What does each of the following statements mean, and which of them are true? Can you find gaming metaphors for each of these statements?
(a) For every positive number $x$ , and every positive number $y$ , we have $y^2 = x$.
(b) There exists a positive number $x$ such that for every positive number $y$, we have $y^2 = x$.
(c) There exists a positive number $x$, and there exists a positive number $y$, such that $y^2 = x$.
(d) For every positive number $y$, there exists a positive number $x$ such that $y^2 = x$.
(e) There exists a positive number $y$ such that for every positive number $x$, we have $y^2 = x$.
Before we dive in, let's remind ourselves of the gaming metaphor. The idea is that we and an opponent are choosing values for variables like $x$ or $y.
- The opponent can choose any value, without constraint. Where possible, the opponent is minded to choose values which disprove the statement. The opponent is playing the role of the universal quantifier, "for all", or $\forall$.
- We can choose a specific value, often trying to meet certain criteria for that variable, with the aim of proving the statement. We are playing the role of an existential quantifier, "there exists", or $\exists$.
For each part of the question we will, (1) write the statement in precise symbolic form, (2) write it in plain English, (3) state whether the statement is true or false, (4) and illustrate it with the game metaphor. I will be following the convention for the symbolic form set out in Keith Devlin's course, which focussed on clarity rather than brevity.
Note: the exercise doesn't state what domain the variables $x$ and $y$ are from, but assuming they are positive real numbers makes sense $x, y \in R^+$.
(a) For every positive number $x$ , and every positive number $y$ , we have $y^2 = x$.
In symbolic form, this is
$$(\forall x \; \forall y)\; [\;y^2 = x\;]$$
In plain English, this says that every possible combination of $x$ and $y$ satisfies $y^2=x$.
The statement is false. A counter-example is $x=1, y=2$, which does not satisfy $y^2=x$. $\square$
In the gaming metaphor, the opponent is choosing both $x$ and $y$ without constraint.
(b) There exists a positive number $x$ such that for every positive number $y$, we have $y^2 = x$.
In symbolic form, this is
$$(\exists x \; \forall y)\; [\;y^2 = x\;]$$
In plain English, if we pick a specific $x$, then for any $y$, the relation $y^2=x$ is satisfied.
The statement is false. If we pick $x=4$, then almost every value of $y$ does not satisfy the relation. Sure, $y=2$ works, but the whole infinitude of other possible values for $y$ fail to satisfy the relation. $\square$
In the gaming metaphor, after we pick a value for x, the opponent can pick a value to ensure the relation $y^2=x$ doesn't hold.
(c) There exists a positive number $x$, and there exists a positive number $y$, such that $y^2 = x$.
In symbolic form, this is
$$(\exists x \; \exists y) \; [\;y^2 = x\;]$$
In plain English, this says there is a specific $x$ and there is a specific $y$, that satisfy the relation $y^2 =x$.
The statement is true. There are (infinitely) many examples, but one is $x=4, y=2$. Another example is $x=9, y=3$. We only need one example to show the statement is true. $\square$
In the gaming metaphore, we can choose specific values for $x$ and $y$ to ensure they satisfy the relation. The opponent is not involved, and therefore can't pick values trying to ruin the relation.
(d) For every positive number $y$, there exists a positive number $x$ such that $y^2 = x$.
In symbolic form, this is
$$(\forall y \; \exists x) \; [\;y^2=x\;]$$
In plain English, this says that for any value of $y$, we can always find an $x$ such that $y^2=x$.
The statement is true. It is in fact saying that every positive natural number has a square. Or more fundamentally, for any $y$, we can always evaluate $y^2$. $\square$
In the gaming metaphor, the opponent can pick any positive number, and our challenge is to find its square, something which is always possible.
(e) There exists a positive number $y$ such that for every positive number $x$, we have $y^2 = x$.
In symbolic form, this is
$$(\exists y \; \forall x) \; [\;y^2 = x\;]$$
In plain English, this says that for any specific value chosen for $y$, then any and every choice of value for $x$ satisfies $y^2=x$.
The statement is false. Consider choosing $y=9$. Here $y^2=81$. This does not equate to every possible choice for $x$, only $x=81$. $\square$
In the gaming metaphor, we first choose a $y$, and our opponent then choose an $x$ that does not satisfy the relation.
Thoughts - Left to Right
Terence Tao is very clear that the plain English phrases need to be read from left to right, and any variables instantiated in that order, left to right.
This is counter to my previous habit of reading such sentences and unconsciously re-ordering them in an attempt to make them make sense. For example, the last example (e) was being read as "for every $x$ there is a $y$.
Another way to think about these is to instantiate the left-most (outer-most) variable and see what the inside means. With example (b), if we instantiate $x=3$ in
$$(\exists x \; \forall y)\; [\;y^2 = x\;]$$
it becomes
$$(\forall y)\; [\;y^2 = 3\;]$$
which is must easier to read and see as false.
No comments:
Post a Comment