Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

Math Discovery Examples

Math Discovery Analysis: Time

Time* C1) Sequence C2) Poset with maximal or minimal elements C3) Least upper bounds, greatest lower bounds C4) Limits The act of ever getting a new sheet (blank or otherwise) makes for a countably infinite list. That is what we need for mathematical induction. Next, we may prefer some sheets as more noteworthy than others, which we ignore, so that some are most valuable. Such extremes are assumed by the extreme principle. An example is the square as the rectangle of a given perimeter that yields the most area. Next, we construct monovariants which say, in effect, that the only results which count are those that beat the record-to-beat, which yields sequences of increasing minimums, thus a greatest lower bound, or alternatively, a least upper bound. Finally, we allow such a boxing-in or boxing-out process to continue indefinitely, yielding (or not) a limit that may very well transcend the existing system (as the reals transcend the rationals). We thereby construct internal "time" which is fully fledged in that the continuum without gaps may be used to model space. 11

Sequence* The act of ever getting a new sheet (blank or otherwise) makes for a countably infinite list. That is what we need for mathematical induction.17

• Axiom of Infinity* Wikipedia: Let S(x) abbreviate x U {x}, where x is some set. Then there exists a set X such that the empty set {} is a member of X and, whenever a set y is a member of X, then S(y) is also a member of X. More colloquially, there exists a set X having infinitely many members. The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω, which can also be thought of as the natural numbers N.1161

• Mathematical induction* 808
  • Natural numbers* Edward Cherlin: The defining characteristic of the standard natural numbers is induction.
    0 is a natural number Every natural number has a unique successor that is a natural number. Every natural number except 0 has a unique predecessor among the natural numbers. If K is a set such that 0 is in K, and for every natural number n, if n is in K, then S(n) is in K, then K contains every natural number.

809

• Standard induction* This is a very powerful method for proving assertions that are "indexed" by integers... Each assertion can be put in the form, P(n) is true for all integers n >= n0, where P(n) is a statement involving the integer n, and n0 is the "starting point". In standard induction: 1. Establish the truth of P(n0). This is called the "base case" and is usually an easy exercise. 2. Assume that P(n) is true for some arbitrary integer n. This is called the inductive hypothesis. Then show that the inductive hypothesis implies that P(n+1) is also true. This is sufficient to prove P(n) for all integers n>=n0, since P(n0) is true by (1) ... pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1440
  • Prove n! > 2**n where integer n >= 3* Weitz, pg.511498
  • Prove that the sum of the interior angles of any n-gon is 180(n-2) degrees* Weitz, pg.501499
• Transfinite induction* Edward Cherlin: Proofs by transfinite induction are entirely analogous to proofs by finite induction. 810
  • Transfinite ordinals* Edward Cherlin: A similar construction [to the natural numbers] and a similar inductive condition define the transfinite ordinals, but with some differences. If S is a set of ordinals with no largest member, then the union of its members is a larger ordinal. This allows us to define the first transfinite ordinal as the order type of the set of natural numbers. This ordinal is called omega. Then we get omega + 1, and so on. Taking all countable ordinals together gives us the first uncountable ordinal, and so on again.811

Poset with maximal or minimal elements* We may prefer some sheets as more noteworthy than others, which we ignore, so that some are most valuable. Such extremes are assumed by the extreme principle. An example is the square as the rectangle of a given perimeter that yields the most area. 18

• Four times a right triangle is the difference of two squares* A right triangle rotated four times brings us back to where we were. This yields a difference of two squares from which the Pythagorean theorem follows. Note also that sin(x) and cos(x) are equal to their fourth derivatives. Gospel Math. 1845
• Right triangles are more basic than circles* Consider a line segment of length AB and consider all of the right triangles with hypotenuse AB. Drop the altimeter Z so that the hypotenuse is X + Y. The radius is the average, the arithmetic mean (X+Y)/2 and the altimeter is the geometric mean of X and Y. This makes clear that the arithmetic mean is greater than the geometric mean because the radius is greater than the altimeter. It also shows that the square has greater area than other rectangles of the same perimeter. Then the right triangles form a semicircle without the two endpoints. Circles depend on distance and thus presume right triangles. Gospel Math. 1844

