Extensions of Godel's Theorem

  • #1
1,569
2

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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:NR, 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.
 

Related Threads on Extensions of Godel's Theorem

  • Last Post
2
Replies
38
Views
11K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
18
Views
5K
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
4K
Replies
24
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
Top