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":

$$g : \mathbb{N} \rightarrow \mathbb{R} :<br /> n \rightarrow \sum_{i = 0}^{n} f(i)$$

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:

$$\sum_{i=^*0}^H {}^*f(i) := {}^*g(H)$$

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:

$$\sum_{i=0}^{\infty} 2^{-i} \approx \sum_{i=^*0}^H (^*2)^{-i}$$

in the sense that their difference is infinitessimal.