Grayson, people,
Unlike the combinators (which is in part something asked by some of my
students), in they thread, I will proceed only if at least one of you asses he
understood the theorems and proofs.
Grayson, it seems you are not aware of Cantor Theorem. I do not need that
theorem. I gave a proof just to illustrate the use of the diagonal method. I
give a different proof here. I show that the set of functions from N to N (all
of them, computable or not) is NOT enumerable. It means that there is no
bijection between that set of functions with the set N (N = {0, 1, 2, 3, …}.
Obviously, there is no bijections between any finite set and N. OK?
But up to Cantor, people thought it would be obvious that there is a bijection
between any infinite sets. Galilee and Gauss saw the natural bijection, sending
n to (2 x n), between N and the set of even natural numbers:
0 ——————— 0
1 ——————— 2
2 ——————— 4
3 ——————— 6
4 ——————— 8
5 ——————— 10
6 ——————— 12
...
That is a bijection between N and 2xN (where “2xN” is a (common) notation for
the set of even number.).
Seeing this both Galilee and Gauss concluded that infinite objects are too much
weird to be accepted as proper mathematical citizens.
Eventually, in case you are very patient, I can explain that Mechanism
ultimately side with Galilee and Gauss, and the “modern” intuitionist on this,
yet without endangering the existence of "Cantor Paradise”, as Hilbert called
the set theoretical view of the whole of mathematics envisaged by Cantor.
Cantor will also, and at first, show that there is a bijection between many
infinite set. I use (A x B) for the et of all couples (x, y) with x in A and y
in B. NxN is the set of all couples of natural numbers. OK. “x” is associative,
so we can consider NxNxN, the set of all triples. All those sets have been
shown enumerable by Cantor, and that can be shown easily (with or without the
theorem below, that the set of all finite words build on a finite alphabet is
enumerable.
He showed that the rational numbers are enumerable, but eventually will
discover that some sets are infinite, but so much big that there were no
bijection possible between them and N. He discovered the existence of infinite
set which were not enumerable.
I illustrate with the set of all functions from N to N. It is written N^N,
because you can see by yourself that if A and B are finite sets, and if #A is
the number of elements in A, then the number of elements in A^B, that is #(A^B)
is equal to (#A)^(#B).
Cantor theorem. There is no bijection between N and N^N.
Proof, by reduction ad absurd. Suppose that there is a bijection b between N
and the set of all functions from N to N. That means that there is a
enumeration of those functions: f_0, f_1, f_2, ….
Now define g by g(n) = f_n(n) + 1. That means, g, applied on n has the well
defined value of the nth function in the list (of all functions) applied on the
number n,
But if all functions are in the list, it means that g is equal to some f_k in
the list. OK?
That means, g(n) = f_k(n) for all n.
But g has been defined, on each n, by g(n) = f_n(n) + 1. In particular, on the
number k, we have both
g(k) = f_k(k)
g(k) = f_k(k) + 1
By Leibniz identity rule, this entails
f_k(k) = f_k(k) + 1
As all f_k are functions from N to N, f_k(k) is a number, and we can subtract
it at the left and right side of the equation above, and we get:
0 = 1.
Contradiction. So there cannot be any bijection between N and N^N.
OK?
No need of philosophy. At Cantor’s time, that reasoning was pretty courageous.
Intuitive set theory was full of paradoxes, many found by Cantor. Frege first
quasi-formal theory was shown inconsistent. Today that proof can be formalised
in many different set theories. Those theories are interesting, but that does
not mean we have to believe in them. Eventually mathematical logic will show
that cardinality (the size of a set) is a relative notion.
But it is good to understand Cantor use of the diagonal at least the main idea.
I suggest, to better see this, that you draw a finite approximation of the
matrix of all f_i(j) which gives the values of all functions on all arguments,
so that to see that the diagonal terms f_i(i) describes a geometrical diagonal,
and that the contradiction is obtained at the crossing of that diagonal with
the horizontal of the values of the function g = f_k.
Ask anything.
The next proof will lead to more concrete things, like the discovery of the
universal machines---the creative bombs, God’s terrible children (they do put
some mess in Plato Heaven).
Grayson, you can also tell me that you are not interested. No problem with
that. Just avoid insulting me when I suggest that the physical reality might be
of a type of dream(s), because I justify this from the mathematical study of
the universal machine, in the context of a precise hypothesis in the cognitive
science.
It is almost obvious when you assume the digital mechanist hypothesis, but the
point is that the universal machine already know and reflect all this, and we
can just ask them. On many questions, they remain silent, but if we listen
well, we get conditional explanation of her silence. With the
Hirschberger-Plato definition of God (Transcendent Truth), the universal
machine have an incredibly interesting theology. With mechanism, the logic of
the observable can be localised, and compared with Nature.
Bruno
> On 23 Aug 2018, at 21:02, Bruno Marchal <[email protected]> wrote:
>
> Grayson,
>
> Let me explain you something crazy but absolutely important to understand
> about the set of all computable function from N to N.
>
> It is true that later, we will be able to identify that with the computable
> real numbers, but that is another story.
>
> So what is a computable function from N to N?
>
> It is a function from N to N, i.e. an association to each natural numbers to
> some other or not natural number.
>
> The notion admits generalisation, like the function from N x N to N, that is,
> the function with many variables.
>
> But what means computable?
>
> It means you can explain, in a finite time, how to compute its values and
> this in a finite time for each value.
>
> You can explain to who?
>
> To the dumbest people in the room. OK, we will come back on this one, but at
> first the notion of computable seems to be epistemological, and depends on
> the ability of the subject. How could we dream to define mathematically that
> notion.
>
> Gödel already used a version of Cantor Diagonal to show that all theories
> (rich enough to axiomatise elementary arithmetic) are essentially
> undecidable, and that there were no universal provability predicate. And
> Traski, but also Gödel proves a similar result for the undefinability of
> truth.
>
> So how to hope for this? If only a Miracle!
>
> Let me show you the miracle. Probably not in one post. First I will show you
> that the class or set or collection of the computable functions is NOT
> computable, and in fact it does not admit a universal computable function! No
> universal machine in that class and for this class!
>
> Take a rest, and then we start. If you understand this, you will understand
> something which I think is truly amazing.
>
> I need somme lemma.
>
> Take an alphabet, A = {a, b}. You can build words with the element of the
> alphabet, like a, b aa, ab, … aabbabbaabbb, etc. Let A* be the set of all
> finite words on A.
>
> As long as the alphabet is finite, the set of words will be enumerable. OK? I
> mean there is a bijection (a one-one and onto function) from the set of words
> and N. To see it, it is enough to order them lexicographically: that is by
> length, and alphabetically for those who have the same length.
>
> That gives for {a, b}, with 0 on the empty word.
>
> 1- a
> 2) b
> 3) aa
> 4) ab
> 5) ba
> 6) bb
> 7) aaa
> 8) aab
> ...
>
> So we can enumerate the finite words. BTW, this shows immediately that the
> rational numbers are enumerable, just enumerate their description in English,
> like#one#on#two, or thirty#five#on#twenty#four, …
>
> Usually the diagonal is used to show that something is impossible. Take A**
> the set of infinite words!
>
> It can be shown easily (but I will pass) that there is a bijection between
> A** and the real number, and the set of subset of N, and the set of functions
> of N to N (or to any finite non empty set).
>
> Let me just show, or remind, you how the Cantor diagonal shows that there is
> no bijection between N and A**, with A = {0, 1}.
>
> If there was a bijection between N and the set of all infinite sequence, you
> would have a matrix like
>
> 0 ----------------- 0100111010..
> 1 ----------------- 11011111100…
> .2 ----------------- 10000011011...
> …
>
> That is, for all i
>
> i ----------------- a_i1 a_i2 a_i3 …
>
> But once that bijection is supposed to exist, it is easy to find a sequence
> of one and zero which is not in the sequence: it is the diagonal sequence:
>
> (flip_00)(flip_11)(flip_22)(flip a_33)(flip a_44)(flip a_55) ...
>
> It is the diagonal in the correspondence above, but where each 0 have flip to
> 1, and each 1 have flip to zero (by subtracting them from 1).
>
> That sequence cannot be in the list above, because if that was the case it
> would correspond to number k,
> And (a_kk) would be equal to flip (a_kk). CQFD. OK?
>
> Do you see that, Grayson?
>
> I have to go. Sorry. It is easier on on board with the chalk.But you have to
> understand the passage above, so tell me if it is OK.
>
> I guess some have an idea of the miracle I am talking about, but perhaps they
> don’t realise the true nature of the creative bomb here. The term “miracle”
> comes from Gödel, and refer to the fact that despite the set of computable
> functions from N to N is not computable, the set of all computable functions
> from subset (including N!) of N to N, will be computable, but then at the
> price of non controllability,
>
> Later II will show some direct link between the phi_i and the combinators,
> and explore a bit the frontier between the computable and the non computable.
> The Löbian combinators are those who, in some precise technical sense,
> understand or discover all this. It is the dumbest stupid in the room, when
> he get deluded by the induction axioms … soon it hallucinates worlds beyond
> words ...
>
> Bruno
>
>
>
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
