On 11 Aug 2009, at 22:24, Mirek Dobsicek wrote: > > >> Well, A^B is the set of functions from B to A. By definition of set >> exponentiation. > > I'd just like to point out that Bruno in his previous post in the > seven > step serii made a small typo > > "A^B - the set of all functions from A to B." > > It should have been from B to A. The latest post is correct in this > respect.

## Advertising

And now Simplicius is coming back and asks: " but why do you define the exponentiation of sets, A^B, by the set of functions from B to A?". The answer of the sadistic teacher: this is a DEFINITION, and is part of the program. If you have complains about the program, write a letter to the minister of education. Hmm... A better answer is given by the solution of the preceding exercise: >> If card(A) = n, and card(B) = m. What is >> card(A^B)? > It happens that if A^B is defined as the set of functions from B to A, then card(A^B) is given by card(A)^card(B) How many functions exist from a set with m elements in a set with n elements? n^m. Hope you see that n^m is NOT equal to m^n (when n and m are different). 3^4 = 3x3x3x3 = 81, and 4^3 = 4x4x4 = 64. 2^7 = 128, 7^2 = 49. In that way, A^B generalizes for set what n^m is for numbers. And why card(A^B) = card(A)^card(B) ? You can see this in the following way: let card(A) = m, and card(B) = n. We must understand why card(A^B) = n^m. For example a function from {a, b, c, d, e, f, g} in {0, 1, 2, 3, 4}. To fix the idea. So m = 7, and n = 5. OK? Let us build an "arbitrary" function F. Well,we begin with "F = {(a, ...", and we have to say where "a" is sent. We have five (n) choices, and then we have to choose where b is sent, and we have again n choices, and for each first choice any second choice is acceptable so we have 5 (n) choices multiplied by 5 (n) choices, itself multiplied by 5 (n) choices, as many times there are elements in the starting set, that is 7 (m). This gives 5 x 5 x 5 x 5 x 5 x 5 x 5, that is 5^7. or more generally n x n x n x n x ... x n, m times. OK? We will be interested in N^N. That is, the set of functions from N to N. The set of computable functions will be an important subset of that set. Let me give a precise definition of bijection, as I promise. I need two rather useful definitions. - I will say that a function from A to B is ONTO, if all elements of B appears in the couples of the function. Note that card(B) has to be less or equal to card(A) to make that possible, by the functional condition. - I will say a function is ONE-ONE, if two different elements of A are sent to two different elements of B. Note that card(A) has to be less or equal to card(B) to make that possible. The condition one-one is the reverse of the functional condition. The functional conditions says that an element cannot be sent on two different elements (a time cannot give two temperature!), and the one- one condition says that two different elements cannot be sent on one element. Exercises: build many examples with little finite sets. You may search examples for infinite sets. OK. The definition of bijection. I will say that a function is a bijection between A and B if it is both a function ONTO from A to B, and a function ONE-ONE from A to B. we say more quicky that f is a bijection if f is both onto and one-one. Exercises: for "2)" below, the real needed exercise is: "do you understand the question?" Unless you like to count things, but such skills are not needed for the sequel. 1) Convince yourself that if A and B are finite sets, then there exists a bijection between A and B if and only if card(A) = card(B). 2) If A has n elements (card(A) = n), how many bijections exists from A to B? Again start with simple examples, and try to generalize. For example, how many bijections from {a, b, c} to {1, 2}. How many bijections from (a, b, c} to {a, b, c}? 3) can you find, or define a bijection between the infinite set N, and the infinite set E = {0, 2, 4, 6, 8, ...} (E for even). 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? 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 -~----------~----~----~----~------~----~------~--~---