by Brian Bosse, Copyright March 17, 2008, all rights reserved.
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.
-----Posted in Cantor's Theorem • 0 Comments • Permalink • 80 views
by Brian Bosse, Copyright March 15, 2008, all rights reserved.
Prove: R is not countable.
Assume: R is countable.
By the definition of Countability, if R is countable, then |R|≤|N|. Since N is a proper subset of R, then we know that |R| is not less than |N|. Therefore, if R is countable, then |R|=|N|.
We also know by the definition of same Cardinality that if |R|=|N|, then there exists a bijection between R and N. Specifically, there exists a function whose domain is N and whose range is R.
Domain (N) Range (R)
1 f(1) 256
2 f(2)
3 f(3)
4 f(4) 5/9
. . .
. . .
. . .
n f(n) r
. . .
. . .
. . .
What Cantor's proof will do is show that there exists an element of R that is not in the range of f. That is to say, in the above listing there is an r that is not listed. This contradicts the claim that f is bijective. Since we have reached a contradiction from the assumption that R is countable, then the conclusion is that R is not countable. In part II we will look at how Cantor does this.
-----Posted in Cantor's Theorem • 0 Comments • Permalink • 109 views
by Brian Bosse, Copyright March 01, 2008, all rights reserved.
Cardinality
The cardinality of a set is the size of a set, i.e., the number of elements that make up a set. For instance, the set A={1, 2, 3} has a cardinality of 3. The cardinality of the natural numbers is:
This is called aleph-0 or aleph-null. The cardinality of a set A can be symbolized as |A|. Therefore, given set A above, |A| = 3. The set of natural numbers, N, |N| = aleph -0.
Cardinality can be determined by using mapping functions. Here is a key definition that will play a very important role as we consider Cantor's Theorem.
Definition: Two sets have the same cardinality if and only if there exists a bijection between them.
Consider the sets A={1, 3, 5} and B={2, 4, 6}. We can see that both sets have the same number of elements, and therefore they have the same cardinality. Our definition above implies that there exists a function taking A to B that is both an injection and a surjection (see Mapping Functions II). This function is as follows:
f: A → B, where f(x)=x+1
The reason this function is an injection is because the only way f(x)=f(y) is when x=y. Proof. Part 1: Assume f(x)=f(y) and x≠y. If f(x)=f(y), then x+1=y+1. By simple algebra, this leads to x=y, which contradicts x≠y. Part 11: Assume f(x)≠f(y) and x=y. If f(x)≠f(y), then x+1≠y+1, and x≠y, which contradicts x=y. The reason this function is a surjection is because for any b ∈ B, there exists an a ∈ A such that b=f(a). I will leave the demonstration of this to the reader.
Countability
Definition: A set A is countable if and only if |A|≤|N|.
Consider the set of even numbers E and the set of natural numbers N. The following function is bijective:
f: N → E, where f(x)=2x
Therefore, the set of even numbers and the set of natural numbers have the same cardinality. Since |E|≤|N|, then E is countable. Consider the following sets:
The set of natural numbers N={1, 2, 3, …} is countable.
The set of integers Z={…, -3, -2, -1, 0, 1, 2, 3, …} is countable.
The set of rational numbers Q={a/b: where a and b are elements of Z} is countable.
The set of real numbers (R) is the set of rational numbers plus the set of irrational numbers (ex. π and e). Cantor's Theorem is that R is uncountable.
-----
Posted in Cantor's Theorem • 0 Comments • Permalink • 95 views
Page 1 of 2 pages 1 2 >