Key concepts : Cardinality, Mapping Functions (injection, surjection, bijection), Countability, Continuum hypothesis.

Definition :

--------------

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: Aleph-0

This is called 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 below, next post)

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 in B, there exists an a in 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| = 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. pi and e).

Cantor’s Theorem is that R is uncountable.