• Arithmetic-Geometric Mean Inequality* 1998 x 2000 ? 1999 x 1999 Your intuition probably tells you that the question mark should be replaced with "<", for the left-hand side is the area of a rectangle that is not quite a square, while the right hand side is the area of a square with the same perimeter as the rectangle (namely 4x1999). It makes sense that given a fixed amount of fencing, the rectangle of maximum area is a square. ... (x+y)/2 >= square-root of xy. ... The arithmetic mean of two positive real numbers is greater than or equal to the geometric mean, with equality only if the numbers are equal. ... Here is a nice geometric proof of AM-GM. Let AC be the diameter of a circle, and let B be any point on the circle. Recall that ABC will be a right triangle. Now locate point D so that BD is perpendicular to AC. Then triangles ABD and BCD are similar; hence x/g = g/y. Thus g = square root of xy, the geometric mean of x and y. Indeed, that's why it is called a geometric mean! pg.193-194 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2191
• Calculus of variations* Wikipedia: Calculus of variations is a field of mathematics that deals with extremizing functionals, as opposed to ordinary calculus which deals with functions. A functional is usually a mapping from a set of functions to the real numbers. Functionals are often formed as definite integrals involving unknown functions and their derivatives. The interest is in extremal functions that make the functional attain a maximum or minimum value - or stationary functions - those where the rate of change of the functional is precisely zero. Perhaps the simplest example of such a problem is to find the curve of shortest length, or geodesic, connecting two points. If there are no constraints, the solution is obviously a straight line between the points. However, if the curve is constrained to lie on a surface in space, then the solution is less obvious, and possibly many solutions may exist.910
• Extremal arguments involving infinite sets* In more complicated problems, it is not always obvious what entities should be monotonized, and the Well-Ordering Principle is not always true for infinite sets. In situations involving infinite sets, sometimes extremal arguments work, but you need to be careful. .... Let f(x) be a polynomial with real coefficients of degree n such that f(x)>=0 for all x in R. Define g(x):= f(x) + f'(x) + f''(x) ... + f(n)(x). Show that g(x)>=0 for all x in R. pg.88, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1739
• Extreme principle* If possible, assume that the elements of your problem are "in order". Focus on the "largest" and "smallest" elements, as they may be constrained in interesting ways. ... Work by contradiction; assume that whatever you wish to prove is not true. Then look at the minimal (or maximal) element and develop an argument that creates a smaller (or larger) element, which is the desired contradiction. As long as a set of real numbers is finite, it will have a minimum and a maximum element. pg.82, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.76
  • When black and white points are interspersed...* Let B and W be finite sets of black and white points, respectively, in the plane, with the property that every line segment which joins two points of the same color contains a point of the other color. Prove that both sets must lie on a single line segment. ... The extreme principle comes to the rescue: Assume that the points do not all lie on a line. Then they form at least one triangle. Consider the triangle of smallest area. Two of its vertices are the same color, so between them is a point of the other color, but this forms a smaller triangle - a contradiction! pg.82, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1630
• Least squares* Wikipedia: The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e. sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every single equation.906
• Maximum* We conceive or find the maximum.860
  • Laffer Curve* Wikipedia: In economics, the Laffer curve is a theoretical representation of the relationship between government revenue raised by taxation and all possible rates of taxation. It is used to illustrate the concept of taxable income elasticity (that taxable income will change in response to changes in the rate of taxation). The curve is constructed by thought experiment. First, the amount of tax revenue raised at the extreme tax rates of 0% and 100% is considered. It is clear that a 0% tax rate raises no revenue, but the Laffer curve hypothesis is that a 100% tax rate will also generate no revenue because at such a rate there is no longer any incentive for a rational taxpayer to earn any income, thus the revenue raised will be 100% of nothing. If both a 0% rate and 100% rate of taxation generate no revenue, it follows that there must exist at least one rate in between where tax revenue would be a maximum.861
• Monotonizing* Always be aware of order and maximum/minimum in a problem, and always assume, if possible, that the elements are arranged in order ... Think of this as "free information". pg.83, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1632
• Sign of the derivative* You certainly know that the derivative f'(x) of a function f(x) has two interpretations: a dynamic definition as rate of change [of f(x) with respect to x], and a geometric definition as slope of the tangent line to the graph y=f(x) at the point (x,f(x)). The rate-of-change definition is especially useful for understanding how functions grow. More elaborate information comes from the second derivative f(x), which of course measures how fast the derivative is changing. Sometimes just simple analysis of the signs of f' and f is enough to solve fairly complicated problems. pg.294 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2240
• Sum of Squares* The Cauchy-Schwarz inequality states that [(the sum of aibi)**2 <= (sum of ai**2)(sum of bi**2)] with equality holding if and only if a1/b1 = a2/b2 = ... = an/bn. ... another way to prove [this] uses the simple but important tool that A sum of squares of real numbers is non-negative, and equal to zero if and only if all the numbers are zero. ... 0 <=(ay-bx)**2 + (az-cx)**2 + (bz-cy)**2. pg.198-199 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2196
• Symmetry-Product Principle* We can extract more information from our algebraic proof of AM-GM. ... S**2 - 4P = D**2, where S, P, D are respectively the sum, product and difference of x and y. ... As the distance between two positive numbers decreases, their product increases, provided that their sum stays constant. This agrees with our intuition: As a rectangle becomes more "squarish", i.e., more symmetrical, it encloses area more "efficiently". pg.193-194 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2193
• Tangent-line approximation* The tangent-line definition of the derivative stems from its formal definition as a limit. ... This suggests a useful, but less well-known, application of the derivative, the tangent-line approximation to the function. ... In general, analyzing f(a+h) with its tangent-line approximation f(a) + hf'(a) is very useful, especially when combined with other geometric information, such as convexity. ... Prove Bernoulli's Inequality (1 + x)**alpha >= 1 + alpha x for x>= -1 and alpha >= 1, with equality when x = 0. ... For integer alpha, this can be proven by induction ... But induction won't work for arbitrary real alpha. Instead, define f(u) = u**alpha, and note that f'(u) = alpha u**(alpha - 1) and f''(u) = alpha(alpha-1)u**(alpha-2). ... Thus the graph y=f(u) is concave up...Therefore, the graph of y=f(u) lies above the tangent line for all u>=0. ... f(1+x) is always strictly greater than its linear approximation 1+alpha x, except when x=0, in which case we have equality. pg.296-297 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2241
• Use of extreme principle with induction* Often, problems involve the extreme principle plus a particular argument style, such as contradiction or induction. A common tactic is to use the extremes to "strip down" a problem into a smaller version ... The formal argument then uses induction. ... Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing. pg.85, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1633
• Well-Ordering Principle* Every non-empty set of positive integers has a least element. pg.83, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1631
  • Division algorithm* The extreme principle in number theory ... Let a and b be positive integers, b>=a. Then there exist integers q,r satisfying q>=1 and 0<=r pg.92, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1634

Least upper bounds, greatest lower bounds* We construct monovariants which say, in effect, that the only results which count are those that beat the record-to-beat, which yields sequences of increasing minimums, thus a greatest lower bound, or alternatively, a least upper bound.19

• Least-upper-bound assumes second-order logic* Wikipedia Second-order logic is more expressive than first-order logic. For example, if the domain is the set of all real numbers, one can assert in first-order logic the existence of an additive inverse of each real number by writing ∀x ∃y (x + y = 0) but one needs second-order logic to assert the least-upper-bound property for sets of real numbers, which states that every bounded, nonempty set of real numbers has a supremum. If the domain is the set of all real numbers, the following second-order sentence expresses the least upper bound property [...] In second-order logic, it is possible to write formal sentences which say "the domain is finite" or "the domain is of countable cardinality." To say that the domain is finite, use the sentence that says that every surjective function from the domain to itself is injective. To say that the domain has countable cardinality, use the sentence that says that there is a bijection between every two infinite subsets of the domain. It follows from the upward Löwenheim-Skolem theorem that it is not possible to characterize finiteness or countability in first-order logic.2255

• Algorithmic proof* AM-GM reformulated...We have managed to change two of the n numbers in such a way that
  • one number that originally was not equal to A became equal to A;
  • the sum of all n numbers did not change;
  • the product of the n numbers increased.

Since there are finitely many numbers, this process will end when all of them are equal to A; then the product will be maximal. This proof is called "algorithmic" because the argument used describes a concrete procedure which optimizes the product in a step-by-step way, ending after a finite number of steps. pg.195-196 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2194

