CS202 Study Guide

4a. Discuss how one conclusion leads to another, in the mathematical sense, for a given situation

• What is the difference between a theorem and an axiom?
• Why is investigation important to mathematical systems?
• How do specific definitions impact a mathematical system?

Mathematical systems are evolved through investigation, what is termed "research" in the figure taken from the first reading in this unit. Yet, it is not always top-down. Sometimes, through intuition, imagination, or some other creative process, it is possible that a theory will be postulated. But then, research (investigation) must take place to prove or disprove that theory. Once proven, a theory becomes an axiom, something that can be used to prove more complex theories.

Underlying even research are clear and specific definitions. We must know exactly what we are talking about. If we say "straight line", what does that mean within the context of the mathematical system in which we are engaged? If we use the symbol "+", what exactly does that mean? If we say, "the color is RED", what do we mean by that? Context is important. And, we must be exact within that context so as to transition colloquial speech, which is vague, to technical speech, which is precise.

Review Mathematical Systems.

4b. Write the terms of a logical sequence as a generalized formula

• Why are truth tables not always the best approach to proving a statement to be true or false?
• How can we overcome the limits of truth tables?
• What are two approaches to generalized proofs?

Truth tables are a fine approach to logical proof when there are few variables (facts) involved. But, as the number of variables increases, the size of the truth table increases as does 2V, where V is the number of variables. The table will have a minimum of V columns and 2V rows. For most industrial applications, the use of such a table is intractable, given the time and machinery available. Thus, we need a different approach. This involves the use of Direct and Indirect Proofs.

Direct and Indirect Proofs follow a series of steps that begin with basic axioms and use those as building blocks to build to a final proof or disproof. Direct Proof seeks to demonstrate that a theorem is true. Indirect Proof seeks to prove the theorem is false. We followed the same basic approach when we built truth tables to prove the truth or falsehood of a statement. We started with variables and then added logical statements until the final statement was shown to be true or false under all possible circumstances. Direct and Indirect Proofs generalize this approach.

Review:

• Direct Proof
• Indirect Proof

4c.    Use mathematical induction to prove the validity of logical sequences

• Why is mathematical induction important?
• What are some examples of how induction can explain complex situations?
• Explain the difference between mathematical induction and strong induction?

Mathematical induction and its cousin, strong induction, allow us to overcome the possibility that a situation may contain an infinite number of variables. Strong induction extends mathematical induction in that it allows us to demonstrate additional assertions that are true if a given assertion is proven true by mathematical induction. Real life contains an unending collection of complex situations. Many of these contain variables that are based on previous versions of earlier variables in a never-ending stream. Let's examine one of those.

Zeno's Paradox describes an archer shooting at a target that is some distance, D, away. Once the arrow, A, is set loose, it travels to the half-way point to the target. Then it flies to a point half of the remaining distance. This continues indefinitely, for each step, T. The arrow is always heading for the next half-way point. That being the case, how does the arrow ever reach the target? (We know that it does, eventually, if the archer is accurate.) Here is a solution modeled after the readings' examples. It is drawn from the problem description.

A(0) = D * (1/2⁰)           base case, distance to target prior to arrow being fired.

A(1) = D * (1/2¹)            situational properties

A(2) = D * (1/2²)

...

A(10) = D * (1/2¹⁰)

A(T) → A(T + 1)            inductive step

A(∞) = D * (1/2^T)|_{lim T} → ∞         calculus

A(∞) = D * 0 = 0            final distance to target is 0, the arrow strikes the target

Notice that, in this philosophical context, infinite steps do not necessarily take infinite time. Mathematically, the solution is reasonable. But, is it reasonable from a physics perspective? Can we really take infinite steps in finite time? Calculus, by the way, offers integration as another approach. We can always integrate using this equation: $\int_{0}^{D} d D=D-0=D$. Thus we show that all the small distances add up to the whole distance. (Integration allows us to perform addition of an infinite number of values. (Recall from the readings that ∑ is the Greek letter for summation and S is the Latin letter for summation. So, this is where ∫comes from). In any case, we have two clear and provable indications that the arrow does indeed reach the target, in finite time, even though there appears to be an infinite number of steps in the process.

Review:

• Discussion and Examples
• Strong Mathematical Induction

4d.    employ inductive reasoning to situations where there is sufficient evidence to warrant generalization

• What is the end result of Peano Postulates?
• Give another name for "strong induction".
• What should we look for when we try to engage inductive reasoning?

To paraphrase the last section of this unit, inductive reasoning's foundation began to be laid in the 1800s with the work of Richard Dedekind. He developed a set of axioms that describe the positive integers. Later that same century, Giuseppe Peano refined these axioms, created a logical interpretation, and generalized them into the Peano Postulates. These are the cornerstone of mathematical induction. 

Another name for "strong induction" is "course-of-values induction". From that perspective, we can attempt to apply inductive reasoning by being alert for patterns in an evolving situation or a sequence of events. For instance, Zeno's Paradox is based on the sequence of milestones reached by the arrows. The progress of the situation can be identified by the event leading to each milestone, traveling the distance from the prior milestone to the present milestone, the arrow traveling from the prior halfway point to the present halfway point. We finally realize that A(T) → A(T + 1). From this general statement, we can write a general solution to the problem that does not depend on the specifics (distance to target or any milestone). We can even generalize to the extent that A(T) → A(T + n), where n is any step in the process.

The detection of patterns can be very important to problem-solving. But, so can the lack of discernible patterns. For instance, some computer languages allow memory references beyond predefined vectors and arrays, "memory overruns". This leads to erratic behavior in computer programs. It is rare that any pattern will be observed. That is one reason programmers will restart a program and run it several times under the exact same conditions. If no pattern occurs, they know to look for memory overruns.

Each type of behavior requires a different approach to solve. Apply the approach that leads to the best solution for the situation at hand.

Review:

• Discussion and Examples
• Strong Mathematical Induction

Unit 4 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• axiom
• base case
• course-of-values induction
  
• Direct Proof
• Indirect Proof
• mathematical induction
• memory overruns
• inductive reasoning
• integration
  
• Peano Postulates
• strong induction
• theorem
• variables
  
• Zeno's Paradox