Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor proof / infinite binary sequences

  1. Apr 12, 2013 #1

    I've been reading a textbook on set theory and came across Cantor's proof of the statement that the set of the infinite binary sequences is uncountable. However there is one thing that is not clear to me:

    The nth such sequence would be:
    An = (an,0,an,1,...), n = 0, 1, 2,...
    where all these elements are either 0 or 1.

    Δ = {A0,A1,...}, the set consisting of all these sequences would look like:

    A0 : a0,0 a0,1 a0,2...
    A1 : a1,0 a1,1 a1,2...
    A0 : a2,0 a2,1 a2,2...

    where again all these elements would be 0's or 1's.

    Cantor proved that Δ is uncountable.

    However, if we consider all the terms of these sequences, as terms and not as numbers, they seem to be countably many. We can use Cantor's first diagonal method to show that. It is the same argument as the one used to show that that the union of a sequence of countable sets, is countable.

    This seems like a paradox to me, since every sequence has countably many terms and according to cantor's proof, these sequences are not countable, so one whould expect that the terms of all of these sequences would not be countable.
  2. jcsd
  3. Apr 12, 2013 #2


    User Avatar
    Science Advisor

    You sound confused. The Cantor argument is: assume ∆ is a complete list of ALL binary sequences, however a binary sequence can be constructed that is NOT on the list, therefore ∆ is incomplete - a contradiction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook