Hi,
I sum up, a little bit, and then I go quickly, just to provide some
motivation for the sequel.
We have seen the notion of set. We have seen examples of finite sets
and infinite sets.
For example the sets
A = {0, 1, 2},
B = {2, 3}
are finite.
The set N = {0, 1, 2, 3, ...} is infinite.
We can make the union of sets, and their intersection:
A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3}
A intersection B = {x such-that x is in A AND x (the same x) is in B}
= {2}. 02 is the only x being both in A and B.
OK?
We have seen the notion of subset. X is a subset of Y, if each time
that x is in X, x is also in Y.
And we have seen the notion of powerset of a set. The powerset is the
set of all subset of a set.
Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}.
OK?
In particular we have seen that the number of element of the powerset
of a set with n elements is 2^n.
Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e.
{{ }, {2}, {3}, {2, 3}} has 2^2 = 04 elements. OK?
We have seen the notion of function from a set A to a set B.
It is just a set of couples (x, y) with x in A and y in B. x is
supposed to be any elements of A, and y some element of B.
To be a function, a set of couples has to verify the *functional
condition* that no x is send to two or more different y. This is
because we want y be depending on x. Think about the function which
describes how the temperature evolves with respect to time: an
instant t cannot be "send" on two different temperature.
Let A = {1, 2} and B = {a, b, c}
F1 = {(1, a), (2, a)}
F2 = {(1, c}, (2, a)}
F1 and F2 are functions.
But the following are not:
G1 = {(1, a), (2, b}, (2, c)} because 2 is send on two different
elements
G2 = {(1, a), (2, b), (1, b)} because 01 is send on two different
elements.
OK?
We have then consider the set of all functions from A to B, written
B^A, and seen that this number is equal to
card(B) ^card(A) where card(A) is the number of elements of A. A
is supposed to be a finite set, and later we will see how Cantor will
generalize the notion of cardinal for infinite sets.
We have then studied the notion of bijection.
A function from A to B is a bijection from A to B when it is both
- ONE-ONE two different elements of A are send to two different
elements of B
- ONTO, this means that all elements of B are in the range of the
function, i.e. for any y in B there is some couple (x, y) in the
function.
Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a
bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO, nor
ONE-ONE.
OK?
We have seen that if A and B are two finite sets, then we have
A and B have the same number of element if and only if there exists a
bijection from A to B.
OK?
Now I can give you the very ingenious idea from Cantor. Cantor will
say that two INFINITE sets have the same cardinality if and only if
there exists a bijection between them.
This leads to some surprises.
Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers.
This is obviously an infinite set, all right?
Let 2N = {0, 2, 4, 6, ....} be the set of even numbers. This is
obviously a subset of N OK?, and actually an infinite subset of N.
Now consider the function from N to 2N which send each n on 2*n. This
function is one-one. Indeed if n is different from m, 2*n is different
from 2*m. OK?
And that function, from N to 2N is onto. Indeed any element of 2N, has
the shape 2*n for some n, and (n, 2*n) belongs to the function.
In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8),
(5, 10), (6, 12), ...}
So here we have the peculiar fact that a bijection can exist between a
set and some of its proper subset. (A subset of A is a proper subset
of A if it is different of A).
The first who discovered this is GALILEE. But, alas, he missed Cantor
discovery. Like Gauss later, such behavior was for them an argument to
abandon the study of infinite sets. They behave too much weirdly for
them.
OK?
At first sight we could think that all infinite sets have the same
cardinality. After all those sets are infinite, how could an infinite
set have a bigger cardinality than another infinite set? This is the
second surprise, and the main discovery of Cantor: the fact that there
are some infinite sets B such that there is no bijection between N and
B.
Cantor will indeed show that there is no bijection between N and N^N,
nor between N and 2^N. We will study this.
Cantor will prove a general theorem, know as Cantor theorem, which
asserts that for ANY set A, there are no bijection between A and the
powerset of A.
The powerset operation leads to a ladder of "bigger infinities". I
will come back with some detail later.
Some surprises were BAD surprises. Conceptual problems which Cantor
will "hide" in its desk, to treat them later. The so-called paradoxes
of "naïve set theory". The root of what has been called the crisis in
mathematics.
For example, we could naively consider the set of all sets. Often
called the universal set, or Universe (of sets). Surely no set can be
bigger that this one? But by Cantor theorem the powerset of the
universe has to be bigger than the universe. So there is a problem.
And the naïve conception of sets will lead to many other problems.
Torgny Tholerus has mentioned some other problems, if you remember.
So what?
Mainly three approaches have been proposed to solve those conceptual
problems.
1) The most liberal one, suggested by Hilbert, who was fond of Cantor
theory. He said that no one will drive us away from Cantor Paradise.
He suggested to build a formal system capable of talking about sets,
and capable of proving the main theorem of Cantor, but free of the
paradoxes. This will lead to the modern axiomatic trend in
mathematics. Hilbert asked for the proof of the consistency of such
formal theories, and this will be shown just impossible, by Gödel.
Despite this, most mathematicians have followed this path, explicitly
or implicitly. In most axiomatic set theories, the axiom will prevent,
for example, the existence of a universal set or universe. To be sure,
some highly non standard axiomatic set theory allows a Universal set
to exist, for example Quine new foundations (cf some post by Brian and
Adam).
2) The least liberal one, suggested by Brouwer (the main opponent to
Cantor and Hilbert). To abandon classical logic, and "set realism".
This consists in abandoning the law of the excluded middle (p or ~p)
in mathematics, and this will lead to intuitionist mathematics and
philosophy, which is a form of mathematical solipsism.
3) Intermediate solutions. One will consist in searching a weaker
notion of function, capable of satisfying both the intuitionist and
the classical mathematicians. This will lead mathematicians to the
notion of computable functions, and when Cantor reasoning is applied
again, this will lead to the (mathematical) notion of universal
machine. In my opinion: this is the biggest discovery ever done by
humanity. And both UDA and AUDA are just non sensical without that
discovery (and this explains why I insist on this). Note that from
empirical data, we can guess that "nature" has done that discovery and
has exploited it again, and again, and again, and again ....
* * *
Exercise: if you have not yet done them, or understand them, please
take some time to just think about those questions. I have to solve
them properly to proceed. You may try to read Brent's correct answer
to some of those questions.
Show that there is a bijection between the following sets:
N and 2N, 3N, 4N, 5N, .... (nN = the set of multiple of n).
N and Z (Z = all integers, that is postive and negative integers, Z
= {... -3, -2, -1, 0, 1, 2, 3, ...}
N and Q (Q = the reduced fractions, or the decimal periodics)
N and NxN
N and NxNxN.
The powerset of A (finite set) and the set of functions from A to {0, 1}
The powerset of N and the set of functions from N to {0, 1}.
The powerset of N and the real numbers. (real numbers = finite of
infinite decimals).
*
* *
Take it easy, and enjoy if you have the time and taste,
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Wed Aug 26 2009 - 19:06:37 PDT