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}. 2 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 = 4 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 1 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@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---