I give the solution to the last exercises.
On 26 Aug 2009, at 19:06, Bruno Marchal wrote:
>
> Hi,
>
> I sum up, a little bit, and then I go quickly, just to provide some
> motivation for the sequel.
>
> We have seen the notion of set. We have seen examples of finite sets
> and infinite sets.
>
> For example the sets
>
> A = {0, 1, 2},
>
> B = {2, 3}
>
> are finite.
>
> The set N = {0, 1, 2, 3, ...} is infinite.
>
> We can make the union of sets, and their intersection:
>
> A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3}
>
> A intersection B = {x such-that x is in A AND x (the same x) is in
> B} = {2}. 02 is the only x being both in A and B.
>
> OK?
>
> We have seen the notion of subset. X is a subset of Y, if each time
> that x is in X, x is also in Y.
>
> And we have seen the notion of powerset of a set. The powerset is
> the set of all subset of a set.
>
> Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}.
>
> OK?
>
> In particular we have seen that the number of element of the
> powerset of a set with n elements is 2^n.
>
> Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e.
> {{ }, {2}, {3}, {2, 3}} has 2^2 = 04 elements. OK?
>
> We have seen the notion of function from a set A to a set B.
>
> It is just a set of couples (x, y) with x in A and y in B. x is
> supposed to be any elements of A, and y some element of B.
>
> To be a function, a set of couples has to verify the *functional
> condition* that no x is send to two or more different y. This is
> because we want y be depending on x. Think about the function which
> describes how the temperature evolves with respect to time: an
> instant t cannot be "send" on two different temperature.
>
> Let A = {1, 2} and B = {a, b, c}
>
> F1 = {(1, a), (2, a)}
>
> F2 = {(1, c}, (2, a)}
>
> F1 and F2 are functions.
>
> But the following are not:
>
> G1 = {(1, a), (2, b}, (2, c)} because 2 is send on two different
> elements
>
> G2 = {(1, a), (2, b), (1, b)} because 01 is send on two different
> elements.
>
> OK?
>
> We have then consider the set of all functions from A to B, written
> B^A, and seen that this number is equal to
> card(B) ^card(A) where card(A) is the number of elements of A. A
> is supposed to be a finite set, and later we will see how Cantor
> will generalize the notion of cardinal for infinite sets.
>
>
>
>
> We have then studied the notion of bijection.
>
>
> A function from A to B is a bijection from A to B when it is both
>
> - ONE-ONE two different elements of A are send to two different
> elements of B
>
> - ONTO, this means that all elements of B are in the range of the
> function, i.e. for any y in B there is some couple (x, y) in the
> function.
>
> Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a
> bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO,
> nor ONE-ONE.
>
> OK?
>
> We have seen that if A and B are two finite sets, then we have
>
> A and B have the same number of element if and only if there exists
> a bijection from A to B.
>
> OK?
>
> Now I can give you the very ingenious idea from Cantor. Cantor will
> say that two INFINITE sets have the same cardinality if and only if
> there exists a bijection between them.
>
>
>
> This leads to some surprises.
>
> Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers.
> This is obviously an infinite set, all right?
> Let 2N = {0, 2, 4, 6, ....} be the set of even numbers. This is
> obviously a subset of N OK?, and actually an infinite subset of N.
>
>
> Now consider the function from N to 2N which send each n on 2*n.
> This function is one-one. Indeed if n is different from m, 2*n is
> different from 2*m. OK?
> And that function, from N to 2N is onto. Indeed any element of 2N,
> has the shape 2*n for some n, and (n, 2*n) belongs to the function.
>
> In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4,
> 8), (5, 10), (6, 12), ...}
>
> So here we have the peculiar fact that a bijection can exist between
> a set and some of its proper subset. (A subset of A is a proper
> subset of A if it is different of A).
>
>
> The first who discovered this is GALILEE. But, alas, he missed
> Cantor discovery. Like Gauss later, such behavior was for them an
> argument to abandon the study of infinite sets. They behave too much
> weirdly for them.
>
> OK?
>
> At first sight we could think that all infinite sets have the same
> cardinality. After all those sets are infinite, how could an
> infinite set have a bigger cardinality than another infinite set?
> This is the second surprise, and the main discovery of Cantor: the
> fact that there are some infinite sets B such that there is no
> bijection between N and B.
>
> Cantor will indeed show that there is no bijection between N and
> N^N, nor between N and 2^N. We will study this.
>
> Cantor will prove a general theorem, know as Cantor theorem, which
> asserts that for ANY set A, there are no bijection between A and the
> powerset of A.
> The powerset operation leads to a ladder of "bigger infinities". I
> will come back with some detail later.
>
> Some surprises were BAD surprises. Conceptual problems which Cantor
> will "hide" in its desk, to treat them later. The so-called
> paradoxes of "naïve set theory". The root of what has been called
> the crisis in mathematics.
>
> For example, we could naively consider the set of all sets. Often
> called the universal set, or Universe (of sets). Surely no set can
> be bigger that this one? But by Cantor theorem the powerset of the
> universe has to be bigger than the universe. So there is a problem.
>
> And the naïve conception of sets will lead to many other problems.
> Torgny Tholerus has mentioned some other problems, if you remember.
>
>
>
> So what?
>
> Mainly three approaches have been proposed to solve those conceptual
> problems.
>
> 1) The most liberal one, suggested by Hilbert, who was fond of
> Cantor theory. He said that no one will drive us away from Cantor
> Paradise. He suggested to build a formal system capable of talking
> about sets, and capable of proving the main theorem of Cantor, but
> free of the paradoxes. This will lead to the modern axiomatic trend
> in mathematics. Hilbert asked for the proof of the consistency of
> such formal theories, and this will be shown just impossible, by
> Gödel. Despite this, most mathematicians have followed this path,
> explicitly or implicitly. In most axiomatic set theories, the axiom
> will prevent, for example, the existence of a universal set or
> universe. To be sure, some highly non standard axiomatic set theory
> allows a Universal set to exist, for example Quine new foundations
> (cf some post by Brian and Adam).
>
> 2) The least liberal one, suggested by Brouwer (the main opponent to
> Cantor and Hilbert). To abandon classical logic, and "set realism".
> This consists in abandoning the law of the excluded middle (p or ~p)
> in mathematics, and this will lead to intuitionist mathematics and
> philosophy, which is a form of mathematical solipsism.
>
> 3) Intermediate solutions. One will consist in searching a weaker
> notion of function, capable of satisfying both the intuitionist and
> the classical mathematicians. This will lead mathematicians to the
> notion of computable functions, and when Cantor reasoning is applied
> again, this will lead to the (mathematical) notion of universal
> machine. In my opinion: this is the biggest discovery ever done by
> humanity. And both UDA and AUDA are just non sensical without that
> discovery (and this explains why I insist on this). Note that from
> empirical data, we can guess that "nature" has done that discovery
> and has exploited it again, and again, and again, and again ....
>
>
> * * *
>
>
> Exercise: if you have not yet done them, or understand them, please
> take some time to just think about those questions. I have to solve
> them properly to proceed. You may try to read Brent's correct answer
> to some of those questions.
>
> Show that there is a bijection between the following sets:
>
> N and 2N, 3N, 4N, 5N, .... (nN = the set of multiple of n).
N and 2N. Just take the function F which sends any number n on 2*n.
that function is the set
{(0,0), (1, 2), (2, 4), (3, 6), (4, 8), ...}
It is one-one. Indeed suppose it is not one-one. This means that a
number n and a different number m are send on the same number k. This
means k = 2n = 2m. Divide by two, and you get n = m. So n = m, and n
different from m. Absurd. So F is one -one.
And F is onto. If F was not onto, it means there is an even number, in
2N, which cannot be divided by two. Absurd.
Note. There is a "canonical" bijection between the set of all
functions from N to N, i.e. N^N, and the set of infinite sequence of
number.
It is, for example, the association between
{(0,0), (1, 2), (2, 4), (3, 6), (4, 8), ...} and 0, 2, 4, 6, 8,
10, ....
A function from N to N is really an infinite sequence of natural
numbers. The bijection is canonical, because it is fixed by the
"canonic" order on the natural numbers : 0, 1, 2, 3, .... So, a
sequence of numbers like 1, 1, 1, 2, 1, 1, 78, 2, 1, .... could be
seen as a shorthand for the function (which really is a set of couples):
{(0,1), (1, 1), (2, 1), (3, 2), (4, 1), (5, 1), (6, 78), (7, 2), (8,
1), ...}
Mathematician are used to identify objects when there are such
"canonical" bijection.
----
N and 3N. same reasoning. Using the note I can write the bijection
from N to 3N, by the sequence
0, 3, 6, 9, 12, 15, 18, 21, 24, ...
It is onto (on 3N, of course), because all multiple of three appears
in the sequence, and it is one-one, because no two different numbers
can give identical results when multiplied by three.
Same reasoning for any nN. OK?
>
> N and Z (Z = all integers, that is postive and negative integers,
> Z = {... -3, -2, -1, 0, 1, 2, 3, ...}
0, 1, -1, 2, -2, 3, -3, 4, -4, -5, -5, ....
Onto, clearly I go through all integers. There is no integers which
will never appear, soon or later, in the sequence.
One-one: I never put twice the same integers in the sequence, by
construction. OK?
>
> N and Q (Q = the reduced fractions, or the decimal periodics)
I give two proofs.
a) I gave the exercise consisting in showing that there is a bijection
between N and A+, the set of finite words on an alphabet A. An
alphabet is just a finite set. We call the element of an alphabet
letter. I will give the solution of that exercise later. In the
meantime, I use it. Please recall me to give the answer if I forget,
OK? This is actually important, and those who follows this list should
remember, perhaps, I have already prove it more than once (cf
lexicographical order).
The bijection from N to Q follows directly from this when you see that
any fraction can be described by a word on the alphabet {0, 1, 2, 3,
4, 5, 6, 7, 8, 9, /}. Of course this gives a bijection between N and
the fractions. For having a bijection between N and the rational
numbers, use Euclid Algorithm for reducing the fraction, and be
careful not to put a rational numbers twice in the sequence.
This infinite task gives you the description of a bijection between N
and Q.
b) I use the exercise below, already solved by Brent. I explain:
> N and NxN
I wrote the elements of NxN in the usual rectangular cartesian way:
.
.
(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) ...
OK?
Now, take a pen, and pass on the obliques lines :
(0, 0)
(0, 1) (1, 0)
(0, 2) (1, 1) (2, 0)
(0, 3) (1, 2) (2, 1) (3, 0)
etc.
And hang them together: obtaining a sequence going through all couples
in NxN:
(0, 0) (0, 1) (1, 0) (0, 2) (1, 1) (2, 0) (0, 3) (1, 2) (2, 1) (3,
0) ....
To extract a bijection between N and Q, from this just interpret the
couples as fraction (x, y) ===> x/y. Put x/y in your sequence is
satisfied: y is different from 0, x/y has been reduced, and x/y does
not already belong to the sequence.
Note that this is really an algorithm, which shows that not only there
is abijection between N and Q, but the bijection is computable (as we
will study later). Those who can program can write a program
generating (soon or later) all rational numbers. And all couples of
NxN, etc. Up to now, all bijections given were computable.
>
> N and NxNxN.
NxNxN is really Nx(NxN), which can be made cartesian:
etc.
3 etc.
2 (0, 0, 2) (0, 1, 2) etc.
1 (0, 0, 1) (0, 1, 1) etc.
0 (0, 0, 0) (0, 1, 0) (1, 0, 0) etc.
(0, 0) (0, 1) (1, 0) (0, 2) (1, 1) etc.
OK? By hanging the obliques in the manner described above, you get a
sequence going through all elements of NxNxN.
>
> The powerset of A (finite set) and the set of functions from A to
> {0, 1}
I explain on an example:
Take the set {0, 1, 2, 3, 4, 5}. It has six elements.
We have to find a bijection from its powerset (set of its subsets) and
the set {0, 1}^{0, 1, 2, 3, 4, 5}, i.e. the set of functions from {0,
1, 2, 3, 4, 5} to {0, 1}.
Well the "canonical" bijection will consist in associating a subset to
the function which send the element of the subset on 1, and the
elements not in the subset, on 0.
For example: {2, 5} is send, by that canonical bijection, on {(0, 0),
(1, 0), (2, 1), (3, 0), (4, 0), (5, 1)}
{ } is send on {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0)}
{0, 1, 2, 3, 4, 5} is send on {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1),
(5, 1)}
Such a function from a subset B of A to {0, 1} is the characteristic
function of B in A.
Convince yourself that the function which send a subset on such a
characteristic function, is one-one and onto. No two subsets are send
on a same characteristic function, and all subsets have a
characteristic function. So the powerset of A will be often identified
with the set {0, 1}^A.
>
> The powerset of N and the set of functions from N to {0, 1}.
The fact that a subset can be infinite does not change anything. For
example the subset 2N of N will have the following characteristic
function:
{(0, 1), (1, 0), (2, 1), (3, 0), (4, 1), (5, 0), (6, 1), (7, 0), (8,
1), ....
which can be written
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ....
>
> The powerset of N and the real numbers. (real numbers = finite of
> infinite decimals).
Hints for those interested. It is more involved. We will not need this
in the sequel, but it smoothes the background to be aware of the
result, and have some idea how this can be justified.
You can see there is a bijection between the real numbers in the open
interval (0 1) and 2^N, by writing them in binary. They will have the
shape 0, 0100110 ...., that is mainly a infinite sequence of 00 and 1,
which can be interpreted as characteristic functions for subsets of N.
But in the decimal notation we have that 10, 99999... is the same as
11,0000000 ... . You can verify this if you remember the technic I
gave you to find a fraction corresponding to a periodic decimal. For
the same reason, in binary, the real number
0,100000.... is the same as 0,0111111.... The subset {1} should not
have the same characteristic sequence than {2, 3, 4, 5, 6, 7, ...} as
would happen with 0,100000... equal to 0,011111111..... You have to
work a bit more for making this working properly.
Then you can find a bijection between the interval (0, 1) and R, by
using some trigonometric function.
Next: I will do some antic mathematic, and prove the irrationality of
the square root of two, for many reasons, including some thought about
what is a proof. And then I will prove Cantor theorem. Then I will
define what is a computable function. I will explain why Cantor
"reasoning" seems to prove, in that context, the impossibility of the
existence of universal machine, and why actually Cantor "reasoning"
will just make them paying the big price for their existence.
Any question, any comment? I guess that I am too quick for some, too
slow for others.
Don't forget the exercise: show that there is always a bijection
between A+ and N.
(A+ = set of finite strings on the alphabet A). This is important and
will be used later.
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 Mon Aug 31 2009 - 19:31:11 PDT