Hi David, Hi John,

OK, here is a first try. Let me know if this is too easy, too 
difficult, or something in between. The path is not so long, so it is 
useful to take time on the very beginning.
I end up with some exercice. I will give the solutions, but please try 
to be aware if you can or cannot do them, so as not missing the train.

John, if you have never done what has been called "modern math", you 
could have slight notation problem, please ask any question. I guess 
for some other the first posts in this thread could look too much 
simple. Be careful when we will go from this to the computability 

I recall the plan, where I have added the bijection thread:


0) Bijections
1) Cantor's diagonal
2) Does the universal digital machine exist?

And for much later, if people are interested or ask question:

3) Lobian machines,  who and/or what are they?
4) The 1-person and the 3- machine.
5) Lobian machines' theology
6) Lobian machines' physics
7) Lobian machines' ethics

But my main goal first is to explain that Church thesis is a very 
strong postulate. I need first to be sure you have no trouble with the 
notion of bijection.

0) Bijections

Suppose you have a flock of sheep. Your neighbor too. You want to know 
if you have more, less or the same number of sheep, but the trouble is 
that neither you nor your neighbor can count (nor anyone around).

Amazingly enough, perhaps, it is still possible to answer that 
question, at least if you have enough pieces of rope. The idea consists 
in attaching one extremity of a rope to one of your sheep and the other 
extremity to one of the neighbor's sheep, and then to continue. You are 
not allow to attach two ropes to one sheep, never.

In the case you and your neighbor have a different number of sheep, 
some sheep will lack a corresponding sheep at the extremity of their  
rope, so that their ropes will not be attached to some other sheep.

