I Loophole in Godel's Incompleteness Theorem?

[Posty McPostface]

Gödel's incompleteness theorem only applies to logical languages with countable alphabets. So it does not rule out the possibility that one might be able to prove 'everything' in a language with an uncountable infinite alphabet.

Is that a loophole in Godel's Incompleteness Theorem?

Doesn't that imply that there can be monist conceptions of logic, and hence pluralism and instrumentalism are irrelevant or even invalid given that you could keep on expanding the countable alphabet up until infinity?

 

[andrewkirk]

Gödel's incompleteness theorem only applies to logical languages with countable alphabets. So it does not rule out the possibility that one might be able to prove 'everything' in a language with an uncountable infinite alphabet.

Is that a loophole in Godel's Incompleteness Theorem?

Doesn't that imply that there can be monist conceptions of logic, and hence pluralism and instrumentalism are irrelevant or even invalid given that you could keep on expanding the countable alphabet up until infinity?

An uncountable alphabet could not be used by humans, or by any finite beings, because it would require an infinitely long string of symbols we could recognise (eg numerals, letters, punctuation marks, kanji) just to denote a single symbol of the uncountable alphabet. So the only symbol string we could ever write or read in the uncountable alphabet would be the empty string.

Gödel, by making the alphabet countable, allows each symbol in the alphabet to be represented by a positive integer.

Also, note that 'countable' does not mean 'finite' as seems to be implied by the statement 'keep on expanding the countable alphabet up until infinity' in the above post. The set of positive integers is infinite but countable, and it is from that set that Gödel would draw the representations of symbols in the alphabet.

So no, not a loophole.

 

[Posty McPostface]

So the only symbol string we could ever write or read in the uncountable alphabet would be the empty string.

Could you please expand on that, if you don't mind?

 

[andrewkirk]

Could you please expand on that, if you don't mind?

Think about a real number that is an infinite, non-repeating decimal, and is not the solution of a rational polynomial (algebraic numbers) or a function of a particular named transcendental number such as pi or e.

The only way to specify such a number is by an infinite sequence of numerals after the decimal point. We can neither write nor read such a sequence. Yet it is only such numbers that make up the uncountable part of the uncountable set of real numbers. Let's call them the Unwritable Irrationals. The numbers that can be written by finite symbol strings - rationals, algebraics, functions of e or pi, trig or exponential transformations of rationals - form a countable set.

It is for this reason that some famous logician - I think it may have been Skolem - denied, or at least challenged, the existence of uncountable sets.

Similarly, if an alphabet is uncountable, we need some way to refer to each member of it, and the only way we can refer to an element of an uncountable set using the finite set of symbols we humans can recognise (letters, numerals etc) is by using an infinite sequence of such recognisable symbols, just like we imagine using an infinite sequence of numerals to refer to an Unwritable Irrational. But we can neither write nor read such a sequence.

But, that doesn't disprove the assumed 'loophole' in Godel's Incompleteness Theorems?

I'm not sure what you mean by a loophole. A theorem generally says that objects with a certain set of properties (premises) have a particular other property (conclusion). One of the premise properties of the Gödel theorem is that the language have a countable alphabet. So a language that has an uncountable alphabet is simply outside the scope of the theorem, not a loophole.

We don't say that Pythagoras's theorem has a loophole because it doesn't work for non-right-angled triangles. They are just outside its scope. [Fun fact - the generalisation of Pythagoras's Theorem to cover non-right-triangles is the Cosine Rule].

 

[Posty McPostface]

Thank you @andrewkirk , you've satisfied my curiosity. Any other members welcome to comment or add to what has been said, or even criticize it.

Thanks!

 

[stevendaryl]

Theories with uncountable languages are not very useful to us, but logicians have studied them. Whether Godel's theorem (or something like it) holds in them or not depends on the system.

The real issue is whether theoremhood is representable. You need two things:

1. A constant (or, which is just as good, a formula with one free variable such that the theory proves that only one element satisfies that formula) for every formula. That is, for every formula $\phi$, there is a corresponding constant $c_{\phi}$.
2. A formula $Th(x)$ representing theoremhood, in the sense that for any formula $\phi$, it is provable if and only if $Th(c_\phi)$ is provable.

If these two things hold, (and a few technical details about manipulation of formulas that have corresponding definable manipulations for the corresponding constants), then you will be able to come up with a formula $G$ such that $G$ is not provable, but the formalized statement $\neg Th(c_G)$ is also not provable. So the fact that $G$ is not provable is not provable, so the theory is incomplete.

I don't think that whether the language is countable or uncountable has much bearing on it, other than the fact that for countable languages, we can more directly constructable the theoremhood predicate $Th$.

