From a Foundations of Mathematics course PROVE the mathemati

From a Foundations of Mathematics course:

PROVE the mathematical statement:

\" The set of all infinite sequences of 0\'s and 1\'s is uncountable. \"

Solution

uppose that we have the set SS of all possible infinite binary sequences sisi (a sequence is simply an ordered set):

S={s1,s2,s3,…}

where the sequences sisi are like {1,1,1,1,…}, {0,0,0,0,…}, {0,1,0,1,…}etc.

Suppose for the sake of contradiction, that S was countably infinite; Cantor\'s diagonal argument tells you how to construct, for any countably infinite collection of binary sequences, a binary sequence not in that collection. Thus, the set S of all binary sequences (which is a perfectly well-defined object) is uncountable.