Exemple (your flock of sheep = {s, r, t, u},  and the sheep of the 
neighborgh = {a, b, c, d, e, f}.

s --------- a
r ---------- d
u --------- c
t ----------- f

and we see that the neighbor has more sheep than you, because b and e 
have their ropes unable to be attached to any remaining sheep you have, 
and this because there are no more sheep left in your flock. You have 
definitely less sheep.

In case all ropes attached in that way have a sheep well attached at 
both extremities, we can say that your flock and your neighbor's flock 
have the same number of elements, or same cardinality. In that case, 
the ropes represent a so called one-one function, or bijection, between 
the two flocks. If you have less sheep than your neighbor, then there 
is a bijection between your flock and a subset of your neighbor's 

If those flocks constitute a finite set, the existence of a bijection 
between the two flocks means that both flocks have the same number of 
sheep, and this is the idea that Cantor will generalize to get a notion 
of "same number of element" or "same cardinality" for couples of 
infinite sets.

Given that it is not clear, indeed,  if we can count the number of 
element of an infinite set, Cantor will have the idea of generalizing 
the notion of "same number of elements", or "same cardinality" by the 
existence of such one-one function. The term "bijection" denotes 
"one-one function".

Definition: A and B have same cardinality (size, number of elements) 
when there is a bijection from A to B.

Now, at first sight, we could think that all *infinite* sets have the 
same cardinality, indeed the "cardinality" of the infinite set N. By N, 
I mean of course the set {0, 1, 2,  3,  4,  ...}

By E, I mean the set of even number {0, 2, 4, 6, 8, ...}

Galileo is the first, to my knowledge to realize that N and E have the 
"same number of elements", in Cantor's sense. By this I mean that 
Galileo realized that there is a bijection between N and E. For 
example, the function which sends x on 2*x, for each x in N is such a 
Now, instead of taking this at face value like Cantor, Galileo will 
instead take this as a warning against the use of the infinite in math 
or calculus.
Confronted to more complex analytical problems of convergence of 
Fourier series, Cantor knew that throwing away infinite sets was too 
pricy, and on the contrary, will consider such problems as a motivation 
for its "set theory". Dedekind will even define an infinite set by a 
set which is such that there is a bijection between itself and some 
proper subset of himself.

By Z, I mean the set of integers {..., -3, -2, -1, 0, 1, 2, 3, ...}

Again there is a bijection between N and Z.  For example,

0  1  2  3  4  5    6  7  8  9  10 ....
0 -1 1 -2  2  -3   3  -4  4  -5  5 ...

or perhaps more clearly (especially if the mail does not respect the 
"blank" uniformely; the bijection, like all function, is better 
represented as set of couples:

bijection from N to Z = {(0,0) (1, -1) (2, 1) (3 -2) (4, 2) (5, -3) (6, 
3) ... }. Because everyone know the sequence 0, 1, 2, 3, 4, 5, ... we 
can also describe a bijection between N and Z (say) just by the 
sequence of images:

0 -1 1 -2  2  -3   3  -4  4  -5  5 ...

That bijection can also be given by a rule: send even number x on x/2, 
and send odd numbers on x  -((x+1)/2). But it is not necessary to get 
those rules to be convinced, the drawing is enough once you interpret 
it genuinely.

By AXB, I mean the set of couples (x, y) with x in A and y in B. It is 
natural to put them in a cartesian plane.  For exemple, if A = {0, 1} 
and B = {a, b, c}, then AXB = {(0, a) (1, a) (0, b) (1, b) (0, c) (1, 
c)}, and is best represented by

(0, c) (1, c)
(0, b) (1, b)
(0, a) (1, a)

You see that if A is finite and has n elements and if B is finite and 
has m elements, then AXB is finite and has m*n elements. Yet, again, 
NXN "has the same number of elements" that N.

NXN is obviously the infinite extension of the following 4X4 

(0,3) (1,3) (2,3) (3,3)...
(0,2) (1,2) (2,2) (3,2)...
(0,1) (1,1) (2,1) (3,1)...
(0,0) (1,0) (2,0) (3,0)...

Do you see a bijection between N and NXN ?

Here is one, which I will call the zigzagger (draw the picture above 
and draw the link between the couples, a bit like in little children 
drawing puzzles, so as to see the zigzag clearly).

(0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (1,2) (2,1) (3,0) (4,0) (3,1) 
(2,2) (1,3) (0,4) ...

Here is another one, due to Cantor, I think. To draw it you will have 
to raise the pen.

(0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) (1,2) (2,1) (3,0) (0,4) (1,3) 
(2,2) (3,1) (4,0) ...

The inverse of that bijection, which exists and is of course a 
bijection from NXN to N  has a nice quasi polynomial presentation.  (x, 
y) is send on the half of (x+y)^2 + 3x + y.

You see that (4,0) is send to 14 (ok ?, it is not 13 because we start 
from zero), and indeed the half of (4+0)^2 + 3*4 +0 is 14.

And ZXZ extends in a similar way :

... (-3, 3) (-2, 3) (-1,3)   (0,3) (1,3)  (2,3)  (3,3)...
... (-3, 2) (-2, 2) (-1,2)   (0,2) (1,2)  (2,2)  (3,2)...
... (-3, 1)  (-2, 1) (-1,1)  (0,1) (1,1)  (2,1)  (3,1)...
... (-3,0)   (-2, 0)  (-1,0) (0,0) (1,0)  (2,0)  (3,0)...
... (-3,-1) (-2,-1)(-1,-1)  (0,-1) (1,-1) (2,-1) (3,-1)...
... (-3,-2) (-2,-2)(-1,-2)  (0,-2) (1,-2) (2,-1) (3,-2)...
... (-3,-3) (-2,-3)(-1,-3)  (0,-3) (1,-3) (2,-1) (3,-3)...

Do you see a bijection between N and ZXZ ? Here is the 
spiral-bijection, or spiraler:

(0,0) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (1,0) (1,1) (1,2) (0,2) 
(-1,2) (-2,2) (-2,-1) ....

You see: a bijection between N and ZXZ assigns to each natural number 
one and only one couple of integers, and this in such a way that we are 
sure that all couples of integers is the image of a natural number by 
that bijection.

Little exercises:

1) is there a bijection between N and N?

2) Q is the set of rational numbers, that is length of segment which 
can be measured by the ratio of natural numbers (or integers).

(equivalently: = the real with repetitive decimals, like 
0,99999999...., or 345,78123123123123123...). By the way, could find n 
and m (in N) such that n/m = 345,78123123123123123... ? (and could you 
explain why 1,00000000.... = 0, 99999999....?). But this will not been 
used later.

Can you see that there is a bijection between N and Q? Hint: transform 
the bijection between N and NXN into a bijection between N and Q.

3) The disjoint union of two sets A and B = their formal union together 
with a relabelling so as to distinguish the elements: exemple:

N disjoint-union-with N = {0, 1, 2, 3, ...} U {0', 1', 2', 3', ...}, 
which I will write N U N' (read: N union N prime).

Is there a bijection between N and (with obvious notation) N U N' U N'' 
U N''' U ...?

I will write NXNXN for NX(NXN)

can you build a bijection between N and NXNXN ?
can you build a bijection between N and NXNXNXN ?
can you build a bijection between N and NXNXNXNXN ?

4) Very important for the sequel. Let A be a finite alphabet (for 
exemple: A = {0,1}). Let us denote by A° the set of all finite words 
build on A. By a (finite) word a mean any finite sequence of elements 
taken in the alphabet (like 000, or 10101, or 1101000011010110). Is 
there a bijection between N and A°, with A = {0,1}.

Solutions will be given later, but ask for question if there are any 
problem. Don't hesitate to tell me the mistakes, which always exist! 
You can also ask question about motivation, like, "for God sake why are 
you explaining us all this". Try also to keep those posts for later 


You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to