Comparing the infinite sequences

What follows is a generalization of the reports on comparing sequences sent recently by George (the teacher of the Sofia group) and Lily (the teacher of the Plovdiv group) and some video-clips I (Jenny) had taken while in Sofia:

Lily: Give me an example of two sequences which according to you have the same size.

Victor:

1,2,3,4,5,6.......   and

2,4,6,8,............

Lily: Why? This is not that obvious.

Victor (Plovdiv): Because they are formed in a similar way and for each number of the first one we can always put a number from the second one. Thus they will be both infinite and for each number of the first one we’ll be able to find another one from the second sequence.

Yana (Sofia) writes on the blackboard the "challenge for the day" - is it true that all the sequences are of the same size?

Yana: Well, for example the even numbers are the half of the natural numbers, aren't they? So we could say that the sequence of the natural numbers is twice bigger than the sequence of the even numbers. Similarly, the odd numbers are the half of the natural numbers, so we could say that the sequnce of the even numbers is equal to a certain extent in size to the sequence of the odd numbers.

1.When can you say two infinite sequences are the same size?

Teddy: Never, because they are infinite and we don’t know the number of their terms.

Ivan, Mitty: Depends on what you mean by “size”.

Teddy: What do WE mean by “size” then?

George: What would you suggest as a measure for the size of a sequence?

Ivan: This could be the difference of the consecutive terms of the sequence.

George: Anything else?

Mitty: I think that we could define three things for determining when one sequence has a greater size than another:

v     The number of the terms;

v     The value of the terms;

v     The distance between consecutive terms

Ivan: I agree, if we could say that there are more terms in a sequence than in another one, the first sequence would be of a greater size.

Mitty: On the other hand, if the distance between the consecutive terms of a sequence is small, i.e. if it grows slowly, and the [corresponding] distance between the consecutive terms of another sequence is bigger we could say that the second one is bigger.

Teddy: This would mean that there are infinities of different size. I think that the number of the terms in a sequence could be bigger than the number of the terms in another one though…

2. Can you give an example of two infinite sequences that are different

sizes? If not, why not?

Victor (Plovdiv): No, there are not such sequences.

Ivan: Well, take these two sequences:

(1) 1,2,3,4,5

(2) 30000, 50000, 70000,…

If we mean ‘the distance between consecutive terms”, then:sequence (2) is of bigger size than (1). But if we think of the number of the terms we couldn’t say that one of them is “bigger”.

Mitty: Here are my two sequences:

(3) 1,2,3,4,..;

(4) 2,4,6,..

I would say that these sequences are different by size but of equal length since the terms of (4) are bigger than the corresponding terms of (3). But they are equally long since neither of them ends - after each pair of odd-even numebrs there follows another pair of odd-even numbers and after each even number there is another even number - both sets are infinite.

Teddy: Yes, but in addition the distance of the consecutive terms of the first sequence (3) is smaller than the corresponding distance of the second one (4) and we could say that the second one grows faster and is bigger than the first one.

George: Can we build a robot (robots) which taking the natural numbers as input would produce two sequences with different number of terms?

Ivan: Yes, we could make the Counter giving 1, 2, 3, … to Robot1 which would produce e.g. 2, 4, 6, … and to Robot2 which would produce a couple of numbers for each natural number, e.g. for input 1 it will produce 1,2 for input 2 -> 2,3, for input 3 -> 3,4 etc. Thus the second sequence 1,2,2,3,3,4,....will have twice as many terms.

Teddy: I can also make robots producing different number of terms:

<robots>

3. If an infinite sequence includes duplicates might it have only a finite number of different terms? If so give an example. If not explain why.

Victor (Plovdiv): If we take the numbers 1,2 and start repeating them infinitely we’ll get an infinite sequence. But since the sequence is infinite there is no way for us to tell how many 1’s and how many 2’s there will be.

George: (This question turned out to be difficult for the kids or maybe it was a matter of interpretation).

Mitty: We can have an infinite set of duplicates, but we could also have only a couple of different numbers which would produce an infinite sequence, e.g.:

(5) 1,2,3,1,2,3,1,2,3,...

5. Are there infinite sequences that have so many terms they can't be

counted?

Ivan: Once a sequence is infinite we can’t count up its terms because they are infinitely many.

Mitty: Yes, all infinite sequences have infinitely many terms and therefore we cant’ count them up!

Jenny: (comment) Here the problem might be with the term we use in Bulgarian (but also even in English). The term “преброявам” we have used corresponds to: “count up”, “take count of”. In Bulgarian this conveys the flavor of a process which should be finished and this contradicts to the notion of “infinite”. A synonym of this verb is “изброявам” which is “to enumerate, to list”. I think that if we had said instead “enumerate” the answers would be different…

4. Can you describe sequences that can't be programmed?

Ivan: I guess that one could program any sequence.

George: Is there a sequence for which one wouldn’t be able to predict the next term?

Ivan: No…

George: Could we make a robot which generates an irreproducible sequence.

Ivan: No, if we have made a robot somebody else would be able to make it as well.

Mitty: Well, what about the following:

(6) 1, -70, 1000000… and whatever crosses my mind at the moment…

Teddy: You mean a sequence of random numbers…

Yana: I was thinking the same. So let me write it down on the board!