Click here to return to the main page
DOI: 10.6084/m9.figshare.28457378
This paper, Avoiding the Paradoxes, is an offshoot of Gödel Incompleteness and Turing Completeness. Now I am applying the linguistic viewpoint of Gödel Incompleteness and Turing Completeness to set paradoxes and axiomatizations.
I have always thought that computing was the proper way of dealing with the paradoxes. In this I was influenced by Post (1936) and Gödel (1946).
As a working hypothesis, Post (1936) defended that Church’s thesis is a natural law stating the limitations of the mathematicizing power of Homo Sapiens (page 105, note 8). So we can define a Post universe as any universe where Post’s hypothesis is right. And if Post were right, then restricting ourselves to what is computable would be the proper way to deal with the paradoxes, and with everything else.
In that very same page 105, Post (1936) also states that his hypothesis is in apparent contradiction to all mathematical development starting with Cantor’s proof of the non-enumerability of the points of a line. This is because, if we restrict ourselves to computability, then every set is enumerable. In other words, some statements that are true in Cantor’s paradise are false in any Post universe, and conversely.
In the same direction, Gödel (1944) wrote:
Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing’s computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen. In all other cases treated previously, such as demonstrability or definability, one has been able to define them only relative to a given language, and for each individual language it is clear that the one thus obtained is not the one looked for. For the concept of computability, however, although it is merely a special kind of demonstrability or decidability, the situation is different. By a kind of miracle it is not necessary to distinguish orders, and the diagonal procedure does not lead outside the defined notion.
Regarding the diagonal procedure, when every set is, at most, infinite enumerable, there is no chance of going outside the diagonal procedure; in particular, the set of all finite strings is enumerable, and the set of all computable subsets of finite strings is enumerable, too, in apparent contradiction to Cantor's theorem. In trying to falsify this we could set a Cantor's diagonal procedure. A computable set is any expressed by a halting program, which either returns the empty string, interpreted as bit 0, meaning the the argument string does not belong to the set, or any other finite string, interpreted as bit 1, meaning the the argument string belongs to the set. Now, as the set of the halting programs and the set of finite strings drawn from a finite set of symbols are both computably enumerable, we can compute a bit matrix with a halting program for each row, and a string for each column, where the bit in row p and column s is 1 if string number s belongs to set number p, and is 0 otherwise. The diagonal procedure defines a set, let us name it X, by negating every bit on the diagonal of the matrix. To compute whether a string s belongs to set X or not, we first compute program number s on string number s, and then we switch the interpreted bits. Since this set X differs on at least one element from every set in the list, it seems that we have proved that the set of computable sets is not computably enumerable. However, as Gödel writes, by a kind of miracle this is not the case. Set X is not in the enumeration, this is true, but set X is not computable, although it could seem so, since we can compute whether any particular string belongs to it or not. Note that, if set X were computable, then it will be computed by a halting program in the enumeration, let us call it program number i. And then, to compute program number i on string number i, we would have first to compute program number i on string number i, in order to negate it. This would close an infinite loop. Therefore, since program number i would not always halt, it could not be in the enumeration of halting programs, and set X is not computable. Set X is computably enumerable, but it is not computable: Set X is undecidable.
And regarding orders, I think Gödel (1944) remarks that computing is self contained, because it can express itself. Each universal Turing machine defines a complete language that is expressive enough to express computing completely. And, because of this, in computing everything is a string of symbols. For example, a function is a string that the universal Turing machine interprets as a program, and its arguments are a string that the universal Turing machine splits into the individual arguments. But it is much more than that, as each argument is a string, the argument of a function can be a function, and so on and on. As Gödel said: By a kind of miracle it is not necessary to distinguish orders.
In opposition to computing, the theory of types mentioned by Scott (1974) distinguishes orders. Again, computing seems to be the proper way of dealing with the paradoxes, although, after writing Gödel Incompleteness and Turing Completeness, I came to realize that there is not any effective way of avoiding the paradoxes, not even computing.
However, I still prefer the inclusive way to the avoiding way. Though neither is effective, at least in the inclusive way one has to be ready to find paradoxes. Meanwhile, in the avoiding way, one is prone to forget the paradoxes, as if there were none. And, more important, inside the protecting wall of the avoiding way, one cannot see the proper instances that are being ignored only because they happen to be outside the wall. In other words, I find more misleading the too much clean avoiding way than the necessarily paradox-aware inclusive way.
The previous summary [there is not any effective way of avoiding the paradoxes] does not rely on the canonical ways, because the halting problem theorem applies to every computable way of dealing with the paradoxes, where computable equals effective under Church’s thesis. In any case, the conclusion is that, if we can define a paradoxical instance of a concept in an expressive language, then any avoiding way of dealing with that concept will be also avoiding some proper instances of it. Therefore, in particular, every paradox-free axiomatization of the concept set is incomplete.
There is not any effective way of avoiding the paradoxes. Therefore, in particular, every paradox-free axiomatization of the concept set is incomplete.
Link to the page of my paper on “Avoiding the Paradoxes” in figshare, and direct link to the pdf file.
These are the external references used in his page:
Versions:
Última actualización: 2025-03-06.
© Ramón Casares 2025