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

Cantor's Diagonal Argument

  1. Aug 25, 2011 #1
    I was reading this up on Wiki so I'll just give a quick overview and then ask my question.

    Let [itex]\cal{S}[/itex] be an infinite sequence of sequences [itex](s_1,\; s_2,\: s_3,...,\; s_n)[/itex] such that each [itex]s_i[/itex] contains an infinite amount of elements that are either a [itex]0[/itex] or a [itex]1[/itex].

    The sequence [itex]\cal{S}[/itex] is countable since every element belonging to the sequence can be mapped to [itex]\mathbb{N}[/itex] i.e it is bijective.

    Now for the sake of simplifying, let [itex]n[/itex] represent the sequence number and [itex]m[/itex] be the element of the sequence.

    For example let [itex]s_1 = (1,\; 0,\; 0,\; 1,... )[/itex] then [itex]s_{1,\; 1} = 1[/itex]

    Let there exist a sequence [itex]s_0[/itex] such that the first element of [itex]s_0[/itex] is [itex]0[/itex] if the first element of the first sequence i.e [itex]s_{1,\; 1}[/itex] in [itex]\cal{S}[/itex] is [itex]1[/itex] otherwise let [itex]s_{0, 1}[/itex] be [itex]1[/itex]. This rule applies for all elements of [itex]s_0[/itex] such that any [itex]s_{0,\; n} \neq s_{n,\; n}[/itex]. This proves that [itex]s_0[/itex] is unique but how does it prove it's uncountable? I mean if [itex]n[/itex] represents the element number of the sequence [itex]s_0[/itex] and every [itex]n[/itex] can be mapped to a subset of [itex]\mathbb{N}[/itex] isn't it countable?
    Last edited: Aug 25, 2011
  2. jcsd
  3. Aug 25, 2011 #2
    You just showed that [itex]s_0[/itex] is not any [itex]s_i[/itex] for i > 0. So your original list does not contain ALL of the possible binary sequences. But since your original list S was arbitrary, that shows there is no list that contains all binary sequences. So the number of binary sequences is uncountable.
  4. Aug 25, 2011 #3
    Oh, very good. I think I read the conclusion wrong, I get it now. Thanks!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook