Hi,
I give the solution of the first of the last exercises.
I reason aloud. I go slowly for those who did not get some math
courses, or just forget them. I cannot stress the importance of the
notion of bijection in the "mathematical discovery of the universal
machine" (the quote means that a nuance will be added here).
Counting is not so important. Th exercise motivation is in to develop
familiarity with the notion of function and bijection. Then counting
things provides example of functions from N to N.
> 1) count the number of bijections from a set A to itself. (= card{x
> such that x is bijection from A to A})
This does not seem very obvious, so let us begin with the simplest
set, for example the one which admits the shorter description when
written in extension, that is the empty set { }.
The question in this case is: count the number of bijection between
{ } and { }.
Hmm... This smells the subtle trap and it may be a good advise to
avoid the simplest set or number. Zero and the empty set may be
simplest in term of description but may be harder conceptually.
A simple case, in this and many cases, would be a set with not much
elements. Let us count the number of bijections from {a, b} to itself.
i.e. the bijections from {a, b} to {a, b}.
Here some beginners could have a trouble: "I don't remember what is a
bijection". Well, the exercise is obviously with notes. I am not yet
asking to buy a webcam so that I can look if you are not cheating, all
right?
Two things can happen. Either you find the passage in your diary where
I explain bijection with the legendary story of the humans who cannot
count, and compare the bigness of sets by using ropes.
You may remember how the farmer compare their *set* of animals,
without being able to count. They compare two sets of animals by
attaching a rope to ONE animal belonging to the set of your animals,
say, and you bring that to ONE animal of your neighbor.
Three things can happen:
1) All your animals get attached to a rope, and got attached to some
neighbor's animals, but some other animal of the neighbor are still
freely going here and there. In this situation we say "damned, the set
of animals of my neighbor is bigger than mine".
2) All your animals get they rope, and got attached to the neighbor's
animals. And all neighbor's animals are attached. In this situation we
say "OK, my set of animals has the same cardinality than the set of my
neighbor animals. Cardinality is the measure of set, when we compare
it in this way. Now, this is the situation where a bijection exists.
3) All the neighbor's animal are attached to the rope, yet some of
your own animals remain free. You can attach the rope to those free
animals, but you will be unable to attach them to some neighbor
animal, they are already all attached. In this situation you say
nothing, because you are polite, you just let the neighbor saying
"damned, the set of animals of my neighbor is bigger than mine".
.... Or you don't remember that story, so you consult the austere
notes with the definition. A, B ... represent sets.
A bijection between A and B is a function from A to B which is ONE-ONE
and ONTO.
And what is a function? A set of couples (x, y), x in A, y in B,
verifying the condition that no x in A is sent on different y in B. In
a very large sense, the element of B depend on the element of A, and
that dependence is represented by a couple (x, y).
With the farmer, the couples where made with one animal x attached by
a rope to one animal y: (x, y).
Well let us go back to the bijections from {a, b} to {a, b}. Oh, I see
some anxiousness can rise due to the fact that we have the same set of
both side. Why would ever a farmer compare the bigness of its set of
animals with the bigness of its set of animals? Is that not a pure
mathematical absurdity?
To ease the pain, in math, consists always in simplifying, so, just to
keep the intuition provided by the farmer, let us distinguish the
animal's neighbor, those which makes the arrival set, by different
letters. And let us first search the bijections from {a, b} to {c, d}.
{a, b} is the set of my animals. {c, d} is the set of animals of my
neighbor. OK?
Well I have to build a bijection, which is a set, so I have to begin
by "{", indicating I am building a set. Of course, this is implicit in
the farmer's mind, because his goal consists in just comparing the two
sets. But our goal is to find all bijections. So we have to be clear
about them as mathematically represented objects, and bijections, like
functions, have been defined or represented as sets.
Now I have to choose one of my animals; let us choose a. and attach
the rope. The description of the bijection looks like:
{(a,
I have to choose an animal belonging to the set of my neighbor's
animals. Well, I have two choices: c or d. Let us choose c. The
description of the bijection looks like:
{(a, c),
And then
{(a, c), (b, d)}
This *is* a function, which is ONTO and ONE-ONE.
Is there another?
Yes. I choose the other animals (cf the two choice above). But note
already, that for the second animals I have only once choice.
The other is {(a, d), (b, c)}. Is there another one? No.
There are two bijections from {a, b} to {c, d}. {(a, c), (b, d)} and
{(a, d), (b, c)}.
The set of bijections from {a, b} to {c, d} is the set {{(a, c), (b,
d)}, {(a, d), (b, c)}}. This is more easy to build than to read.
Now the name of the element, or even what they consists in (animals,
numbers, letters) is not relevant OK?
In particular there are as many bijection from {a, b} to {a, b} than
from {a, b} to {c, d}. They are
{(a, a), (b, b)}
and
{(a, b), (b, a)}
A bijection from A to A is called a permutation of A. {(a, a), (b,
b)} is called the identity permutation on {a, b}.
Oh, card(A) = 02 (= A has two elements) entails that there is 2
bijections.
WE may generalize and believe that there are as many bijections from A
to A, than there are elements in A.
OK? Let us test this theory on the simpler set {a}. How many
bijections are there from (a} to {a}. Well, there is {(a,a)}, and
that's all. One! Our theory succeeds.
If we infer that theory on { }, we may be tempted to say 0, for the
number of bijections between { } and { }. But with a sample of two
elements ..., it is dangerous to infer too much quickly.
Let us look at {a, b, c}. Are there three bijections? And only three
bijections? (Well if you remember the number of function from A to B
is card(B)^card(A), so we could be astonished our conjecture is
tenable).
And indeed, I go systematically trying to figure out how to count the
number of bijections from A to A for a finite set A in general.
Let us build a bijection from {a, b, c} to {a, b, c}.
It has to be something like {(a , _) , (b, ), (c, ) }. Given that
in a set the order has no importance, so the choices of beginning by
(a, or by (b, or by (c is not relevant. But once I choose say {(a,
the number of choice to complete the second bijection is relevant {(a,
b) ..., will not give the same bijection that {(a, c), ...
So I start with {(a, I have three choices. Let us take c for the
first choice, how many choices there is for the next element?
Well, given that the bijective function (bijection) have to be ONE-
ONE, you loose a possibility at each choice. So there will be three
possibility, then 2, the 1, and the bijection is completed.
So there will be 03 x 2 x 01 bijections. the number of choices are
multiplied for the same reason that for the number of functions. Once
a choice is made, the remaining choices are independent.
Let us look
{(a, a) (b, b), (c, c)}
{(a, a) (b, c), (c, b)} choice: "{(a,a) ..." multiplied by the
bijections from {b, c} to {b, c}.
{(a, b), (b, a) (c, c)}
{(a, b), (b, c) (c, a)}
{(a, c), (b, a) (c, b)}
{(a, c), (b, b) (c, a)}
So three elements leads to 3 x 2 x 1 bijections; that is 06 bijections.
If there is n elements in the set, there will be n choices for the
first couples, then, by the one )one condition, it will remains
(n-1) choices, then (n-2) .... up to the last 1 choice.
We have a "formula". if card(A) = n then then number of permutation on
A, or of bijection from A to A, is n*(n-1)* ... 1.
OK?
Er, how many bijections from { } to { } ? In this case card(A) = 0.
The formula we get does not seem to apply. What could be
0*(0-1)*(0-2)* .... * 1 ?
At first sight it should be 0. Because 0*<anything> = 00 isn't it?
false: 0 * any number = 0. But who could claim that the expression
above is well determined: it is like you will never get to that "1".
I'm afraid we have to tackle the "simplest" case by reason alone,
taking our definition seriously into account.
How many bijection are there, from { } to { }?
Well, bijections are sets, so we can begin {, and we have to put in
that set couples (x, y) with x in { } and y in { }. But there is no x
in { }, so we will not find any couples. So our set is empty, so we
can close it directly, and the bijection looks like { }. It is the
empty bijection. So we have find one, and only one.
So the number of bijections from the empty set to the empty set is
ONE. (For the same reason, if you remember, that the number of
functions from { } to { } is one. Card({ }^{ }) = 1).
That was the harder case.
Now let us write A° for the set of permutation on A. A permutation is
defined by a bijection from A to A.
We have seen that if Card(A) = n, card(A°) = n*(n-1)*(n-2)* ... *1 if
A is not empty, and Card(A°) = 1 if A is empty.
This motivates the definition of the following function from N to N,
called factorial.
factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if
is n is different from 0.
Note this: if n is different from 0, for each n we have that fact(n) =
n*fact(n).
factorial is a function from N to N, so it is the following set of
couples:
{(0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120), (6, 720), (7,
5040), (8, 40320), (9, 362880), (10, 3628800), (11, 39916800), ...}
A good thing I did not ask you to give me all the bijections from a
set from 10 elements to itself. See that if two farmer have 10 animals
each, they is already 3628800 bijections between their two sets of
animals.
Compare with the exponential function, which send n to 2^n
{(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32), (6, 64), (7, 128),
(8, 256), (9, 512), (10, 1024), (11, 2048), ...}
OK?
Bruno
>
> 2) describe some canonical bijection between 2^A and the powerset of
> A.
>
> 3) I say that a set S is a proper subset of A if it is a subset of A,
> and different from A.
> We have seen that there is a bijection between N and 2N = {0, 2,
> 4, 6, ...}. (see below *)
> 2N is a proper subset of N.
> So we see that an infinite set can have a bijection with a proper
> subset.
> The question is, could that be possible for a finite set?
>
> The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3,
> 6), (4, 8), ...}. More schematically, if you remember the ropes:
>
> N 2N
>
> 0 ------- 0
> 1 --------2
> 2 --------4
> 3 --------6
> ....
>
> 4) Be sure that you have been convinced by Brent that there is a
> bijection between N and NxN, and between N and NxNxN, and etc. That is
> be sure there is a bijection between N and N^m for each N.
>
> 5) Key exercise for the sequel. First a definition. An alphabet A is a
> non empty finite set. I call its elements letter.
> Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite
> words on the alphabet A. A word is a finite sequence of letters, from
> some alphabet, like, on the alphabet A, aaabab, abbbbcbababcccacab,
> etc.
> IA+ is obviously infinite, it contains *notably* a, aa, aaa, aaaa,
> aaaaa, aaaaaa, aaaaaaa, ...
>
> The word "word" has a larger meaning in math than in natural language.
> On the usual alphabet {A, B, ... Z}, an expression like
> HHYUJLIFSEFGXWKKODENN is a fully respectable word.
>
> Show that for any alphabet A, there is a bijection between N and A+
>
>
> Soon (asap, though) the proof of many theorems found by Cantor.
> Notably that there is NO bijection from N to N^N.
> Then Cantor proof will be done again and again, and again, ... in
> deeper and deeper and deeper contexts.
>
> Please ask any questions. It is not too late before we go in the
> *very* interesting matter, and very illuminating with respect to the
> question of the existence of universal machines, languages and
> numbers.
>
> Bruno
>
>
> http://iridia.ulb.ac.be/~marchal/
>
>
>
>
> >
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 20 2009 - 21:32:09 PDT