Back to the on-screen lesson ·
For-all and there-exists, what each one asks a proof to do, and why swapping a mixed pair produces a different claim.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write an English claim in quantifiers with its domains named, say which object is chosen first and which may depend on it, and decide which of two orders a definition actually uses. You will also be able to read the first line of a proof off the leftmost quantifier — cope with an arbitrary one, or produce a witness — and say why one order of a mixed pair implies the other and not the reverse.
Propositional logic settled statements that are true or false on their own. '$x > 3$' is neither until you say what $x$ is, and almost every statement in mathematics is of that kind. Quantifiers are what turn an open sentence into a statement, and once they are in place the whole of units 2 to 7 can be written down precisely.
A predicate $P(x)$ is a sentence with a slot in it. $\forall x\, P(x)$ says for every $x$, and $\exists x\, P(x)$ says for at least one $x$. The scope of a quantifier is everything that follows it, and a variable inside a quantifier's scope is bound; one outside every scope is free, and a formula with a free variable is not yet a statement. The set the variable ranges over is the domain, and a claim is only as true as its domain: $\forall x\, (x^2 \ge 0)$ is true over the reals and false over the complex numbers.
$\forall x\, P(x)$ is proved by taking an arbitrary $x$ and arguing about it without using anything special about it; it is refuted by producing one $x$ that fails. $\exists x\, P(x)$ is the mirror image: proved by producing one witness, refuted by an argument covering every $x$. Notice that the work is quite different in the two cases even though the statements look alike, and which kind of work a claim calls for is read straight off the quantifier.
The fact that catches everybody is the mixed pair.
$$\forall x\, \exists y\, R(x, y) \qquad \text{against} \qquad \exists y\, \forall x\, R(x, y)$$
In the first, $y$ is chosen after $x$ and may depend on it — a different $y$ for every $x$ is allowed. In the second, $y$ is fixed before $x$ is even mentioned, so one $y$ has to serve every $x$ at once. The second implies the first; the first does not imply the second.
'Every real number is less than some integer' is true and is $\forall x\, \exists n$. 'Some integer is greater than every real number' is false and is $\exists n\, \forall x$. Same three symbols, reordered, and one of the two is the Archimedean property while the other says the reals are bounded.
The reading that never fails is to treat a formula as a game played left to right. At each $\forall$ an opponent picks; at each $\exists$ you pick, knowing everything picked so far. The statement is true when you have a winning strategy. Written that way, the order is obviously the whole of the difference: it is who moves first.
Another way: steps
To write an English claim in quantifiers:
Another way: picture
Draw a row of boxes, one per choice, left to right. A $\forall$ box is filled by somebody trying to defeat you and a $\exists$ box by you. Moving a box you fill to the front means committing before you have seen their move — always harder, sometimes impossible, and never easier.
| Definition | Shape | What is fixed first |
|---|---|---|
| $f$ is bounded | $\exists M\, \forall x$ | the bound |
| $f$ is injective | $\forall a\, \forall b$ | nothing |
| $f$ is surjective | $\forall y\, \exists x$ | the target |
| $a_n \to L$ | $\forall \varepsilon\, \exists N\, \forall n > N$ | the tolerance |
Two of these begin by letting an opponent choose, so a proof begins 'let $\varepsilon > 0$ be given' or 'let $y$ be arbitrary'. One begins by you choosing, so the proof begins 'take $M = \ldots$'. The first line of a proof is dictated by the leftmost quantifier, which is why reading the shape is worth doing before anything else. It is also why the definition of convergence is hard the first time: it has three quantifiers, and the proof has to alternate between coping and producing three times over.
Leaving the domain out. '$\forall x\, (x^2 \ge 0)$' is not true without saying over what. The domain is part of the statement, and a theorem that omits it is a theorem about nothing in particular.
Swapping a mixed pair while translating. 'Everybody has a mother' and 'somebody is everybody's mother' differ in exactly one transposition.
Proving a for-all by examples. Checking $x = 1, 2, 3$ does not establish $\forall x$. It is evidence for a conjecture and it is not an argument, which is the whole subject of unit 2.
'Let $x$ be arbitrary' does not mean 'let $x$ be some particular number I have not decided'. It means the argument that follows may use nothing about $x$ beyond its membership of the domain. That is what makes the conclusion apply to all of them: not that $x$ was chosen fairly, but that the argument never looked at it. The test is mechanical — read your proof back and check that no line would break if $x$ were replaced throughout by any other element.
'Every positive real has a positive real smaller than it.' Both variables range over the positive reals.
Name the domains first.
The number chosen first is the one we are given, so: $\forall x > 0\, \exists y > 0\, (y < x)$, and $y$ may depend on $x$ — take $y = x/2$.
Given, then produced.
The other order, $\exists y > 0\, \forall x > 0\, (y < x)$, claims a smallest positive real. That is false, and the two sentences differ only in which quantifier is written first.
The swap changes a truth into a falsehood.
'The set $S$ is unbounded above' means: no number bounds it. Writing that positively, every candidate bound is beaten.
Turn the negative into a sweep.
$\forall B\, \exists x \in S\, (x > B)$ — the opponent names a bound and we produce an element above it, and we may produce a different element for each bound.
For-all first, so we cope; exists second, so we produce.
So a proof of unboundedness starts 'let $B$ be any real number' and ends by exhibiting an element. The shape has told us both lines before we know anything about $S$.
The shape writes the skeleton of the proof.
Statement A: $\forall x \in \mathbb{R}\, \exists n \in \mathbb{N}\, (n > x)$. Statement B: $\exists n \in \mathbb{N}\, \forall x \in \mathbb{R}\, (n > x)$. Read each as a game.
Same symbols, different order.
In A the opponent names a real and we then produce a natural number above it — a different one each time, which is allowed.
We choose second, so we may adapt.
In B we must name one natural number in advance that exceeds every real, which is plainly impossible. So A is the Archimedean property and B is false. The property is exactly the statement that we are allowed to choose second.
Take the relation 'the integer $y$ exceeds the real number $x$'. Put these four claims in order, strongest first — strongest meaning the one that implies the most.
Number the steps in order (write the number in the box):
Write 'some integer is greater than every real number' in symbols.
Let $S = \{1, 2, \ldots, 8\}$. Mark every statement that is true of $S$.
This task has no paper form; do it on a device.
Match each definition to its shape in quantifiers.
| $\exists M\, \forall x\, (\ldots)$ — one object fixed, then a sweep | $\forall a\, \forall b\, (\ldots)$ — a sweep over pairs | $\forall y\, \exists x\, (\ldots)$ — a sweep, producing something each time | $\forall B\, \exists x \in S\, (\ldots)$ — a sweep over candidates, defeating each | |
|---|---|---|---|---|
| $f$ is bounded | ||||
| $f$ is injective | ||||
| $f$ is surjective | ||||
| $S$ is unbounded above |
A function is **uniformly continuous** when $\forall \varepsilon\, \exists \delta\, \forall x, y\, (|x - y| < \delta \Rightarrow |f(x) - f(y)| < \varepsilon)$. Ordinary continuity puts $\forall x$ before $\exists \delta$. What does that change?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take the relation 'the student $y$ can answer the question $x$'. Put these four claims in order, strongest first — strongest meaning the one that implies the most.
Number the steps in order (write the number in the box):
You can write a quantified claim, order a mixed pair correctly and read a definition's shape. Say in your own words what changes when for-all and there-exists are swapped, and give an example where one order is true and the other is false. Next: how to negate a quantified statement, which is the move every proof by contradiction starts with.
10. Your turn: which of these two is the Archimedean property?, step 3