Cantor's Diagonal Argument

  • #1
901
2

Main Question or Discussion Point

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:

Answers and Replies

  • #2
795
7
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 [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].
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.
 
  • #3
901
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.
Oh, very good. I think I read the conclusion wrong, I get it now. Thanks!
 

Related Threads on Cantor's Diagonal Argument

  • Last Post
2
Replies
49
Views
9K
  • Last Post
2
Replies
38
Views
9K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
3
Replies
62
Views
4K
  • Last Post
Replies
17
Views
779
  • Last Post
4
Replies
86
Views
4K
Top