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.


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.


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  

  - 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  

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?



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 
For more options, visit this group at 

Reply via email to