Hi,

I give the solution of the first of the last exercises. I reason aloud. I go slowly for those who did not get some math courses, or just forget them. I cannot stress the importance of the notion of bijection in the "mathematical discovery of the universal machine" (the quote means that a nuance will be added here). Counting is not so important. Th exercise motivation is in to develop familiarity with the notion of function and bijection. Then counting things provides example of functions from N to N. > 1) count the number of bijections from a set A to itself. (= card{x > such that x is bijection from A to A}) This does not seem very obvious, so let us begin with the simplest set, for example the one which admits the shorter description when written in extension, that is the empty set { }. The question in this case is: count the number of bijection between { } and { }. Hmm... This smells the subtle trap and it may be a good advise to avoid the simplest set or number. Zero and the empty set may be simplest in term of description but may be harder conceptually. A simple case, in this and many cases, would be a set with not much elements. Let us count the number of bijections from {a, b} to itself. i.e. the bijections from {a, b} to {a, b}. Here some beginners could have a trouble: "I don't remember what is a bijection". Well, the exercise is obviously with notes. I am not yet asking to buy a webcam so that I can look if you are not cheating, all right? Two things can happen. Either you find the passage in your diary where I explain bijection with the legendary story of the humans who cannot count, and compare the bigness of sets by using ropes. You may remember how the farmer compare their *set* of animals, without being able to count. They compare two sets of animals by attaching a rope to ONE animal belonging to the set of your animals, say, and you bring that to ONE animal of your neighbor. Three things can happen: 1) All your animals get attached to a rope, and got attached to some neighbor's animals, but some other animal of the neighbor are still freely going here and there. In this situation we say "damned, the set of animals of my neighbor is bigger than mine". 2) All your animals get they rope, and got attached to the neighbor's animals. And all neighbor's animals are attached. In this situation we say "OK, my set of animals has the same cardinality than the set of my neighbor animals. Cardinality is the measure of set, when we compare it in this way. Now, this is the situation where a bijection exists. 3) All the neighbor's animal are attached to the rope, yet some of your own animals remain free. You can attach the rope to those free animals, but you will be unable to attach them to some neighbor animal, they are already all attached. In this situation you say nothing, because you are polite, you just let the neighbor saying "damned, the set of animals of my neighbor is bigger than mine". .... Or you don't remember that story, so you consult the austere notes with the definition. A, B ... represent sets. A bijection between A and B is a function from A to B which is ONE-ONE and ONTO. And what is a function? A set of couples (x, y), x in A, y in B, verifying the condition that no x in A is sent on different y in B. In a very large sense, the element of B depend on the element of A, and that dependence is represented by a couple (x, y). With the farmer, the couples where made with one animal x attached by a rope to one animal y: (x, y). Well let us go back to the bijections from {a, b} to {a, b}. Oh, I see some anxiousness can rise due to the fact that we have the same set of both side. Why would ever a farmer compare the bigness of its set of animals with the bigness of its set of animals? Is that not a pure mathematical absurdity? To ease the pain, in math, consists always in simplifying, so, just to keep the intuition provided by the farmer, let us distinguish the animal's neighbor, those which makes the arrival set, by different letters. And let us first search the bijections from {a, b} to {c, d}. {a, b} is the set of my animals. {c, d} is the set of animals of my neighbor. OK? Well I have to build a bijection, which is a set, so I have to begin by "{", indicating I am building a set. Of course, this is implicit in the farmer's mind, because his goal consists in just comparing the two sets. But our goal is to find all bijections. So we have to be clear about them as mathematically represented objects, and bijections, like functions, have been defined or represented as sets. Now I have to choose one of my animals; let us choose a. and attach the rope. The description of the bijection looks like: {(a, I have to choose an animal belonging to the set of my neighbor's animals. Well, I have two choices: c or d. Let us choose c. The description of the bijection looks like: {(a, c), And then {(a, c), (b, d)} This *is* a function, which is ONTO and ONE-ONE. Is there another? Yes. I choose the other animals (cf the two choice above). But note already, that for the second animals I have only once choice. The other is {(a, d), (b, c)}. Is there another one? No. There are two bijections from {a, b} to {c, d}. {(a, c), (b, d)} and {(a, d), (b, c)}. The set of bijections from {a, b} to {c, d} is the set {{(a, c), (b, d)}, {(a, d), (b, c)}}. This is more easy to build than to read. Now the name of the element, or even what they consists in (animals, numbers, letters) is not relevant OK? In particular there are as many bijection from {a, b} to {a, b} than from {a, b} to {c, d}. They are {(a, a), (b, b)} and {(a, b), (b, a)} A bijection from A to A is called a permutation of A. {(a, a), (b, b)} is called the identity permutation on {a, b}. Oh, card(A) = 2 (= A has two elements) entails that there is 2 bijections. WE may generalize and believe that there are as many bijections from A to A, than there are elements in A. OK? Let us test this theory on the simpler set {a}. How many bijections are there from (a} to {a}. Well, there is {(a,a)}, and that's all. One! Our theory succeeds. If we infer that theory on { }, we may be tempted to say 0, for the number of bijections between { } and { }. But with a sample of two elements ..., it is dangerous to infer too much quickly. Let us look at {a, b, c}. Are there three bijections? And only three bijections? (Well if you remember the number of function from A to B is card(B)^card(A), so we could be astonished our conjecture is tenable). And indeed, I go systematically trying to figure out how to count the number of bijections from A to A for a finite set A in general. Let us build a bijection from {a, b, c} to {a, b, c}. It has to be something like {(a , _) , (b, ), (c, ) }. Given that in a set the order has no importance, so the choices of beginning by (a, or by (b, or by (c is not relevant. But once I choose say {(a, the number of choice to complete the second bijection is relevant {(a, b) ..., will not give the same bijection that {(a, c), ... So I start with {(a, I have three choices. Let us take c for the first choice, how many choices there is for the next element? Well, given that the bijective function (bijection) have to be ONE- ONE, you loose a possibility at each choice. So there will be three possibility, then 2, the 1, and the bijection is completed. So there will be 3 x 2 x 1 bijections. the number of choices are multiplied for the same reason that for the number of functions. Once a choice is made, the remaining choices are independent. Let us look {(a, a) (b, b), (c, c)} {(a, a) (b, c), (c, b)} choice: "{(a,a) ..." multiplied by the bijections from {b, c} to {b, c}. {(a, b), (b, a) (c, c)} {(a, b), (b, c) (c, a)} {(a, c), (b, a) (c, b)} {(a, c), (b, b) (c, a)} So three elements leads to 3 x 2 x 1 bijections; that is 6 bijections. If there is n elements in the set, there will be n choices for the first couples, then, by the one )one condition, it will remains (n-1) choices, then (n-2) .... up to the last 1 choice. We have a "formula". if card(A) = n then then number of permutation on A, or of bijection from A to A, is n*(n-1)* ... 1. OK? Er, how many bijections from { } to { } ? In this case card(A) = 0. The formula we get does not seem to apply. What could be 0*(0-1)*(0-2)* .... * 1 ? At first sight it should be 0. Because 0*<anything> = 0 isn't it? false: 0 * any number = 0. But who could claim that the expression above is well determined: it is like you will never get to that "1". I'm afraid we have to tackle the "simplest" case by reason alone, taking our definition seriously into account. How many bijection are there, from { } to { }? Well, bijections are sets, so we can begin {, and we have to put in that set couples (x, y) with x in { } and y in { }. But there is no x in { }, so we will not find any couples. So our set is empty, so we can close it directly, and the bijection looks like { }. It is the empty bijection. So we have find one, and only one. So the number of bijections from the empty set to the empty set is ONE. (For the same reason, if you remember, that the number of functions from { } to { } is one. Card({ }^{ }) = 1). That was the harder case. Now let us write A° for the set of permutation on A. A permutation is defined by a bijection from A to A. We have seen that if Card(A) = n, card(A°) = n*(n-1)*(n-2)* ... *1 if A is not empty, and Card(A°) = 1 if A is empty. This motivates the definition of the following function from N to N, called factorial. factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if is n is different from 0. Note this: if n is different from 0, for each n we have that fact(n) = n*fact(n). factorial is a function from N to N, so it is the following set of couples: {(0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120), (6, 720), (7, 5040), (8, 40320), (9, 362880), (10, 3628800), (11, 39916800), ...} A good thing I did not ask you to give me all the bijections from a set from 10 elements to itself. See that if two farmer have 10 animals each, they is already 3628800 bijections between their two sets of animals. Compare with the exponential function, which send n to 2^n {(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32), (6, 64), (7, 128), (8, 256), (9, 512), (10, 1024), (11, 2048), ...} OK? Bruno > > 2) describe some canonical bijection between 2^A and the powerset of > A. > > 3) I say that a set S is a proper subset of A if it is a subset of A, > and different from A. > We have seen that there is a bijection between N and 2N = {0, 2, > 4, 6, ...}. (see below *) > 2N is a proper subset of N. > So we see that an infinite set can have a bijection with a proper > subset. > The question is, could that be possible for a finite set? > > The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3, > 6), (4, 8), ...}. More schematically, if you remember the ropes: > > N 2N > > 0 ------- 0 > 1 --------2 > 2 --------4 > 3 --------6 > .... > > 4) Be sure that you have been convinced by Brent that there is a > bijection between N and NxN, and between N and NxNxN, and etc. That is > be sure there is a bijection between N and N^m for each N. > > 5) Key exercise for the sequel. First a definition. An alphabet A is a > non empty finite set. I call its elements letter. > Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite > words on the alphabet A. A word is a finite sequence of letters, from > some alphabet, like, on the alphabet A, aaabab, abbbbcbababcccacab, > etc. > IA+ is obviously infinite, it contains *notably* a, aa, aaa, aaaa, > aaaaa, aaaaaa, aaaaaaa, ... > > The word "word" has a larger meaning in math than in natural language. > On the usual alphabet {A, B, ... Z}, an expression like > HHYUJLIFSEFGXWKKODENN is a fully respectable word. > > Show that for any alphabet A, there is a bijection between N and A+ > > > Soon (asap, though) the proof of many theorems found by Cantor. > Notably that there is NO bijection from N to N^N. > Then Cantor proof will be done again and again, and again, ... in > deeper and deeper and deeper contexts. > > Please ask any questions. It is not too late before we go in the > *very* interesting matter, and very illuminating with respect to the > question of the existence of universal machines, languages and > numbers. > > Bruno > > > http://iridia.ulb.ac.be/~marchal/ > > > > > > 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 -~----------~----~----~----~------~----~------~--~---