Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: ALL PERMUTATIONS OF INFINITY
Posted:
May 22, 2012 5:53 AM


Graham Cooper <grahamcooper7@gmail.com> writes:
> On May 22, 2:46 am, torb...@diku.dk (Torben Ægidius Mogensen) wrote: >> Graham Cooper <grahamcoop...@gmail.com> writes: >> > How many ways can you reorder <f, a, t> ? >> > <f a t> >> > <f t a> >> > <a f t> >> > <a t f> >> > <t f a> >> > <t a f> >> >> > 3! = 3 Factorial = 3X2X1 = 6 >> >> > How many different ways can you order <1,2,3,4....> ? >> >> > oo X oo1 X oo2 X .... X 3 X 2 X 1 >> > It's not well defined! >> >> Not if you write it like this, but the number of permutations of a set >> is well defined even for infinite sets  just like the number of all >> subsets of a set is defined even for infinite sets. >> >> For finite and infinite sets, two sets are considered to have the same >> number of elements if there exists a bijection between them. For >> example, the set of even naturals has the same size as the set of all >> naturals (N), because f(n)=2*n is a bijection between naturals and even >> naturals. For the same reason, the set of all sets of naturals (P(N) >> or, equivalently, 2^N) has the same size as the set of real numbers (R): >> There is a bijection between sets of naturals and reals. >> >> There is a bijection between permutations of N and subsets of N, so the >> set of permutations has the same size as the set of subsets. >> >> > How are you calculating O(2^alepth_0) for an algorithm PS(N) you claim > doesn't exist?
I didn't say I could _calculate_ the value, just that I could reason about it. This is similar to reasoning about the exact value of pi even though you can never calculate it.
> You must have ASSUMED the amount of subsets of N is 2X2X2... = R
Not at all. This is, in fact, fairly easy to prove: We use the theorem that there exists a bijection between two sets A and B if there exists an injection from A to B and an injection from B to A. So all we need to do to prove that P(N) = R is to find injections both ways.
First, we define a mapping from R to P(N). This works as follows:
Write the real number x as a binary string s b_n ... b_1 . d_1 d_2 ... where s is the sign, b_i are the bits of the integral part and d_j are the bits of the fractional part.
For reals that have two binary representations (such as 1 which can be represented both as 1.000... and 0.111...), we choose the one without an infinite sequence of 1 bits.
From this we construct a set of naturals:
 if s is positive, 0 is in the set.  if b_i is 1, 2i is in the set.  if d_j is 1, 2j+1 is in the set.
Clearly, different real number produce different sets, so this mapping is an injection.
Going the other way, we have a set which is either finite or infinite. For a finite set {n_1,n_2,...,n_k}, we produce the number 2 + 2^n_1 + 2^n_2 + ... + 2^n_k. So we get a number greater than or equal to 2.
For an infinite set {n_1,n_2,....}, we produce the number 2^(n_1) + 2^{n_2} + ..., which is a number between 0 (exclusive) and 1 (inclusive).
Clearly, every set maps to a different real number, so this mapping is an injection.
Since we have injections both ways, the sets are equipotent (i.e., having the same size).
> You're the ones who can't find algorithms to Halt(), Prv(), PS() not > me!
With all due respect, neither can you.
> Perm(N) clearly has complexity O(1X2X3X4X5...) > > 1X2X3X4X5X6... > 2X2X2X2X2X2...
I can in a similar way "prove" that 1X2X3X4X5X6... < 2X2X2X2X2X2...:
Each integer n is smaller than 2^k for some k. So by grouping a sufficient number of 2s in the product to the right, we get:
1 x 2 x 3 x 4 x 5 x 6 ... < 2 x (2x2) x (2x2) x (2x2x2) x (2x2x2) ...
So we have a product to the left where all factors are smaller than the factors in the product to the right. So, clearly, the product on the left is smaller. And by associativity of multiplication, 2 x (2x2) x (2x2) x (2x2x2) x (2x2x2) ... = 2x2x2x2x2x2x2x2x2x2x2..., so we have 1x2x3x4x5x6... < 2x2x2x2x2x2.... QED.
Torben



