Math for Non-Geeks/Limit: Convergence and divergence

oben In this chapter we will introduce the central concept of a limit in the context of sequences. We will discuss what the term convergence is and what it means for a sequence to be convergent. All of the important concepts of Analysis like continuity, derivatives and integrals can only be defined if we have a notion of limits and convergence. Thus the concepts introduced in this chapter will serve as the backbone of our entire discussion about Analysis. Intuition behind the idea of convergence thumb|Intuition behind the idea of convergence (in German) (Youtube-Video by Math-Intuition) thumb|A video explaining convergence (in German). (YouTube-Video by the channel Quatematik) Before one sets about finding a precise mathematical definition of a new concept, it is always a good idea to first develop an intuition. Let us therefore consider the harmonic sequence . The first few elements of the sequence are: You can already tell that elements become smaller and go towards zero as we increase the index . We can make the following intuitive assertions: The sequence will get arbitrarily close to . The bigger the index , the more the member gets close to . The sequence tends to . The sequence tends to as , although no term equals . … All these intuitive statements already give us an idea of what the limit of a sequence is. To give a first intuitive definition we would say: The limit is the thing (or in this case the value) that the sequence approaches as we go further and further, i.e. as the index goes to infinity. In our case is the limit of the harmonic sequence . We say that the harmonic sequence is convergent. Of course not all sequences are convergent and thus have a finite limit: Think about the natural numbers as a sequence. They grow bigger and bigger and never get closer to any particular value. We say that the sequence of the natural numbers is divergent. Finding a definition for the limit First steps In mathematics, we need an exact definition of what we mean by a "limit" to be able to talk and reason precisely. We can find such a definition if we start with an intuitive idea and gradually concretize it until we have a rigorous mathematical definition. The process of concretion will go on until we have a definition that employs only previously defined terms. Let's start with the following intuitive description of a limit: "A sequence has a limit , if the members of the sequence get arbitrarily close to ." But what does "arbitrarily close" mean in the above sentence? We could translate this as follows: Imagine the members of the sequence in a coordinate system, where the -axis shows the indices and the -axis has the members/values of the sequence . So every member of the sequence corresponds to a point in this coordinate system. The limit is marked by a dotted line. 500px|center|Sequence elements in KOSY If the members converge to , then their distances to eventually stay below any prescribed positive number. They need not decrease at every step. Try to visualize a really narrow "tube" that has a radius of . Imagine taking this tube and "threading" it over the limit from the right. As long as the distance of the members from the limit is smaller than the radius of the tube, we can keep pushing the tube to the left. All points are still inside the tube. But as soon as a point has a bigger distance from the limit, this point will not be inside the tube. At this point, we stop threading the tube. 500px|center|epsilon tube The point is the member of the sequence, from which on all members (so those with index greater than or equal to ) will be inside the tube. In this illustration, directly before there is a point that is outside the tube (even by just a tiny amount). If we make the tube smaller, maybe some of the points that were inside the bigger one, now will be outside, and thus if your goal is to capture all later points inside you can't "push" the tube as far as the bigger one. But even with this smaller tube, it's still possible to capture almost all points: 500px|center|epsilon tube small The points that don't fit into the smaller tube are now more to the right than in the previous image. Let's call the first new member in the tube . All members with an index greater than or equal to will be inside the smaller tube. Of course, this "tube" has no mathematical meaning. We used it as a mental tool to show that the members of the sequence eventually stay as close to the dotted line as we prescribe. They keep approaching and will indeed not start drifting away from the dotted line, because we have seen that all members starting from a certain index will be inside the tube, no matter how small we choose to make it. If we understood that, we don't need the "tube" any more. We will replace our arbitrarily small "tube" with radius with a mathematical object we call an -neighbourhood (it sounds more scary than it really is). Every neighbourhood around the limit contains almost all members thumb|250px| The limit is a number with the property that for every -neighbourhood, almost all members of the sequence are contained in that neighbourhood around that number. We have found indices or , from which on all later members of the sequence will be contained in the respective -tube. If we make the tube smaller, then we can find another , from which on all members will be inside the tube and so on. No matter how small we choose our tube, we will always find a point so that all subsequent points are captured inside that "tube". Since all these starting indices are natural numbers, there are only finitely many members outside the tube (at most ). All other points are inside the tube. Since a sequence has infinitely many members, we can "ignore" the finite number of members that are outside and say that "almost all" members are inside the tube. This is still true, even if we choose to be really big. Compared to infinity, a finite amount – no matter how big you choose - is still little. Understanding this is important to understand the idea of limits. Let's repeat this one more time: No matter how small you choose your tube to be, almost all members will be captured inside it. That means that the members will approach . And this is the central idea about the limit. The members will get arbitrarily close to , if we choose a sufficiently large index . What is a neighbourhood of a number? We can construct the neighbourhood of a number geometrically with a circle. Let be the centre of a circle with radius . Then we have only marked the point on the number line. If we increase the radius of the circle, we see that the diameter expands from . On an intuitive level, a neighbourhood is a set of numbers that encloses . The points on the number line strictly inside this circle form an open interval. A neighbourhood of a number can be mathematically described by such an interval. The radius of the circle is the distance to the left and right boundary of the interval . The radius is an arbitrary (small) positive number . An interval of this sort is characterized as the set of all numbers that are less than apart from . Thus, these intervals will have the form . We call this interval -neighbourhood of , and it looks like this: center|500px|The epsilon-neighbourhood The -neighbourhood of will more generally define a neighbourhood of . A set is a neighbourhood of , if and only if there exists an -neighbourhood , such that . Let's see how this works by considering the following set : center|500px|Set M with inner point a on the line of numbers First, we need to find an -neighbourhood of . Choose an adequate and draw a circle with radius around . So that will mark an interval . The set is also an interval. It encloses the interval . Thus is a superset of the -neighbourhood of . So our definition says that is a neighbourhood of . center|500px|Set M with an interior point a and ε-neighbourhood around a Neighbourhood A set is a neighbourhood of a number , if there exists an , such that (i.e. an -neighbourhood is contained in ). What does "almost all" mean? To better understand this idea, imagine a coordinate system in which we have infinitely many members of a convergent sequence with limit . We thread a small -tube from the right over the limit. Then there are only a finite number of members which are outside the tube, because their distance to is not small enough. But infinitely many members are inside the interval and thus in the -tube. The number of members that are inside the interval is infinitely larger than the number outside. Therefore, it is reasonable to say that almost all members are inside . Another way of expressing this idea would be to say that all but finitely many members are contained in the -tube. A mathematical definition for the limit Now that we have an idea about what we are trying to define, we will try to find a rigorous mathematical definition. We start by observing that: "A sequence has a limit , if for every -neighbourhood of , i.e. , there exists a member such that it and all following members are inside the neighbourhood." We could already work with this definition. But for practical purposes, it is useful to further formalise this definition. Note that a member is an element of , if and only if . Thus: "A real-valued sequence has a limit if for every , there exists a member , starting from which all following members are less than away from , that means that they satisfy ." The part with "there exists a member, starting from which…" can be equivalently formulated as "there exists a natural number , so that for all with it follows that …". Thus: "A real-valued sequence has a limit if for every there exists a natural number , so that for all ." This is the mathematical definition of the limit. Definition of limit Limit A real-valued sequence has a limit if for every there exists an index , so that for every member with the inequality is true. So is a limit of if and only if: This is what the individual parts of the above formula mean: There are a few other important definitions when studying limits: Convergence A sequence is convergent, if the sequence has a limit. We say that the sequence converges towards , if there is a limit . Divergence If there is no limit, a sequence is called divergent. Thus, a sequence is divergent if it is not convergent. Null Sequence A sequence that has a limit of is called a Null Sequence. If a sequence converges to , we also write it like or " as ". We say "The limit of as goes to infinity is ". What is the formula in predicate logic to express that is convergent? As we discussed above, the formula to express that a sequence has a limit is the following: If we only want to express convergence, we do it like this: What is the formula in predicate logic to express that diverges? We need to negate the previous formula. How this is done correctly is explained in the Section „Negating statements“ in the book „Mathematical Fundamentals“. We need to invert the universal and existential quantifiers. The negated statement is: In words: For every there is a real number , so that for all there is an with . For the absolute value we have: . Thus, also: We could use either or in our definition of limit. ja From the definition of convergence it follows immediately that converges towards , if and only if is a Null Sequence. If converges to , then from the definition we see: But this is exactly the definition for what it means for to converge towards . If conversely converges to , we use the definition to conclude: But this implies that and the quantifiers and the variables in the formula don't change, so that converges to and thus is a Null Sequence. A common misconception is that "A sequence is divergent if and only if it is unbounded". This statement is false! The intuitive mistake that often happens is to assume that: „The opposite of is , thus must become arbitrarily large.“ But as we have seen this is not the definition of divergence! What is true is that every unbounded sequence is divergent (more on this in "Unbounded sequences diverge"), but not every divergent sequence must necessarily be unbounded. Take for example the following alternating sequence , which is in fact divergent but bounded. Explanation of convergence Besides the above derivation of limits, there is another intuition for the limit: The quantity is the distance between the n-th member and . It is a measure of the error between and . The inequality means that the error between and is guaranteed to be smaller than . Therefore, we can interpret the definition of limit as follows: No matter how small we choose our maximum error to be, almost all members are less than away from the limit . The error between the members and the limit becomes arbitrarily small. There are also historical reasons for this interpretation. Augustin-Louis Cauchy, who helped develop the concept of a limitsee w:en:Augustin-Louis Cauchy#Professor at École Polytechnique, maybe wanted to remind readers of the French word "erreur", which means "error".see http://web.archive.org/web/20130302094052/http://matheguru.com/analysis/24-grenzwerte.html. Example: Convergence of the harmonic progression thumb|300px|The first ten elements of the harmonic sequence Let's see these concepts in action by studying the harmonic progression with the generic member . It should be intuitive that this sequence converges towards . If this is correct, then this sequence should satisfy the definition for convergence towards . Take for example . Starting from the third member the distance between and is smaller than . All later members of this sequence are contained inside the -neighbourhood of . For this is true starting from and for starting from . But the definition of limit requires that this is true for all . Therefore, let us assume we are given an . From the Archimedean axiom it follows that there exists an , so that for all (See Archimedean Axiom with the choices of and .) From this onwards, all members are contained inside the -neighbourhood . The definition tells us that is the limit of the harmonic progression. The limit is unique Uniqueness of the limit The limit of a convergent sequence is unique. This theorem allows us to write things such as . Imagine that there is a sequence with more than one limit. Then it is not clear what the expression should stand for (there are two possibilities). But because we know that has a unique limit, it is clear that can only mean one thing, i.e. the (unique) limit of that sequence (if it is convergent). The above theorem allows us to talk about the limit and not a limit. We can prove this by contradiction. We assume that there is a sequence with two distinct limits. Now we need to show that this assumption will result in a contradiction, and that it therefore cannot be true. We label the two distinct limits and . To find a contradiction, we can use the following method: We try to prove the opposite of what we really want to show. Of course, we set ourselves up for failure. Why do we even try, then? Because by understanding why it fails, we get a lot of clues that will help us prove the right thing. So, for the sake of gathering insight, let us (try) to prove that there is a sequence with two distinct limits. Take a piece of paper and draw a line of real numbers. Mark two distinct numbers and that will represent our two limits. Now try to find a real sequence that converges to both these limits (Remember that starting from a certain index, your sequence has to be in an arbitrarily small -neighbourhood around and ). But for arbitrarily small -neighbourhoods of and , that do not intersect, it is impossible that almost all members are contained in both. The following drawing will highlight this problem: center|600px|Line of real numbers with two numbers and disjoint ε-neighbourhoods Thus, if we choose so small that and do not overlap, then we know that there must be a contradiction hiding somewhere (the one we need to prove our original proposition!). We choose . We know that there must be an that must be contained both in and . But such an cannot exist, since those two neighbourhoods can't intersect for . A contradiction emerges from the triangle inequality: We cancel both sides with and find the contradiction . Proof by contradiction: Let be a sequence with two distinct limits and . Distinct means that and therefore . Per definition, there exist and with and This follows from the definition of limit if we set . Thus, for all members with index , both and are true. In this case, we have: Because of we have and we can cancel both sides in the inequality with . This results in the contradiction: It is essential for this proof that and thus . Else we could not have divided by (division by zero!) and we could not have chosen . unten