PG1.3 Quantifiers: for every and there exists

Simulate

Check the claim with numbers

Lesson 0.2.1 read $\forall$ as "for every" and $\exists$ as "there exists". A sentence such as " $x^2 \ge x$ " is neither true nor false until you say which $x$ . Put "for every real $x$ " in front and it becomes a statement.

Python can test a "for every" on many numbers at once. The cell takes 601 exact fractions from $-3$ to $3$ , in steps of $0.01$ , and tests two claims at each.

from fractions import Fraction xs = [Fraction(k, 100) for k in range(-300, 301)] print("points tested:", len(xs)) fails_1 = [x for x in xs if not x**2 >= x] fails_2 = [x for x in xs if not x**2 - 2*x + 2 > 0] print("x^2 >= x fails at", len(fails_1), "points, from", min(fails_1), "to", max(fails_1)) print("x^2 - 2x + 2 > 0 fails at", len(fails_2), "points") print("smallest value of x^2 - 2x + 2:", min(x**2 - 2*x + 2 for x in xs))

⌘/Ctrl + Enter runs the cell

The first claim fails at 99 points, every one strictly between 0 and 1, from $\frac{1}{100}$ to $\frac{99}{100}$ . The second never fails, and its smallest value is 1. Now a "there exists": is there a whole number $x$ with $x^2 = x + 6$ ?

⌘/Ctrl + Enter runs the cell

Two whole numbers work, $-2$ and $3$ , and only $3$ is positive. The last cell shows that the order of "for every" and "there exists" matters. It works on the whole numbers from $-5$ to $5$ .

xs = range(-5, 6) ys = range(-5, 6) print("for every x there is a y with x + y = 0:", all(any(x + y == 0 for y in ys) for x in xs)) print("there is a y with x + y = 0 for every x:", any(all(x + y == 0 for x in xs) for y in ys))

⌘/Ctrl + Enter runs the cell

For each $x$ some $y$ works, namely $-x$ . But no single $y$ works for every $x$ at once.

Conjecture

x

The cells tried 601 fractions, but claims 1 and 4 are about every real number, which no computer can try. Claims 2 and 3 are different: one well-chosen number settles each of them.

Proving and disproving with quantifiers

A quantifier says how many elements a statement is about. "For every" ( $\forall$ ) is a promise about all of them, so it needs an argument that covers them all. "There exists" ( $\exists$ ) is a promise about at least one, so showing one is enough.

To	do this
prove $\forall x \in A,\ P(x)$	take any $x \in A$ , assume nothing else about it, and show $P(x)$
disprove it	find one $x \in A$ where $P(x)$ fails: a counterexample
prove $\exists\, x \in A : P(x)$	find one $x \in A$ and check $P(x)$
disprove it	show that $P(x)$ fails for every $x \in A$

Here $A$ is a set and $P(x)$ a sentence about each of its elements $x$ . Two quantifiers in a row are read left to right, and swapping them changes the meaning.

Rule: The order of quantifiers

\begin{gathered} \forall x,\ \exists\, y : x + y = 0 \\ \exists\, y : \forall x,\ x + y = 0 \end{gathered}

In the first, $y$ is chosen after $x$ , so it may depend on $x$ : $y = -x$ works, and the statement is true. In the second, one $y$ must be chosen first and then work for every $x$ . No $y$ can, so it is false.

Analysis writes small positive numbers with the Greek letters $\varepsilon$ (epsilon) and $\delta$ (delta). "For every $\varepsilon > 0$ there is a $\delta > 0$ …" lets $\delta$ depend on $\varepsilon$ , exactly as $y$ depended on $x$ above. Lesson PG1.5 builds on this.

Format 2

Fill the gap

Four short proofs, one for each move in the table. Type each missing piece as you would a quick answer, such as 1/4 or -x, then check.

x

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

Simulate

Check a claim about ε and δ

Here is a claim with its quantifiers the other way round: there is a $\delta > 0$ smaller than every $\varepsilon > 0$ . First, each $\varepsilon$ does have a smaller positive number below it, such as $\varepsilon / 2$ .

from fractions import Fraction for eps in [Fraction(1), Fraction(1, 10), Fraction(1, 1000)]: delta = eps / 2 print("eps", eps, "has delta", delta, "below it:", 0 < delta < eps)

⌘/Ctrl + Enter runs the cell

But a single $\delta$ chosen first is always beaten: take $\varepsilon = \delta$ .

from fractions import Fraction for delta in [Fraction(1), Fraction(1, 10), Fraction(1, 1000)]: eps = delta print("delta", delta, "is below eps =", eps, ":", delta < eps)

⌘/Ctrl + Enter runs the cell

Each of the three $\delta$ prints False: it is not below the $\varepsilon$ equal to itself.

Format 3

Find the error

This proof claims there is a $\delta > 0$ with $\delta < \varepsilon$ for every $\varepsilon > 0$ . The simulation says the claim is false. Select the line where the proof goes wrong, then say why.

x

Quantifiers: for every and there exists

Check the claim with numbers

Proving and disproving with quantifiers

Rule: The order of quantifiers

Fill the gap

Check a claim about ε and δ

Find the error

Summary card

Free further reading