The Infinite Hotel

Originally posted by SPMars
then clearly | R |

well its not clear to me.
why can't it be 2^aleph?

Originally posted by aginis
well its not clear to me.
why can't it be 2^aleph?

What is not clear?

Anyhow I've edited my previous post to give an explanation of why the set of countable subsets of R has cardinality R.

Originally posted by SPMars
R is the set of real numbers.
N is the set of natural numbers.
X is the set of countable subsets of R (including the finite ones).

If C and D are sets let C^D denote the set of functions from D to C.

If C and D are sets then C < D means "there is an injection from C to D" and C=D means "there is a bijection from C to D".

We have

R < X < R^N = (2 ...[text shortened]...

Since we have R < X and X < R it follows from the Schroeder-Bernstein Theorem that X = R.

ok, thats a good proof. so |X| = |R|
therefore |P(R)| = |T(R)| + |R| but it still doesn't follow that |T(R)| = 2^aleph

Originally posted by aginis
ok, thats a good proof. so |X| = |R|
therefore |P(R)| = |T(R)| + |R| but it still doesn't follow that |T(R)| = 2^aleph

The Axiom of Choice is equivalent to the statement that, for any two sets A and B we have A < B or B < A.

We shall assume the Axiom of Choice, as is normal within mathematics.

As proven above, we have P(R) = T(R) + R.

It cannot be the case that T(R) < R, since then

P(R) = T(R) + R = R

a contradiction. Therefore R < T(R) and we have

P(R) = T(R) + R = T(R)

as required.

Originally posted by SPMars
Therefore R < T(R) and we have

P(R) = T(R) + R = T(R)

as required.

|T(R)| + |R| = T(R) ????
this is only proven for known cardinalties however there could exist a cardinality x such that x < 2^aleph but x + aleph = 2^aleph

the proof i used is as follows.

let A = {x < 0 }
B = [0,1]
C = { x > 1}
then |A|=|B|=|C|=|R|
T(R) is a subset of P(R) therefore T(R) < 2^aleph (1)

however if we define S_k = A u K where K is an element of P(B) then
|R|=|A| |R\S_k| = |R| = |S_k|

S = {S_k} is a subset of T(R) therefore
2^aleph = |P(B)| = |S| < |T(R)| (2)

from (1) and (2) it follows that |T(R)| = 2^aleph

Originally posted by aginis
|T(R)| + |R| = T(R) ????
this is only proven for known cardinalties however there could exist a cardinality x such that x < 2^aleph but x + aleph = 2^aleph

I thought that the cardinality of A + B was the max of the cardinalities of A and B? This is assuming the Axiom of Choice which tells us that A < B or B < A. Then the 'max' of A and B is well-defined.

If this is correct then you can say

P(R) = T(R) + R = T(R)

when R < T(R).

I'll go and look it up. If this is true then your statement about x < 2^aleph_1 but x + aleph_1 = 2^aleph_1 can't be right (except in the case that x = 2^aleph_1).

Originally posted by aginis
the proof i used is as follows.

let A = {x < 0 }
B = [0,1]
C = { x > 1}
then |A|=|B|=|C|=|R|
T(R) is a subset of P(R) therefore T(R) < 2^aleph (1)

however if we define S_k = A u K where K is an element of P(B) then
|R|=|A| |R\S_k| = |R| = |S_k|

S = {S_k} is a subset of T(R) therefore
2^aleph = |P(B)| = |S| < |T(R)| (2)

from (1) and (2) it follows that |T(R)| = 2^aleph

Yep that's a nice proof!

I still think mine is fine though, too.

Originally posted by SPMars
Yep that's a nice proof!

I still think mine is fine though, too.

ok i also did a little checking and i see where the communication problem is comming up. I am assumming that the (generalized)continuum hypothesis is false (or at the least i won't use it in a proof).
whereas you are using it to say that
if A,B > aleph_0 then A+B = max {A,B}
that is to say that cardinalities are "known" if
1. it is finite OR
2. it is aleph_0 OR
3.it is of the form 2^x where x is a known cardinality.

then A+B = min {A,B} + max{A,B} < 2*max{A,B} = 2*2^x = 2^(x+1) = 2^x = max{A,B}

however if cardinalities don't have to be of the form 2^x (i.e. continuum hypothesis is false) then this fails.

Since the continuum hypothesis is undecidable anything you can prove with it you should be able to prove without it (i think).

Originally posted by aginis
ok i also did a little checking and i see where the communication problem is comming up. I am assumming that the (generalized)continuum hypothesis is false (or at the least i won't use it in a proof).
whereas you are using it to say that
if A,B > aleph_0 then A+B = max {A,B}
that is to say that cardinalities are "known" if
1. it is finite OR
2. it is undecidable anything you can prove with it you should be able to prove without it (i think).

Hi aginis!

I don't think the continuum hypothesis (generalised or not) has anything to do with it.

What I'm saying assumes the Axiom Of Choice, and that's all. If you believe that (as is often done) then the following theorem is true:

"Let A and B be cardinal numbers, the larger of which is infinite and the smaller of which is non-zero. Then

A + B = A . B = max(A,B)."

This is true for any cardinals A, B.

I have taken this from the book "Elements of Set Theory" by H. B. Enderton, published by Academic Press.

Originally posted by SPMars
Hi aginis!

I don't think the continuum hypothesis (generalised or not) has anything to do with it.

What I'm saying assumes the Axiom Of Choice, and that's all. If you believe that (as is often done) then the following theorem is true:

"Let A and B be cardinal numbers, the larger of which is infinite and the smaller of which is non-zero. Then

A + ...[text shortened]... is from the book "Elements of Set Theory" by H. B. Enderton, published by Academic Press.

i think you are getting axiom of choice mixed with something else.
AoC says that if you have a non-empty set you can choose one of its elements at random.

can you cite a proof of A+B = max {A,B} ?

Originally posted by aginis
i think you are getting axiom of choice mixed with something else.
AoC says that if you have a non-empty set you can choose one of its elements at random.

can you cite a proof of A+B = max {A,B} ?

No, I'm not, honestly. The Axiom Of Choice says that an arbitrary (no matter how large) product of non-empty sets is non-empty. Although this result seems highly plausible, it cannot be proven from the ZF axioms. So "Choice" is added to form the ZFC axioms. The Axiom of Choice is equivalent to Zorn's Lemma, the form in which it's most used.

You can look all this up in Wikipedia.

Consequently, the Axiom of Choice doesn't really say what you have just said. (It says that if you have an arbitrary collection of non-empty sets there's another set containing one element from each set in your collection.)

The proof of the result

A + B = max( A, B )

is longish and I shaln't repeat it here. It's on page 164 of the Enderton book I mentioned earlier (incidently you can view the contents of this book on Amazon).

(Basically the proof goes: if A < B then

A < A + B < A + A = A . 2 < A . A = A

and so A = A + B. But this relies on earlier results.)

The A + B = max( A, B ) result is also mentioned in the section on cardinal addition in the Wikipedia entry on "Cardinal number",

Originally posted by SPMars
No, I'm not, honestly. The Axiom Of Choice says that an arbitrary (no matter how large) product of non-empty sets is non-empty. Although this result seems highly plausible, it cannot be proven from the ZF axioms. So "Choice" is added to form the ZFC axioms. The Axiom of Choice is equivalent to Zorn's Lemma, the form in which it's most used.

You can loo ...[text shortened]... oned in the section on cardinal addition in the Wikipedia entry on "Cardinal number",

thanks i was looking for that but couldn't find it.