An intermittently philosophical blog

n objects can be arranged exactly n! ways. Thats easy to work out for a finite amount of objects say 3! = { 132, 312, 321, 213, 231 } = 6. But for an infinite amount?

Incidentally, I thought of operations to manipulate a list to rearrange the elements. It turns out all you need is a operation which swaps the nth element with the n+1th element (like in a bubble sort). For instance you can rearrange 123 into 321 by the following steps

123 ( swap 1st and 2nd ) rule 1
213 ( swap 2nd and 3rd ) rule 2
231 ( swap 1st and 2nd ) rule 1
321

Its not very efficient and there is more than one way to do it (we could have done the swaps in a different order). We could use a natural number to label each swap, so to go from 123 to 321 we applied 121 = (1)swap 1 and 2, (2)swap 2 and 3, (1)swap 1 and 2 again.

Another example

123456 S135
214365 S24
241635 S135
426153 S24
462513 S135
645231 S24
654321

Total rule = S135241352413524

We could say 123456 S 135241352413524 = 654321

By swapping adjacent elements can we ever completely reverse an infinite list? apart from the fact the natural numbers have no highest element so i’m not sure what it would look like, the rule to get 1 from the beginning to the “end” of the list is not even finitely representable in my notation – it would be S123456789….inf

I was never really happy with the assymetry in the natural numbers in that you can’t really reverse the list as there is no last element, so you cant really swap the first and last element even if you could do it in one operation. I did think that perhaps it didn’t matter that you couldn’t completely reverse the list as the list reversed is pretty much the same object as the list not reversed.

Yesterday I realised there are sets with the same cardinality as the natural numbers that do have a distinct least and greatest element. One such set is the set of fractions between 0 and 1. Each member has the property of being less or greater than every other member, there are no adjacent elements like there is in the naturals but at least first and last elements can be swapped.

Its much easier to deal with if we don’t use all the fractions but just 0 , 1 and odd multiples of all the the powers of 1/2 in between. i.e.{ 0, 1, 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, … }

In binary = { 0, 1, 0.1, 0.01, 0.11, 0.001, 0.011, 0.101, 0.111 }

However I still can’t figure out how many arrangements there are, even though I can describe an operation to reverse the elements (replace each element with 1 – element) and imagine the result.

Apparently dividing a cake into two pieces fairly is easy. One person cuts and the other can choose which piece they want. Both should be happy seeing as one has made a cut which they presume as fair and if the other thinks its unfair then he can just choose the bigger piece.

Cutting a cake into three pieces so everyone is happy is trickier, its a problem posed in Ian Stewart’s book “Cabinet of Mathematical Curiosities”. I came up with a solution based on the binary expansion of 1/3 which is 0.01010101…, basically you cut the cake into 4, so you have a spare piece then divide the spare piece into 4 and so on until there’s only crumbs.

Repeatedly dividing the number line into three pieces gives rise to the ternary cantor set. It just doesn’t work in binary. I tried it. Anyway this is how it goes. Take the interval closed interval [0, 1] and remove the open middle third (1/3, 2/3) leaving [0, 1⁄3] U [2⁄3, 1]. Next remove the open middle third segment of those segments and repeat ad infinitum.

What you are left with is a very interesting object. I don’t really know much about it yet except that it has as many points as is in the interval [0, 1] even though the entire length has been removed and 1/4 is in the set which has a ternary representation of 0.02020202020…

A device for choosing a random number from the natural numbers (courtesy of Brian) is a correctly programmed coin computer

Step 0: Think of the number zero.
Step 1: Flip a coin, if it land heads up add one to the number you are thinking of and repeat step 1.
Step 2: Write down the number you are thinking of.

The output will be a non-negative integer and the average number output if repeated will be 1.

Brian thought the problem with the black and white balls were similar to a series named after Grandi. 1 – 1 + 1 – 1 + 1 – 1… Many have argued about the evaluation of this sum. Depending on how you group the terms, you can get it to sum to almost anything. If you bracket it like this. ( 1 – 1 ) + ( 1 – 1 ) + ( 1 – 1 )… it comes to 0. If you bracket it like this 1 + ( -1 + 1 ) + ( -1 + 1 ) + ( -1 + 1 )… it comes to 1. Grandi and many others have argued that it is in fact 1/2.

Grandi noted the binomial expansion of 1 / ( 1 + x ) is 1 + x^2 – x^3 + x^4 – x^5… If you substitute 1 for x you get 1/2 on the left and Grandi’s series on the right. Whilst this seems a good argument for the sum being 1/2, a further argument by Grandi in the form of a story

“Two brothers inherit a priceless gem from their father, whose will forbids them to sell it, so they agree that it will reside in each other’s museums on alternating years. If this agreement lasts for all eternity between the brother’s descendants, then the two families will each have half possession of the gem, even though it changes hands infinitely often”

As time goes on, the amount of time the gem spends with one brother divided by the total time approaches 1/2. If you apply this same logic (although i’m not sure you can) to Grandi’s series then as the series goes on the number of positive terms divided by the total number of terms approaches 1/2 but then if 1/2 the terms are +ve and 1/2 -ve then I would expect the sum to equal 0 not 1/2.

However Grandi did think the sum was both 0 and 1/2 and used this as a theological argument as how god could have created the universe out of nothing.

I wonder if people make mistakes because they assume that things can be divided into pieces in a certain ratio. For instance a cake can be divided into two equal pieces, well roughly at least. Four apples can be split into two piles of two apples. We are used to finite quantities that can be compared, a < b, or a is 2 x b, etc. We are so used to this that it guides us in thinking about things that it may in fact not apply to.

We might say that if a bag contains an equal number of black and white balls that the chance of picking out a white ball is 1/2. If the number of balls in the bag was finite I don’t suppose many people would disagree.

When dealing with infinite sets and infinite subsets of them all is not so simple. Indulge me for a moment and suppose that a bag is filled with an infinite number of balls, all numbered with a natural number, 1, 2, 3, 4, 5, etc and that the odd numbered balls are coloured black and the even numbered balls coloured white. What now is the chance of picking a white ball?

In the finite case we just worked it out as a ratio. In the simplest case there is one black and one white ball, so of course its 1/2, the white is one possibility out of two.

In the infinite case its not possible to do that. Infinity over infinity does not compute. The most reasonable way out of it is to be more precise about the selection mechanism. We use a the toss of coins to select the ball. The first toss decides whether it is even or odd. If it lands on heads then we pick an even ball, if it lands on tails, an odd ball. Then we have our expected answer 1/2.

This is very unsatisfactory as it seems we’ve only really got this answer because its what we expected. We intuitively “know” the answer must be 1/2 so we devise a selection mechanism that gives us the right answer.

Now at this point you might be thinking this is stupid. Of course its paradoxical, because we can’t really have a bag with an infinite number of balls in, that’s the problem. Or you might rightly object to the idea of “random” selection, of course that’s going to lead to different answers depending on the selection mechanism.

Lets go back to the example with two balls. The probability of the ball being picked being white is 1/2, but why? Because that’s what we observe, with real balls and real bags? If we are more precise we could say that we choose the ball by tossing a coin which we assume to be fair and choose white for heads and black for tails. Now can we be sure the answer is half. But we’ve only really done the same trick here as we did with the infinite balls. It just happens that the ratio of white balls to balls is 1/2 and we observe that is the same as the probability of getting a white ball.