Hands on Mathematics for CS - News

10. Session: January 12th

Erroneous examples: Find errors in proofs ( Session 7 )

• Hideo Sato, Björn Gehl
• Steffen Heil, Verena Kremer, Daniel Schmitt

• Sebastian Germesin, Stefan Nesbigall

• Steffen Knapp, Christian Hümbert
• Sarmad Hussain, Noreen Nasar

• Maciej Mrowiec, Khoa Chu
• Sebastian Blohm, Daniel Beck (Schlussfolgerung)

Exercises

A typical approach to prove a limit theorem such as LIM+

is by using the epsilon-delta definition of limit and dealing with inequalities. The epsilon-delta definition of limit states that the limit of function h at point c equals l iff

That is, in order to prove that the limit of function h at point c equals l we have to prove that for every ε > 0 there exists a δ >0 such that |h(x)-l| < ε holds for all x in the delta environment around c .

If you look up a proof by epsilon-delta definition in a math textbook you will typically find (more or less) the following pattern: Choose delta as follows ... Then, the following inequalities hold ... because of some arithmetic simplifications ...

The problem with such a proof presentation is that it gives the concrete delta for the problem at hand but no explantion how the suitable delta was found. So the question is ``What's the mathematical way to find a delta to construct a proof?''

Now, proof and delta construction works as follows: After the application of the epsilon-delta definition we have to deal with inequalities. we can apply the following pseudo algorithm:

1. Extract/derive simple inequalities resulting in value restrictions for variables. For instance, the epsilon-delta definition always includes the statement that delta has to be greater than zero. This restricts the possible values for delta to positive reals.
   

2. Reduce complex inequalities to simpler ones, which probably yield value restricions.
   

3. Collect value restrictions for variables until you can figure out suitable instantiations for the variables that satisfy all inequalities.

As example for complex inequalities that have to be reduced to simpler ones consider the following inequality resulting from the epsilon-delta defitinition applied to LIM+:

How can we deal with such an inequality? Well, the goal is to prove that (*) can be made arbitrarily small. One assumption of LIM+, lim f(x) = l_f, states that |f(x)-l_f| < ε__f can be made arbitrarily small. This statement can be used to reduce the complex inequality (*) as follows:

1. Express |(f(x)+g(x))-(l_f+l_g)| as a linear combination by |f(x)-l_f|
   
   |(f(x)+g(x))-(l_f+l_g)| = |f(x)-l_f| + |g(x)-l_g|
   

2. Apply transitivity:
   
   |f(x)-l_f| + |g(x)-l_g| < ε
   

3. Splitting the sum yields:
   
   |f(x)-l_f| < ε_1 and
   |g(x)-l_g| < ε_2
   

   Where ε_1 + ε_2 = ε. Usually we assign ε_1 and ε_2 to ε/2 resulting in:
   

   |f(x)-l_f| < ε/2 and
   |g(x)-l_g| < ε/2
   

4. Another application of transitivity yields (see definition):
   
   ε_f < ε/2 and
   ε_g < ε/2
   

5. ... see exercises ...

The general pattern for obtaining new inequalities is described below:

Suppose two approximations a≤E_a and b≤E_b are given. We want to derive the latter from the first in reasoning backwards. Thus, the algorithm (ESTIMATE) is logically correct if you read it bottom up.

1. Formulate a linear combination of b by a , obtaining the result b=k*a+l.
   

2. Applying the triangle inequality and the product rule yields: |b| ≤ |k|*|a|+|l|
   

3. Applying the transitivity rule yields: |k|*|a|+|l| ≤ E_b
   

4. Splitting the inequality yields two new inequalities: |k|*|a| ≤ Z1 and |l| ≤ Z2 with Z1+Z2=E_b .
   

Exercise: ESTIMATE algorithm: (*)

• What kind of new inequalities can we derive in general?
  

• What kind of new inequalities can we derive if k=1?
  

• What kind of new inequalities can we derive if l=0?
  

• Suppose ESTIMATE is an algorithm which encapsulates all these introduced steps. Formulate the application condition and the return value of the algorithm. Include also special cases.
  

• Do you think it is possible to apply ESTIMATE to other standard limit proofs? Give examples.
  

• Give other non-limit examples?
  

Exercise: Deriving new inequalities (** exercise)

1. Apply the approach to tackle limit problems (simple inequalities --> value restrictions, complex inequalities --> simple inequalities, collect value restricions until suitable instantiations can be computed) to the simple problem lim_x-->c x = c.
   

2. Afterwards, apply it to the more complex LIM+ problem (using the ESTIMATE pattern).
   

3. Derive all value restrictions and inequalities. Use them for determination of a suitable delta. Highlight your line of reasoning and make the key step(s) in your reasoning explicit. Afterwards describe math-textbook style proofs of the problems and compare them with the introduced approach.
   

4. Discussion: Do you think the approach is cognitively adequate?
   

Exercise: ESTIMATE Applet

• Write an applet, which implements a Gui for ESTIMATE. The Gui should be a wizard or a template with fill in blanks. Other suggestions are mostly welcome. The user is supposed to fill in the values for k, l, Z1, Z2 and Z. Configure your applet according to pedagogical goals (support learning). (***)