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 everything-list+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/0782a943-8843-4926-b6b2-e5a34426926d%40googlegroups.com.
