I haven’t forgotten this debate, but I also still haven’t got my computer set up at home. It might be a couple days before I can do any serious posting at home.
FWIW, one of my professors at school told me that Solomon Fefferman (I think that’s how you spell his last name) came up with a formulation of consistency that could be proved inside of number theory, but he wasn’t able to find the paper. I’ll see if I can find it, but again, it might be a little while.
Sounds like it’s all well worth the wait, Ultra.
Hey, just a quick update to let you guys know that I’m set up at home now. I’m gonna sit down for a little while tonight to see what all I need to explain, and I’ll go from there. I’ll try to have it all posted by tomorrow evening, but I’m not making any promises.
All right, I’m gonna give this a shot. What I’m presenting is a modern statement of the Gödel-Rosser theorem, a generalization of Gödel’s original theorem (more on this later). I’ll begin with a basic set of symbols, state the theorem, and go into detail as to what the conditions mean. In all that follows, all lower-case variables represent non-negative integers. Italic capital letters (like G) will denote sentences. Capital letters (like K) will denote theories. Of course, any exceptions will be noted.
I think we all know that ’ denotes the successor function (i.e., 0’ is the successor of zero). What the successor function is not specified, it just has to be defined for zero. n is used to denote the nth successor of zero.
Symbols
We say x < y if there is a number z such that x + z = y.
|–[sub]K[/sub] G means that there is a proof in theory K of the sentence G.
Lastly, != will be used to mean “not equal to”. I imagine everyone knows that, but I just thought I’d throw it out for clarity.
And just for ease of my typing, V will represent the logical “or”.
Universal quantifiers on free variables will be assumed. This is a standard convention among logicians.
The Theorem
So here are the conditions for the Gödel-Rosser theorem. Let K be a theory with equality in the language L[sub]A[/sub] that satisfies the following:[ol][li] K has a recursive axiom set.[/li][li] |–[sub]K[/sub] 0 != 1.[/li][li] Every recursive function is representable in K.[/li][li] |–[sub]K[/sub] x < n [symbol]®[/symbol] x = 0 V x = 1 V … V x = n[/li][li] |–[sub]K[/sub] x < n V n < x[/ol]Then, if K is consistent, an undecidable sentence R exists in K.[/li]
Initial explanations
All right, so there’s a lot of jargon in there. Where to begin? I’m not going to go into all the detail, just enough that you can do something with that statement other than stare at it googly-eyed.
A theory with equality is just a theory that has a predicate “=” which is reflexive, symmetric, and transitive. There’s that.
L[sub]A[/sub] is the language of arithmetic. It has the predicate “=”, the constant 0, the successor function, and functions for addition and multiplication (not necessary, but what the heck, we’ll use 'em). And that’s all you can talk about.
I’ve already explained what “consistent” means, but just for ease of reading, a theory is consistent if there is some sentence which is not a theorem of that theory.
Condition 1
K has a recursive axiom set iff the function Pr: N -> 2 defined as Pr(y) = “y is the Gödel number of a proper axiom of K” is recursive. A proper axiom is one that the theory has in addition to the basic axioms of predicate calculus (which could be any old axiom, if you take the right formulation of predicate calculus). I’ll write about recursive functions later–look it up on Mathworld if you like, but realize that they use a slightly different definition from the one I use. I think they’re equivalent, but I haven’t shown that.
Condition 2
I think we’re good on this. Let me know if we’re not.
Condition 3
A recursive function f of n functions is representable in a theory K iff there’s a wff (sentences are wff’s with no free variables) B(x[sub]1[/sub], …, x[sub]n[/sub], y) such that[ol][li] If f(k[sub]1[/sub], …, k[sub]n[/sub]) = m, then B(k[sub]1[/sub], …, k[sub]n[/sub], m)[/li][li] |–[sub]K[/sub] ([symbol][/symbol][sub]1[/sub]y)*B*(k[sub]1[/sub], ..., k[sub]n[/sub], y)[/ol]The subscripted existential quantifier ([symbol][/symbol][sub]1[/sub]y) means “there exist exactly n distinct y’s such that…”[/li]
Condition 4
Pretty self-evident, I hope.
Condition 5
Again, this should be pretty straightforward.
I think that’s all I’m gonna do tonight. By my count, all I’ve got left to do is explain what a recursive function is, and explain why the Gödel-Rosser theorem is more general than Gödel’s original theorem. Let me know if there’s anything else I need to do, and I’ll get to it tomorrow.
Oh, I should mention that I’m taking all this from E. Mendelson’s Introduction to Mathematical Logic, 4e.
Oops, had to correct a typo there. This should read “The subscripted existential quantifier ([symbol]$[/symbol][sub]n[/sub]y) means “there exist exactly n distinct y’s such that…””
All right, recursive functions. This is pretty simple, I just got tired last night.
First, I need to mention, again, that all variables are non-negative integers, and in this case, the output of every function is also a non-negative integer.
btw, I say “non-negative” integer instead of “natural number” because there’s no convention as to whether zero is a natural number, and I need it.
Initial functions
The following functions are taken to be recursive:[ol][li] The zero function, Z(x) = 0.[/li][li] The successor function, N(x) = x + 1.[/li][li] The projection function, U[sub]n, j[/sub](x[sub]1[/sub], …, x[sub]n[/sub]) = x[sub]j[/sub].[/ol]Note that I’m giving the definitions of these functions, not their representations in the language of arithmetic.[/li]
Substitution
Let g(x[sub]1[/sub], …, x[sub]m[/sub]) be recursive, and let h[sub]i[/sub](x[sub]1[/sub], …, x[sub]n[/sub]) be recursive for 1 < i < m. Then f(x[sub]1[/sub], …, x[sub]n[/sub]) = g(h[sub]1[/sub](x[sub]1[/sub], …, x[sub]n[/sub]), …, h[sub]m[/sub](x[sub]1[/sub], …, x[sub]n[/sub])) is also recursive. Note that a given h[sub]i[/sub] may be constant with respect to one or more variables.
Recursion
Define f(x[sub]1[/sub], …, x[sub]n[/sub], k) as follows:[ol][li]f(x[sub]1[/sub], …, x[sub]n[/sub], 0) = g(x[sub]1[/sub], …, x[sub]n[/sub])[/li][li]f(x[sub]1[/sub], …, x[sub]n[/sub], y + 1) = h(x[sub]1[/sub], …, x[sub]n[/sub], y, f(x[sub]1[/sub], …, x[sub]n[/sub], y))[/ol]If g and h are recursive, then f is recursive as well. Note that n may be equal to zero in this case.[/li]
The Restricted [symbol]m[/symbol]-Operator
Let g(x[sub]1[/sub], …, x[sub]n[/sub], y) be a function such that, for any values of the x[sub]i[/sub]'s, there is a y such that g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0. [symbol]m[/symbol]y(g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0) is the least y such that g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0.
A function obtained without use of the restricted [symbol]m[/symbol]-operator is called primitive recursive. Otherwise, it’s known as just recursive. There are functions which are recursive but not primitive recursive; Ackerman’s function is the simplest known example.
You can take a recursive function and add dummy variables, permute the variables, or set two of them equal (e.g., f(x, y) = g(y, x, y)), and you’ll get a recursive function.
That seems like enough for now. Later, I’ll talk about the difference between consistency and [symbol]w[/symbol]-consistency.
All right, recursive functions. This is pretty simple, I just got tired last night.
First, I need to mention, again, that all variables are non-negative integers, and in this case, the output of every function is also a non-negative integer.
btw, I say “non-negative” integer instead of “natural number” because there’s no convention as to whether zero is a natural number, and I need it.
Initial functions
The following functions are taken to be recursive:[ol][li] The zero function, Z(x) = 0.[/li][li] The successor function, N(x) = x + 1.[/li][li] The projection function, U[sub]n, j[/sub](x[sub]1[/sub], …, x[sub]n[/sub]) = x[sub]j[/sub].[/ol]Note that I’m giving the definitions of these functions, not their representations in the language of arithmetic.[/li]
Substitution
Let g(x[sub]1[/sub], …, x[sub]m[/sub]) be recursive, and let h[sub]i[/sub](x[sub]1[/sub], …, x[sub]n[/sub]) be recursive for 1 < i < m. Then f(x[sub]1[/sub], …, x[sub]n[/sub]) = g(h[sub]1[/sub](x[sub]1[/sub], …, x[sub]n[/sub]), …, h[sub]m[/sub](x[sub]1[/sub], …, x[sub]n[/sub])) is also recursive. Note that a given h[sub]i[/sub] may be constant with respect to one or more variables.
Recursion
Define f(x[sub]1[/sub], …, x[sub]n[/sub], k) as follows:[ol][li]f(x[sub]1[/sub], …, x[sub]n[/sub], 0) = g(x[sub]1[/sub], …, x[sub]n[/sub])[/li][li]f(x[sub]1[/sub], …, x[sub]n[/sub], y + 1) = h(x[sub]1[/sub], …, x[sub]n[/sub], y, f(x[sub]1[/sub], …, x[sub]n[/sub], y))[/ol]If g and h are recursive, then f is recursive as well. Note that n may be equal to zero in this case.[/li]
The Restricted [symbol]m[/symbol]-Operator
Let g(x[sub]1[/sub], …, x[sub]n[/sub], y) be a function such that, for any values of the x[sub]i[/sub]'s, there is a y such that g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0. [symbol]m[/symbol]y(g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0) is the least y such that g(x[sub]1[/sub], …, x[sub]n[/sub], y) = 0.
A function obtained without use of the restricted [symbol]m[/symbol]-operator is called primitive recursive. Otherwise, it’s known as just recursive. There are functions which are recursive but not primitive recursive; Ackerman’s function is the simplest known example.
You can take a recursive function and add dummy variables, permute the variables, or set two of them equal (e.g., f(x, y) = g(y, x, y)), and you’ll get a recursive function.
That seems like enough for now. Later, I’ll talk about the difference between consistency and [symbol]w[/symbol]-consistency.
Oops, double-posted. They’re exactly the same, so only read one.
Alright, ultrafilter, you’ve done some excellent work here. My lack of posting is not indicative of ignoring you, just so you don’t feel that I am! Thank you so much for your assistance here.
By my count, I’ve only got to explain [symbol]w[/symbol]-
consistency, and I’m done. Although, I have been assuming all along that everyone knows what the Gödel number of a sentence is (Basically, it’s a number that uniquely identifies the sentence. There’re a lot of ways to assign them, so let’s not worry about the specifics). Just for ease of notation, I’m gonna let |C| denote the Gödel number of the sentence C.
All right, we all know what consistency is. A theory K is consistent if there is some sentence which is not a theorem in K.
Let K be any theory with the constant zero and the successor function (so that K can describe the natural numbers). Let B(x) be a wff containing x as its only free variable. If |–[sub]K[/sub]~B(b) for every natural number n implies that it is not the case that |–[sub]K/sub(B(x)), then K is [symbol]w[/symbol]-consistent.
If K is [symbol]w[/symbol]-consistent, then K is consistent, but the converse is only true if you allow infinite-length proofs (and we don’t).
My apologies, but I can’t give an example of an [symbol]w[/symbol]-inconsistent theory. I’ll try and think up one, but don’t hold your breath. At this point, I can only assure you that they do exist.
So what’s the point to all this? Well, Gödel’s original theorem only applies to [symbol]w[/symbol]-consistent theories. If a theory is consistent and satisfies conditions 1-3 from my previous post, then you’re not guaranteed anything–there might be an undecidable sentence, or there might not be. The Gödel-Rosser theorem applies to any consistent theory that satisfies conditions 1-5 (including S, the standard theory of arithmetic).
The Gödel number of a proof is just some way of assigning a number that uniquely identifies the proof. Again, don’t worry about how it’s done. Gödel’s original theorem uses a sentence which says “There is no natural number which is the Gödel number of my proof”. The Rosser sentence, on the other hand, says “If x is the Gödel number of my proof, then there exists a y such that y is the Gödel number of my negation’s proof, and y < x.” That’s why you need conditions 4-5.
That’s it for now. Feel free to ask me any questions you might have, and I’ll answer them if I can.