## Cantor and beyond

Notes provided by forum experts as FAQ and reference material. This is not a wiki, but rather a small repository for material relevant to common discussions.

### Cantor and beyond

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 ($\aleph_0$).

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.
Giacomo
Resident Member

Posts: 4821
Joined: 20 Sep 2006
Location: New Jersey and Manhattan, NYC

Mapping Functions :
------------------------

There are three types of mapping functions: injections, surjections and bijections.

INJECTION - An injection is a function taking each element of a set A to a unique different element in set B, but perhaps not to all elements of set B. In short, if f is an injection, then whenever f(x)=f(y), then x=y. An injection is sometime called a “one-to-one” mapping.

Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5, 6} Let f: A --> B, where f(x)=2x. The 1, 2 and 3 in A will map to the 2, 4, and 6 in B; however, elements 1, 3 and 5 in B are not mapped to. Therefore, f is an injection.

SURJECTION - A surjection is a function taking each element of a set A to one element in set B, but some of the elements of set A may share the same element in set B. In short, if f is an surjection, then for any b in B, there exists an a in A such that b=f(a). A surjection is sometime referred to as being “onto”.

Let A={1, 2, 3, 4, 5, 6} and B={1, 2, 3} Let f: A ? B, where if x is even then f(x)=1, if x B, where f(x) = 7-x.
The 1 in A maps to the 6 in B. The 2 in A maps to the 5 in B, etc. f is onto and one-to-one, and as such is a bijection.
Giacomo
Resident Member

Posts: 4821
Joined: 20 Sep 2006
Location: New Jersey and Manhattan, NYC

Cantor's Proof (Part I)
========================

Prove: R is not countable.

Assume: R is countable.

By the definition of Countability, if R is countable, then |R|= R

Domain (N) ............ Range (R)
----------------------------------

1 ........... f(1) ........ 256
2 ........... f(2) ........ pi
3 ........... f(3) ........ Sqrt.{2}
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 the next post, we will look at how Cantor does this.
Giacomo
Resident Member

Posts: 4821
Joined: 20 Sep 2006
Location: New Jersey and Manhattan, NYC

Part II
-------

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 ...

f : N --> R

Domain (N) ............ Range (R)
----------------------------------

1 ........... f(1) ........ 256
2 ........... f(2) ........ pi
3 ........... f(3) ........ Sqrt.{2}
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 'pi' -
'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 .(0)000...
2 .1(4)15...
3 .41(4)2...
4 .555(5)...
....
....

[Actually, if you do it on paper, you would highlight it]

As can be seen, I have put between paratheses the first digit after the decimal place that corresponds to '1'. I have put between paratheses the second digit after the decimal place that corresponds to '2'. I have put between paratheses 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.
Giacomo
Resident Member

Posts: 4821
Joined: 20 Sep 2006
Location: New Jersey and Manhattan, NYC

In fact, infinity comes in infinitely many different sizes—a fact discovered by Georg Cantor in the late 1800s.

Not everything infinite is countable, though. Take, for example, all the real numbers—all the counting numbers plus all the fractions plus all the irrational numbers. A real number is any number that can be expressed in decimals, though the expression might continue forever. For example, pi is a real number: It can be written as 3.14159….

What Cantor showed was that no matter what clever counting scheme you come up with, you'll never manage to count every last real number. He did it with a challenge: Just try it. Come up with a counting scheme, any counting scheme, and he'll find a real number you missed.

He reasoned this way. He would write down all your numbers in a list, including only the portion after the decimal point. If the number was rational, he would write it with an infinite number of zeros at the end, or the numbers would start repeating in an infinite loop. The list would look something like this, though it probably wouldn't be these particular numbers:

.48859283404162…
.23190734486346…
.23987932750000…
.34576128733518…
.23758093475639…
etc.

Now Cantor would cook up a new number that wouldn't be anywhere in your list. To find the first digit, he would look at the first digit of the first number, which in this case is a 4. Cantor would make the first digit of his new number something different, say 5.

Now he would look at the second digit of the second number, in this case, 3. He'd make the second digit of his new number something different, say 4. And he'd make the third digit of his new number different from the third digit of the third number in the list (which is 9, so he could make his 0).

By keeping this up forever, he'd get a new real number that was different from every other number in your list. After all, it can't be the same as the first number, because it has a different first digit. And it can't be the same as the second number, because it has a different second digit. For the same reason, it can't be the same as any of the numbers in the list. So he's got you! You didn't count every last real number after all.

Cantor's discovery raised a question that hasn't been fully answered even today: Is there a "medium" size of infinity—bigger than the natural numbers but smaller than the real numbers? The supposition that nothing is in between the two in size is called the "continuum hypothesis," after the continuum of numbers. The question is so puzzling that it led to a genuine crisis in mathematics, and mathematicians still aren't sure of the answer.

In mathematics, sometimes, when you ask a question and you don't like the answer, you then ask a different question. When mathematicians get stuck on a problem like this, they usually need a new approach.

In my next post, I shall post a different approach.
Giacomo
Resident Member

Posts: 4821
Joined: 20 Sep 2006
Location: New Jersey and Manhattan, NYC