The n-Category Café

Gödel’s own explanation for incompleteness was given in his 1931 article:

… [T]he true reason for the incompleteness inherent in all formal systems of mathematics is that the formation of higher types can be continued into the transfinite … while in any formal system at most denumerably many of them are available. For it can be shown that the undecidable propostions constructed here become decidable whenever higher types are added (e.g., of type $\omega$ for the system P). An analogous situation prevails for the axiom system of set theory. (Gödel’s 1931, “On Formally Undecidable Propositions …”, footnote 48a.)

Gödel almost certainly knew by then that “the undecidable propositions … become decidable whenever higher types are added” because the relevant truth definition can be given when the higher types are added.

The other reference by Gödel to the “true reason” for incompleteness that I know of occurs in a letter to AW Burks, published in 1966 - where Gödel explained that the “true reason” for the incompleteness of formal systems is the undefinability of truth:

… the theorem of mine that von Neumann refers to is … the fact that a complete epistemological description of a language A cannot be given in the same language A, because the concept of truth of sentences in A cannot be defined in A. It is this theorem which is the true reason for the existence of undecidable proposotions containing arithmetic. (Gödel, letter to A.W. Burks, published in 1966.)

Alfred Tarski made a similar point in the Postscript to his 1936 article “The Concept of Truth in Formalized Languages”:

All sentences constructed according to Gödel’s method possess the property that it can be established whether they are true or false on the basis of the metatheory of higher order having a correct definition of truth. (Tarski 1936, p. 274)

John wrote:

I think I’ve also heard it said that ‘most’ statements in arithmetic are undecidable in PA, but right now I’m having trouble remembering any precise theorem to that effect. (Is it even true in any sense?)

Jeffrey wrote:

Yes. The set of non-theorems of PA is not r.e..

Yes. I don’t think this fact has any easy consequences for the question I asked, which concerned the density of the undecidable sentences as a subset of all the sentences of PA.

For example, looking at subsets of $\mathbb{N}$, I think I can cook up subsets $S \subseteq \mathbb{N}$ such that neither $S$ nor $S^c$ are recursively enumerable and such that $S$ has very low density, e.g.:

$$\lim_{n \to \infty} \displaystyle{ \frac{ | S \cap \{1, \dots, n\} | }{n} = 0 }$$

Simply take a set $X \subseteq \mathbb{N}$ such that neither $X$ nor $X^c$ is recursively enumerable, and say that $n \in S$ iff $n = 2^k$ and $k \in X$.

David Speyer has just shown that if $T_n$ is the set of theorems of PA that are strings of $n$ symbols, while $S_n$ is the set of sentences in the language of arithmetic that are strings of $n$ symbols, we have

$${\lim \, \sup} \; \displaystyle{\frac{|T_n|}{|S_n|} \; \gt \; 0 }$$

This eliminates one possible sense in which ‘almost all’ sentences are unprovable.

But I still believe a lot of sentences are undecidable. So, if $U_n$ is the set of sentences with $n$ symbols that are neither provable nor disprovable in PA, I believe that

$${\lim \, \sup} \; \displaystyle{\frac{|U_n|}{|S_n|} \; \gt \; 0 }$$

This would be nice to show.

Since $F(n) \leq L^n$, we must have $F(n+6) \leq L^6 F(n)$ infinitely often, so that gives that the limsup is greater than $L^{-6}$.

To say something about the liminf, we need to know something about our grammar. (For example, if all grammatical sentences have length $0 \mod 5$, it won’t be true, but then tagging on $\vee (0=0)$ isn’t grammatical.)

If our language is an unambiguous context free grammar, then the Chomsky–Sch¼tzenberger enumeration theorem tells us that $\sum_n F(n) z^n$ is an algebraic function of $z$. We should be able to use standard methods for computing asymptotics of power series coefficients to get $F(n) \sim \chi(n) n^{\alpha}/r^n$ where $r$ is the radius of convergence, $\alpha$ is a real number encoding the order of the branching/poles at the boundary and $\chi(n)$ is of the form $\sum_{j=1}^m a_j \exp(i n \theta_j)$ for some real $\theta_j$ (so quasi-periodic). That quasi-periodic function is a nuisance, but I think I can wipe it out given a bit more thought and using that $F(n+6) \geq F(n)$.