• Bounded monotonic sequence* In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the sequence is bounded and monotonic. A sequence (an) is bounded if there is a finite number B such that |an|<=B for all n. The sequence is monotonic if it is either non-increasing or non-decreasing. ... Bounded monotonic sequences are good, because they always converge. To see this, argue by contradiction: if the sequence did not converge, it would not have the Cauchy property, etc. ... pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2234
• Convergence of upper and lower bounds* In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the terms of the sequence are bounded above and below by the terms of two convergent sequences that converge to the same limit. For example, suppose that for all n, we have 0 < xn < (0.9)**n. This forces the limit as n goes to infinity of xn to be zero. Conversely, if the terms of a sequence are greater in absolute value than the corresponding terms of a sequence that diverges (has infinite limit), then the sequence in question also diverges. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2235
• Finite Injury Priority Method* Muchnik [1956] and Friedberg [1957] invented a computable approximation to this forcing argument, called the finite injury method , where they allow a requirement to finitely often be injured (i.e, previous progress to be destroyed), and then they begin again to satisfy the given requirement, until after it is finally satisfied and never injured thereafter. We present finite injury priority arguments and a solution to Post's problem of c.e. sets A and B of incomparable Turing degree. Robert Soare's upcoming book, "Computability Theory and Applications: The Art of Classical Computability".1660
• Growth rates of functions* It is important to understand the hierarchy of growth rates for the most common functions. The best way to learn about this is to draw lots of graphs. Any quadratic function of x will dominate any linear function of x, provided that x is "large enough". ... x**a will eventually dominate x**b provided that a > b > 0. ...if a is any positive number, and b > 1, then b**x eventually dominates x**a ... exponential functions grow faster than polynomial functions ... if a is any positive number, and b > 1, then x**a eventually dominates log(b)x. In summary, the hierarchy of growth rates, from slowest to highest, is logarithms, powers, exponents. pg.190-191 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2190
• Limits and Colimits in Category Theory* In category theory, the limit of a diagram is the "least upper bound" for the diagram, in the sense that it is a cone (generalization) of the diagram such that it is more specific than any other such cone. Similarly, the colimit of a diagram is the "greatest lower bound" for the diagram, in the sense that it is a co-cone that is more general than any other such co-cone. Wikipedia: Limits are also referred to as universal cones, since they are characterized by a universal property (see below for more information). As with every universal property, the above definition describes a balanced state of generality: The limit object L has to be general enough to allow any other cone to factor through it; on the other hand, L has to be sufficiently specific, so that only one such factorization is possible for every cone. Limits may also be characterized as terminal objects in the category of cones to F. It is possible that a diagram does not have a limit at all. However, if a diagram does have a limit then this limit is essentially unique: it is unique up to a unique isomorphism. For this reason one often speaks of the limit of F.2254
• Massage* 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... Show that the harmonic series diverges ... 1/3 + 1/4 >= 1/2, 1/5+1/6+1/7+1/8 >= 1/2, etc. ... Therefore the entire harmonic series is greater than or equal to 1 + 1/2 + 1/2 + 1/2 + ... which diverges. The key idea used above combines the obvious fact that a>=b => 1/a <= 1/b with the nice trick of replacing a "complicated" denominator with a "simpler" one. This is an example of the many-faceted massage tool - the technique of fiddling around with an expression, with whatever method works (adding zero, multipying by one, adding or subtracting a bit, etc.) in order to make it more manageable. ... Yet another idea inspired by the Wishful Thinking strategy. ... The philosophy of massage is to "loosen up" an expression in such a way that it eventually becomes easier to deal with. ... Sometimes the first stage of massage seemingly worsens the difficulty. But that is temporary, much like physical massage, which can be rather painful until your muscles magically relax. Here is an instructive example which combines massage with its frequent partner, telescoping. ... pg.176-177, 197 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2182
• Monovariant* A monovariant is a quantity which may or may not change at each step of a problem, but when it does change, it does so monotonically (in only one direction). Another term used for monovariant is semi-invariant. Monovariants are often used in the analysis of evolving systems, to show that certain final configurations must occur, and/or determine the duration of the system. Many monovariant arguments also make use of the extreme principle (at least the well-ordering principle). pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1747
  • John Conway's Checker Problem* Put a checker on every lattice point ... in the plane with y-coordinates less than or equal to zero. The only legal moves are horizontal or vertical "jumping". By this we mean that a checker can leap over a neighbor, ending up 2 units up, down, right, or left of its original position, provided that the destination point is unoccupied. After the jump is complete, the checker that was jumped over is removed from the board. ... Is it possible to make a finite number of legal moves and get a checker to reach the line y=5? pg.114, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1751
  • Number of games in an elimination-style tournament* Find a formula for the number of games that must be played in an elimination-style tournament starting with n contestants. ... The number of people who are left in the tournament is clearly a monovariant over time. This number decreases by one each time a game is concluded. Hence if we start with n people, the tournament must end after exactly n-1 games! pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1748
  • Reversing cards in a deck* The n cards of a deck ... are labeled 1,...,n. Starting with the deck in any order, repeat the following operation: if the card on top is labeled k, reverse the order of the first k cards. Prove that eventually the first card will be 1 (so no further changes occur). pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1750

