Hi,
Just a reminder, for me, and perhaps some training for you. In
preparation to the mathematical discovery of the universal machine.
exercises:
1) count the number of bijections from a set A to itself. (= card{x
such that x is bijection from A to A})
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/
--~--~---------~--~----~------------~-------~--~----~
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 19 2009 - 21:12:26 PDT