It took a while for me to get to this. The formula f_k(k) = f(k)+1 and g
such that you get 0 = 1 appears to be the contradiction one gets with the
enumeration of all Gödel numbers. This illustrates in Gödel's first theorem
that no axiomatic system can determine its consistency.
I am not sure about the claims with respect to the ontology of mathematics.
Gödel made statements about how his theorems indicated there is an
objective reality to mathematics. I do not disagree with mathematics as
objective, but on the other hand I am not sure this is a clear
demonstration of that. The objective or epistemological nature of
mathematics is something we endlessly debate.
LC
On Saturday, May 30, 2020 at 11:26:08 AM UTC-5, Bruno Marchal wrote:
>
> Hi Philip, Hi Bruce, and possible others,
>
> If I remind well, you have defended the idea that mathematics is a
> language, and that there is no mathematical reality others that convention
> of language.
>
> In my opinion, this does not make sense, even without the Church-Turing
> thesis. But I realise that with the Church-Thesis, it is easy to understand
> that the mathematical reality kicks back in a way enforcing some amount of
> realism. It helps also to understand that in computer science, there are
> many theorems which are “machine independent” (to use the computer science
> terminology), and this means that the results concerns all programming
> language. That gives examples of general truth which are independent of the
> formalism and language used to express them.
>
> The reason is fundamental, and shows how much incompleteness by itself is
> an example where the mathematical, even the arithmetical, reality kicks
> back: quite a lot!
>
> I very often present the reasoning which follows. Sometimes my motivation
> for it is more limited, to “just” show that the Church-Turing thesis (CT)
> is …a thesis, to oppose those who sometimes defend the idea that CT is only
> a definition (of what is computable).
>
> Indeed, incompleteness is a direct consequence of CT.
>
> I need you to accept that not set S can have a subset SS with more element
> that itself. SS included in S implies that the cardinality of SS is smaller
> or equal than the cardinality of S. This is obvious, but with infinite set,
> we have to be careful. I will not prove this, and refer you to
> cantor-Bernstein Theorem, from which it follows “easily”.
> So, in particular, a subset of an enumerable set cannot be a non
> enumerable set. OK? I define a set S to be enumerable if it exists a
> bijection between S and N (N = the set of natural numbers).
>
> CT is the thesis that a function f from N to N is computable iff f is
> computable by an expression in their language (claimed to be universal:
> they both agree and have proven that their language are equivalent.
>
> *Theorem: CT entails Incompleteness*
>
> I need a lemma.
>
> Lemma: The set of finite words build on a finite alphabet is enumerable.
>
> Indeed, take a finite alphabet, like {a, b}, you can enumerate the set of
> all finite words by enumerating them simply by their length, and generate
> alphabetically the words which have the same length. On the alphabet {a,
> b}, you get in this way the bijection
>
> 0 ———————————— a
> 1 ———————————— b
> 2 ———————————— aa
> 3 ———————————— ab
> 4 ———————————— ba
> 5 ———————————— bb
> 6 ———————————— aaa
> 7 ———————————— aab
> …
>
> The same idea works for any finite set (alphabet), like a …z, aa, ab, …
> zz, aaa, aab, ...
>
> Imposing a syntax on the words, like in the alphabet {a, b, =}, would only
> diminish the number of words, and an’t augment the cardinality of the set
> (of all words on some finite alphabet). That ordering on finite alphabet is
> called the lexicographical ordering.
>
> By a (formal) language, I mean the given of an alphabet, and some easily
> checkable grammar. An expression is a grammatically correct word.
>
> Now it is easy to give an intuitive, informal definition of what is a
> computable function defined on N and with values in N.
>
> The idea is that a function from N to N is computable means that there is
> an expression, finite thus and written in some language, explaining how to
> compute its values in a finite time, with a finite result.
>
> That makes the set of computable functions from N to N being enumerable.
>
> Now, that looks eminently epistemological? Explaining to Who? How could we
> be sure that the functions computable in French are the same than the
> function computable by the English? They disagree already on the sign of 0.
>
> Here the idea is that we can decompose the explanation on elementary steps
> on which everyone agree that they are indeed quite simple.
>
> The question is, is there a universal language which expressions exist to
> compute all computable functions from N to N?
>
> CT asserts yes, and provides precise mathematical candidates.
>
> But even before betting on that answer, we can understand that IF such a
> universal language exists,* it will have to compute much more than the
> computable functions from N to N.* It will have to be able to compute
> also the functions defined only on subsets of N, and undefined out of that
> subset. And worse, the expressions denoting the computable function from N
> to N, will have to be ordered in a *necessarily non computable way* among
> the expressions in that universal language.
>
> Imagine (to make a reduction ad absurdum) that L is a universal language
> enumerating *only* the computable functions from N to N. We get a
> correspondence, maybe with repetition of the computable functions from N to
> N, by enumerating the grammatically correct expression.We get a computable
> bijection between N and the computable functions from N to N.
>
> Let us write f_n for the function from N to N computed by nth expression.
>
> Now, the function g defined by g(n) = f_n(n) + 1 is computable, and is
> defined on all N. So it is a computable function from N to N. It is
> computable because it each f_n is computable, “+ 1” is computable, and, vy
> our hypothesis it get all and only all computable functions from N to N.
>
> But then, g has have itself an expression in that universal language, of
> course. There there is a number k such that g = f_k. OK?
>
> But then we get that g_k, applied to k has to give f_k(k), as g = f_k, and
> f_k(k) + 1, by definition of g.
>
> So f_k(k) = f_k(k) +1.
>
> And f_k(k) has to be number, given that we were enumerating functions from
> N to N. So we can subtract f_k(k) on both sides, and we get 0 = 1. CQFD.
>
> If we keep our belief that a universal language exists, it has to compute
> other objects, and insert the expressions of the computable functions in a
> non computable way (if not you can filter out those other objects, and
> enumerate again only (but all) computable functions.
>
> Accepting that the universal language enumerates more than the functions
> from N to N saves the situation, the proof above, made on the phi_i (the
> enumeration of the mix of functions from N to N and functions from subset
> of N to N), shows only that the corresponding function “g” is such that
> g(k) = phi_k(k) = phi_k(k) + 1, and in this case it means that phi_k(k) is
> not defined, and g is not a function from N to N, but from a subset of N to
> N. No contradiction, and CT remains consistent.
>
> This means that, with CT, and thus with the mathematical definition of
> computable functions, obtained by CT, the set of computable functions,
> although enumerable, is not recursively or computably enumerable. Like for
> provability, you have the choice to stay in the “total” domains, with
> functions everywhere defined, and extends them in the (constructive)
> transfinite, or you can transcend it, but then the partial (defined only on
> subset) is mixed in a non computable way, with the total functions, and you
> are in front of the unknown: you get situation where you don’t know what
> the machine is computing.
>
> That shows that any theory capable of talking about those universal
> languages and their expressions are irremediably incomplete.
>
> Gödel’s incompleteness mainly uses this showing the Turing universality of
> elementary arithmetic, and indeed of the necessary partialness of the
> arithmetical provability predicate. This means tat the realism implied by
> CT applies to arithmetic. That is what Kleene has made explicit with its
> Kleene predicate.
>
> The truth about the behaviour of the expressions, that is the (halting or
> not) computations is far larger than what can be proved in any effective
> theory. Then, all this is true also for the machine with Oracles, and this
> makes possible to study mathematically the degrees of unsolvability of the
> problem in arithmetic, and in analysis (descriptive set theory).
>
> There is a bit of more work to prove the unsolvability of the halting
> problem, and indeed being the code of a total function is of a higher
> degree of unsolvability than the halting problem. I can do that another
> day.
>
> Gödel, with his own admission, missed CT. After accepting it, he called
> miracle the closure of the formalism of computability for the diagonal
> procedure, transforming the paradoxes into non stopping machine. The
> miracle is the immunity of the notion of computation for the diagonal
> procedure. It is a bit like a sort of God has to put those codes in a very
> complex way among the digital machines. (In fact the set of such codes is
> PI_2 complete, equivalent with qG).
>
> With Indexical Digital Mechanism, (YD + CT), we have a simple ontological
> realm (any model of any first order completely theory without induction
> axioms), and we get an explanation of why we will still need an infinity of
> axioms to get the internal phenomenologies, including the stable measurable
> sharable quanta appearances, and the non sharable first person singular
> qualia experiences.
>
> The digital mechanist thesis makes the dream argument rigorous, and
> constructive, and testable, and rather well confirmed by contemporary
> physics, up to now.
> Strictly speaking invoking a god or a “material universe" at this stage is
> a bit premature. With mechanism, this would be like invoking a precise
> universal number with a precise oracle, and is at the antipode, needless to
> say, of the original “everything” philosophy of this list (supposedly).
>
> Anyone can ask precision. Even what is a function. The beauty of this is
> that you dot need any sophisticated mathematics: only finite numbers and
> words, and elementary succession of simple action/relation.
>
>
> 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 view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/0782a943-8843-4926-b6b2-e5a34426926d%40googlegroups.com.
