The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Replies: 3   Last Post: May 22, 2012 6:10 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Torben Mogensen

Posts: 60
Registered: 12/6/04
Posted: May 22, 2012 5:53 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Graham Cooper <> writes:

> On May 22, 2:46 am, (Torben Ægidius Mogensen) wrote:
>> Graham Cooper <> 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

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.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.