Let S denote the set of all innite tuples s = (s1, s2, . . . , sn, . . .)with en
ID: 2941995 • Letter: L
Question
Let S denote the set of all innite tuples s = (s1, s2, . . . , sn, . . .)with entries in N. In other word, S is a countably innitecartesian product of copies of N, sometimes denoted N^N. We want to show that S is uncountable.To do so, suppose that there is a bijection f : N S and, foreach k, let f(k) = sk = (sk1, sk2, . . . , skn, . . .). For every i, let tibe an integer dierent from sii. What can you say about the element t = (t1, t2, . . . , tn, . . .) compared to the sk’s. Argue bycontradiction to show that S is uncountable.
Explanation / Answer
Definition. Call a set S countable iff it has a bijection with the natural numbers N. (Sometimes this is used as the definition for "countable" -- sometimes "countable" is also allowed to mean "finite." We'll use this as the definition here.)
Proof by contradiction. (This is what's known as a "diagonalization" proof for showing set uncountable. You'll see why.)
We assume that there is some bijection f:N->S. We'll label the infinite tuples in S according to what elements in N map to them, which is possible because we have a bijection. We'll say f(1) = s1, f(2) = s2, f(3) = s3, and so on. Let's list these out in order according to which natural number maps to them:
f(1) = s1 = (s11, s12, s13, s14, s15, ..., s1n, ...)
f(2) = s2 = (s21, s22, s23, s24, s25, ..., s2n, ...)
f(3) = s3 = (s31, s32, s33, s34, s35, ..., s3n, ...)
f(4) = s4 = (s41, s42, s43, s44, s45, ..., s4n, ...)
....
f(k) = sk = (sk1, sk2, sk3, sk4, sk5, ..., skn, ...)
....
Since this list will eventually include f(k) for every natural number k, it lists the function on every value in its domain. As f is bijective, it must be surjective, which means that every element in the range must get mapped to, and since this list includes every possible instance of the function acting on its domain, we therefore know that every possible infinite tuple in S is somewhere in this list.
Now let's create one that isn't there, and get a contradiction!
For every natural number i, define a new natural number ti such that ti does not equal sii. We can define ti any number of ways to make it different from sii; one easy way is to let ti = sii + 1.
In words, what we are doing is looking at the list of tuples above and going down the diagonal from the upper left. We're taking the first entry from s1, adding 1 to it, and calling that the first entry of t. We're taking the 2nd entry of s2, adding 1 to it, and calling it the second entry of t. We're taking the 3rd entry of s3, adding 1 to it, and calling it the third entry of t. And so on, using the entries on the diagonal, each with 1 added to them, to compose the components of t. Eventually we have
t = (s11+1, s22+1, s33+1, s44+1, s55+1, ..., snn+1, ...).
And drumroll, please: t differs from every sk in the kth element. The first element of t differs from the first element of s1 -- it's one greater -- so since the first element of t doesn't match the first element of s1, t does not equal s1. The second element of t differs from the second element of s2 -- again, we've made it one greater -- so since their second elements don't match, t does not equal s2. The third elements of t and s3 don't match, so t does not equal s3. And so on. For any k, the kth element of sk does not match the kth element of t, so t does not equal sk for any sk on the list above! But that means that we've just found an infinite tuple in S missing from the list -- which contradicts the fact that we thought we listed them all! We concluded we had listed them all because we listed every instance of f and we had assumed f was a bijection. But clearly f cannot be a bijection, since listing every result f(n) for n in N still does not list every infinite tuple in S, meaning f cannot be surjective and thus not bijective. As f was a completely arbitrary function, defined only as a function that was a bijection between N and S, there can be no such function possible. Since there is no possible bijection between the natural numbers and S, S is uncountable.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.