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) defends 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 (1946) 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, though Cantor had showed that the real numbers cannot be enumerated using the diagonal procedure, Turing showed that the computable real numbers are enumerable, in spite of the diagonal procedure!
Minsky (1967), page 159, defines “a computable number to be one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number.” Since each Turing machine can generate at most one computable real number and the set of all Turing machines is computably enumerable, then the set of all computable real numbers is computably enumerable. However, given that Turing machines are computably enumerable, we can replicate Cantor's matrix of rows of real numbers (and colunms of digits) setting one Turing machine in each row (and one digit in each column). Changing the digits in the diagonal of this new matrix we would get a computable real number that is not in any row of the matrix, thus showing that the computable real numbers are not enumerable. However, this does not work! Why? Because not every Turing machine generates a computable real number, but only those that halt on every input, and the set of always halting Turing machines is not computably enumerable.
And regarding orders, I think Gödel (1946) 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 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:
Last update: 2025-07-18.
© Ramón Casares 2025