by Brian Bosse, Copyright March 17, 2008, all rights reserved. 78 views
In part I, we saw that on the assumption R is countable, then there exists a function, f, whose domain is the set of natural numbers and whose range is the set of real numbers. In other words, the elements in N are uniquely mapped to elements in R such that there is no element in R that is not mapped to by an element in N. If we could find an element in R that is not mapped to by an element in N, then this would contradict our assumption that f is bijective. Let's look at our mapping function from part I…
Domain (N) Range (R)
1 f(1) 256
2 f(2)
3 f(3)
4 f(4) 5/9
. . .
. . .
. . .
n f(n) r
. . .
. . .
. . .
By the assumption that R is countable, and that f is bijective, this listing above represents a complete listing of the real numbers as they correspond to the natural numbers: '1′ corresponds to '256′ - '2′ corresponds to '' - '3′ corresponds to
- and so on and so forth. Consider the numbers in the range of f, i.e. the real numbers 'r'. I would like to represent these numbers with their full decimal expansions. The following table shows this…
Domain (N) Range (R)
1 f(1) 256.0000…
2 f(2) 3.1415…
3 f(3) 1.4142…
4 f(4) .5555….
. . .
. . .
n f(n) r
. . .
. . .
. . .
Consider each real in the list above, but only that part of the real after the decimal point. In other words, our first listed real is '256.000…' We are only going to consider the '.0000…'. Regarding our second listed real, we are only going to consider the '.1415…'. And so on and so forth. In other words, we have the following…
1 ↔ .0000…
2 ↔ .1415…
3 ↔ .4142…
4 ↔ .5555…
…
As can be seen, I have highlighted the first digit after the decimal place that corresponds to '1′. I have highlighted the second digit after the decimal place that corresponds to '2′. I have highlighted the third digit after the decimal place that corresponds to '3′. And so on and so forth. At this point, we now perform the action called diagonalization on all of the highlighted numbers in the above array to create a new real number. We take a number in the diagonal and if it is '5′, then we change it to a '6′. If the number in the digonal is any number other than '5′, then it is changed to a '5′. Since the first highlighted number in our above diagonal is a '0′, then we change it to a '5′. Since the second highlighted number is a '4′, then we change it to a '5′. Since the third highlighted number is a '4′, then we change it to a '5′. Since the fourth highlighted number is a '5′, then we change it to a '6′. And so on and so forth. This creates the following real number…
DN = .5556…
Is DN in the list above? Remember, the list above is suppose to be a complete listing of all real numbers, and as such is supposed to contain DN. However, DN is different than the first number because the first digit after the decimal in the DN is different than the first digit after the decimal of '256.0000…'. DN is different than the second number because the second digit after the decimal in the DN is different than the second digit after the decimal of '3.1415…'. In fact, given any 'n' and its corresponding 'r' in the list, the DN differs from this 'r' precisely at the nth digit after the decimal place of the 'r'. As such, DN is a real number that is not in our list. This contradicts our assumption that f is bijective. Based on this, we conclude that R is uncountable. Q.E.D.
-----No comments yet.