submited by

Style Pass

Subscribe! My latest posts can be found here: Colins Blog Previous blog posts: Sieve Of Eratosthenes In Python Fast Perrin Test Russian Peasant Multiplication FindingPerrinPseudoPrimes Part2 FindingPerrinPseudoPrimes Part1 The Unwise Update Miles Per Gallon Tracking An Item On Hacker News Hacker News User Ages Poking The Dusty Corners There Is No Time For This Publically Sharing Links Learning Times Tables Graceful Degradation Diagramming Maths Topics On The Rack Square Root By Long Division Beyond The Boundary Fill In The Gaps Software Checklist NASA Space Crews The Birthday Paradox The Trapezium Conundrum Revisiting The Ant The Ant And The Rubber Band Irrationals Exist Multiple Choice Probability Puzzle Random Eratosthenes Wrapping Up Square Dissection Dissecting A Square Part 2 Dissecting A Circle Dissecting A Square An Oddity In Tennis Decision Tree For Tennis Decision Trees In Games A Matter Of Convention Do You Nourish Or Tarnish Binary Search Reconsidered Two Equals Four The Lost Property Office The Forgiving User Interface Setting Up RSS Withdrawing From Hacker News Additionally, some earlier writings: Random Writings. Colins Blog 2010 Colins Blog 2009 Colins Blog 2008 Colins Blog 2007 Colins Blog Before 2007 This page has been Tagged As Maths. The Point Of The Banach-Tarski Theorem One of my favourite Limited Audience Jokes (although technically it's actually a riddle) goes: Added after seeing some discussion ... This is not intended to explain why the Banach-Tarski theorem is true, nor to give a proof, nor to talk about what the pieces look like, etc. No ... the purpose of this article is to explain why the result is relevant. In short, the Banach-Tarski Theorem tells us what is and is not possible in measure theory. It tells us that things we would in general want to be true of a measure are mutually inconsistent. Now read on ... Q: What's an anagram of Banach-Tarski? A: Banach-Tarski Banach-Tarski Now, if you already know what the Banach-Tarski theorem says, that riddle is really funny. If you don't, then you're simply not in the audience, and you'll just go: "Huh?" Which is a perfectly reasonable reaction. Indeed, if you then have the Banach-Tarski theorem explained to you, you most likely will still go: "Huh?" It's a perplexing result, some even call it a paradox, but the fact that it's so odd actually masks the fact that it's a truly important result, with some deep implications. So I'm going to explain here why it's important, and what some of the implications are. The hope is that even if you do know the result you will find this interesting, largely because in the shock of seeing what the result says, you've never been shown why it's interesting. So for those of you who don't know the result, here it is in simple, non-technical terms: In $\Re^3$, given a solid ball $B$ of radius $R,$ it is possible to partition $B$ into finitely many pieces such that those pieces can be reassembled to form two solid balls $B_1$ and $B_2,$ each of radius $R.$ Apart from using the Axiom Of Choice. Now, that's obvious nonsense, and that's why the result is so shocking. It defies common sense, and immediately makes you go looking for some kind of loophole. But there isn't one. So in part because it's so surprising, and shocking, and nonsensical, you might think it's in a dead-end of mathematics and of no real use or interest. That's what this article is intending to address. To do so, let's consider the idea of measurement. We can talk about the length of a line, the area of a polygon (or other shape), the volume of a lump, or whatever. The development of the concept of accurate measurement goes back millennia, and is critical in the development of commerce, engineering, and so many other things. So we're going to look at the concept of measuring something, and see what we can say about it mathematically. To do that we'll talk about a function called a "measure". One of the problems in maths is we use ordinary words in a technical sense, so it's a bit dangerous to call this thing a "measure," but I'll try to use that word only ever in its technical sense. And fairly obviously we'll need a different function, or measure, when we're in one dimension as compared with two dimensions, or more, so we'll talk about a measure for each dimension. So a "measure" is a function that takes a set and returns a number that somehow represents the length, area, volume, whatever. But regardless of dimension there are things we expect a measure to do, ways we expect it to behave. For example, we expect the measure of a zero length line to be zero. We also expect the measure of a non-zero length line to be non-zero. These seem to be obvious requirements. Also, when we're talking about length (or area or volume, etc ) we would expect the sum of the measure of the parts to be the same as the measure of the whole. In other words, if you take the measure of a set, then partition the set into two pieces and take the measure of each of those, you'd expect the sum of the measures to be the measure of the original. Let's start writing these down. If we are working in $n$ dimensions and we have a measure, $\mu$ which is defined on subsets of $\Re^n,$ we expect that: $\mu(\{\})\;=\;0$ - the measure of the empty set is 0. If I is the unit object, then $\mu(I)=1.$ For sets $A$ and $B$ that do not overlap, then $\mu(A{\cup}B)\;=\;\mu(A)+\mu(B).$ If we want to, we can weaken the middle condition to simply ask that $\mu(I)\;>\;0,$ because then we can just apply a scaling. This is like changing units. The last one we can repeat over and over to get the idea of the measure being finitely additive. In fact, we'd really like to extend that to being countably additive, so that: $\mu(\bigcup_{i=0}^{\infty}A_i)\;=\;\sum_{i=0}^\infty\mu(A_i)$ Provided all the sets are (pairwise) disjoint In other words, when we have a set that's made up of countably infinitely many disjoint pieces, we can choose to take the measure of them all and add them up, or we can think of the union of them all, and take the measure of that. But there are other things we expect to be true of a measure. We expect that if we take the measure of something, move the something around, and then take the measure again, we get the same answer. Moving something around should not change its size. In mathematics the idea of moving something around is captured by the idea of what we call an isometry. An isometry is a function that doesn't change distances, so if we have an isometry $\tau$ and apply it to a set $A$, none of the distances between points in $A$ will change, so we can think of $\tau(A)$ as being $A$ moved somewhere else (and maybe flipped over to give a mirror image). So for any set $A,$ and any isometry $\tau,$ then we expect of a measure $\mu$ that: $\mu(A)\;=\;\mu(\tau(A))$ In words, we expect a measure to be isometry invariant. So far: $\mu(I)\;=\;1$ $\mu$ is countably additive $\mu$ is isometry invariant Finally, we'd like $\mu$ to be defined for all sets, although it might end up being infinite if our set is unbounded (and even then not always). So if we have a bounded set (and I've not given a technical definition of what that means) then we would like the measure of that to exist. So we finally want: For all bounded sets $A$, $\mu(A)$ exists. Well, the problem is that we can't have all of these. This was shown in 1905, and is a classic example of a set of desirable requirements that are not mutually satisfiable. In short, these natural and obvious requirements for a measure are mutually inconsistent. We cannot have all of: $\mu(I)\;=\;1$ $\mu$ is countably additive $\mu$ is isometry invariant For all bounded sets $A$, $\mu(A)$ exists. Outline of the Vitali Set proof The idea is: Consider the points from 0 (inclusive) to 1 (not inclusive) Declare two points to be equivalent if they differ by a rational This gives us families of points, the members of a family differing only by a rational number. Points from different families do not differ by a rational. From each equivalence class (family) choose one element Call that set $V$. Given two points in $V$ they do not differ by a rational Enumerate the rationals in $[0,1)$ : $r_0,\;r_1,\;r_2,\;\ldots$ For each rational $r_i$ consider $V_i\;=\;V+r_i\;\;(mod\;1)$ These are disjoint (Exercise: you should check that) For any measure $\mu$, for all $i$, $\mu(V_i)\;=\;\mu(V).$ This requires some proof, but basically $V_i$ is just $V$ moved about. By the properties we have: $\mu([0,1))\;=\;\sum_i\mu(V_i)$ But what can $\mu(V)$ possibly be? If $\mu(V)\;=\;0$ then when we add them all up we get zero, which would mean the measure of $[0,1)$ is zero. If $\mu(V)\;\ne\;0$ then when we add infinitely many together we definitely don't get a finite answer. Which is wrong. Which is wrong. So either way, using only the things we decided were obvious and natural for a measure, we've arrived at a contradiction. So we cannot have a measure that has all the properties that we quite reasonably want. The proof is simple, and can be found all over the 'net. Look for the Vitali Set. So what do we do? Well, what we have to do is relax one of our requirements, and make it weaker. The obvious thing that people want to try is to reduce the power of the additivity rule. So our requirements become: $\mu(I)\;=\;1$ $\mu$ is finitely additive $\mu$ is isometry invariant For all bounded sets $A$, $\mu(A)$ exists. Can we do this? As it happens, for $\Re^1$ we can do this. Even more, for $\Re^2$ we can do this! But for $\Re^3,$ we can't. How do we know? Because of the Banach-Tarski theorem. The Banach-Tarski theorem says that if $B$ is the unit ball in $\Re^3$, there exist pair-wise disjoint sets $\{A_i\}_{i=1}^n$ and isometries $\{\tau_i\}_{i=1}^n$ and $\tau$ such that: $\bigcup_{i=1}^nA_i\;=\;B$ $B\cap\tau(B)=\{\}$ $\bigcup_{i=1}^n\tau_i(A_i)\;=\;B\cup\tau(B)$ In other words, $B$ can be partitioned into sets, and those sets can be moved about and reassembled to make two balls the same as the original. That means there can be no measure satisfying the requirements even when weakened from countable additivity to finite additivity. It's not enough in three dimensions. And that's what the Banach-Tarski theorem is really all about. There's more we can say about this. Do we want or need every set to have a measure? We can define some really weird sets - should it always make sense for them to have a concept of length/area/volume? There is one thing that could save us, and that's the Axiom Of Choice. Or rather, denying the Axiom Of Choice. In each case, showing that in $\Re^1$ there's an unmeasurable set, and showing that in $\Re^3$ we can have a paradoxical decomposition, we need to use the Axiom Of Choice. So maybe we should choose not to believe in the Axiom Of Choice. But that's another discussion. <<<< Prev <<<< Sieve Of Eratosthenes In Python : >>>> Next >>>> Photocopy A Mirror ... You should follow me on twitter Comments I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely. Contents The Point Of The _ Banach-Tarski Theorem Outline of the _ Vitali Set proof Comments Links on this page AMatterOfConvention AnOddityInTennis AxiomOfChoice BeyondTheBoundary BinarySearchReconsidered ColinsBlog ColinsBlog2007 ColinsBlog2008 ColinsBlog2009 ColinsBlog2010 ColinsBlogBefore2007 DecisionTreeForTennis DecisionTreesInGames DiagrammingMathsTopics DissectingACircle DissectingASquare DissectingASquarePart2 DoYouNourishOrTarnish FastPerrinTest FillInTheGaps FindingPerrinPseudoPrimes_Part1 FindingPerrinPseudoPrimes_Part2 GracefulDegradation HackerNewsUserAges Infinity IrrationalsExist LearningTimesTables LimitedAudienceJokes Mathematics MilesPerGallon MultipleChoiceProbabilityPuzzle NASASpaceCrews OnTheRack PhotocopyAMirror PokingTheDustyCorners PublicallySharingLinks RandomEratosthenes RandomWritings RevisitingTheAnt RussianPeasantMultiplication SettingUpRSS SieveOfEratosthenesInPython SoftwareChecklist SquareRootByLongDivision TaggedAsMaths TheAntAndTheRubberBand TheBirthdayParadox TheForgivingUserInterface TheLostPropertyOffice TheTrapeziumConundrum TheUnwiseUpdate ThereIsNoTimeForThis TrackingAnItemOnHackerNews TwoEqualsFour WithdrawingFromHackerNews WrappingUpSquareDissection Site hosted by Colin and Rachel Wright: Maths, Design, Juggling, Computing, Embroidery, Proof-reading, and other clever stuff. Suggest a change ( <-- What does this mean?) / Send me email Front Page / All pages by date / Site overview / Top of page

Added after seeing some discussion ... This is not intended to explain why the Banach-Tarski theorem is true, nor to give a proof, nor to talk about what the pieces look like, etc. No ... the purpose of this article is to explain why the result is relevant. In short, the Banach-Tarski Theorem tells us what is and is not possible in measure theory. It tells us that things we would in general want to be true of a measure are mutually inconsistent. Now read on ... Q: What's an anagram of Banach-Tarski? A: Banach-Tarski Banach-Tarski Now, if you already know what the Banach-Tarski theorem says, that riddle is really funny. If you don't, then you're simply not in the audience, and you'll just go: "Huh?" Which is a perfectly reasonable reaction. Indeed, if you then have the Banach-Tarski theorem explained to you, you most likely will still go: "Huh?" It's a perplexing result, some even call it a paradox, but the fact that it's so odd actually masks the fact that it's a truly important result, with some deep implications. So I'm going to explain here why it's important, and what some of the implications are. The hope is that even if you do know the result you will find this interesting, largely because in the shock of seeing what the result says, you've never been shown why it's interesting. So for those of you who don't know the result, here it is in simple, non-technical terms: In $\Re^3$, given a solid ball $B$ of radius $R,$ it is possible to partition $B$ into finitely many pieces such that those pieces can be reassembled to form two solid balls $B_1$ and $B_2,$ each of radius $R.$ Apart from using the Axiom Of Choice. Now, that's obvious nonsense, and that's why the result is so shocking. It defies common sense, and immediately makes you go looking for some kind of loophole. But there isn't one. So in part because it's so surprising, and shocking, and nonsensical, you might think it's in a dead-end of mathematics and of no real use or interest. That's what this article is intending to address. To do so, let's consider the idea of measurement. We can talk about the length of a line, the area of a polygon (or other shape), the volume of a lump, or whatever. The development of the concept of accurate measurement goes back millennia, and is critical in the development of commerce, engineering, and so many other things. So we're going to look at the concept of measuring something, and see what we can say about it mathematically. To do that we'll talk about a function called a "measure". One of the problems in maths is we use ordinary words in a technical sense, so it's a bit dangerous to call this thing a "measure," but I'll try to use that word only ever in its technical sense. And fairly obviously we'll need a different function, or measure, when we're in one dimension as compared with two dimensions, or more, so we'll talk about a measure for each dimension. So a "measure" is a function that takes a set and returns a number that somehow represents the length, area, volume, whatever. But regardless of dimension there are things we expect a measure to do, ways we expect it to behave. For example, we expect the measure of a zero length line to be zero. We also expect the measure of a non-zero length line to be non-zero. These seem to be obvious requirements. Also, when we're talking about length (or area or volume, etc ) we would expect the sum of the measure of the parts to be the same as the measure of the whole. In other words, if you take the measure of a set, then partition the set into two pieces and take the measure of each of those, you'd expect the sum of the measures to be the measure of the original. Let's start writing these down. If we are working in $n$ dimensions and we have a measure, $\mu$ which is defined on subsets of $\Re^n,$ we expect that: $\mu(\{\})\;=\;0$ - the measure of the empty set is 0. If I is the unit object, then $\mu(I)=1.$ For sets $A$ and $B$ that do not overlap, then $\mu(A{\cup}B)\;=\;\mu(A)+\mu(B).$ If we want to, we can weaken the middle condition to simply ask that $\mu(I)\;>\;0,$ because then we can just apply a scaling. This is like changing units. The last one we can repeat over and over to get the idea of the measure being finitely additive. In fact, we'd really like to extend that to being countably additive, so that: $\mu(\bigcup_{i=0}^{\infty}A_i)\;=\;\sum_{i=0}^\infty\mu(A_i)$ Provided all the sets are (pairwise) disjoint In other words, when we have a set that's made up of countably infinitely many disjoint pieces, we can choose to take the measure of them all and add them up, or we can think of the union of them all, and take the measure of that. But there are other things we expect to be true of a measure. We expect that if we take the measure of something, move the something around, and then take the measure again, we get the same answer. Moving something around should not change its size. In mathematics the idea of moving something around is captured by the idea of what we call an isometry. An isometry is a function that doesn't change distances, so if we have an isometry $\tau$ and apply it to a set $A$, none of the distances between points in $A$ will change, so we can think of $\tau(A)$ as being $A$ moved somewhere else (and maybe flipped over to give a mirror image). So for any set $A,$ and any isometry $\tau,$ then we expect of a measure $\mu$ that: $\mu(A)\;=\;\mu(\tau(A))$ In words, we expect a measure to be isometry invariant. So far: $\mu(I)\;=\;1$ $\mu$ is countably additive $\mu$ is isometry invariant Finally, we'd like $\mu$ to be defined for all sets, although it might end up being infinite if our set is unbounded (and even then not always). So if we have a bounded set (and I've not given a technical definition of what that means) then we would like the measure of that to exist. So we finally want: For all bounded sets $A$, $\mu(A)$ exists. Well, the problem is that we can't have all of these. This was shown in 1905, and is a classic example of a set of desirable requirements that are not mutually satisfiable. In short, these natural and obvious requirements for a measure are mutually inconsistent. We cannot have all of: $\mu(I)\;=\;1$ $\mu$ is countably additive $\mu$ is isometry invariant For all bounded sets $A$, $\mu(A)$ exists. Outline of the Vitali Set proof The idea is: Consider the points from 0 (inclusive) to 1 (not inclusive) Declare two points to be equivalent if they differ by a rational This gives us families of points, the members of a family differing only by a rational number. Points from different families do not differ by a rational. From each equivalence class (family) choose one element Call that set $V$. Given two points in $V$ they do not differ by a rational Enumerate the rationals in $[0,1)$ : $r_0,\;r_1,\;r_2,\;\ldots$ For each rational $r_i$ consider $V_i\;=\;V+r_i\;\;(mod\;1)$ These are disjoint (Exercise: you should check that) For any measure $\mu$, for all $i$, $\mu(V_i)\;=\;\mu(V).$ This requires some proof, but basically $V_i$ is just $V$ moved about. By the properties we have: $\mu([0,1))\;=\;\sum_i\mu(V_i)$ But what can $\mu(V)$ possibly be? If $\mu(V)\;=\;0$ then when we add them all up we get zero, which would mean the measure of $[0,1)$ is zero. If $\mu(V)\;\ne\;0$ then when we add infinitely many together we definitely don't get a finite answer. Which is wrong. Which is wrong. So either way, using only the things we decided were obvious and natural for a measure, we've arrived at a contradiction. So we cannot have a measure that has all the properties that we quite reasonably want. The proof is simple, and can be found all over the 'net. Look for the Vitali Set. So what do we do? Well, what we have to do is relax one of our requirements, and make it weaker. The obvious thing that people want to try is to reduce the power of the additivity rule. So our requirements become: $\mu(I)\;=\;1$ $\mu$ is finitely additive $\mu$ is isometry invariant For all bounded sets $A$, $\mu(A)$ exists. Can we do this? As it happens, for $\Re^1$ we can do this. Even more, for $\Re^2$ we can do this! But for $\Re^3,$ we can't. How do we know? Because of the Banach-Tarski theorem. The Banach-Tarski theorem says that if $B$ is the unit ball in $\Re^3$, there exist pair-wise disjoint sets $\{A_i\}_{i=1}^n$ and isometries $\{\tau_i\}_{i=1}^n$ and $\tau$ such that: $\bigcup_{i=1}^nA_i\;=\;B$ $B\cap\tau(B)=\{\}$ $\bigcup_{i=1}^n\tau_i(A_i)\;=\;B\cup\tau(B)$ In other words, $B$ can be partitioned into sets, and those sets can be moved about and reassembled to make two balls the same as the original. That means there can be no measure satisfying the requirements even when weakened from countable additivity to finite additivity. It's not enough in three dimensions. And that's what the Banach-Tarski theorem is really all about. There's more we can say about this. Do we want or need every set to have a measure? We can define some really weird sets - should it always make sense for them to have a concept of length/area/volume? There is one thing that could save us, and that's the Axiom Of Choice. Or rather, denying the Axiom Of Choice. In each case, showing that in $\Re^1$ there's an unmeasurable set, and showing that in $\Re^3$ we can have a paradoxical decomposition, we need to use the Axiom Of Choice. So maybe we should choose not to believe in the Axiom Of Choice. But that's another discussion. <<<< Prev <<<< Sieve Of Eratosthenes In Python : >>>> Next >>>> Photocopy A Mirror ... You should follow me on twitter Comments I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely.

Read more solipsys.co....