• Constraint optimization* Wikipedia: Constraint optimization (also called constrained optimization) seeks for a solution maximizing or minimizing a cost function. A constraint optimization problem can be defined as a regular constraint satisfaction problem in which constraints are weighted and the goal is to find a solution maximizing the weight of satisfied constraints. Alternatively, a constraint optimization problem can be defined as a regular constraint satisfaction problem augmented with a number of "local" cost functions. The aim of constraint optimization is to find a solution to the problem whose cost, evaluated as the sum of the cost functions, is maximized or minimized. The regular constraints are called hard constraints, while the cost functions are called soft constraints. Note that solutions of constraint optimization generally involve a series of maximums or minimums.933

  • Noah practiced constrained optimization* Tom Wayburn, 2011.04.28: Richard Tapia of Rice University math department suggests that Noah must have been one of the earliest practitioners of constrained optimization, as he had to house all the animals and in such a way that none got eaten.940

  • Branch and bound* Wikipedia: Constraint optimization can be solved by branch and bound algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and use it for avoiding part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.935
  • First-choice bounding functions* Wikipedia: In the branch and bound method, one way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume a higher value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for x = a while another constraint is maximal for x = b.936
  • Russian doll search* Wikipedia: This method runs a branch-and-bound algorithm on n problems, where n is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables x_1, ..., x_i from the original problem, along with the constraints containing them. After the problem on variables x_i+1, ..., x_n is solved, its optimal cost can be used as an upper bound while solving the other problems. In particular, the cost estimate of a solution having x_i+1, ..., x_n as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. 937

Limits* We allow a boxing-in or boxing-out process to continue indefinitely, yielding (or not) a limit that may very well transcend the existing system (as the reals transcend the rationals). 20

• Continuum hypothesis* Wikipedia: There is no set whose cardinality is strictly between that of the integers and that of the real numbers. ... The contributions of Kurt Gödel in 1940 and Paul Cohen in 1963 showed that this continuum hypothesis can neither be disproved nor be proved using the axioms of Zermelo-Fraenkel set theory, the standard foundation of modern mathematics, provided ZF set theory is consistent.1174

• Cauchy property* In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the ai eventually get arbitrarily close to one another. More precisely, a sequence (an) possesses the Cauchy property if for any (very tiny) epsilon > 0 there is a (huge) N such that |am - an| < epsilon for all m, n >= N. If a sequence of real numbers has the Cauchy property, it converges. The Cauchy property is often fairly easy to verify, but the disadvantage is that one doesn't get any information about the actual limiting value of the sequence. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2233
• Convergence* We say that the real-valued sequence (an) converges to the limit L if ... That if we pick an arbitrary distance epsilon > 0, eventually, and forever after, the ai will get within epsilon of L. More specifically, for any epsilon > 0 (think of epsilon as a really tiny number), there is an integer N (think of it as a really huge number, one that depends on epsilon) such that all of the numbers aN, aN+1, aN+2, ... lie within epsilon of L. In other words, for all n >= N, |an - L| < epsilon. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2231
• Infinite Injury Priority Method* Shoenfield [1961] and Sacks independently [1963a,b,c] invented the infinite injury method for computable constructions in which a given requirement may be injured infinitely often, but only computably so, and still somehow succeed. Yates, Martin, and Lachlan extended and refined this method and added others such as the minimal pair construction of a pair of noncomputable c.e. sets A and B whose degree have infimum degree 0 the degree of the computable sets. By the end of the initial period of computability 1930--1970 the constructions and proofs had become so complicated that it had become very difficult to obtain any intuition about them. Fortunately, Lachlan introduced: (1) the method of games in computability Lachlan [1970a] (see Chapter on Lachlan Games); (2) the topology of priority arguments Lachlan [1973], which gave rise to the true stages method for infinite injury (refined in Chapter 8); and (3) the use trees in Lachlan [1975] to divide a strategy for a priority argument into a collection of strategies, one assigned to each node of the tree, and each equipped with a guess about the outcome of higher priority strategies. Lachlan's original use of trees [1975] for a 0''' argument was very complicated, but the tree method with simplifications was presented in Soare [1985] and is further refined in this book in Chapters 9 and 10. It has been used very extensively in computability theory ever since. These three improvements and their refinements allow the reader of this book to help keep in mind what Leo Harrington calls the mountain top view of the proof: a small number of key elements, their interaction, how we resolve conflicts between conflicting requirements, and the underlying beauty of the proof. Robert Soare's upcoming book, "Computability Theory and Applications: The Art of Classical Computability".1661
• Integrals* The fundamental theorem of calculus gives us a method for computing definite integrals. ... There is a lot of interplay between summation, integration, and inequalities; many problems exploit this. Compute the limit as n approaches infinity of the sum from k =1 to n of n/(k**2 + n**2). The problem is impenetrable until we realize that we are not faced with a sum, but the limit of a sum; and that is exactly what definite integrals are. So let us try to work backwards and construct a definite integral whose value is the given limit. ... Even finite sums can be analyzed with integrals. If the functions involved are monotonic, it is possible to relate integrals and sums with inequalities... pg.301-302 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2245