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 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
approximation:
...
(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
considerations.
================
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 Nov 14 2007 - 10:21:43 PST