[Gilgames]

Consider the following problem: We have the following sets:

A={S where S is a bounded sequence of natural numbers}
B={S where S is an increasing bounded sequence of natural numbers}

I need to prove that set A is not denumerable and set B is denumerable.

For the first one, could I use Diagonal Argument like this:
Let's suppose that A is denumerable. Then we can find a function that puts all bounded sequences into a one-to-one correspondence with the positive integers. Let's construct another sequence, that is different in the first number from the maximum element of sequence1, is different in the second element from the maximum element of sequence2 etc. Then we have a sequence that is different from every other sequence in A but cannot be in one-to-one correspondence with a positive integer. So we have supposed wrong and A is not denumerable.

Is something like this correct?

Also for B, can I prove it by enumerating all the elements of the set like this:

B={maximumValueOfsequence1,maximumValueOfsequence2 ,. etc}

A little help would be really appreciated :o

[Elisha Grey]

The trouble with your solution for A is, is the resulting sequence bounded?

As for B, there is no increasing bounded sequence of natural numbers. This is because, if a sequence is bounded, say by X, then all the numbers of the sequence must be no greater than X. But there are only a finite number of natural numbers no greater than X.

If however you mean non-decreasing instead of increasing, then such a sequence must eventually be of constant terms. These sequences can be mapped onto the natural numbers as follows: the sequence b1, b2, b3, bn, bn, bn, Is mapped onto the natural number b1b2b3... bn. Hence this set is denumerable.

I was a little hasty in my last post. The mapping I suggest is not one-to-one. However there are only a finite number of sequences that map into a given natural number, so this set is still denumerable.

Also of course my sugggested solution is very similar to yours.

Of course your method works. You just have to be a little more careful.

Form a new sequence as follows: if the nth term of the nth sequence is 1 then the nth term of your new sequence is 2. otherwise it's 1.

Then clearly your new sequence is not on th llist, and is bounded (by 2). So the bounded sequences are not denumerable.