Well, given that nobody dare to ask question, I will play the role of the idiot myself.

## Advertising

On 30 Jul 2009, at 21:22, Bruno Marchal wrote: > > > > Exercise: > > > 1) how many functions and what are they, from the set {0, 1} to > himself. What are the functions from {0, 1) to {0, 1}? > > Solution: > > {(0,0), (1,0)} the constant function which associates zero to any > value of its argument. > {(0,1), (1,1)} the constant function which associates one to any > value of its argument. > {(0,0), (1,1)} the identity function, which output its argument as > value. > {(0,1), (1,0)}, the NOT function, which associate 0 to 1, and 1 to 0. > > There is four functions from {0, 1} to {0, 1}. OK. But a function from A to B, (with A and B being sets) is simply a set of couples (x, y) with x in A, and y in B. No? So it seems you are forgetting the functions {(0, 0), (0, 1)}, no? ANSWER: no! Not all set of couples are function. In particular {(0, 0), (0, 1)} is not a function because the "input" 0 has two outputs: 0 and 1. The functional condition is not met, and a function is a set of couples provided it obeys to the functional condition. Let me introduce vocabulary, to ease the talk. If the couple (a, b) belongs to the function F, I will say that a is an argument of F, and that b is a value of F. I will write F(a) = b, for (a, b) belongs to F. We also say that F send a on b. Later, when we will arrive at the notion of computable function: argument will be called input, and value will be called output. The idea is that a function F is a sort of generalized machine: you give argument and it gives back a value. When F *is* mechanical, you give an input and the machine gives back an output. With that vocabulary, the functional condition can be stated by saying than a function F cannot gives back two values for one argument. A function cannot send an elements on two elements. To help your mind, think about typical "physical" function. For example the temperature in a room in function of time. For example: we look at the temperature a 1 o'clock, then 2, 3, 4, etc. T = {(1, 24), (2, 25) (3, 24), (4, 24), (5, 23), (6, 23), (7, 23), (8, 23), (9, 22), (10, 20), (11, 19) ...} Meaning, at time 1 there is 24 degrees celsius. At time 2, there is 24 degrees celsius, etc. The functional condition is respected: you cannot have two values of the temperature at the same time. Does this help? Another example of a typical physical function. Movement of a mobile in space SPACE in function of TIME. This can be described by a function M from the set of moment in TIME in the set of position in SPACE: M is a function from TIME to SPACE. M = {(t1, p1), (t2, p2), (t3, p3) ... } where t1, t2, t3, are time coordinate, and p1, p2, p3 are space coordinate. Again, this will be a function because the mobile cannot be in two places at the same moment. OK? > > > 2) how many functions, and what are they, from the set cartesian > product {0, 1} X {0, 1} to {0, 1} > > Among them many are celebrities, you know. The AND, the OR, and many > (how many?) others. > > For a beginner in math, this is not at all an easy exercise. The > real useful exercise is to try to understand the enunciation of the > question. We will take the time needed. First let us compute {0, 1} X {0, 1}. This is simple, as it is the "rectangular" set of all couples (x, y) with x and y each in {0, 1}. Thus it gives 1 (0, 1) (1, 1) 0 (0,0) (1, 0) 0 1 that is {0, 1} X {0, 1} = {(0,0), (1, 0), (0, 1), (1, 1)}. Let us build one function F1 from {(0, 0), (1, 0), (0, 1), (1, 1)} to {0, 1}. Here the arguments are (0, 0), (1, 0), (0, 1), (1, 1), and we must decide on which, among 0 and 1, those couples will be sent. I am lazy, so I will send them all on 0. I will get the constant function 0. F1((0, 0)) = 0 F1((1, 0)) = 0 F1((0, 1)) = 0 F1((1, 1)) = 0 OK? Thus F1 is the set of couples {((0, 0), 0), ((1, 0), 0), ((0, 1), 0), ((1, 1), 0)}. Note that here the arguments are themselves couples. Another one: the constant F2 which sends all couples on 1: F2((0, 0)) = 1 F2((1, 0)) = 1 F2((0, 1)) = 1 F2((1, 1)) = 1 Thus F2 is the set of couples {((0, 0), 0), ((1, 0), 0), ((0, 1), 0), ((1, 1), 0)}. If you remember how many binary strings of length 4 can exist, you can guess that we have 16 (2x2x2x2) such functions. Exercise: find them all. Beginners have to train themselves, if only to develop (slowly but surely) the familiarization with the definitions and notations. > > > 3) A bit tricky perhaps: how many functions exist from { } to { } ? Solution: A function F from { } to { } has to be a SET of couples (x, y) with x in { }, and y in { }. But { } is empty, so there are no such couples, so F is an empty set of couples, so F is the empty set. F = { }. So there is ONE function from { } to { }. That function is the empty set itself, and is sometimes called the empty function. OK? Now, a few new material. It is just vocabulary. ------------------------------------------------------------------------------------- SET EXPONENTIATION Definition. If A and B are sets, we define A to the power of B = A^B, by the set of all functions from A to B. Thus the exercise above could have been written: 1) compute {0, 1} ^ {0, 1} 2) compute {0, 1} ^ ({0, 1} X {0, 1}) and card({0, 1} ^ ({0, 1} X {0, 1})) where "card" = "cardinal of" = "number of elements of" 3) compute { } ^ { } and card({ } ^ { }) Little subject research. If card(A) = n, and card(B) = m. What is card(A^B)? In english: how many functions exist from a set of n elements in a set of m elements? Hint: ask yourself how many choices you have at each step of the construction of a function from A to B. For the sequel, i suggest you reread everything I have said about "bijection". All right? Any trouble? Courage. We are no so far from introducing the computable functions, which is an obvious prerequisite to get the mathematical notion of computation, which is needed to understand the notion of computational supervenience, and get both UDA-7 and UDA-8. 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 -~----------~----~----~----~------~----~------~--~---