Showing that Increasing sequences of natural numbers is uncountable

[renjean]

Homework Statement

Show that A, the set of all increasing sequences of natural numbers is uncountable

Homework Equations

I know that the natural numbers themselves are countable.

The Attempt at a Solution

I am thinking of using some sort of diagonal argument to prove this.

 

[mtayab1994]

Well take the example:

Let R denote the reals. Let R′ denote the set of real numbers, between 0 and 1, having decimal expansions that only involve 3s and 7s. s. (This set R′ is an example of what is called a Cantor set. ) There is a bijection between R′ and the set S of infinite binary sequences. For instance, the sequence 0101001.. is mapped to .3737337... Hence R′ is uncountable. Hope this gives you a clue on how to start.

 

[Dick]

You probably know how to show that the set of all infinite sequences of 0's and 1's is uncountable by a diagonal argument. Can you think of a bijection between infinite sequences of increasing natural numbers and infinite sequences of 0's and 1's?

 

[mtayab1994]

You probably know how to show that the set of all infinite sequences of 0's and 1's is uncountable by a diagonal argument. Can you think of a bijection between infinite sequences of increasing natural numbers and infinite sequences of 0's and 1's?

That's kind of what I was trying to tell him.

 

[Dick]

That's kind of what I was trying to tell him.

Yes, I see that it was. Sorry to be redundant.

 

[mtayab1994]

Not a problem he's here for our help.

 

[renjean]

That helps a lot! Thank you to the both of you.