Or take Russel's paradox. Either the barber does or doesn't shave himself -- that's all there is. How you describe it is an artificial construct.

Godel's theorem is like dividing by zero and declaring arithmetic incomplete.

It seems to me that all it means is, humans can construct artificial incomplete formal systems. You might as well assert that TRUE = FALSE and be amazed at the "paradox."

Is there some utility in believing that arithmetic is incomplete under pathological infinite recursion?

  • $\begingroup$ Well, I think most mathematicians would agree that there is some utility in understanding that mathematics cannot be axiomatized. To understand the utility, it might help to read some relevant history, e.g. plato.stanford.edu/entries/hilbert-program . One take-away was that to even come up with a consistent theory of sets, one had to somehow figure out how to understand and formalize what you point at with the term "pathological recursion". $\endgroup$
    – Neal Young
    Commented Mar 31 at 22:28
  • $\begingroup$ This question is not about computer science but about logic and foundations of mathematics. Please delete it here and ask it on math.stackexchange.com where it belongs. While you're at it, it would help if you explain why you think there is anything "pathological" in recursion. using an unexplained non-mathematical phrase like that just disqualifies your question as being about mathematics. $\endgroup$ Commented Mar 31 at 22:32
  • $\begingroup$ I'll just delete it; the hell with points. I speak lambda calculus as good as the next hacker, but you don't need it to convey the concept of a singularity due to nonterminating recursion involving a non-well-defined predicate. I'm not making it about terminology. That trivializes it. But I'll delete this, as I seem to be handling a social context fault interrupt again, and I hate it. I asked here because I associate incompleteness with redundant explainations of its brilliance in almost every CS class. $\endgroup$ Commented Apr 1 at 12:06
  • $\begingroup$ Oops, it won't let me delete it. oh well. i officially abandon it. $\endgroup$ Commented Apr 1 at 12:14
  • $\begingroup$ Hey, I was permanently banned from the logic stack xch for asking this exact same question. Is it any wonder that I avoid saying what are seemingly-normal things to non-autstics because they get inexplicably outraged? $\endgroup$ Commented Apr 1 at 12:23

1 Answer 1


Russell's paradox and incompleteness are two different things. I begin with your question regarding Russell's paradox.

Russell's paradox showed that a proposed set theory, proposed for the foundation of mathematics itself, contained a contradiction:

Let $R = \{x \mid x \notin x \}$, then $R \in R$ if and only if $R \notin R$.

From a contradiction, anything follows.

The main take-away here, was that any axiomatization of set theory containing unrestricted comprehension, must lead to a contradiction.

The (first) incompleteness theorem of Gödel, says

Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$.

It has great impacts on mathematical logic and philosophy.

It means that there are things in maths that are true, but that cannot be proved by any argument (inside that mathematical system).

  • $\begingroup$ I know Russell and Godel are different, but they both force a contradiction via pathological recursion. And the unrestricted axiom of comprehension asserts the existence of objects with any and every attribute you can think of, including contradictions. ("To every condition there corresponds a set of things meeting the condition"). That's just like asserting T = F and calling it a paradox. Russell/Godel seem like just an indirect way of asserting a contradiction. $\endgroup$ Commented Mar 31 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.