Proving the Equivalence of Cardinalities with Hilbert's Hotel

[Auron87]

Just come across this question on a problem sheet and it's got me rather confused!
You have to prove that |[0,1]|=|[0,1)|=|(0,1)| without using Schroeder-Bernstein and using the Hilbert Hotel approach. After looking at the Hilbert Hotel idea I can't really understand how this helps! This questions quite bugging me now!

Thanks for any help!

 

[matt grime]

You're probably trying to write down nice functions, don't.You can biject the rationals {1/n : n in N} with a proper subset of itself a la hilbert hotel, this gives you a bijection between [0,1] and [0,1) by extension, and shows you how to explicitly write bijections between any infinite set S and S\F for any finite subset F.

 

[mathwonk]

clever. i kind of like the bernstein approach.

i just discovered for myself (while teaching an elementary course in proofs) the well known idea of defining an injection from positive rationals to positive integers sending n/m to 2^n 3^m.

to me this is nicer since it can be written down, than cantors diagonal construction of a surjection fro Z+ to Q+.

by the way bernstein's theorem was proved first by cantor, but with the hypotheses that all infinite sets are comparable. i did not know this either until today.

my extreme ignorance is offered as a lesson of inspriation to all budding mathematicians, i.e. even if you do not know squat, you can still create a lot of new mathematics, in some specialized field.

 

[matt grime]

The prime power proof certailny far nicer than the diagonal counting argument for at least two reasons.

1. it embodies a general constructive proof that the finite union of any countable sets is countable since there are infinitely many primes.

2. it doesn't use the word diagonal: diagonal proofs show that Q is countable and that R is not; this is a a pedagagoically stupid situation.

 

[VazScep]

The prime power proof certailny far nicer than the diagonal counting argument for at least two reasons.
1. it embodies a general constructive proof that the finite union of any countable sets is countable since there are infinitely many primes.

And indeed, any countable union of countable sets, $\bigcup_{k\in\mathbb{N}}A_k$, is countable. If $f_k$ is a bijection from $A_k$ to $\mathbb{N}$ then we have the injection $x \mapsto 2^m3^n$ where $m$ is the smallest natural number such that $x\in A_m$ and $f_m(x)=n$.

 

[matt grime]

Does that work? It doesn't appear to, in fact it appears to fail spectacularly to even be a function. Of course i might be wrong, but it just doesn't appear to make sense as a definition. I mean, what if all the A_k are equal (say N) and each f_k is the identity. Then how does that map even work? I can see how it could be altered to be an injection, since any element in the union is uniquely specified by a 2-tuple (p,q), but just not by the definition given.

In any case I meant to state that the method given generalizes to show that any finite *product* of countable sets is countable, not finite *union* (or coproduct). finite coproducts and countable coproducts of countable sets are easily shown to be countable.

 

[VazScep]

Does that work? It doesn't appear to, in fact it appears to fail spectacularly to even be a function. Of course i might be wrong, but it just doesn't appear to make sense as a definition. I mean, what if all the A_k are equal (say N) and each f_k is the identity. Then how does that map even work?

In this case, the union is just $\mathbb{N}$, and for any $x\in\mathbb{N}$, the smallest $m$ such that $x\in A_m$ is 0. Since $f_0$ is the identity function, $x$ is mapped to $2^03^x=3^x$.

I don't really like the way my definition reads. One small modification: Let $g:\bigcup_{k\in\mathbb{N}}A_k\rightarrow\mathbb{N}$ be the function $x \mapsto 2^m3^{f_m(x)}$ where $m$ is the smallest natural number such that $x\in A_m$.

I can see how it could be altered to be an injection, since any element in the union is uniquely specified by a 2-tuple (p,q), but just not by the definition given.

In any case I meant to state that the method given generalizes to show that any finite *product* of countable sets is countable, not finite *union* (or coproduct). finite coproducts and countable coproducts of countable sets are easily shown to be countable.

Ah, right.

 

[matt grime]

Ah, I see what's wrong (in my viiew). Your unions are not taken to be disjoint unions. Usually, in set theory questions like this, we assume the unions are disjoint. So in my example where each A_k is a copy of N we view them as distinct copies of N so that the '3' in the first copy is not the same '3' as the one in the second copy. THis is probably just me being sloppy.