Q1 12
MATH1090 Logic Q2
Q3
36
25
Assignment 4 Q4 20
Q5 7
Intermediate Value Theorem
100
0
f(x)
a r b
I really wanted you to follow the parse tree
and prove something cool.
But this was tooooo hard.
Jeff Edmonds
…. Aaaaaah!
York University
Epsilon Delta Proofs: Key to calculus, analysis, and set theory.
Continuous
Continuous:
Let the function f(x) be from reals to reals.
f is said to be continuous everywhere
iff "x, f is continuous at x
iff "x, for an arbitrary definition of closeness,
as x' approaches x
f(x') stays close to f(x).
iff "x, " infinitesimal >0, within a sufficiently small range near x,
f does not vary by more than
iff "x, ">0, $>0, "x'[x-,x+], |f(x')-f(x)|≤
f(x')
f(x)
f(x)
x'
x
Continuous
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Question 1: Parse this using the context free grammar
and follow the game to prove that
f(x) = x3 is continuous at x=0.
1. First you need to express the math problem
as a first order logic statement.
2. Parse it with the following Contest Free Grammar
– S "x S(x) | $x S(x) | SiS | SbothS | SoneS | R(T,T) | …
– S "x S(x) | $x S(x) | S2S | S1bothS2 | ScasesS | R(T,T) | …
3.Mechanically traverse each player’s parse tree
following the dictated script.
4. Merge in the scripts of the oracle when stuck.
…. Aaaaaah!
Continuous
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Question 1: Parse this using the context free grammar
and follow the game to prove that
f(x) = x3 is continuous at x=0.
S(i-1) ≡ Planar Colouring(i-1) S(i) ≡ Planar Colouring(i)
I will assure you S(i-1). " planar graph G " planar graph G
# nodes in G = i-1 # nodes in G = i
I need to prove S(i)].
$ colouring C $ colouring C
# colours in C ≤ 6 # colours in C ≤ 6
Let G be an arbitrary graph. " edge u,v " edge u,v
C(u) ≠ C(v) C(u) ≠ C(v)
…. Aaaaaah!
Continuous & Converging
Converge: Consider the infinite sequence.
It is said to converge to the value a
iff for an arbitrary definition of closeness,
the sequence eventually gets and stays close to a
iff ">0, $i, "i'i, |ai'-a|≤.
a
a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, ….
i'
Continuous & Converging
Try to prove the follow:
• Assume that f(x) is continuous everywhere.
• As 1, 2, 3, 4, 5, … goes to infinity,
• 1
/1, 1/2, 1/3, 1/4, 1/5, … converges to 0
• f(1/1), f(1/2), f(1/3), f(1/4), f(1/5), … converges to f(0)
af(0)
a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, ….
i i'
Question 2: Continuous & Converging
"f, [Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]]
[Converging: ">0, $i, "i´, [ i´i |f(1/i´)-f(0)|≤]]
Parse this using the context free grammar
and follow the game to prove it.
Hint: Use the fact that f is continuous at x=0.
f(0)
a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, ….
i i'
Continuous
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Reals:
• eg x = 0.2904857920495839506803….
• Most reals do not have a finite description
Rationales/Fractions:
• eg x = 27/99 = 0.27272727272…
• Each has a finite description.
Round brackets
Axiom Dense: "reals x,y, $rational c(x,y)
means that c is
Proof: Let x and y be arbitrary reals.
not x or y.
x = 0.2904857932495839506803….
y = 0.2904853948839579020918….
Though these have an infinite number of digits,
the index i of each digit is finite.
There must be a first index i at which their digits differ.
Define the rational
c = 0.290485794 (x,y)
Continuous
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Reals:
• eg x = 0.2904857920495839506803….
• Most reals do not have a finite description
Rationales/Fractions:
• eg x = 27/99 = 0.27272727272…
• Each has a finite description.
Axiom Dense: "reals x,y, $rational c(x,y)
Despite this, in EECS2001,
we learn that there are more reals than rationales.
Crazy! I can’t wait to learn that!
Continuous
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Dense: "reals x,y, $rational c(x,y)
Rationales/Fractions: Suppose instead of the reals, our universe of
objects are the rationales. f(x) 1
−1 for x<√2 0
Let f(x) =
1 for x>√2 -1
√2
That’s not fair √2 True. But for every rational x,
is not rational. the output f(x) is a well a define rational.
We do not have to define it,
What is f(√2)?
because √2 is not a rational.
Clearly this function is not continuous!
Question 3: Follow the game to prove that f(x) is continuous
at every rational x. (By symmetry assume x>√2.)
…. Aaaaaah!
Intermediate Value Theorem
Intermediate Value Theorem:
• "f where f(x) is a continuous function from the reals to the reals
"a,b with f(a)<0 and f(b)>0,
$r[a,b] for which f(r)=0.
Binary search gets you closer and closer but not there.
0
f(x)
a r b
Intermediate Value Theorem
Intermediate Value Theorem:
• "f where f(x) is a continuous function from the reals to the reals
"a,b with f(a)<0 and f(b)>0,
$r[a,b] for which f(r)=0.
More generally, if g(x) is a continuous function and u ∈ [g(a), g(b)],
then there exists a real value r∈[a,b] for which g(r) = u.
This is proved from the previous by setting f(x) = g(x) − u.
u
g(x)
a r b
Intermediate Value Theorem
Intermediate Value Theorem:
• "f where f(x) is a continuous function from the reals to the reals
"a,b with f(a)<0 and f(b)>0,
$r[a,b] for which f(r)=0.
Clearly this is true!
It is not true over the rationales! f(x) 1
Hence to prove it, you need to 0
-1
differentiate between reals and rationales.
√2
0
f(x)
a r b
Supremum
max upper supremum upper
bound bound
Supremum
Dense: "reals x,y, $rational c(x,y)
Supremum: ["r´<r, $x, r´<x≤r and xS] and ["x´>r, x´S]
S = {x | x<5}
Question 4: Prove r=5 is the
supremum of S = {x | x<5}
by following this supremum upper
definition’s parse tree. 5 bound
Question 5: Follow this axiom’s parse tree
to prove that it is NOT true over the rationales.
Defining zero
Intermediate Value Theorem
Continuous: "x, ">0, $>0, "x´, [x´[x-,x+] |f(x')-f(x)|≤]
Supremum: "S⸦R, [S is non-empty and bounded]
$r [["r´<r, $x, r´<x≤r and xS] and ["x´>r, x´S]]
Defn zero: "q, [[">0, |q|≤] [q=0]]
Intermediate Value Theorem:
"a,b, [f(a)<0 & f(b)>0] [$r[a,b], f(r)=0]
0
f(x)
a r b
Question 6: Prove this.
Hint: Let S = {x≤b | f(x)<0}. Don’t do it.
Let r be the supremum of S. It is too hard.
Prove f(r)=0