You might find the variant of ZFC, called NBG (von Neumann Bernays Goedel) class theory, usually with the axiom of choice like ZFC, convenient. Then we have the actual class of all finite sets = class of all finite classes. See, for you, conveniently, the finite classes are exactly the finite sets.

Well, there should be a contemporary philosophical literature on “foundations of X” but I think there isn’t, at least not a sufficiently interesting one.

One reason may be that there really aren’t good successful examples of X’s which have been given a good foundations. Although often the word “foundations” is meant in a comparatively limited informal sense, where it is difficult to codify. Like “important basic information before we really do something interesting and important”.

That’s of course not the sense in which I mean “foundations for mathematics”.

In real foundations, you expect to have

1. A philosophically coherent description of the concepts of X that are going to be taken as undefined - i.e., as primitive, from which all other concepts are going to be defined.

2. A listing of fundamental facts involving the primitives in 1 which are to be taken for granted and not derived. There should be a philosophically coherent justification given for these fundamental facts. Of course, this is going to fall short of a proof of these facts, otherwise they would be replaced by facts yet more fundamental.

3. A philosophically coherent description of how inferences are to proceed. Of course, the universal default is the famous FOL=.

4. A recasting of a representative sampling of fundamental developments in X in accordance with 1-3, as a test that one has sufficiently captured the essence of X, at least methodologically. In the case of math, ZFC doesn’t do anything with mathematical intuition, mental pictures, formulation of problems and conjectures, etcetera. But it does deal with the formulation of definitions, statements, and presentation of rigorous proofs.

I am completely open to the possibility that there might be genuine foundations which does not take the above exact form 1-4, or maybe some totally new idea of what a foundation is. But the standards for doing that are very high, and the standards for a totally new idea of what a foundation is has to be very very very high.

In particular, ZFC is totally inadequate to deal with quite a number of important mathematical matters, e.g., mental pictures. You can’t even do deep math without having clear mental pictures.

However, there is no chance that anybody is going to do a serious foundation of mental mathematical pictures without incorporating all of the standard f.o.m. that we know, and much more. After all, ZFC itself is based on a reasonably clear mental mathematical picture, and a very powerful and effective one indeed.

I appreciate your response. It’s interesting.

You might find the variant of ZFC, called NBG (von Neumann Bernays Goedel) class theory, usually with the axiom of choice like ZFC, convenient.

Thank you for mentioning NBG. I agree that there are category theory books that try to work within that system. To me it doesn’t feel natural that there only two sorts of collections: sets and proper classes. In the context of category theory it feels more natural to keep taking collections of collections. And after one step or two of doing this, NBG is no better than ZFC.

At some point of my life I was unhappy about this and kept wishing for better foundations than NBG. Your reply makes me think that this is not coming any time soon.

Eugene wrote:

To me it doesn’t feel natural that there only two sorts of collections: sets and proper classes. In the context of category theory it feels more natural to keep taking collections of collections. And after one step or two of doing this, NBG is no better than ZFC.

Of course — I’ll say this just in case someone doesn’t know — category theorists usually deal with this problem using ZFC plus the axiom of universes. A Grothendieck universe is roughly a set $U$ of sets that serves as a model of ZFC, so we can act like it’s ‘the’ universe of ‘all’ sets. The axiom of universes says that every set is in some universe.

This gives us a universe $U_0$, a bigger universe $U_1$ containing $U_0$, an even bigger universe $U_2$ containing $U_1$, and so on. We can say sets in $U_0$ are ‘small’, sets in $U_1$ are ‘large’, sets in $U_2$ are ‘2-large’, etc..

There is then an $(n+1)$-large category of all $n$-large categories, and we’re good to go!

