blog POST

Does incompleteness implies undecidability ?



Incompleteness implies mechanical but not absolute undecidability.

For a statement-set to be incomplete is for there to be no recursion that generates it.

When there is no such recursion, it means that there isn’t a mechanical test for determining whether a given object belongs to that set, but it doesn’t mean that there isn’t some other way of making this determination.

The class of real numbers is incomplete, since, as Cantor proved, you can always construct a real number that is not in a given recursively defined number-set. But we can recognize real numbers when we come across them—we just don’t do so by applying recursions. In other words, we don’t do so mechanically.

The class of arithmetical truths is non-recursive, since, as Godel proved, we can always construct an arithmetical truth that does not belong to a given recursively defined class of such truths. We are able to recognize such a truth for what it is—but we don’t do so by applying recursions. In other words, we don’t do so mechanically.

0 views0 comments