by Brian Bosse, Copyright March 01, 2008, all rights reserved. 37 views
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.
-----
No comments yet.