My personal prediction for the 2013 Atlantic hurricane season is (written May 20, 2013):
18 cyclones attaining tropical depression status
16 cyclones attaining tropical storm status
9 cyclones attaining hurricane status
4 cyclones attaining major hurricane status
This predictions are slightly above normal for an Atlantic hurricane season, particularly in the hurricanes category.
The last decade or so has constituted by far the most active such period in known history for tropical cyclone formation. This may reflect a long-term cycle in Atlantic tropical cyclone activity, known as the Atlantic Multidecadal Oscillation (AMO). The AMO could theoretically explain, for example, the lull in formation in the 1980's and the recent surge in the 2000's.
However, the state of the El Nino is fairly neutral. It is fairly unlikely that a strong El Nino or La Nina event will develop significantly before the conclusion of this year's hurricane season. A neutral state of the ENSO would suggest a fairly average season. This reasoning, coupled with the fact that the Altantic basin is still in a long-term active period, suggests a slightly above above normal hurricane season.
Finally, sea surface temperatures near the U.S., especially near the Gulf Coast, are below normal, and well below where they were in May 2012, partially stemming from a much colder winter and early spring across several areas of the country. Favorable conditions may then be slow to reach areas near the U.S., though this of course does not exclude powerful mid- or late-season storms.
Below, my anticipated risk factors for four major regions of the Atlantic basin are listed. The risk index runs from 1 meaning very low potential to 5 being very high potential.
U.S. East Coast: 3
Though the Bermuda High is still far to the east, near the Azores, small blocking ridges may be frequent in the western Atlantic, so tropical cyclones could very well be steered towards the east coast. Again, such an event is unlikely towards the beginning of the season due to cooler waters and anomalously high wind shear, but the risk near the end of the season is higher.
U.S. Gulf Coast/Northern Mexico: 2
The Gulf of Mexico has not only been anomalously cool, but also the jet stream has dipped well into the U.S. Midwest over the first few months of this year. Such events cause disturbed weather to be frequent, but generally inhibit cyclone formation. As such, the Gulf coasts of U.S. and Mexico are relatively protected, though there is still potential for a sufficiently powerful cyclone to track through the Gulf and make landfall. Also, Florida is at an above average risk, despite the low Gulf index overall.
Yucatan Peninsula and Central America: 3
As usual, the Yucatan and surrounding areas can expect some tropical cyclone activity, particularly in the form of weak systems. The eastern Atlantic is warm and conditions will be favorable for the development of tropical waves before such waves enter the southwestern Caribbean, so stronger storms will almost certainly track to the north.
Caribbean Islands: 5
It has been a few years since a "traditional" Cape Verde hurricane has formed in the east Atlantic and stayed on a westerly path over the Caribbean Islands. However, the likely development of temporary ridges over the tropical Atlantic would push even strong hurricanes on such a path. The strongest cyclones of the season are likely to come over, or pass close to, these islands.
Overall, a slightly above average 2013 season is expected, with particular risk to the Caribbean Islands and the southeast U.S.. Since the climate of the Atlantic region is less volatile than last year, there may be fewer meandering storms such as Hurricane Nadine, and fewer unusual jet stream interactions, such as the one which caused Hurricane Sandy to make landfall in the northeast.
Wednesday, May 22, 2013
Thursday, May 16, 2013
Hurricane Names List-2013
For the North Atlantic Basin, the hurricane names list for 2013 is as follows:
Andrea
Barry
Chantal
Dorian
Erin
Fernand
Gabrielle
Humberto
Ingrid
Jerry
Karen
Lorenzo
Melissa
Nestor
Olga
Pablo
Rebekah
Sebastien
Tanya
Van
Wendy
This list is the same as that of the 2007 Atlantic Hurricane Season, except for the addition of Dorian, Fernand, and Nestor, to replaced retired hurricanes Dean, Felix, and Noel, respectively.
Andrea
Barry
Chantal
Dorian
Erin
Fernand
Gabrielle
Humberto
Ingrid
Jerry
Karen
Lorenzo
Melissa
Nestor
Olga
Pablo
Rebekah
Sebastien
Tanya
Van
Wendy
This list is the same as that of the 2007 Atlantic Hurricane Season, except for the addition of Dorian, Fernand, and Nestor, to replaced retired hurricanes Dean, Felix, and Noel, respectively.
Tuesday, April 30, 2013
The Arctic and North Atlantic Oscillations
The Arctic Oscillation (AO) and North Atlantic Oscillation (NAO) are two climatological phenomena that characterize the changes in atmospheric pressure over their respective regions, the Arctic, and the North Atlantic.
Based on anomalies in the pressure of the regions from their long-term averages (computed over a period of over 100 years), the oscillations are assigned parameters, called the AO index and NAO index, respectively, which change with time. The sign of the parameter (whether it is positive or negative) can predict certain features of the climate of much of the northern hemisphere, and are particularly important in the winter.
The Arctic Oscillation index is computed from the pressures of the subtropical and subarctic regions. The pressure gradient between the two latitudes determines the sign of the AO index. If pressures are higher in the subtropics than normal and lower in the subarctic, the AO index is positive, and the AO is said to be in its positive phase, while if subtropical pressures are anomalously low and subarctic pressures anomalously high, the AO index is negative, and the AO is said to be in its negative phase.
The above figure shows the general shape of the path of the jet stream during positive and negative phases of the AO. During positive AO, the jet stream tends to be stronger and more linear in its path during the winter, locking cold air in the Arctic regions and generally leading to warmer winters in the subtropical regions. Since the position of the jet stream allows tropical moisture to venture farther north, the subtropics are also generally wetter during these periods.
When the AO index is negative, the jet stream becomes more sinusoidal, with the amplitude of the variations in the jet stream's latitude generally proportional to the magnitude of the negative phase. Where the jet stream dips south, large masses of cold air can engulf regions for days or weeks, generally resulting in colder, snowier winters. At the same time, however, the upswings in the jet stream can bring warm air to generally cold areas. Winters in the northern hemisphere with a negative AO index generally tend to be more volatile.
The NAO is closely related to the AO, except that the index is determined only by the pressure gradient between latitudes only in a very specific region: the North Atlantic near 30°W longitude, or the subtropical region near the Azores Islands, and the Arctic region near Iceland. The effects of the NAO on the jet stream are similar to the AO, but they are not the same. The NAO index is generally a very good indicator of the winter temperature anomaly in the eastern U.S. and Europe, and though its sign usually agrees with that of the AO, this is not always the case:
The graphs of the AO index (top) and the NAO index (bottom) over the winters of roughly the same time period, from the late 1800's to the early 2000's. The indices clearly are related; both are predominantly negative in the period 1960-1980 and predominantly positive from 1980 to 2000, but on some years, they disagree. For example, if the NAO index is positive and the AO index negative, the jet stream may be straight over the Atlantic, bringing warm air to the eastern U.S. and western Europe, but sinusoidal elsewhere. This happened, for example, in the winter of 2011-2012. Conversely, if the NAO index is negative and the AO positive, there may be a large dip in the jet stream over the U.S. and a weak pressure gradient over the Atlantic, but cold air masses may be fairly well confined to the Arctic at other longitudes. This situation occurred in the winter of 2008-2009.
These oscillations, relative to El Nino and La Nina, are notoriously hard to predict. In addition, while the weather of any given winter is influenced by the El Nino/La Nina, the AO, and the NAO, many other factors also come into play. However, the fairly consistent accuracy with which the AO and NAO have predicted the winter weather of North America and Europe serve to exemplify the importance of atmospheric phenomena even in determining the climate of a region thousands of miles away.
Sources: The Winters of Our Discontent from The Scientific America, December 2012, AO and NAO on Wikipedia
Based on anomalies in the pressure of the regions from their long-term averages (computed over a period of over 100 years), the oscillations are assigned parameters, called the AO index and NAO index, respectively, which change with time. The sign of the parameter (whether it is positive or negative) can predict certain features of the climate of much of the northern hemisphere, and are particularly important in the winter.
The Arctic Oscillation index is computed from the pressures of the subtropical and subarctic regions. The pressure gradient between the two latitudes determines the sign of the AO index. If pressures are higher in the subtropics than normal and lower in the subarctic, the AO index is positive, and the AO is said to be in its positive phase, while if subtropical pressures are anomalously low and subarctic pressures anomalously high, the AO index is negative, and the AO is said to be in its negative phase.
The above figure shows the general shape of the path of the jet stream during positive and negative phases of the AO. During positive AO, the jet stream tends to be stronger and more linear in its path during the winter, locking cold air in the Arctic regions and generally leading to warmer winters in the subtropical regions. Since the position of the jet stream allows tropical moisture to venture farther north, the subtropics are also generally wetter during these periods.
When the AO index is negative, the jet stream becomes more sinusoidal, with the amplitude of the variations in the jet stream's latitude generally proportional to the magnitude of the negative phase. Where the jet stream dips south, large masses of cold air can engulf regions for days or weeks, generally resulting in colder, snowier winters. At the same time, however, the upswings in the jet stream can bring warm air to generally cold areas. Winters in the northern hemisphere with a negative AO index generally tend to be more volatile.
The NAO is closely related to the AO, except that the index is determined only by the pressure gradient between latitudes only in a very specific region: the North Atlantic near 30°W longitude, or the subtropical region near the Azores Islands, and the Arctic region near Iceland. The effects of the NAO on the jet stream are similar to the AO, but they are not the same. The NAO index is generally a very good indicator of the winter temperature anomaly in the eastern U.S. and Europe, and though its sign usually agrees with that of the AO, this is not always the case:
The graphs of the AO index (top) and the NAO index (bottom) over the winters of roughly the same time period, from the late 1800's to the early 2000's. The indices clearly are related; both are predominantly negative in the period 1960-1980 and predominantly positive from 1980 to 2000, but on some years, they disagree. For example, if the NAO index is positive and the AO index negative, the jet stream may be straight over the Atlantic, bringing warm air to the eastern U.S. and western Europe, but sinusoidal elsewhere. This happened, for example, in the winter of 2011-2012. Conversely, if the NAO index is negative and the AO positive, there may be a large dip in the jet stream over the U.S. and a weak pressure gradient over the Atlantic, but cold air masses may be fairly well confined to the Arctic at other longitudes. This situation occurred in the winter of 2008-2009.
These oscillations, relative to El Nino and La Nina, are notoriously hard to predict. In addition, while the weather of any given winter is influenced by the El Nino/La Nina, the AO, and the NAO, many other factors also come into play. However, the fairly consistent accuracy with which the AO and NAO have predicted the winter weather of North America and Europe serve to exemplify the importance of atmospheric phenomena even in determining the climate of a region thousands of miles away.
Sources: The Winters of Our Discontent from The Scientific America, December 2012, AO and NAO on Wikipedia
Monday, April 15, 2013
More About Constructible Numbers and Figures
This series of posts deals with determining which geometric figures are "constructible", that is, can be formed using only a compass and straightedge.
The set of constructible real numbers, or those numbers whose absolute value is equal to the length of a line segment constructible with compass and straightedge, has already been shown to be of the type called a field. In addition, this field contains all of the rational numbers. But what others, if any, does it contain?
It may be noted that the circle has not featured in any of the constructions thus far. In fact, by use of a circle, one can construct a segment whose length is the (positive) square root of that of a given segment. The construction is illustrated below.
A segment of length a1/2 is constructed by first drawing segments of length 1 and a on end (1). Then, a circle is drawn with the combined segment (of length 1 + a) as a diameter (2). Finally, a perpendicular is erected from the diameter at the point of intersection of the two segments to the circle, and two other segments are drawn connecting the point of intersection of the perpendicular and the circle to the endpoints of the diameter (3). The resulting figure has three triangles, the largest partitioned into the two smaller by the perpendicular. One need only observe that the large triangle is a right triangle, as one of its angles subtends a semicircular arc, and since this large triangle shares a side and an angle with each of the two smaller right triangles, it is similar to each. The two smaller right triangles are then also perpendicular to each other, and so the ratio of 1 to the length of the perpendicular must be equivalent to the ratio of the same length to a. The length of the perpendicular is thus the square root of a.
Thus the field of constructible numbers includes any number that can be derived from a finite sequence of additions, subtractions, multiplications, divisions, and square roots from the unit length 1. In fact, these are all of the constructible numbers. To see this, note first that the construction of segments in the plane involves only the intersections of lines and/or circles. The general equation for a line is ax + by = c, a linear equation, and the general equation for a circle is (x - h)2 + (y - k)2 = r2. It is clear that in solving for the intersection of these two types of functions, the highest degree one could encounter for the intersection points to satisfy is 2, i.e., a quadratic. Finally, by the quadratic formula and the distance formula, which each involve only square roots, the most general type of number one can construct can be seen to be one involving nested square roots, a conclusion in agreement with the previous result.
To illustrate the power of this new concept, we know turn to some applications. First, we relate our result to the geometric construction problems posed at the beginning of this series of posts:
Example 1:
The problem of "squaring the circle" was shown to require the constructibility of the length π1/2. This condition is equivalent to the constructibility of π and is therefore impossible, as π is what is called a transcendental irrational number; there is no polynomial with integer (or rational, by extension) coefficients with π as a root.
Example 2:
"Doubling the cube" was shown to require the constructibility of a segment of length 21/3. This problem is impossible as well, because though there is a polynomial with this number as a root, namely x3 - 2 = 0, this polynomial is of degree 3, not 2, and cannot be factored in any way to reduce its degree. Please note that even though a number such as 21/4 is the root of the degree 4 polynomial x4 - 2 = 0, the substitution y = x2 reduces it to two polynomials of degree 2, and this number is thus constructible.
Example 3: To illustrate the applicability of this concept to figures that actually are constructible, consider the equilateral triangle. Since all three sides are of the same (arbitrary) length, the ability to draw an equilateral triangle depends on its angles, all of which are 60°. To equate the construction of an angle to the construction of a segment, we use trigonometry:
The above figure illustrates that the constructbility of the angle 60° is equivalent to that of the segments of lengths cos(60°) = 1/2 and sin(60°) = 31/2/2. If they are given, a right triangle can be drawn with legs of these lengths, thereby giving the angle. Since 31/2/2 involves only a square root, it is constructible, and 1/2 obviously is. Thus the equilateral triangle can be drawn with compass and straightedge as well.
The problem of constructibility played a greater role in ancient times than it does today. The standards that constitute "existence" for a mathematical object, though still debated, are much looser than in the time of the Ancient Greek mathematicians. For example, we now accept cubic curves, for example, as perfectly reasonable mathematical objects, even though they cannot be constructed with compass and straightedge (in fact, an arbitary point on one of these curves may not be constructible). The problem now mainly serves as a mathematical curiosity, and as an example of how one can calculate the power, in this case the constructing power, of certain systems in mathematics.
Sources: A First Course in Abstract Algebra by John B. Fraleigh, Constructible Number on Wikipedia
The set of constructible real numbers, or those numbers whose absolute value is equal to the length of a line segment constructible with compass and straightedge, has already been shown to be of the type called a field. In addition, this field contains all of the rational numbers. But what others, if any, does it contain?
It may be noted that the circle has not featured in any of the constructions thus far. In fact, by use of a circle, one can construct a segment whose length is the (positive) square root of that of a given segment. The construction is illustrated below.
A segment of length a1/2 is constructed by first drawing segments of length 1 and a on end (1). Then, a circle is drawn with the combined segment (of length 1 + a) as a diameter (2). Finally, a perpendicular is erected from the diameter at the point of intersection of the two segments to the circle, and two other segments are drawn connecting the point of intersection of the perpendicular and the circle to the endpoints of the diameter (3). The resulting figure has three triangles, the largest partitioned into the two smaller by the perpendicular. One need only observe that the large triangle is a right triangle, as one of its angles subtends a semicircular arc, and since this large triangle shares a side and an angle with each of the two smaller right triangles, it is similar to each. The two smaller right triangles are then also perpendicular to each other, and so the ratio of 1 to the length of the perpendicular must be equivalent to the ratio of the same length to a. The length of the perpendicular is thus the square root of a.
Thus the field of constructible numbers includes any number that can be derived from a finite sequence of additions, subtractions, multiplications, divisions, and square roots from the unit length 1. In fact, these are all of the constructible numbers. To see this, note first that the construction of segments in the plane involves only the intersections of lines and/or circles. The general equation for a line is ax + by = c, a linear equation, and the general equation for a circle is (x - h)2 + (y - k)2 = r2. It is clear that in solving for the intersection of these two types of functions, the highest degree one could encounter for the intersection points to satisfy is 2, i.e., a quadratic. Finally, by the quadratic formula and the distance formula, which each involve only square roots, the most general type of number one can construct can be seen to be one involving nested square roots, a conclusion in agreement with the previous result.
To illustrate the power of this new concept, we know turn to some applications. First, we relate our result to the geometric construction problems posed at the beginning of this series of posts:
Example 1:
The problem of "squaring the circle" was shown to require the constructibility of the length π1/2. This condition is equivalent to the constructibility of π and is therefore impossible, as π is what is called a transcendental irrational number; there is no polynomial with integer (or rational, by extension) coefficients with π as a root.
Example 2:
"Doubling the cube" was shown to require the constructibility of a segment of length 21/3. This problem is impossible as well, because though there is a polynomial with this number as a root, namely x3 - 2 = 0, this polynomial is of degree 3, not 2, and cannot be factored in any way to reduce its degree. Please note that even though a number such as 21/4 is the root of the degree 4 polynomial x4 - 2 = 0, the substitution y = x2 reduces it to two polynomials of degree 2, and this number is thus constructible.
Example 3: To illustrate the applicability of this concept to figures that actually are constructible, consider the equilateral triangle. Since all three sides are of the same (arbitrary) length, the ability to draw an equilateral triangle depends on its angles, all of which are 60°. To equate the construction of an angle to the construction of a segment, we use trigonometry:
The above figure illustrates that the constructbility of the angle 60° is equivalent to that of the segments of lengths cos(60°) = 1/2 and sin(60°) = 31/2/2. If they are given, a right triangle can be drawn with legs of these lengths, thereby giving the angle. Since 31/2/2 involves only a square root, it is constructible, and 1/2 obviously is. Thus the equilateral triangle can be drawn with compass and straightedge as well.
The problem of constructibility played a greater role in ancient times than it does today. The standards that constitute "existence" for a mathematical object, though still debated, are much looser than in the time of the Ancient Greek mathematicians. For example, we now accept cubic curves, for example, as perfectly reasonable mathematical objects, even though they cannot be constructed with compass and straightedge (in fact, an arbitary point on one of these curves may not be constructible). The problem now mainly serves as a mathematical curiosity, and as an example of how one can calculate the power, in this case the constructing power, of certain systems in mathematics.
Sources: A First Course in Abstract Algebra by John B. Fraleigh, Constructible Number on Wikipedia
Sunday, April 7, 2013
Constructible Numbers and Figures
The problem of constructible figures—determining which geometrical objects can be constructed using only the straightedge and compass—was a longstanding problem of mathematics, resolved in the early 19th century. It is closely related to the famous problems of squaring the circle (constructing a square of equal area to a given circle) doubling the cube (finding a cube with double the volume of a given cube), and trisecting the angle (constructing an angle with measure exactly a third of a given one), and actually encompasses these problems, as we shall see below.
The Ancient Greeks did not merely focus on the problem of determining which figures were constructible to categorize geometric objects—their standards of rigor were such that, if a curve or figure could not be constructed, they did not consider it to exist!
But, as we shall show, the problem of constructible figures can be reduced to determining what length line segments can be constructed. Thus the set of constructible figures is determined by a set of real numbers that corresponds to a set of line segments with these numbers as lengths. To illustrate this concept, we will reduce a few of the problems mentioned above to the problem of constructing a line segment of a given length.
The problem of squaring the circle can be reduced to finding a line segment that is one side of the square, i.e., constructing a line segment of length π1/2. (More precisely, the construction requires the ability to construct a line segment whose length forms a ratio of π1/2 to the radius of the circle. However, assuming the base segment to be of length 1, the problem reduces to the one above)
The problem of doubling the cube is technically in three-dimensions, but it depends on the ability, in plane geometry, to construct a line segment of length 21/3 (again, this is actually the ratio of the side of the larger cube to that of the smaller).
Many other construction problems can similarly be translated into the language of lengths of line segments or ratios of such. Now, the problem is to find what lengths can be constructed. First, we determine what sort of set the set of constructible lengths is. To do this, consider two lengths a and b that are given to be constructible. In other words, if one were forming geometric objects on a piece of paper, one would have, in addition to a compass and straightedge, objects of length a and b from which things can be measured. What other lengths can be obtained from these?
Clearly, given lengths a and b, one can place two lines of these respective lengths end to end, giving a line of length a + b.
Similarly, the length b - a can be constructed from lines of respective lengths a and b. Some care must be taken here, as this construction only yields a positive number for the length of b - a if the length b is greater than the length a. Alternatively, one could consider oriented line segments, or vectors, with initial and terminal points that can be "negative". Here we shall limit ourselves to regular line segments, but allow negative values to be members of the set of constructible lengths. Hence a real number x is a member of the set if its absolute value is the length of a constructible line segment.
Constructing a line segment whose length is the product of two given numbers is a little trickier. In the above figure, we assume a and b to be positive. First, mark a line segment of length a on a given ray, beginning at the endpoint of the ray. Then, draw any other ray out of the endpoint not coincident with the first ray (1). On this second ray, mark two segments beginning from the endpoint of lengths 1 and b. Draw a line segment, l, connecting the the other end of the line segment of length 1 to the end of the segment of length a (2). Finally, draw a line, k, through the end of the segment of length b parallel to l. The intersection of this line with the initial ray demarcates a line segment of length ab from the endpoint. This conclusion follows from the similar triangle law, as the ratio of 1 to a is the same as the ratio of b to ab.
A similar method, again using similar triangles and ratios involving their sides, brings about a segment of length a/b for positive a and b. Begin by marking a line segment of length a along a ray, and draw another ray sharing its endpoint with the first (1). On the second ray, draw a line segment of length b from the endpoint, and connect the opposite end of that segment with that of the segment of length a, forming l (2). Finally, draw the line segment k, beginning at the point on the second ray one unit away from the endpoint (3). The intersection of k with the first ray will define a segment of length a/b, as the ratio of b to a is the same as that of 1 to a/b.
Therefore, given lengths a and b, one can construct a + b, a - b, ab, and a/b. In other words, performing any of these operations on two members of the set of constructible lengths creates another constructible length. The set is said to be closed under these operations. In addition, it is interesting to note that the unit length 1 is needed to compute the product and quotient of lengths. Therefore, we assume all lengths to be in terms of the unit 1, which is also given. Finally, we assume the existence of the length 0, which is simply a point. (It is easy to confirm that the algebraic properties of 0 are satisfied by its geometric counterpart. If one takes b to be 0 in the diagram for division, the line l coincides with the first ray, and the line k, being parallel to l but through a different point, never intersects the first ray. This is consistent with division by zero being undefined.)
A set of this type, closed under addition, subtraction, multiplication, and division, and including 0 and 1, (though division by 0 is undefined) is called a field. Thus the set of constructible real numbers is a field. Any rational function of a and b is a member of this field, where a rational function of a and b is a quotient of polynomials f(a,b)/g(a,b) where both are of finite degree and g(a,b) does not equal 0. Thus the set of constructible real numbers contains all rational numbers, a rather intuitive conclusion. The question of what other numbers the set contains, and its consequences on the motivating problems discussed above, is addressed in the next post, coming April 15.
Sources: History of Mathematical Thought from Ancient to Modern Times, vol. 2, by Morris Kline, A First Course in Abstract Algebra by John B. Fraleigh
The Ancient Greeks did not merely focus on the problem of determining which figures were constructible to categorize geometric objects—their standards of rigor were such that, if a curve or figure could not be constructed, they did not consider it to exist!
But, as we shall show, the problem of constructible figures can be reduced to determining what length line segments can be constructed. Thus the set of constructible figures is determined by a set of real numbers that corresponds to a set of line segments with these numbers as lengths. To illustrate this concept, we will reduce a few of the problems mentioned above to the problem of constructing a line segment of a given length.
The problem of squaring the circle can be reduced to finding a line segment that is one side of the square, i.e., constructing a line segment of length π1/2. (More precisely, the construction requires the ability to construct a line segment whose length forms a ratio of π1/2 to the radius of the circle. However, assuming the base segment to be of length 1, the problem reduces to the one above)
The problem of doubling the cube is technically in three-dimensions, but it depends on the ability, in plane geometry, to construct a line segment of length 21/3 (again, this is actually the ratio of the side of the larger cube to that of the smaller).
Many other construction problems can similarly be translated into the language of lengths of line segments or ratios of such. Now, the problem is to find what lengths can be constructed. First, we determine what sort of set the set of constructible lengths is. To do this, consider two lengths a and b that are given to be constructible. In other words, if one were forming geometric objects on a piece of paper, one would have, in addition to a compass and straightedge, objects of length a and b from which things can be measured. What other lengths can be obtained from these?
Clearly, given lengths a and b, one can place two lines of these respective lengths end to end, giving a line of length a + b.
Similarly, the length b - a can be constructed from lines of respective lengths a and b. Some care must be taken here, as this construction only yields a positive number for the length of b - a if the length b is greater than the length a. Alternatively, one could consider oriented line segments, or vectors, with initial and terminal points that can be "negative". Here we shall limit ourselves to regular line segments, but allow negative values to be members of the set of constructible lengths. Hence a real number x is a member of the set if its absolute value is the length of a constructible line segment.
Constructing a line segment whose length is the product of two given numbers is a little trickier. In the above figure, we assume a and b to be positive. First, mark a line segment of length a on a given ray, beginning at the endpoint of the ray. Then, draw any other ray out of the endpoint not coincident with the first ray (1). On this second ray, mark two segments beginning from the endpoint of lengths 1 and b. Draw a line segment, l, connecting the the other end of the line segment of length 1 to the end of the segment of length a (2). Finally, draw a line, k, through the end of the segment of length b parallel to l. The intersection of this line with the initial ray demarcates a line segment of length ab from the endpoint. This conclusion follows from the similar triangle law, as the ratio of 1 to a is the same as the ratio of b to ab.
A similar method, again using similar triangles and ratios involving their sides, brings about a segment of length a/b for positive a and b. Begin by marking a line segment of length a along a ray, and draw another ray sharing its endpoint with the first (1). On the second ray, draw a line segment of length b from the endpoint, and connect the opposite end of that segment with that of the segment of length a, forming l (2). Finally, draw the line segment k, beginning at the point on the second ray one unit away from the endpoint (3). The intersection of k with the first ray will define a segment of length a/b, as the ratio of b to a is the same as that of 1 to a/b.
Therefore, given lengths a and b, one can construct a + b, a - b, ab, and a/b. In other words, performing any of these operations on two members of the set of constructible lengths creates another constructible length. The set is said to be closed under these operations. In addition, it is interesting to note that the unit length 1 is needed to compute the product and quotient of lengths. Therefore, we assume all lengths to be in terms of the unit 1, which is also given. Finally, we assume the existence of the length 0, which is simply a point. (It is easy to confirm that the algebraic properties of 0 are satisfied by its geometric counterpart. If one takes b to be 0 in the diagram for division, the line l coincides with the first ray, and the line k, being parallel to l but through a different point, never intersects the first ray. This is consistent with division by zero being undefined.)
A set of this type, closed under addition, subtraction, multiplication, and division, and including 0 and 1, (though division by 0 is undefined) is called a field. Thus the set of constructible real numbers is a field. Any rational function of a and b is a member of this field, where a rational function of a and b is a quotient of polynomials f(a,b)/g(a,b) where both are of finite degree and g(a,b) does not equal 0. Thus the set of constructible real numbers contains all rational numbers, a rather intuitive conclusion. The question of what other numbers the set contains, and its consequences on the motivating problems discussed above, is addressed in the next post, coming April 15.
Sources: History of Mathematical Thought from Ancient to Modern Times, vol. 2, by Morris Kline, A First Course in Abstract Algebra by John B. Fraleigh
Saturday, March 30, 2013
Banach-Tarski Paradox II
This is the second post concerning the Banach-Tarski paradox. For the first, see here.
The Banach-Tarski paradox allows one to, through decomposition and reassembly, turn one three-dimensional ball into two without changing the individual pieces, apparently violating the additivity of volume in Euclidean three-dimensional space. In the previous post, a decomposition of the group F2, roughly the set of finite strings of the symbols "a" and "b", was shown to yield two copies of the same group when the pieces were "translated" in a certain sense.
In carrying over the properties of F2 into three-dimensional space, one treats the symbols a and b as rotations about axes in Euclidean three-dimensional space. Traditionally, the axes are considered to be the x- and z-axes of Cartesian coordinates. In fact, the necessity of a choice of axes is why a paradoxical decomposition can only occur in dimensions of three and above, and not in two. This is because, in F2, the strings ab and ba are distinct; following their respective paths on the Cayley graph yields two different points. In two dimensions, any two rotations about the origin are commutative, i.e. can be performed in either order with the same result. Since the noncommutativity of F2 cannot be carried over into two-dimensional space, the paradox is not possible there.
The rotations that correspond to a and b are taken to move through an angle of the inverse cosine of 1/3, or about 70.5°. This exact angle choice is unnecessary, but the angles chosen for a and b must be irrational multiples of a right angle. This is because no two linear combinations of them can be allowed to yield the same rotation; all linear combinations of the angles must be distinct. The purpose of this condition is to mimic a property of the group F2, namely that no two distinct simplified strings represent the same element, or, in other words, no two distinct paths (without retracing) lead to the same point on the Cayley graph.
Next, we briefly restrict our attention to the sphere (which, unlike the ball, does not include the interior area; the sphere is as the surface of the earth and the ball like the surface as well as the interior). The set F2, which we shall now consider a group of rotations, can act on any point p of the sphere. The set of points thus obtained, following any sequence of rotations (each corresponding to an element of F2) beginning at p, is called the orbit of p.
In this way, the entire surface of the sphere can be partitioned into an infinite set of these orbits, none of which overlap. Since a set of finite sequences is countable, F2 is as well. Since the number of points on the sphere is uncountably infinite, it follows that there are uncountably many of these orbits. Here the axiom of choice is invoked to select a single point from each orbit, and collect these into another set M.
The details involved in explicitly applying the decomposition of the sphere are too technical to consider here; the above steps were included to illustrate the use of the axiom of choice. The next step essentially brings about the paradoxical decomposition of the sphere by shifting M by the rotations a and b. Two copies of the sphere arise in a manner similar to that of F2.
Finally, the result is extended to the three-dimensional ball by performing the decomposition on a continuum of spheres of radii 0<r<R, where R is the original radius of the ball being considered. Each point p on the outer sphere can be paired to a point on any of the smaller spheres by projecting inward along the ray from p to the origin (see below). Clearly the union of all these spheres contains all the points of the ball, with the exception of the origin, O.
The final obstacle, therefore, is proving that the ball with its center removed can be decomposed and reassembled to form the entire ball. In fact, there are subtle difficulties in doing this that do not concern us here. Once this is done, the Banach-Tarski theorem is proven.
Following this technical formulation, it is enlightening to step back and consider the implications of the paradox. It is important to see that the decomposition above could not be applied to a physical object. The above procedure depends on the infinite divisibility of the ball, which an object composed of matter does not possess. Additionally, the pieces in the decomposition, though finite in number, are not "chunks" of the ball but infinite collections of points, and so are not physically continuous.
Though inapplicable to the physical world, the Banach-Tarski paradox helps to elucidate the fundamental differences between mathematical and physical space, and the wide-reaching consequences of assuming statements such as the axiom of choice.
In response to this and similar paradoxes that follow from the axiom of choice, there have been attempts to appropriately weaken the axiom of choice to an axiom which, though giving most of the same benefits, eliminates the paradoxes. One of these is called the axiom of countable choice, which limits the applicability of the axiom to countable sets. This avoids the Banach-Tarski paradox, but some set theoretical results are lost. In addition, the rather arbitrary restriction to countable sets seems inelegant, as it complicates the axiom, bringing in more concepts.
Also, some interesting work has been done since the Banach-Tarski paradox was published in 1924 that has extended the result. First, the final step of the proof above, in its original form, involved a total of 24 pieces. Through an alteration of the orbit scheme above, the number of pieces can be reduced to five.
Furthermore, the beginning and ending sets can be more general than simply a ball and two balls. Clearly, by a repetition of the above process, any (finite) number of balls can be produced by decomposition. It has even been shown that, if the original ball can be decomposed into an infinite number of pieces, one can obtain infinitely many copies of the ball, and even uncountably many. By allowing these decompositions, we can simply conjure up as many balls as we want from a single one!
In fact, the statement has been generalized even further to allow any bounded three-dimensional regions which are not "empty" to be broken up into a finite number of pieces and reassembled into any other of these regions.
The Banach-Tarski paradox is central in proving that there is no finitely additive measure in three-dimensional (and higher) spaces which agrees with the basic conception of volume. In one and two dimensions, there still is no countably additive measure that can be universally applied due to the existence of non-measurable sets (see again the Lebesgue measure series for an example of a measure in mathematics). The above are a few of the surprising geometric applications of the axiom of choice, showing how pervasive this assumption is, even beyond its native set theory.
Sources: http://www.math.hmc.edu/~su/papers.dir/banachtarski.pdf, http://www.bsu.edu/libraries/virtualpress/mathexchange/05-01/Coleman.pdf, Banach-Tarski Paradox at Wikipedia
The Banach-Tarski paradox allows one to, through decomposition and reassembly, turn one three-dimensional ball into two without changing the individual pieces, apparently violating the additivity of volume in Euclidean three-dimensional space. In the previous post, a decomposition of the group F2, roughly the set of finite strings of the symbols "a" and "b", was shown to yield two copies of the same group when the pieces were "translated" in a certain sense.
In carrying over the properties of F2 into three-dimensional space, one treats the symbols a and b as rotations about axes in Euclidean three-dimensional space. Traditionally, the axes are considered to be the x- and z-axes of Cartesian coordinates. In fact, the necessity of a choice of axes is why a paradoxical decomposition can only occur in dimensions of three and above, and not in two. This is because, in F2, the strings ab and ba are distinct; following their respective paths on the Cayley graph yields two different points. In two dimensions, any two rotations about the origin are commutative, i.e. can be performed in either order with the same result. Since the noncommutativity of F2 cannot be carried over into two-dimensional space, the paradox is not possible there.
The rotations that correspond to a and b are taken to move through an angle of the inverse cosine of 1/3, or about 70.5°. This exact angle choice is unnecessary, but the angles chosen for a and b must be irrational multiples of a right angle. This is because no two linear combinations of them can be allowed to yield the same rotation; all linear combinations of the angles must be distinct. The purpose of this condition is to mimic a property of the group F2, namely that no two distinct simplified strings represent the same element, or, in other words, no two distinct paths (without retracing) lead to the same point on the Cayley graph.
Next, we briefly restrict our attention to the sphere (which, unlike the ball, does not include the interior area; the sphere is as the surface of the earth and the ball like the surface as well as the interior). The set F2, which we shall now consider a group of rotations, can act on any point p of the sphere. The set of points thus obtained, following any sequence of rotations (each corresponding to an element of F2) beginning at p, is called the orbit of p.
In this way, the entire surface of the sphere can be partitioned into an infinite set of these orbits, none of which overlap. Since a set of finite sequences is countable, F2 is as well. Since the number of points on the sphere is uncountably infinite, it follows that there are uncountably many of these orbits. Here the axiom of choice is invoked to select a single point from each orbit, and collect these into another set M.
The details involved in explicitly applying the decomposition of the sphere are too technical to consider here; the above steps were included to illustrate the use of the axiom of choice. The next step essentially brings about the paradoxical decomposition of the sphere by shifting M by the rotations a and b. Two copies of the sphere arise in a manner similar to that of F2.
Finally, the result is extended to the three-dimensional ball by performing the decomposition on a continuum of spheres of radii 0<r<R, where R is the original radius of the ball being considered. Each point p on the outer sphere can be paired to a point on any of the smaller spheres by projecting inward along the ray from p to the origin (see below). Clearly the union of all these spheres contains all the points of the ball, with the exception of the origin, O.
The final obstacle, therefore, is proving that the ball with its center removed can be decomposed and reassembled to form the entire ball. In fact, there are subtle difficulties in doing this that do not concern us here. Once this is done, the Banach-Tarski theorem is proven.
Following this technical formulation, it is enlightening to step back and consider the implications of the paradox. It is important to see that the decomposition above could not be applied to a physical object. The above procedure depends on the infinite divisibility of the ball, which an object composed of matter does not possess. Additionally, the pieces in the decomposition, though finite in number, are not "chunks" of the ball but infinite collections of points, and so are not physically continuous.
Though inapplicable to the physical world, the Banach-Tarski paradox helps to elucidate the fundamental differences between mathematical and physical space, and the wide-reaching consequences of assuming statements such as the axiom of choice.
In response to this and similar paradoxes that follow from the axiom of choice, there have been attempts to appropriately weaken the axiom of choice to an axiom which, though giving most of the same benefits, eliminates the paradoxes. One of these is called the axiom of countable choice, which limits the applicability of the axiom to countable sets. This avoids the Banach-Tarski paradox, but some set theoretical results are lost. In addition, the rather arbitrary restriction to countable sets seems inelegant, as it complicates the axiom, bringing in more concepts.
Also, some interesting work has been done since the Banach-Tarski paradox was published in 1924 that has extended the result. First, the final step of the proof above, in its original form, involved a total of 24 pieces. Through an alteration of the orbit scheme above, the number of pieces can be reduced to five.
Furthermore, the beginning and ending sets can be more general than simply a ball and two balls. Clearly, by a repetition of the above process, any (finite) number of balls can be produced by decomposition. It has even been shown that, if the original ball can be decomposed into an infinite number of pieces, one can obtain infinitely many copies of the ball, and even uncountably many. By allowing these decompositions, we can simply conjure up as many balls as we want from a single one!
In fact, the statement has been generalized even further to allow any bounded three-dimensional regions which are not "empty" to be broken up into a finite number of pieces and reassembled into any other of these regions.
The Banach-Tarski paradox is central in proving that there is no finitely additive measure in three-dimensional (and higher) spaces which agrees with the basic conception of volume. In one and two dimensions, there still is no countably additive measure that can be universally applied due to the existence of non-measurable sets (see again the Lebesgue measure series for an example of a measure in mathematics). The above are a few of the surprising geometric applications of the axiom of choice, showing how pervasive this assumption is, even beyond its native set theory.
Sources: http://www.math.hmc.edu/~su/papers.dir/banachtarski.pdf, http://www.bsu.edu/libraries/virtualpress/mathexchange/05-01/Coleman.pdf, Banach-Tarski Paradox at Wikipedia
Friday, March 22, 2013
Banach-Tarski Paradox
The Banach-Tarski paradox is a very counterintuitive theorem in geometry that, in effect, states that a three-dimensional ball can be broken up and reassembled in such a way that two identical balls of the same size as the first are formed. This "doubling" of the ball seems contrary to the usual ideas of Euclidean geometry, and is therefore exemplifies the controversy over its underlying assumption, the axiom of choice.
The axiom of choice is one of the most debated topics in mathematics. It is an axiom of set theory, and the debate is whether it is right to assume it, and in what "strength" or version. The axiom itself, put informally, runs thus:
From any collection of nonempty sets, there exists a way to choose exactly one member from each set.
The ability to make such choice seems intuitive enough, but as seen elsewhere on this blog, the assumption of the axiom of choice implies the existence of sets that have no "volume", i.e. their size cannot be measured in any way. And this, as we shall see, is a crucial concept needed to derive the Banach-Tarski paradox.
The "translation" of the paradox into set theoretical concepts involves treating the three-dimensional ball as a set, call it A. We consider a division of the ball as a partition of the set A into the subsets A1, A2,...,An, where none of the subsets overlap, or in set notation, where Ai∩Aj = Ø whenever i ≠ j (i and j run from 1 to n). In this decomposition, n is finite, and only a finite number of pieces are needed to transform one ball into two. This in itself makes the paradox even more unbelievable.
After the ball is partitioned, each piece would then undergo a translation (some movement in space) and a rotation, taking each subset Ai to a corresponding Bi. In this translation, the intrinsic properties of the subsets are not altered; they are simply rearranged in space. The resulting sets, B1,...,Bn, can be split into two groups in such a way that B1∪B2∪...∪Bm is a ball congruent to the first, and the union of remaining subsets, Bm + 1∪...∪Bn, is another ball also congruent to the original one. The transformation is illustrated below:
Since Euclidean translations and rotations preserve volume, the Banach-Tarski paradox violates the principle of the additivity of volume, i.e., that the sum of the volumes of two disjoint sets is the volume of their unions. The beginning ball and the (union of) two equivalent balls are composed of the same (translated) pieces, but they have different volumes. The reason this principle is violated is that the sets in question are non-measurable, or cannot be assigned a volume by any measure. Therefore, the idea of volume additivity has no meaning for them. Non-measurable sets, in addition, can only be proved to exist with the axiom of choice or an equivalent statement. We shall assume the existence of these non-measurable sets, but a construction of such a set under the Lebesgue measure can be found here.
The proof of the Banach-Tarski paradox at first does not work directly with the ball, but instead deals with a more abstract group of points. As we shall see, the decomposition of this abstract set can be performed analogously on the ball with slight modifications.
The abstract set in question is called the free group of two generators, or F2, and it refers, in effect, to the set of strings of the symbols a and b, as well as their inverses, a-1 and b-1. For example, the strings aba-1b and bba-1baa are members of F2. We also define e, or the empty string, as the string in F2 with no members. Finally, we define an operation, *, on strings in F2 that combines two strings into one by placing the second directly after the first. Therefore ab-1*b-1aab = ab-1b-1aab. Additionally, strings are simplified by two rules, where x stands for any string in F2:
a-1bab*b-1a-1bab-1 = a-1babb-1a-1bab-1 = a-1baea-1bab-1 = a-1baa-1bab-1 = a-1bebab-1 = a-1bbab-1
The group F2 can be visualized in several ways. One is as an infinite "tree" of elements, where points on the tree represent strings and "branches" describe the construction of these strings. Below is one example of such a visualization.
A tree of this type is called a Cayley graph of the group F2. Illustrated are the strings of F2 up to three symbols in length. The segments connecting the strings (black dots) illustrate the addition of a symbol to the right of the existing string. One begins in the center with e, the empty string, and moves right to add an "a" and up to add a "b". Moving oppositely to either of the above directions appends an inverse of the corresponding symbol. Note that tracing a path and then retracing backward produces a symbol adjacent to its inverse, causing cancellation. The construction of the string ba-1b-1 is illustrated; staring at e, one first proceeds upward, then left, then down. The reader can verify this construction.
The decomposition of F2 requires the use of some new notation. By S(a) denote the set of all strings in F2 beginning with the symbol a. Define the expression similarly in the case that a-1, b, and b-1, respectively, are substituted for a. Next, the notation, aS(a-1), for example, refers to the set of strings produced by joining the string "a", with a member of the set S(a-1). Thus there is a string in aS(a) for every string in S(a). It must be made clear, however, that the set S(a) and the other related sets contain only simplified strings. Nowhere in any string in S(a) will there appear a term "aa-1" or "bb-1", as these will have already been cancelled.
Armed with these notions, we can construct the "paradoxical" decomposition of F2. The first step is a simple decomposition involving separating the group into each of four disjoint quadrants, the sets S(a), S(a-1), S(b), and S(b-1), and the set {e}, consisting only of the empty string.
The next operation required is a "shift" of the set S(a-1) by the element a into the set aS(a-1), which, as discussed above, has as members every string obtained by adjoining a, (through the operation *) on the left, to some member of S(a-1). The significance of this shift in relation to the sphere will be apparent later. This shifted set is interesting because, when a is combined with a string beginning with a-1, the two elements cancel. Since, in S(a-1), the second and subsequent symbols of each member are arbitrary, every string beginning with a-1, b, or b-1 is a member of aS(a-1). For example, the string bab-1 is the same as a combined with a-1bab-1, a member of S(a-1). Also, strings beginning with a-1 such as a-1bb can be formed as the combination of a and a suitable string beginning with "a-1a-1", in this case a-1a-1bb. Finally, since a-1 is obviously a member of S(a-1), the string aa-1 = e is therefore a member of aS(a-1). In fact, the only strings that are not included in aS(a-1) (ironically) are those beginning with a! This is because, for this to occur, the second element of a member of S(a-1) would have to be a, and this cannot occur, as all strings in S(a-1) are assumed to be simplified.
The above is another view of the Cayley graph, this time illustrating the quadrant S(a-1) along with the shifted set aS(a-1). The only strings not members of the latter set belong to S(a). Therefore, the group F2 is a union of aS(a-1) and S(a). A similar procedure, substituting b for a, leads to the conclusion that the union of bS(b-1) and S(b) is again F2. In summary,
F2 = {e}∪S(a)∪S(a-1)∪ S(b)∪S(b-1) = aS(a-1)∪S(a) = bS(b-1)∪S(b).
The sets S(a-1) and S(b-1) from the original have been shifted by a and b, respectively, and been incorporated into two other decompositions of the same group F2. One copy of F2 has been made into two. (One might well wonder "what happened to {e}?" It turns out that this piece is simply discarded in the above procedure, but the scheme is modified slightly in application to the ball to correct this subtlety).
The relation between F2 and the three-dimensional ball, as well as other extensions of the paradox, are found in another post.
Sources: http://www.kuro5hin.org/story/2003/5/23/134430/275, Banach-Tarski Paradox on Wikipedia
The axiom of choice is one of the most debated topics in mathematics. It is an axiom of set theory, and the debate is whether it is right to assume it, and in what "strength" or version. The axiom itself, put informally, runs thus:
From any collection of nonempty sets, there exists a way to choose exactly one member from each set.
The ability to make such choice seems intuitive enough, but as seen elsewhere on this blog, the assumption of the axiom of choice implies the existence of sets that have no "volume", i.e. their size cannot be measured in any way. And this, as we shall see, is a crucial concept needed to derive the Banach-Tarski paradox.
The "translation" of the paradox into set theoretical concepts involves treating the three-dimensional ball as a set, call it A. We consider a division of the ball as a partition of the set A into the subsets A1, A2,...,An, where none of the subsets overlap, or in set notation, where Ai∩Aj = Ø whenever i ≠ j (i and j run from 1 to n). In this decomposition, n is finite, and only a finite number of pieces are needed to transform one ball into two. This in itself makes the paradox even more unbelievable.
After the ball is partitioned, each piece would then undergo a translation (some movement in space) and a rotation, taking each subset Ai to a corresponding Bi. In this translation, the intrinsic properties of the subsets are not altered; they are simply rearranged in space. The resulting sets, B1,...,Bn, can be split into two groups in such a way that B1∪B2∪...∪Bm is a ball congruent to the first, and the union of remaining subsets, Bm + 1∪...∪Bn, is another ball also congruent to the original one. The transformation is illustrated below:
Since Euclidean translations and rotations preserve volume, the Banach-Tarski paradox violates the principle of the additivity of volume, i.e., that the sum of the volumes of two disjoint sets is the volume of their unions. The beginning ball and the (union of) two equivalent balls are composed of the same (translated) pieces, but they have different volumes. The reason this principle is violated is that the sets in question are non-measurable, or cannot be assigned a volume by any measure. Therefore, the idea of volume additivity has no meaning for them. Non-measurable sets, in addition, can only be proved to exist with the axiom of choice or an equivalent statement. We shall assume the existence of these non-measurable sets, but a construction of such a set under the Lebesgue measure can be found here.
The proof of the Banach-Tarski paradox at first does not work directly with the ball, but instead deals with a more abstract group of points. As we shall see, the decomposition of this abstract set can be performed analogously on the ball with slight modifications.
The abstract set in question is called the free group of two generators, or F2, and it refers, in effect, to the set of strings of the symbols a and b, as well as their inverses, a-1 and b-1. For example, the strings aba-1b and bba-1baa are members of F2. We also define e, or the empty string, as the string in F2 with no members. Finally, we define an operation, *, on strings in F2 that combines two strings into one by placing the second directly after the first. Therefore ab-1*b-1aab = ab-1b-1aab. Additionally, strings are simplified by two rules, where x stands for any string in F2:
- ex = xe = x
- aa-1 = a-1a = bb-1 = b-1b = e
a-1bab*b-1a-1bab-1 = a-1babb-1a-1bab-1 = a-1baea-1bab-1 = a-1baa-1bab-1 = a-1bebab-1 = a-1bbab-1
The group F2 can be visualized in several ways. One is as an infinite "tree" of elements, where points on the tree represent strings and "branches" describe the construction of these strings. Below is one example of such a visualization.
A tree of this type is called a Cayley graph of the group F2. Illustrated are the strings of F2 up to three symbols in length. The segments connecting the strings (black dots) illustrate the addition of a symbol to the right of the existing string. One begins in the center with e, the empty string, and moves right to add an "a" and up to add a "b". Moving oppositely to either of the above directions appends an inverse of the corresponding symbol. Note that tracing a path and then retracing backward produces a symbol adjacent to its inverse, causing cancellation. The construction of the string ba-1b-1 is illustrated; staring at e, one first proceeds upward, then left, then down. The reader can verify this construction.
The decomposition of F2 requires the use of some new notation. By S(a) denote the set of all strings in F2 beginning with the symbol a. Define the expression similarly in the case that a-1, b, and b-1, respectively, are substituted for a. Next, the notation, aS(a-1), for example, refers to the set of strings produced by joining the string "a", with a member of the set S(a-1). Thus there is a string in aS(a) for every string in S(a). It must be made clear, however, that the set S(a) and the other related sets contain only simplified strings. Nowhere in any string in S(a) will there appear a term "aa-1" or "bb-1", as these will have already been cancelled.
Armed with these notions, we can construct the "paradoxical" decomposition of F2. The first step is a simple decomposition involving separating the group into each of four disjoint quadrants, the sets S(a), S(a-1), S(b), and S(b-1), and the set {e}, consisting only of the empty string.
The next operation required is a "shift" of the set S(a-1) by the element a into the set aS(a-1), which, as discussed above, has as members every string obtained by adjoining a, (through the operation *) on the left, to some member of S(a-1). The significance of this shift in relation to the sphere will be apparent later. This shifted set is interesting because, when a is combined with a string beginning with a-1, the two elements cancel. Since, in S(a-1), the second and subsequent symbols of each member are arbitrary, every string beginning with a-1, b, or b-1 is a member of aS(a-1). For example, the string bab-1 is the same as a combined with a-1bab-1, a member of S(a-1). Also, strings beginning with a-1 such as a-1bb can be formed as the combination of a and a suitable string beginning with "a-1a-1", in this case a-1a-1bb. Finally, since a-1 is obviously a member of S(a-1), the string aa-1 = e is therefore a member of aS(a-1). In fact, the only strings that are not included in aS(a-1) (ironically) are those beginning with a! This is because, for this to occur, the second element of a member of S(a-1) would have to be a, and this cannot occur, as all strings in S(a-1) are assumed to be simplified.
The above is another view of the Cayley graph, this time illustrating the quadrant S(a-1) along with the shifted set aS(a-1). The only strings not members of the latter set belong to S(a). Therefore, the group F2 is a union of aS(a-1) and S(a). A similar procedure, substituting b for a, leads to the conclusion that the union of bS(b-1) and S(b) is again F2. In summary,
F2 = {e}∪S(a)∪S(a-1)∪ S(b)∪S(b-1) = aS(a-1)∪S(a) = bS(b-1)∪S(b).
The sets S(a-1) and S(b-1) from the original have been shifted by a and b, respectively, and been incorporated into two other decompositions of the same group F2. One copy of F2 has been made into two. (One might well wonder "what happened to {e}?" It turns out that this piece is simply discarded in the above procedure, but the scheme is modified slightly in application to the ball to correct this subtlety).
The relation between F2 and the three-dimensional ball, as well as other extensions of the paradox, are found in another post.
Sources: http://www.kuro5hin.org/story/2003/5/23/134430/275, Banach-Tarski Paradox on Wikipedia
Thursday, March 14, 2013
Lebesgue Measure III
For an introduction to the Lebesgue measure and various applications to sets in Rn, see the previous two posts, beginning here.
The utility of the Lebesgue Measure has been described in the previous two posts. To briefly summarize, the Lebesgue measure provides a more general notion of the "size" of a set in space that matches up with the intuitive notions of length, area and volume in 1, 2, and 3 dimensions, respectively, as well as preserving natural properties such as the volume of a union of disjoint sets being the sum of volumes of the individual sets. It even goes beyond these notions to measure countable and uncountable sets, manifolds, and even fractals of various sorts. However, under certain assumptions, there exist sets which cannot be consistently assigned a Lebesgue Measure. Such sets and the validity of the underlying assumption necessary for their existence are discussed in this post.
For the construction of these Lebesgue non-measurable sets or Vitali Sets, one must assume one of the most dubious and controversial statements in mathematics: the axiom of choice.
The axiom of choice is not by any means specific to measure theory, but rather is an axiom of set theory, and therefore lies at the foundation of mathematics. The axiom, put informally, is the seemingly innocent statement below:
For any family of sets, there exists a way of choosing (hence the name "axiom of choice") one member from each set in the family.
Slightly more formally, it states that for any set X containing only nonempty sets as members, there exists a choice function f which selects exactly one member from each member of X. Of course, there may be many choice functions for a collection X of sets; the axiom simply guarantees that at least one exists. For example, set
X = {x1,x2,x3} = {{4,5,6},{1,4,7},{2,7,9}}. A choice function on this collection of sets maps each subset of X to one of its members. For example, one could have
f(x1) = f({4,5,6}) = 4, and the function would be similarly defined on x2 and x3.
The act of selecting one member from each of a class of sets seems completely natural and perhaps even fundamental. It seems impossible to imagine a collection of sets where such a choice function would not be possible. Yet the axiom of choice implies the existence of a set that is not measurable by the Lebesgue Measure, and therefore has no definable volume. That such a set exists and can be embedded in a "well-behaved" space like Rn seems surprising, almost contradictory. Without further ado, let us construct a Vitali Set.
For simplicity, the Vitali Set considered will be in R1. The first step in constructing a Vitali Set relies on a concept called a quotient group, specifically the quotient of the real numbers and the rational numbers, denoted R/Q.
R/Q contains a number of classes. Each class is the set of rational numbers Q shifted by a real number r. More specifically, each class, denoted Q + r, contains every number that is formed by adding a rational number to r. For example, if r is π, a real number, then Q + π contains members such as 3/4 + π and -9 + π, but not multiples of π such as π/2, nor rational numbers themselves (e.g. 1/2). Conversely, a real number x is a member of Q + r if and only if x - r is rational. Finally, to form the quotient group R/Q, we discard any "repeats", so that each pair of classes Q + r and Q + s in R/Q is disjoint, i.e. the two have no common elements.
Since the real numbers form an uncountable set, but each class Q + r has as many members as the rational numbers and is countable, the quotient group R/Q is an uncountable set, containing countable sets as members. It is also a partition of R, as every real number is contained within one of the classes, but only one, as they are disjoint.
The next step in construction makes use of the axiom of choice. Clearly, each class
Q + r contains members in the interval [0,1] (as each is dense in the real numbers). Therefore, for each class Q + r, the set (Q + r)∩([0,1]) (∩ denotes the intersection of two sets) is nonempty. The axiom of choice then allows one to select exactly one member from each (Q + r)∩([0,1]), and combine them into their own set. The resulting set has one member for each class of R/Q, all within the interval [0,1].
Call the set just formed V. Note that V was not determined in any precise sense, and rather could be any one of an infinity of possible sets satisfying the same conditions, but for a different selection of choice functions. Furthermore, V is uncountable, and for every real number r, there is exactly one v∈V such that v - r is rational. Also, taking r = 0, there is exactly one rational number in V.
V is the Vitali set. Now it must be proven that it does not have a Lebesgue measure. The final step involves translations of V itself, formed in a manner analogous to those of the classes of R/Q. This time, however, the shifts will be of certain rational numbers.
Since the rational numbers are countable, we can make use of a "catalog" of them, indexed by the positive integers. In other words, we can list the rational numbers, and assign every one a number which will serve as its index. This is called an enumeration of the rational numbers. The enumeration, in this case, will be confined to the rational numbers in the interval [-1,1]. As with the selection of choice functions, the enumeration of these numbers chosen is arbitrary, as differences between specific enumerations will not affect the final result. Denote each rational number in the list qi, for a positive integer i. For example, one could have q1 = 0, q2 = 1/2, q3 = -2/5, etc..
Now we form, for each qi, the set Vi = V + qi, or the set of all numbers created by adding qi to a member of V. It is very important to note that the resulting sets are pairwise disjoint; no two of the translations contain a common member. To see this, remember that each member v of V is representative of a class of the form Q + r. There is one, and only one member of V for every class of the above form in R/Q. The corresponding member in each Vi will also be a member of the class Q + r, as it differs from v only by a rational number. Therefore, it cannot be the same as any member of any Vi formed from another class Q + s. Finally, since the qi are distinct, no two translations of the member v of the original V yield the same number.
After this fact is accepted, the non-measurability of V can be proven. The set that must next be considered is actually the union of of all the Vi. Since there are countably many Vi, and they are pairwise disjoint, the Lebesgue measure of the union is the sum of the Lebesgue measures of each Vi. Hence,
What is the value of this sum? We can place some limitations on it by an examination of the union of the Vi. Note first that every real number on the interval [0,1] is contained within the union of the Vi, since the original V contains representative members of each class in a partition of R/Q. Since these representative elements are within [0,1], it is only necessary to shift them by a number such that |q| ≤ 1, because a distance of 1 is the "farthest away" two objects in [0,1] can be from one another. This reveals the purpose of the enumeration only being of the rational numbers between -1 and 1. Shifting a single element v of V that represented the class Q + r by all of the qi (which lie in the interval [-1,1]) will recreate all of Q + r in [0,1], as well as more outside the interval.
The logical basis for the second limitation is even simpler. Since each v in V must be within [0,1], and the maximum shift induced by the qi to form the Vi has a magnitude of 1, all members of the union of the Vi must be within [-1,2]. More precisely, the smallest possible member of V is 0, causing the smallest possible member of the Vi to be -1, and the largest possible member of V is 1, causing the largest possible member of the Vi to be 2. The above limitations are illustrated in equation below:
We can now use the simple property of the Lebesgue measure that if a set A is contained within another set B, then λ(A) ≤ λ(B). Substituting inequality for inclusion, we can then replace the sets in the above equation with their measures:
Note, finally, that a translation of a set has the same measure as the original set. This is a basic property of the Lebesgue measure, and is reflected in one's intuitive notion of Euclidean geometry; moving figures around in the plane, for example, does not change their area. In light of this property, since each Vi is a translation of V, the last inequality becomes
However, this is a contradiction. Since the expression in the infinite sum is independent of i, it is simply a constant added to itself an infinite number of times. However, the Lebesgue measure of a set can only be a positive real number or zero, and neither of these, when added to itself an infinite number of times, can produce a number between 1 and 3. The assumption that V is measurable is therefore false.
V is not unique of course, due to the different choice function possibilities. In fact, uncountably many Vitali sets arise from the above construction. The idea that so many sets on such a simple structure as the real number line could be non-measurable is remarkable. This brings us back to the main question: is the axiom of choice valid?
There is little consensus on this topic among mathematicians. The axiom itself (in its set-theoretical form) seems intuitive but there are many equivalent or implied statements that seem counterintuitive, such as the result above. Non-measurable sets have been applied to formulate a statement that seems so blatantly contradictory that it is called the Banach-Tarski paradox. It states that, given the axiom of choice, one can subdivide a three-dimensional ball into discrete pieces, and, without altering them, rearrange them in such a way that two three-dimensional balls are formed of identical size to the first. Such an act of "cloning" in reality is contrary to common physical principles. Yet mathematically, many important and seemingly valid theorems depend on the axiom. Therefore, there is evidence for both arguments, and the matter is not likely to be conclusively resolved in the near future.
Returning briefly to the Lebesgue measure, the effectiveness and generality of this instrument, despite the above defect, has led to growth in many related areas of mathematics. Lebesgue himself used the measure and related concepts to more rigorously define properties of functions on Rn, including those which, in earlier periods, were often disregarded. Since the theory of measure is related to that of manifolds, the above developments had great significance in the area of topology as well.
Sources: Vitali Sets, Axiom of Choice on Wikipedia, http://homepage.univie.ac.at/erhard.reschenhofer/pdf/probstat/P_A.pdf
The utility of the Lebesgue Measure has been described in the previous two posts. To briefly summarize, the Lebesgue measure provides a more general notion of the "size" of a set in space that matches up with the intuitive notions of length, area and volume in 1, 2, and 3 dimensions, respectively, as well as preserving natural properties such as the volume of a union of disjoint sets being the sum of volumes of the individual sets. It even goes beyond these notions to measure countable and uncountable sets, manifolds, and even fractals of various sorts. However, under certain assumptions, there exist sets which cannot be consistently assigned a Lebesgue Measure. Such sets and the validity of the underlying assumption necessary for their existence are discussed in this post.
For the construction of these Lebesgue non-measurable sets or Vitali Sets, one must assume one of the most dubious and controversial statements in mathematics: the axiom of choice.
The axiom of choice is not by any means specific to measure theory, but rather is an axiom of set theory, and therefore lies at the foundation of mathematics. The axiom, put informally, is the seemingly innocent statement below:
For any family of sets, there exists a way of choosing (hence the name "axiom of choice") one member from each set in the family.
Slightly more formally, it states that for any set X containing only nonempty sets as members, there exists a choice function f which selects exactly one member from each member of X. Of course, there may be many choice functions for a collection X of sets; the axiom simply guarantees that at least one exists. For example, set
X = {x1,x2,x3} = {{4,5,6},{1,4,7},{2,7,9}}. A choice function on this collection of sets maps each subset of X to one of its members. For example, one could have
f(x1) = f({4,5,6}) = 4, and the function would be similarly defined on x2 and x3.
The act of selecting one member from each of a class of sets seems completely natural and perhaps even fundamental. It seems impossible to imagine a collection of sets where such a choice function would not be possible. Yet the axiom of choice implies the existence of a set that is not measurable by the Lebesgue Measure, and therefore has no definable volume. That such a set exists and can be embedded in a "well-behaved" space like Rn seems surprising, almost contradictory. Without further ado, let us construct a Vitali Set.
For simplicity, the Vitali Set considered will be in R1. The first step in constructing a Vitali Set relies on a concept called a quotient group, specifically the quotient of the real numbers and the rational numbers, denoted R/Q.
R/Q contains a number of classes. Each class is the set of rational numbers Q shifted by a real number r. More specifically, each class, denoted Q + r, contains every number that is formed by adding a rational number to r. For example, if r is π, a real number, then Q + π contains members such as 3/4 + π and -9 + π, but not multiples of π such as π/2, nor rational numbers themselves (e.g. 1/2). Conversely, a real number x is a member of Q + r if and only if x - r is rational. Finally, to form the quotient group R/Q, we discard any "repeats", so that each pair of classes Q + r and Q + s in R/Q is disjoint, i.e. the two have no common elements.
Since the real numbers form an uncountable set, but each class Q + r has as many members as the rational numbers and is countable, the quotient group R/Q is an uncountable set, containing countable sets as members. It is also a partition of R, as every real number is contained within one of the classes, but only one, as they are disjoint.
The next step in construction makes use of the axiom of choice. Clearly, each class
Q + r contains members in the interval [0,1] (as each is dense in the real numbers). Therefore, for each class Q + r, the set (Q + r)∩([0,1]) (∩ denotes the intersection of two sets) is nonempty. The axiom of choice then allows one to select exactly one member from each (Q + r)∩([0,1]), and combine them into their own set. The resulting set has one member for each class of R/Q, all within the interval [0,1].
Call the set just formed V. Note that V was not determined in any precise sense, and rather could be any one of an infinity of possible sets satisfying the same conditions, but for a different selection of choice functions. Furthermore, V is uncountable, and for every real number r, there is exactly one v∈V such that v - r is rational. Also, taking r = 0, there is exactly one rational number in V.
V is the Vitali set. Now it must be proven that it does not have a Lebesgue measure. The final step involves translations of V itself, formed in a manner analogous to those of the classes of R/Q. This time, however, the shifts will be of certain rational numbers.
Since the rational numbers are countable, we can make use of a "catalog" of them, indexed by the positive integers. In other words, we can list the rational numbers, and assign every one a number which will serve as its index. This is called an enumeration of the rational numbers. The enumeration, in this case, will be confined to the rational numbers in the interval [-1,1]. As with the selection of choice functions, the enumeration of these numbers chosen is arbitrary, as differences between specific enumerations will not affect the final result. Denote each rational number in the list qi, for a positive integer i. For example, one could have q1 = 0, q2 = 1/2, q3 = -2/5, etc..
Now we form, for each qi, the set Vi = V + qi, or the set of all numbers created by adding qi to a member of V. It is very important to note that the resulting sets are pairwise disjoint; no two of the translations contain a common member. To see this, remember that each member v of V is representative of a class of the form Q + r. There is one, and only one member of V for every class of the above form in R/Q. The corresponding member in each Vi will also be a member of the class Q + r, as it differs from v only by a rational number. Therefore, it cannot be the same as any member of any Vi formed from another class Q + s. Finally, since the qi are distinct, no two translations of the member v of the original V yield the same number.
After this fact is accepted, the non-measurability of V can be proven. The set that must next be considered is actually the union of of all the Vi. Since there are countably many Vi, and they are pairwise disjoint, the Lebesgue measure of the union is the sum of the Lebesgue measures of each Vi. Hence,
What is the value of this sum? We can place some limitations on it by an examination of the union of the Vi. Note first that every real number on the interval [0,1] is contained within the union of the Vi, since the original V contains representative members of each class in a partition of R/Q. Since these representative elements are within [0,1], it is only necessary to shift them by a number such that |q| ≤ 1, because a distance of 1 is the "farthest away" two objects in [0,1] can be from one another. This reveals the purpose of the enumeration only being of the rational numbers between -1 and 1. Shifting a single element v of V that represented the class Q + r by all of the qi (which lie in the interval [-1,1]) will recreate all of Q + r in [0,1], as well as more outside the interval.
The logical basis for the second limitation is even simpler. Since each v in V must be within [0,1], and the maximum shift induced by the qi to form the Vi has a magnitude of 1, all members of the union of the Vi must be within [-1,2]. More precisely, the smallest possible member of V is 0, causing the smallest possible member of the Vi to be -1, and the largest possible member of V is 1, causing the largest possible member of the Vi to be 2. The above limitations are illustrated in equation below:
We can now use the simple property of the Lebesgue measure that if a set A is contained within another set B, then λ(A) ≤ λ(B). Substituting inequality for inclusion, we can then replace the sets in the above equation with their measures:
Note, finally, that a translation of a set has the same measure as the original set. This is a basic property of the Lebesgue measure, and is reflected in one's intuitive notion of Euclidean geometry; moving figures around in the plane, for example, does not change their area. In light of this property, since each Vi is a translation of V, the last inequality becomes
However, this is a contradiction. Since the expression in the infinite sum is independent of i, it is simply a constant added to itself an infinite number of times. However, the Lebesgue measure of a set can only be a positive real number or zero, and neither of these, when added to itself an infinite number of times, can produce a number between 1 and 3. The assumption that V is measurable is therefore false.
V is not unique of course, due to the different choice function possibilities. In fact, uncountably many Vitali sets arise from the above construction. The idea that so many sets on such a simple structure as the real number line could be non-measurable is remarkable. This brings us back to the main question: is the axiom of choice valid?
There is little consensus on this topic among mathematicians. The axiom itself (in its set-theoretical form) seems intuitive but there are many equivalent or implied statements that seem counterintuitive, such as the result above. Non-measurable sets have been applied to formulate a statement that seems so blatantly contradictory that it is called the Banach-Tarski paradox. It states that, given the axiom of choice, one can subdivide a three-dimensional ball into discrete pieces, and, without altering them, rearrange them in such a way that two three-dimensional balls are formed of identical size to the first. Such an act of "cloning" in reality is contrary to common physical principles. Yet mathematically, many important and seemingly valid theorems depend on the axiom. Therefore, there is evidence for both arguments, and the matter is not likely to be conclusively resolved in the near future.
Returning briefly to the Lebesgue measure, the effectiveness and generality of this instrument, despite the above defect, has led to growth in many related areas of mathematics. Lebesgue himself used the measure and related concepts to more rigorously define properties of functions on Rn, including those which, in earlier periods, were often disregarded. Since the theory of measure is related to that of manifolds, the above developments had great significance in the area of topology as well.
Sources: Vitali Sets, Axiom of Choice on Wikipedia, http://homepage.univie.ac.at/erhard.reschenhofer/pdf/probstat/P_A.pdf
Wednesday, March 6, 2013
Lebesgue Measure II
For the definition of the Lebesgue Measure and some of its simple applications to sets, see the previous post.
So far, many of the sets discussed have been products of non-degenerate intervals (or sets approximated by these products of intervals), and these have had positive Lebesgue Measures. Since an interval in R1 is an uncountable set, so are the products of intervals in Rn. The other sets that have been considered have been either finite or countable, and all of these have had Lebesgue Measure 0. Therefore, thus far, negligibility has coincided with countability. However, there are also uncountable sets which are negligible.
The key concept is that a subset A of Rn is negligible if it has a dimension less than n. Before exploring the implications of this statement, consider a simple example:
Let the set A be interval [0,1] embedded in R2 (illustrated below). This, being an interval, is an uncountable set, but it can be shown by a succession of approximations by squares in R2 that this set has Lebesgue Measure 0.
A portrayal of the set A in R2. The standard Cartesian coordinates and axes are superimposed for clarity. The first approximation (top), uses the single square (2-prism) [0,1]x[0,1], which clearly contains A, to approximate the volume of A. Having side length 1, the volume is 1. In the second approximation (middle), the union of two squares, J21 and J22, each with side length 1/2, clearly contains A, the total volume of the approximation (denoted by J2) being (1/2)2 + (1/2)2 = 1/2. The third approximation (bottom), follows a similar approach, with four squares of side length 1/4 containing A and yielding the approximation J3 = 1/4 to A. Clearly, if the side length of the approximating squares is halved in each successive approximation, the resulting estimated volume is halved each time. Since this can be done indefinitely, λ(A) = 0.
The above example shows how squares, the most basic units of area in R2, can be used to calculate the volumes of other sets, including negligible ones. This example also motivates a useful condition for negligibility: A set S is negligible in Rn if, for every ε > 0, no matter how small, there exists a (finite) collection of rectangular n-prisms Ji, such that S is contained within the union of the Ji and the Lebesgue measure of the union of the Ji is less than or equal to ε.
Since the set A in the example is one-dimensional (in our as yet intuitive sense), its negligibility is consistent with the previous statement that a set of some dimension embedded in a real space of higher dimension is negligible, as 1 < 2. Note that, if the same set A were being considered as a subset of R1, it would not be negligible, but rather λ(A) would equal 1. This reveals the importance of specifying the dimension of the ambient space Rn. More generally, if A is a "well-behaved" manifold of dimension m embedded within Rn, and m < n, then A is negligible under the Lebesgue Measure.
The purpose of the qualifier "well-behaved" is to distinguish between two types of dimension. The common idea of dimension, the number of perpendicular directions one can "contain" in space, is what is called the topological dimension. However, the Lebesgue Measure also depends on something called the Hausdorff dimension, named after the German mathematician Felix Hausdorff. This alternate measure of dimension applies to a larger class of sets, notably fractals, and does not assign only integer values; many sets have Hausdorff dimension between 1 and 2, for example.
For any space, the Hausdorff dimension of the space is always greater than or equal to the topological dimension (if applicable) of the same space. Thus, even if a set topologically has a smaller dimension than the real space around it, it may still have nonzero Lebesgue Measure.
Take, for example, the Cantor Set. It is produced by removing the middle third of the interval [0,1], and, on every subsequent step, removing the middle third from each remaining line segment. After an infinite number of steps, the set remains. The properties of this set are proved elsewhere. The Cantor set is a fractal, an uncountable set, but not a dense set. Also, if its points are expressed in ternary (base 3) notation, the numerical expansion of each member of the set contains only 0's and 2's (in base 3, the possible digits are 0, 1, and 2). The Hausdorff dimension of the Cantor set is related to its property of containing points which "use" only 2 out of the 3 digits of the ternary system; the dimension is ln(2)/ln(3) ≈ .6309. This figure gives some idea to "how big" the set is. Since this is less than 1, the dimension of the real space in which it is embedded, the Cantor Set has Lebesgue Measure 0.
In the above case, the topological dimension can be considered to be 0, as the set contains only "isolated" points. However, the Hausdorff dimension, though greater, was still less than that of the ambient space, giving the same result: the Cantor set is negligible. In other cases, the distinctness of the Hausdorff dimension does affect the Lebesgue Measure. Consider the figure below.
The above illustrates three stages of the construction of a fractal known as a space-filling curve, or Peano curve. It is a fractal because it is self-similar (structures are duplicated on smaller levels in each step), and after infinite steps, it fills every point in the space it occupies, which, for simplicity, we will assume to be the unit square [0,1]x[0,1] in R2. Locally, each part of the space-filling curve looks like a line, giving the set topological dimension 1. However, it fills every point in a two-dimensional region, and has Hausdorff dimension 2. With respect to the Lebesgue Measure on R2, the space-filling curve is not a negligible set, but rather has a positive Lebesgue Measure, equal in magnitude to the volume of the unit square, that is, 1.
This post has illustrated the application of the Lebesgue Measure to an even wider variety of sets. However, there are some even more exceptional sets to which the Lebesgue Measure does not assign a value at all! (see the next post)
Sources: Advanced Calculus of Several Variables by C.H. Edwards Jr., Vitali Sets on Wikipedia
So far, many of the sets discussed have been products of non-degenerate intervals (or sets approximated by these products of intervals), and these have had positive Lebesgue Measures. Since an interval in R1 is an uncountable set, so are the products of intervals in Rn. The other sets that have been considered have been either finite or countable, and all of these have had Lebesgue Measure 0. Therefore, thus far, negligibility has coincided with countability. However, there are also uncountable sets which are negligible.
The key concept is that a subset A of Rn is negligible if it has a dimension less than n. Before exploring the implications of this statement, consider a simple example:
Let the set A be interval [0,1] embedded in R2 (illustrated below). This, being an interval, is an uncountable set, but it can be shown by a succession of approximations by squares in R2 that this set has Lebesgue Measure 0.
A portrayal of the set A in R2. The standard Cartesian coordinates and axes are superimposed for clarity. The first approximation (top), uses the single square (2-prism) [0,1]x[0,1], which clearly contains A, to approximate the volume of A. Having side length 1, the volume is 1. In the second approximation (middle), the union of two squares, J21 and J22, each with side length 1/2, clearly contains A, the total volume of the approximation (denoted by J2) being (1/2)2 + (1/2)2 = 1/2. The third approximation (bottom), follows a similar approach, with four squares of side length 1/4 containing A and yielding the approximation J3 = 1/4 to A. Clearly, if the side length of the approximating squares is halved in each successive approximation, the resulting estimated volume is halved each time. Since this can be done indefinitely, λ(A) = 0.
The above example shows how squares, the most basic units of area in R2, can be used to calculate the volumes of other sets, including negligible ones. This example also motivates a useful condition for negligibility: A set S is negligible in Rn if, for every ε > 0, no matter how small, there exists a (finite) collection of rectangular n-prisms Ji, such that S is contained within the union of the Ji and the Lebesgue measure of the union of the Ji is less than or equal to ε.
Since the set A in the example is one-dimensional (in our as yet intuitive sense), its negligibility is consistent with the previous statement that a set of some dimension embedded in a real space of higher dimension is negligible, as 1 < 2. Note that, if the same set A were being considered as a subset of R1, it would not be negligible, but rather λ(A) would equal 1. This reveals the importance of specifying the dimension of the ambient space Rn. More generally, if A is a "well-behaved" manifold of dimension m embedded within Rn, and m < n, then A is negligible under the Lebesgue Measure.
The purpose of the qualifier "well-behaved" is to distinguish between two types of dimension. The common idea of dimension, the number of perpendicular directions one can "contain" in space, is what is called the topological dimension. However, the Lebesgue Measure also depends on something called the Hausdorff dimension, named after the German mathematician Felix Hausdorff. This alternate measure of dimension applies to a larger class of sets, notably fractals, and does not assign only integer values; many sets have Hausdorff dimension between 1 and 2, for example.
For any space, the Hausdorff dimension of the space is always greater than or equal to the topological dimension (if applicable) of the same space. Thus, even if a set topologically has a smaller dimension than the real space around it, it may still have nonzero Lebesgue Measure.
Take, for example, the Cantor Set. It is produced by removing the middle third of the interval [0,1], and, on every subsequent step, removing the middle third from each remaining line segment. After an infinite number of steps, the set remains. The properties of this set are proved elsewhere. The Cantor set is a fractal, an uncountable set, but not a dense set. Also, if its points are expressed in ternary (base 3) notation, the numerical expansion of each member of the set contains only 0's and 2's (in base 3, the possible digits are 0, 1, and 2). The Hausdorff dimension of the Cantor set is related to its property of containing points which "use" only 2 out of the 3 digits of the ternary system; the dimension is ln(2)/ln(3) ≈ .6309. This figure gives some idea to "how big" the set is. Since this is less than 1, the dimension of the real space in which it is embedded, the Cantor Set has Lebesgue Measure 0.
In the above case, the topological dimension can be considered to be 0, as the set contains only "isolated" points. However, the Hausdorff dimension, though greater, was still less than that of the ambient space, giving the same result: the Cantor set is negligible. In other cases, the distinctness of the Hausdorff dimension does affect the Lebesgue Measure. Consider the figure below.
The above illustrates three stages of the construction of a fractal known as a space-filling curve, or Peano curve. It is a fractal because it is self-similar (structures are duplicated on smaller levels in each step), and after infinite steps, it fills every point in the space it occupies, which, for simplicity, we will assume to be the unit square [0,1]x[0,1] in R2. Locally, each part of the space-filling curve looks like a line, giving the set topological dimension 1. However, it fills every point in a two-dimensional region, and has Hausdorff dimension 2. With respect to the Lebesgue Measure on R2, the space-filling curve is not a negligible set, but rather has a positive Lebesgue Measure, equal in magnitude to the volume of the unit square, that is, 1.
This post has illustrated the application of the Lebesgue Measure to an even wider variety of sets. However, there are some even more exceptional sets to which the Lebesgue Measure does not assign a value at all! (see the next post)
Sources: Advanced Calculus of Several Variables by C.H. Edwards Jr., Vitali Sets on Wikipedia
Tuesday, February 26, 2013
Lebesgue Measure
The idea of a "measure", intuitively a rule that determines the size of an object, is very important to mathematics. It is used as a baseline for comparing mathematical "objects", usually sets. However, what consistent way is there to assign sizes to sets that varies over such the wide variety of sets found in mathematics?
One approach is called the Lebesgue measure, named after the mathematician Henri Lebesgue, who introduced the concept around 1902. With this measure, the size of a set A is denoted λ(A). The "objects" or sets that can be measured are considered to reside within the a real Euclidean space Rn for some positive integer n. For each dimension n, Rn is the typical flat (Euclidean) space. For n = 1, it is the line, n = 2, the plane, etc. An intuitively easy way to deal with many sets in real space is simply to measure their volumes. For such sets where this is easily done, the Lebesgue measure coincides with what we traditionally calculate as "volume".
The basis for area in n dimensions is found in one dimension, where "volume" is simply length. To a closed interval [a,b] in R1 (the set of real numbers from a to b, including a and b, see below), the Lebesgue measure assigns the value b - a.
In more than one dimension, we define the Cartesian product of two closed intervals [a,b] and [c,d] in R1 as the rectangle in R2 bounded by the lines x = a, x = b, y = a, and y = b. Its volume, as per the usual practice, is the product of the lengths of the respective intervals; in this case, it is (b - a)(d - c). In equation form, with the Cartesian product indicated by x, λ([a,b]x[c,d]) = (b - a)(d - c).
This approach is extended to three dimensions by considering the Cartesian product of 3 (non-degenerate) closed intervals, which takes the form of a rectangular prism, the volume of this set being the length times the width times the height, as is normal. In n-dimensions, the Cartesian product of n closed intervals I1, I2,..., In forms an n-dimension rectangular prism with volume |I1|·|I2|·...·|In|, where |Ii| is the length of the respective interval.
This rectangular prisms in n-dimensions, or rectangular n-prisms, are the building blocks of volume in Rn. Another basic property of the Lebesgue measure is that, if two sets A and B are disjoint, i.e. do not overlap, or more formally, their intersection is empty, then λ(A∪B) = λ(A) + λ(B). This expression holds as long as the measures are defined. More generally, if n disjoint measurable sets are involved:
This formula simply states that the volume of the union of the sets is the sum of their individual volumes. Remarkably, this even applies to infinite unions of sets, as long as the number of sets is countable, or, equivalently, if the collection of sets can be put into a one-to-one correspondence with the natural numbers (for more, see here).
To define volume for a more general set, one approximates the set as an addition of smaller sets, usually n-prisms. To be more precise, for a set A, if a set of disjoint rectangular n-prisms are contained completely within A, then the sum of their volumes is an lower approximation to the volume of A. If a set of rectangular n-prisms (not necessarily disjoint, i.e. there could be some overlap) completely covers the set A in Rn, then it serves as an upper approximation to the volume of A. This method of finding area is called integration.
An illustration of how rectangular n-prisms can provide upper and lower approximation to the volume of a more general set A.
Another property of the Lebesgue measure is invariance under translation and rotation. In other words, if a set A is rotated or moved around in Rn to another set B, then λ(A) = λ(B). On the other hand, if a set is dilated, or expanded, by a factor d, where d is a positive real number, and the dilated set is denoted dA, then
λ(dA) = dnλ(A),
where n is the dimension of the ambient space (Rn).
Now, one can consider various sets in Rn and their Lebesgue measures. First, any point, or more precisely, the set containing a single point P, {P}, has measure 0. This is because it can be viewed as a product of intervals each with length zero. Now, any finite set, that is, including a finite number of points, has Lebesgue measure 0, as such a set can be expressed as the union of many sets, each containing one point, which we known to have measure 0. A set with measure 0 is called negligible.
Similarly, the set of integers, or, for higher dimensions, the set of ordered n-tuplets of the form (a1,a2,...,an) where the ai are integers, is negligible, as these sets are countable (this is proven here).
Returning to R1, the set Q of rational numbers, or those numbers expressible as a quotient of two integers, is countable, and therefore negligible, with λ(Q) = 0. This is the first example of a dense set that is negligible. The higher dimension analog of the rational numbers in R1 is, for each dimension n, the set of n-tuplets (a1,a2,...,an) where the ai are rational numbers. For every n, this set is negligible, with Lebesgue measure 0.
However, the Lebesgue Measure does far more than distinguish between countable and uncountable sets. More properties and measures of sets are presented in the next post.
Sources: Advanced Calculus of Several Variables by C.H. Edwards Jr., Lebesgue Measure on Wikipedia
One approach is called the Lebesgue measure, named after the mathematician Henri Lebesgue, who introduced the concept around 1902. With this measure, the size of a set A is denoted λ(A). The "objects" or sets that can be measured are considered to reside within the a real Euclidean space Rn for some positive integer n. For each dimension n, Rn is the typical flat (Euclidean) space. For n = 1, it is the line, n = 2, the plane, etc. An intuitively easy way to deal with many sets in real space is simply to measure their volumes. For such sets where this is easily done, the Lebesgue measure coincides with what we traditionally calculate as "volume".
The basis for area in n dimensions is found in one dimension, where "volume" is simply length. To a closed interval [a,b] in R1 (the set of real numbers from a to b, including a and b, see below), the Lebesgue measure assigns the value b - a.
In more than one dimension, we define the Cartesian product of two closed intervals [a,b] and [c,d] in R1 as the rectangle in R2 bounded by the lines x = a, x = b, y = a, and y = b. Its volume, as per the usual practice, is the product of the lengths of the respective intervals; in this case, it is (b - a)(d - c). In equation form, with the Cartesian product indicated by x, λ([a,b]x[c,d]) = (b - a)(d - c).
This approach is extended to three dimensions by considering the Cartesian product of 3 (non-degenerate) closed intervals, which takes the form of a rectangular prism, the volume of this set being the length times the width times the height, as is normal. In n-dimensions, the Cartesian product of n closed intervals I1, I2,..., In forms an n-dimension rectangular prism with volume |I1|·|I2|·...·|In|, where |Ii| is the length of the respective interval.
This rectangular prisms in n-dimensions, or rectangular n-prisms, are the building blocks of volume in Rn. Another basic property of the Lebesgue measure is that, if two sets A and B are disjoint, i.e. do not overlap, or more formally, their intersection is empty, then λ(A∪B) = λ(A) + λ(B). This expression holds as long as the measures are defined. More generally, if n disjoint measurable sets are involved:
This formula simply states that the volume of the union of the sets is the sum of their individual volumes. Remarkably, this even applies to infinite unions of sets, as long as the number of sets is countable, or, equivalently, if the collection of sets can be put into a one-to-one correspondence with the natural numbers (for more, see here).
To define volume for a more general set, one approximates the set as an addition of smaller sets, usually n-prisms. To be more precise, for a set A, if a set of disjoint rectangular n-prisms are contained completely within A, then the sum of their volumes is an lower approximation to the volume of A. If a set of rectangular n-prisms (not necessarily disjoint, i.e. there could be some overlap) completely covers the set A in Rn, then it serves as an upper approximation to the volume of A. This method of finding area is called integration.
An illustration of how rectangular n-prisms can provide upper and lower approximation to the volume of a more general set A.
Another property of the Lebesgue measure is invariance under translation and rotation. In other words, if a set A is rotated or moved around in Rn to another set B, then λ(A) = λ(B). On the other hand, if a set is dilated, or expanded, by a factor d, where d is a positive real number, and the dilated set is denoted dA, then
λ(dA) = dnλ(A),
where n is the dimension of the ambient space (Rn).
Now, one can consider various sets in Rn and their Lebesgue measures. First, any point, or more precisely, the set containing a single point P, {P}, has measure 0. This is because it can be viewed as a product of intervals each with length zero. Now, any finite set, that is, including a finite number of points, has Lebesgue measure 0, as such a set can be expressed as the union of many sets, each containing one point, which we known to have measure 0. A set with measure 0 is called negligible.
Similarly, the set of integers, or, for higher dimensions, the set of ordered n-tuplets of the form (a1,a2,...,an) where the ai are integers, is negligible, as these sets are countable (this is proven here).
Returning to R1, the set Q of rational numbers, or those numbers expressible as a quotient of two integers, is countable, and therefore negligible, with λ(Q) = 0. This is the first example of a dense set that is negligible. The higher dimension analog of the rational numbers in R1 is, for each dimension n, the set of n-tuplets (a1,a2,...,an) where the ai are rational numbers. For every n, this set is negligible, with Lebesgue measure 0.
However, the Lebesgue Measure does far more than distinguish between countable and uncountable sets. More properties and measures of sets are presented in the next post.
Sources: Advanced Calculus of Several Variables by C.H. Edwards Jr., Lebesgue Measure on Wikipedia
Subscribe to:
Posts (Atom)
