How Do Nonstandard Models of Arithmetic Impact Godel's Theorem Extensions?

[phoenixthoth]

From what I understand of one of Godel's incompleteness theorems, it involves coding wffs into numbers. Each wff corresponds to a Godel number and each Godel number gives rise to a wff. And then by using a kind of logical isomorphism between the set of wffs and N, incompleteness of any "adequate" theory is implied by the fact that computability implies definability.

Is that basically right?

Assuming it is... Here's my question. We use arithmetic to encode formulas. What if we used a nonstandard model of arithmetic or some other poset to encode wffs? What kind of results do we get, for instance, something about infinitary logic if our model of arithmetic has unlimited numbers that could correspond to an infinite string of OR or AND?

Thanks.

 

[Hurkyl]

Eww, nonstandard formal logic?

Well, we still have the transfer principle. We can write down a first-order theory that includes formal logic and the integers. Presumably, Gödel's theorem couldn't even be stated within the theory, but can be proven about the theory.

Then, we could take a nonstandard model of this theory, and we will indeed have logical statements with infinitely many terms, and we will also have the hypernatural numbers, and I presume we would still be able to prove Gödel's theorem.

Now, we don't get just any old infinitary logic when we do this, we get a very specific one. I can demomstrate the limitations I would expect to see with an example from nonstandard analysis: the infinite sum.


In standard analysis, we look at a sequence of partial sums. For a given sequence f:N→R, we can define a "finite sum function":

[tex]
g : \mathbb{N} \rightarrow \mathbb{R} :
n \rightarrow \sum_{i = 0}^{n} f(i)
[/tex]

So, by the transfer principle, we have the function *g : *N → *R. Through this way, we are able to define, for a transfinite hypernatural number H, the infinite sum:

[tex]
\sum_{i=^*0}^H {}^*f(i) := {}^*g(H)
[/tex]

The point is that we don't get just any infinite sum: we only get sums of internal functions indexed by intervals of hypernatural numbers.

For example, we don't get the sum 1 + 1/2 + 1/4 + 1/8 + ... + 1/2^n + ... where n ranges over the ordinary naturals.

Though, we do know that, for any transfinite hypernatural H:

[tex]
\sum_{i=0}^{\infty} 2^{-i} \approx \sum_{i=^*0}^H (^*2)^{-i}
[/tex]

in the sense that their difference is infinitessimal.

 

[tacman]

Your understanding of Godel's incompleteness theorems is correct. The coding of wffs into numbers and the use of logical isomorphism between the set of wffs and N is a fundamental part of Godel's work. However, your question about using a nonstandard model of arithmetic to encode wffs is an interesting one.

There have been some extensions of Godel's theorem that explore the implications of using nonstandard models of arithmetic. One such extension is the "Godel's Second Incompleteness Theorem for Nonstandard Models", which states that if a nonstandard model of arithmetic satisfies certain properties, then it too will be incomplete. This result suggests that the incompleteness of adequate theories is not limited to standard models of arithmetic, but can also occur in nonstandard models.

Another interesting result is the "Godel's Completeness Theorem for Nonstandard Models", which shows that if a nonstandard model of arithmetic satisfies certain properties, then it will also be complete. This result suggests that the completeness of theories is not limited to standard models of arithmetic, but can also occur in nonstandard models.

In terms of your question about using nonstandard models to encode wffs, there have been some investigations into the implications for infinitary logic. For example, in nonstandard models with unlimited numbers, it has been shown that infinitary logic can be used to express certain statements that are not expressible in standard models. This suggests that nonstandard models can provide a richer framework for expressing logical concepts.

Overall, the extensions of Godel's theorem to nonstandard models of arithmetic have opened up new avenues for exploring the limits of logical systems and the implications for theories in mathematics and other fields. These extensions continue to be an active area of research and have led to many interesting results and insights.