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
matter.
I recall the plan, where I have added the bijection thread:
Plan
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
e
b
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
flock.
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
bijection.
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 56 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)
