Cardinality Question

MrJB

I'm fairly sure that the intervals (0,1) and [0,1] of real numbers have the same cardinality, but I can't think of a bijection between them. Any thoughts?

Hurkyl

Let's start with a warmup exercise:

Can you find a bijection between the set of all nonnegative integers and the set of all positive integers?


Once you've answered that, can you think of a way to apply this very example to your problem? Or at least this technique?

MrJB

Well, for the warm-up, I'd define f(n)=n+1 as my map from the set of nonnegative integers to the set of positive integers. Thus, 0,1,2... would get mapped to 1,2,3... etc.
I don't see the connection to my problem though.

morphism

I'm wondering why you want to find a bijection. Very rarely does one produce an explicit bijection to show that two sets have the same cardinality. One of the main tools is the Shroeder-Bernstein theorem: it says that if you have an injection from A into B and an injection from B into A, then there exists a bijection between A and B (note: this is an existence result; it doesn't tell us how to construct the bijection). You can apply it to your problem.

In regards to Hurkyl's hint, try using this to find a bijection between [0,1] and (0,1], for example.

MrJB

I was just curious what such a bijection might look like.

In regards to the Schroeder-Bernstein Theorem, the injection from (0,1) into [0,1] is obvious, and the injection from [0,1] into (0,1) I can define as f(x)=x/2+1/4. So there is a bijection between them.

I'm still lost on Hurkyl's hint. With the integers, my map just moved all the elements to the next integer, but with the reals there is no 'next' real.

morphism

How about, say, the sets {1/n : n a positive integer} and {1/n : n a nonnegative integer} in [0,1]?

Hurkyl

What this tells you is that, if you're given a countable set, you know how to make an individual point "appear" or "disappear".

Now, if you could find a countable subset of [0, 1], then you know how to make a point of that subset disappear...

MrJB

I think I can work with that...

So my map would take the set {1/n : n a positive integer} to {1/(n+1) : n a positive integer}. That is, 1,1/2,1/3... would map to 1/2,1/3,1/4... and the rest of the reals would map to themselves, thus defining a bijection from [0,1] to [0,1). Then I would repeat a similar technique to the other side.

Thanks.

Hurkyl

Yep. That is the basic technique for "removing" individual points from an infinite set. The core idea works in a wide variety of situations.

MrJB

Awesome.
You could use the same idea to 'remove' infinite sets of points too? If I wanted to map the closed unit disc to the open unit disc, I would map the sets of points with distances from the origin 1,1/2,1/3 to the sets of points with distances 1/2,1/3,1/4 from the origin?

Hurkyl

That certainly seems to work!

fopc

Thoughts on an example construction of f:[0,1] -> (0,1) that's bijective. (There are many such f's.)

1. The sets differ only at two points, 0 and 1.
2. Must find images for 0 and 1 somewhere in (0,1) while still keeping f bijective.
3. Let A={0,1,1/2,1/3,...,1/n,...}. (Something like this has already been suggested.)
4. Send 0 to 1/2, and 1 to 1/3.
5. This can be effected by, f(0)=1/2, f(1/n)= 1/(n+2) for n >= 1.

6. Then complete the definition of f by, f(x)=? for all x in ?

The final step is to actually verify that f is bijective.

Typically, it's easier to find two injections than one bijection.
This example brings the point out a little bit.
So yes, in many cases Schroeder-Bernstein has considerable practical value.
But, it's greatest value is theoretical, not practical.
I'd say there's something to be learned by actually constructing an f (like the one above), and demonstrating that's it's bijective.


EDIT: I'll complete the definition of f.
f(x)=x for all x in [0,1]-A. (Obviously there was a reason for A.)

HallsofIvy

Try this: irrational numbers between 0 and 1 map into themselves.

The rational numbers between 0 and 1 are countable so the can be written in a list:
[itex]r_1, r_2, r_3, \cdot\cdot\cdot[/itex]. Now map [itex]r_1\rightarrow 0[/itex], [itex]r_2/rightarrow 1[/itex], [itex]r_3\right arrow r_1[/itex], [itex]r_4\rightarrow r_2[/itex],[itex]\cdot\cdot\cdot[/itex], [itex]r_n\rightarrow r_{n-2}[/itex].

grossgermany

Still why would this be bijective? How do you know that step A 1/n->1/(n+1)
and step B f(x)=x for all x in [0,1] won't end up in the same number.
I know intuitively it makes sense, but it doesn't seem very mathematically rigorous.

fopc

I suspect you didn't read the EDIT.
It reads, f(x) = x for all x in [0,1]-A.

Not mathematically rigorous?
Well, I defined an f, and made a claim that f is a bijection; nothing more. I then suggested the need to demonstrate this by showing f is injective and surjective. There's hidden value here. It forces you to think about definitions.

You question that f is bijective (in particular you seem to doubt that it's injective). Well?

Finally, I apologize to Ernst. It should be Schröder.