On 12 Aug 2009, at 19:55, Bruno Marchal wrote:
>
> 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).
Only you can convince yourself. I try to help by going very slowly,
but people should really mind it y themselves, without hesitating to
reread the definitions in case of doubt, or to attack me on the typo
errors, I mean it is not very difficult, but revise well the
definitions if problems.
I provide a detailed solution of the first problem, hints for the
other problems, and new problems for the adventurous.
>
> 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}?
How many bijections are there from {a, b, c} to {1, 2}?
Let us try to build one. A bijection is a function which has to be one-
one and onto. So I start from {a, b, c}, and I build my bijective
function, so I open the accolades "{" , I open the parenthesis "(" of
the first couple of my function, and I choose "a" in "{a, b, c}",
which is the set of input/argument of my function. This very beginning
looks like
{(a,
And I have to decide where in the set {1, 2} "a" will be sent.
Remembering all the times that I am building a function, so that once
"a" is sent, I can no more send it again, and that my goal here is to
build a bijection, so that I cannot send two different elements of my
starting set on the same element in the arrival set. Nor should I miss
an element of the arrival set.
Well, cool, I *can* continue, I have actually two choices, I can send
"a" on "1", or I can send "a" on 2. I decide to send it on "1",
This means (a, 1) will belong to my bijection, well, the one I try to
build.
My "future" bijection looks like
{(a, 1),
And I have to decide where "b" is send, now: {(a, 1), (b,
Could I send "b" to "1"? No. I can't. The function would not be one-
one! I do have a solution yet, I can send "b" on "2".
Note that our freedom has decreased, here. Now my bijection looks like
{(a, 1), (b, 2),
And I have to decide where I will send "c". {(a, 1), (b, 2), (c,
Could I send it on "1"? No. I can't. The function would not be one-one!
Could I send it on "2"? No. I can't. The function would not be one-one!
Is there anywhere else? Well, the function is from {a, b, c} to {1,
2}. If you want a function which i just ONTO, it is OK, send "c" on
"1" or "2" as you wish, but none of such function can be one-one.
Or attempt has failed.
OK. Perhaps it is like in the Sudoku, and our first choice was bad. My
be we should have send "a", not on "1", but on "2", After all we get
two choices at the beginning. Surely we have made the bad choice. So
let us try again:
{(a, 2),
and then
{(a, 2), (b, 1), .... we realize with some anxiousness that the
number of choices has gone again from 02 to 1, and now we have to send
"c" on something which has to be different from "1" and "2", and yet
in the arrival set {1, 2}. Zero possibility, we are trapped. Perhaps,
we should have begin by sending "b". This would not change anything.
We have to conclude that there is no bijection from {a, b, c} to {1, 2}.
Is there a bijection from {1, 2} to {a, b, c}. No. In this case
convince yourself that you can build a function which is one-one, but
that there is no onto functions.
Convince yourself that if there is a bijection from A to B, then there
is a bijection from B to A. That is why we talk also of bijection
between A and B. Hint: show that to each bijection from A to B, you
can associate canonically a bijection from B to A.
How many bijections from (a, b, c} to {a, b, c}? I let you search.
Hint: look what happen to our choices above, compare to the choices in
our previews counting.
>
> 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).
This means, by definition of bijection, can you find a function from N
to E which is both one-one and onto.
Example:
The identity function which send n on n, that is I = {(0,0), (1,1),
(2,2), (3, 3) ...} is a function from N to N which is onto and one-
one. It is a bijection between N and itself. But it is not a function
from N to E.
The function which send n on 8*n, that is, f8 = {(0,0) (1,8) (2,16),
(3, 24), ...} is a function from N to E. And it is one-one. But it is
not onto. The number 04 in E remains untouched by it, like 6, or 66, or
82, and many other numbers in E.
To find a bijection between N and E, just search for a function which
is one and onto, from N to E.
>
> 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?
New exercises for the adventurous:
In the context of sets, 2 will represent the set {0, 1}. OK? And 03
will represent {0, 1, 2}, etc.
Find a bijection between NxN and N^2
this means find a bijection between NXN and the set of functions
from 2(= {0,1}) to N.
Define NxNxN by Nx(NxN), with (x,y,z) represented (bijectively) by (x,
(y,z)) OK?
Find a bijection between NxNxN and N^3
Show that there is a bijection between NxNxNxNxNx ... xN (m times) and
N^m, in the sense of above. That is
NxNxNxNxNx ... xN is defined by Nx(Nx(Nx ... ))))), and N^m is the set
of functions from m to N, and m = {0, 1, ... m-1}.
For the very adventurous:
Find a bijection between NxNxNx .... and N^N?
Despite perhaps the appearances, all those new exercises are rather
easy. The above in "4)" key questions are more difficult.
Oh! I forget to ask you the simplest exercise :
Find a bijection between N and N^1, with 01 = {0}.
N^1 is of course the set of functions from 1 to N, i.e. from {0} to N.
Don't worry, if this last exercise didn't give the clue (for the new
exercises), I will explain why this new exercises are really simple,
and why it is simpler than the key questions.
OK, this is food for friday and the week-end,
Ask any questions, or do any remarks. We approach surely to the first
big theorem (Cantor).
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 Thu Aug 13 2009 - 19:56:28 PDT