Math Forum Discussions

Torben Mogensen

Posts: 60
Registered: 12/6/04

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

Plain Text

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 re-order <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 oo-1 X oo-2 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