# The universe is incomplete or inconsistent

**URL:** <https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528>\
**Category:** Great Debates\
**Created:** [June 17, 2002, 2:34pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528 "2002-06-17T14:34:31Z")\
**Posts on this page:** 11\
**Page:** 5

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 24, 2002, 2:30pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/81 "2002-06-24T14:30:48Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Liberal](https://avatars.discourse-cdn.com/v4/letter/l/848f3c/32.png) [@Liberal](https://boards.straightdope.com/u/Liberal)\
**Post date:** [June 24, 2002, 3:28pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/82 "2002-06-24T15:28:37Z")

</div>

Sounds like it’s all well worth the wait, Ultra.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 2:14am UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/83 "2002-06-30T02:14:43Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 3:07am UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/84 "2002-06-30T03:07:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 4:50am UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/85 "2002-06-30T04:50:31Z")

</div>

Oh, I should mention that I’m taking all this from E. Mendelson’s _Introduction to Mathematical Logic_, 4e.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 8:47pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/86 "2002-06-30T20:47:55Z")

</div>

> [@](#):
>
> \*Originally posted by ultrafilter \*  
> **The subscripted existential quantifier ([symbol]$[/symbol][sub]1[/sub]y) means "there exist exactly n distinct y’s such that…"**

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…””

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 9:05pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/87 "2002-06-30T21:05:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 9:40pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/88 "2002-06-30T21:40:16Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 30, 2002, 9:45pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/89 "2002-06-30T21:45:21Z")

</div>

Oops, double-posted. They’re exactly the same, so only read one.

---

<div class="post-metadata">

**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\
**Post date:** [July 1, 2002, 5:40pm UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/90 "2002-07-01T17:40:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [July 2, 2002, 12:58am UTC](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528/91 "2002-07-02T00:58:11Z")

</div>

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.

[Previous page](https://boards.straightdope.com/t/the-universe-is-incomplete-or-inconsistent/114528.md?page=4)