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.
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 05 (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 07 (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.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 Wed Aug 12 2009 - 19:55:31 PDT