Well, given that nobody dare to ask question, I will play the role of
the idiot myself.
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 00 to 1, and 01 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 04 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.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 Fri Aug 07 2009 - 10:45:09 PDT