An example of a theory that does not have a theoremhood predicate is true arithmetic: The set of all true statements of the language of arithmetic. In that theory, you can map every formula to a constant, but then there is no corresponding theoremhood predicate $Th(x)$. You can actually extend true arithmetic to have a theoremhood predicate, in which Godel's theorem applies and the extension is incomplete.

 

[rubi]

An uncountable alphabet would be of no use, since proofs are finite by definition and any (finite) proof that uses symbols from an uncountable alphabet can be recast into a proof that uses just a finite alphabet by replacing the finitely many symbols in the (finite) proof by symbols from the finite alphabet. A theory with an uncountable alphabet will prove exactly the same theorems as a theory with a countable alphabet.

 

[stevendaryl]

An uncountable alphabet would be of no use, since proofs are finite by definition and any (finite) proof that uses symbols from an uncountable alphabet can be recast into a proof that uses just a finite alphabet by replacing the finitely many symbols in the (finite) proof by symbols from the finite alphabet. A theory with an uncountable alphabet will prove exactly the same theorems as a theory with a countable alphabet.

Nobody ever suggested using an uncountable alphabet.

 

[rubi]

Nobody ever suggested using an uncountable alphabet.

The OP did in post #1:

Gödel's incompleteness theorem only applies to logical languages with countable alphabets. So it does not rule out the possibility that one might be able to prove 'everything' in a language with an uncountable infinite alphabet.

 

[stevendaryl]

The OP did in post #1:

I took that, not as a suggestion for what we should do, but as a purely mathematical question: If you generalize the notion of a language and a theory to allow for uncountably many symbols and uncountably many axioms, what are the consequences? Does Godel's theorem (or a generalization) still hold? That isn't a suggestion that WE should use an uncountable language.

 

[nomadreid]

As stevendaryl says in Post #6: [edited from my incorrect statement that no one had addressed this], the OP makes a false assumption in saying that the theorem only applies to logics with countable language. The theorem is valid for any system in which you can embed Peano Arithmetic. This would include a system with an uncountably infinitary language.
Oh, and such logics have been studied for quite some time (and not judged useless within mathematical logic): see, for example, https://plato.stanford.edu/entries/logic-infinitary/#1

 

[stevendaryl]

Something no one seems to have addressed: the OP makes a false assumption in saying that the theorem only applies to logics with countable language.

Why do you say "no one seems to have addressed [it]"? That's exactly what I said in post #6.

 

[nomadreid]

Oops, stevendaryl, my profound apologies. For some reason I scrolled too fast, and missed your post. I have edited my post accordingly. Or should I just delete it, to add to the confusion?

 

[rubi]

I took that, not as a suggestion for what we should do, but as a purely mathematical question: If you generalize the notion of a language and a theory to allow for uncountably many symbols and uncountably many axioms, what are the consequences? Does Godel's theorem (or a generalization) still hold? That isn't a suggestion that WE should use an uncountable language.

Well, I understood that he just wanted to enlarge to alphabet. However, if you also allow for uncountably many axioms (of finite length), this wouldn't change anything either, because we can again recast each of these axioms into an axiom expressed in a given countable alphabet, just by replacing symbols. The sentence $\forall\text{章} P(\text{章})$ is equivalent to $\forall x P(x)$ and there are only countably many possible sentences with symbols from a countable alphabet, so theories of this type don't give us anything new. New things happen if we allow for sentences of infinite length such as $P_1\land P_2\land\ldots$ with infinitely many conjunctions. That's what an infinitary logic would be.

 

[stevendaryl]

Well, I understood that he just wanted to enlarge to alphabet. However, if you also allow for uncountably many axioms (of finite length), this wouldn't change anything either, because we can again recast each of these axioms into an axiom expressed in a given countable alphabet, just by replacing symbols.

I don't know what you mean. Let's take a concrete example of a trivial theory with uncountably many symbols and axioms:

• For every real number $r$, there is a corresponding constant $c_r$.
• For every pair of real numbers $x,y$, if $x > y$ then there is an axiom $c_x > c_y$

That theory has an uncountable number of theorems. You can't get those by a countable alphabet.

 

[rubi]

I don't know what you mean. Let's take a concrete example of a trivial theory with uncountably many symbols and axioms:

• For every real number $r$, there is a corresponding constant $c_r$.
• For every pair of real numbers $x,y$, if $x > y$ then there is an axiom $c_x > c_y$

That theory has an uncountable number of theorems. You can't get those by a countable alphabet.

Well, now you're considering yet another class of theories. Unless stated otherwise, I understand a theory to have finitely many relation and function symbols. I understood the alphabet to be the set, where the variable symbols are drawn from.

 

[nomadreid]

Unless stated otherwise, I understand a theory to have finitely many relation and function symbols.

Why?

 

[andrewkirk]

