## More on Gödel, Structuralism, and Machines

4 06 2005

I was just talking to Fabrizio Cariani (one of the other students in my program here) about my earlier post on a version of structuralism that treats elementarily equivalent structures as the same, rather than just isomorphic ones. But he pointed out that although this would avoid the problems of the Löwenheim-Skolem theorems, it still wouldn’t avoid the problem of Gödel’s incompleteness theoresm. That is, we need to have a complete theory to specify a structure completely in this sense, but Gödel’s incompleteness theorems show that no recursive theory extending Peano arithmetic or ZFC is complete, so we can’t even pin down the natural numbers or the sets to this extent. It’s sort of nice that the platonist account of mathematical objects runs afoul of isomorphic models, the standard structuralist account runs afoul of the Löwenheim-Skolem theorems, and the “elementary equivalence structuralist” account runs afoul of the Gödel theorems.

Fabrizio had been thinking about this because he had just been looking at the result that there are continuum-many non-equivalent countable models of PA. This is because for any recursive, consistent theory T extending PA, Gödel shows that T+Con(T) and T+~Con(T) are both recursive, consistent theories extending PA. Thus, there is a complete binary tree of such theories, and by the compactness theorem, each infinitary branch of the tree is a consistent theory extending PA. Since any two such branches differ at some stage over whether they add Con(T) or ~Con(T), the models of the theories are going to be non-equivalent, so there are continuum many non-isomorphic models. (This is also the theoretical upper bound on the number of countable models for any theory in a finite language, because there are only countably many objects and tuples of objects, and for each of the finitely many predicates and relations in the language, there are two choices for each tuple of the appropriate size.)

Now, returning to yesterday’s post on mechanism, I think Lewis’ point is stronger than I had thought originally. In the comments, Peter McB suggests that there is a machine that takes any consistent, recursive theory T extending PA and outputs the sentence Con(T). Now that I think about it, I think the procedure Gödel himself used is amenable to this sort of recursive construction. Now, for any countable string of 0’s and 1’s, we can use this machine to recursively enumerate an axiomatization for some consistent extension of PA, by letting T_0 be PA, and using the machine to enumerate the axioms Con(T_i) or ~Con(T_i), depending on whether the ith bit of the string is 1 or 0. The fact that these enumerations are recursive in the string doesn’t violate Gödel’s theorem, because it just means that the theory PA + Con(PA) + Con(PA+Con(PA)) + … is itself not a complete theory. And similarly for the theory PA + ~Con(PA) + ~Con(PA+~Con(PA)) + …, and so on for any other theory given by some recursive string of 0’s and 1’s.

Now, it seems intuitive to me that no such theory is going to be complete, but Gödel’s theorem only tells us that the ones produced by recursive strings of 0’s and 1’s aren’t complete. Is it possible that some non-recursive string of 0’s and 1’s gives a complete theory? That would be weird. I suppose recursion theorists might have a better idea about this.