It almost always doesn’t require much thought: you just carry around $n$ as an adjustable parameter (since its value doesn’t affect any interesting theorems in category theory), and increment it by 1 each time you need to say “the category of all the categories we’ve been talking about so far”.

By the way, the existence of a universe (or let’s say an uncountable universe, since some wimps allow the empty set to be a universe, or certain other countable sets) is equivalent to the existence of a strongly inaccessible cardinal. This is almost obvious; they are closely connected ideas.

Speaking of Grothendieck and his axiom of universes, this is a nice summary of Colin McLarty’s work on the axiomatic underpinning’s of Fermat’s Last Theorem:

• Julie Rehmeyer, A mathematician puts Fermat’s Last Theorem on an axiomatic diet, Science News, February 20, 2013.

I’ll quote a chunk:

When Wiles finally proved the theorem in 1994, he used a deep connection between Fermat’s Last Theorem and algebraic geometry, a field in its infancy in Fermat’s time. Modern algebraic geometry was built using extraordinarily powerful tools developed in the mid-20th century by the mathematician Alexander Grothendieck that rely on an extra axiom in addition to those of standard mathematics — so Wiles’ proof did too.

Grothendieck introduced the axiom to deal with a pesky logical problem. His tools got much of their power through being extremely abstract. For example, instead of just considering the set of all whole numbers, Grothendieck also included the spaces defined by equations of whole numbers. (Think, for example, of the circles and parabolas and ellipses defined by equations in two variables). Then he threw in the set of all functions between such spaces, and so on, with one set building on another.

Set theory (that is, the standard axioms of mathematics) puts limits on how far this process can go. For example, there is no set of all sets, because a set of all sets would lead to logical difficulties like the famous Russell paradox: Imagine the set whose elements are precisely those sets that don’t contain themselves. Does it contain itself? Prepare yourself for some brain-twisting here: The answer can’t be yes, because then by its own definition it’s a set that doesn’t contain itself. But the answer can’t be no, either: If the set doesn’t contain itself, then it satisfies its own definition, so it does contain itself. Damned if you do, damned if you don’t!

With his sets built on sets built on sets, Grothendieck wanted to go into territory perilously close to this. So he created a new axiom that would allow him to use these very large sets of sets of sets while still keeping clear of paradox. This axiom posited the existence of a larger type of set called a “universe.” Grothendieck’s approach was fabulously successful, allowing him to prove one major theorem after another and laying the groundwork for modern algebraic geometry, among other fields — all leading to the remarkable success of the proof of Fermat’s Last Theorem. But all this work relies on the axiom of universes. “Everyone sees that this is a quick and dirty fix,” says Colin McLarty of Case Western Reserve University in Cleveland. “But it works.”

Intuitively, many mathematicians thought Grothendieck didn’t need his fancy universes. Ordinary set theory seemed like it should suffice — or even less. In particular, set theory involves axioms about infinity that seem unnecessary for something like Fermat’s Last Theorem, which involves only finite whole numbers. But no one had proved it until now. McLarty recently showed that Fermat’s Last Theorem can be proven using the ordinary axioms of mathematics, and even a bit less. He presented his results at the Joint Mathematics Meetings in San Diego in January.

“This justifies a feeling that lots of people had and I had too,” McLarty says. McLarty showed that a subset of set theory called finite-order arithmetic, which assumes less about the concept of infinity, is sufficient to undergird Grothendieck’s work.

“This is a well-done, major, clarifying first step,” says Harvey Friedman of Ohio State University. Friedman believes the work could be extended to show that Fermat’s Last Theorem requires only axioms relevant to arithmetic, with no use of infinity at all.

The real thing is here:

• Colin McLarty, What does it take to prove Fermat’s Last Theorem? Grothendieck and the logic of number theory.

“However, it seems to me that there is an important level of “practical/mathematical foundations for mathematics” that is purely mathematical, and can be recognized for what it is without needing any philosophical support. Maybe you would prefer that the word “foundations” not appear in the name of such a thing. That ship may have sailed; but I would be curious to know what name you would prefer to use for this level?”

Framework.

algebraic topology framework categorical framework algebraic geometry framework …