the OP makes a false assumption in saying that the theorem only applies to logics with countable language.

The proof of the First Incompleteness Theorem with which I am familiar, which is this one, includes the countability of the language in its premise and uses it critically in the proof. Countability is necessary to be able to create the Godel numbering system, which is an injection from the set of all wffs in the language to the natuiral numbers. Without Godel numbering there is no diagonalisation and without diagonalisation there is no proof of the existence of an undecidable sentence.

I would be very interested, and surprised, to see a proof of the theorem that does not rely on countability of the language. It seems from the above discussion that there may be later extensions of Godel's theorem to uncountable languages that have some lesser restrictions. But my understanding is that Godel's original theorem, and proof, only applied to countable languages.

Well, now you're considering yet another class of theories. Unless stated otherwise, I understand a theory to have finitely many relation and function symbols.

The version Steven gave only used only one relation symbol (<) and no function symbols. It had uncountably many constant symbols, but that's a different thing (unless we take the approach that is sometimes taken of regarding a constant as a 0-ary function).

 

[stevendaryl]

Well, now you're considering yet another class of theories. Unless stated otherwise, I understand a theory to have finitely many relation and function symbols. I understood the alphabet to be the set, where the variable symbols are drawn from.

Oh, yeah. Certainly having countably many variables is sufficient for anything. But if you're going to generalize the notion of a countable language, I would think you would allow uncountably many constant, function and/or relation symbols.

 

[stevendaryl]

But what is true is that for proving facts about arithmetic (the usual language of +, *, 0, 1, =), it doesn't help to have uncountably many axioms.

 

[rubi]

Why?

Probably because it's defined this way in standard textbooks. Of course one can generalize it (and sometimes that's even useful in model theory). If the OP wanted to find a loophole in the incompleteness theorem, he can't just add symbols and new axioms, because then it wouldn't be standard arithmetic anymore, so I was assuming that he just wanted to allow for new variable symbols and leave everything else as is.

 

[nomadreid]

andrewkirk: the short answer: you are correct that I meant an extension , or perhaps one should say a corollary .
The long answer: you are correct that Gödel's original theorem was crafted based on a countable system, although, in the same vein, you are not correct in saying that it applied to (only) countable languages in general -- it was specifically applied to the system of arithmetic set up by Whitehead and Russell. In fact, the original proof did not explicitly use the diagonal lemma; it was Carnap who made it explicit. Anyway, when I wrote that the theorem applied to systems in which PA could be embedded, I did not mean that the proof used these systems, but that the result, the incompleteness, also for other systems than Whitehead and Russell was then established. In fact, the strengthening of the theorem into the Gödel-Rosser theorem is often simply referred to as Gödel's First Incompleteness Theorem, and in https://plato.stanford.edu/entries/goedel-incompleteness/#FirInc, the, the statement of the theorem starts "Assume F is a formalized system which contains Robinson arithmetic Q." In other words, historically you are correct, but in common parlance one often uses the extended versions. And yes, the countability is necessary for Gödel numbering, but as long as part of the system is countable... which, of course, is the case for uncountable systems... the extensions/corollaries/commonly-used-versions go ahead.

 

[nomadreid]

Unless stated otherwise, I understand a theory to have finitely many relation and function symbols. I understood the alphabet to be the set, where the variable symbols are drawn from.

Why?

Probably because it's defined this way in standard textbooks.

Ah,dusting off my old copy of Chang & Kiesler (Model Theory), I find absolutely no restriction to the cardinality of the set of relation and function symbols (and of course none on the cardinality of the set of variables and constant symbols.) Perhaps you are thinking of the restriction, unless otherwise stated, that a sentence should be of finite length.

I understood the alphabet to be the set, where the variable symbols are drawn from.

The alphabet, or rather the language, is the union of all these sets (constant symbols, variables, function symbols, relation symbols) , not just of the variables .

 

[rubi]

Ah,dusting off my old copy of Chang & Kiesler (Model Theory), I find absolutely no restriction to the cardinality of the set of relation and function symbols (and of course none on the cardinality of the set of variables and constant symbols.)

Well, it's a model theory book and allowing for uncountable alphabets can be very useful in model theory. When I wrote that, I was thinking of Ebbinghaus, Flum and Thomas, but in fact, they just restrict to countable alphabets for most of the book. The reason for such a restriction is that if you are a formalist and want to think of logic as the foundation of mathematics rather than just an object of mathematical study, you only have finitistic syntax at first. Only then can you propose something like a set theory, wherein you can do all the nice things like writing down theories with uncountably many symbols and axioms and study models. You can't do this in the metalanguage. But anyway, we're drifting off.

 

[nomadreid]

But anyway, we're drifting off.

Right, in fact the OP said that he/she was satisfied already by Post #4...