Just a reminder, for me, and perhaps some training for you. In  
preparation to the mathematical discovery of the universal machine.


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  
     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.



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