Talk:Gödel number

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class High Priority  Field: Foundations, logic, and set theory

Contents

[edit] Moved

Should this article more properly be moved to "Gödel number", or are the numbers better known by the "phonetic" form?


Wouldn't it make more sense to have both this and Goedel number just redirect to Gödel's incompleteness theorem? -- John Owens 11:15 Apr 9, 2003 (UTC)


Note that the exact form of the Gödel number encoding is unimportant: there just needs to be a 1:1 mapping between local statements and manipulable expressions such as integers. You can do clever stuff with arithmetic, or you can just follow Chaikin and use Lisp S-expressions -- The Anome 23:48 15 Jul 2003 (UTC)

John - you may well be right. But in defense of a separate article, I thought there could be a place for a slightly less formal article on this topic. Gödel lite, as it were. I personally struggled to grasp the technical side of the argument (as expert readers can no doubt tell(!)), and I hoped that other people like me might appreciate a practical demo along these lines. Anome - A paragraph along these lines at the end could be a good idea. I guess it's worth pointing out the difference between a single instantiation like this, and the mathematician's quest for a general exposition. Wikid 06:24 16 Jul 2003 (UTC)

Another thought - we could re-name this page Gödel numbers - demonstration, and link to it from the Gödel's incompleteness theorem article, while redirecting Gödel number to the main article as John suggests. I'll leave that decision to the meta-mind. Wikid 08:33 16 Jul 2003 (UTC)

Anome is correct, there are a number (infinite?) of different mappings that are possible for use in Gödel's proof. I believe Gödel's original numbering system, however, used prime numbers taken to different powers to differentiate between variables, sentential variables and predicate variables. The mapping currently demonstrated in the article only works for encoding symbols and formulas but not sequences of formulas, a necessary characteristic for Gödel's proof. --128.253.167.158 18:13, 24 Oct 2004 (UTC)

Godel's original used only 7 elementary operators and assigned primes, squared primes, and cubed primes to the 3 variables u listed respectively above - at least according to E. Nagel in Gödel's Proof, which is where you probably got your info. from in the first place. I actually have Godel's original paper onhand but have never really read more than the introduction. It uses a lot of outdated terminology and symbolism.
Anyway, the numbering method used in this wiki article is capable of coding sequences of formulae, so I'm not sure why you thought otherwise. Why did you? Because it isn't explicitly stated? Nortexoid 08:17, 4 Nov 2004 (UTC)

[edit] Gödel numbering

What does the DA before GN is idiomatic mean ?

I have put the

In mathematics and computer science

at the start of the article because I thought you deleted my previous edit because it was to specific. What is formal number theory ? I am not sure what fields of study to use in the introduction. I know Gödel numbers are used in the proof of the incompleteness result and in computability theory. So I think it is perhaps best to use mathematical logic and theoretical computer science. More specific terms are probably useless in an introduction as most people dont know what they refer to.MathMartin 14:52, 11 Nov 2004 (UTC)

Formal number theory is essentially propositional logic with peano arithmetic and/or any extension thereof. The domain is the natural numbers (or (0 and) the positive integers). It is also known as simply 'arithmetic' - i.e., theories closed under addition and multiplication in which the naturals can be constructed.
GN cannot be performed in all of mathematics or computer science. It doesn't make any sense to say "In mathematics and computer science, GN is..." because you cannot perform GN in numerous branches of mathematics - i.e. you cannot perform GN in the theory of real closed fields because you cannot define the naturals. I am reverting again to formal number theory, and I hope I have made myself clear as to why. If not, we'll need to talk about it in the article's discussion page. I don't see why we should need to, though.
The thing about the DA before GN was a mistake. I meant the indefinite article, not the definite article (DA), which is the word 'a'. It is more idiomatic to say "...is called a GN." vs. "...is called GN.". Cheers, Nortexoid 05:19, 12 Nov 2004 (UTC)
Formal number theory may be the correct term to use, but the term is too specific. Most people will have no idea what you are talking about (e.g. myself). So I think it is better, even if slightly incorrect, to use more generic fields like mathematics and computer science. The first sentence should serve as a introduction for the reader, and set the context for the rest of the page. After reading the first sentence most readers, even non-mathematicians (remember this is wikipedia and not mathworld) should have a rough idea what we are going to talk about. As I wrote in my edit summary I have no intention to start an edit war, so I will leave the article as is.I just wanted to voice my concerns. MathMartin 06:01, 12 Nov 2004 (UTC)
The term is actually not specific at all, though it is accurate. It is not as general as mathematics, but it is far more informative. If I said, "what subject do you think formal number theory falls in?" to a non-mathematician, I'm sure they'd be able to respond "mathematics". So it is more specific and informative than 'mathematics' while obviously implying the subject matter to be mathematics. There is a fine line between targeting a broader audience and being as accurate as possible without being overly specific. I think 'formal number theory' is a happy medium. If I were to consider a runner-up, it would be your previously proposed 'mathematical logic'. Both seem fine to me. I used 'formal number theory' because it is popular in the literature (see Kleene, Mathematical Logic, 1967). Nortexoid 07:36, 12 Nov 2004 (UTC)

[edit] Negation

\forallx, ¬R(v,x) Can also be interpeted to mean "The negation of a proposition of type v can be proved", yielding:

x=(0,1,¬, ask)
R(0,0)=¬0 = ask 1
R(1,1)=(¬0)0 = ask 0
R(1,0)=0
R(0,1)=1

Hackwrench 04:29, 12 November 2005 (UTC) (Still flawed, but have to include \infty, shiftleft, shiftright, and \forall

I'm trying to figure out why certain pages aren't rendering a TOC Hackwrench 04:47, 12 November 2005 (UTC)

[edit] Requesting equivalent statement for Intentionally blank page

I do not know much in the way of number theory, but it appears that Godel numbering is what is needed to construct a mathematical equivalent to the usage of the phrase "This page intentionally blank" on blank pages. It is self-refuting, in that it falsifies itself by its very existence on the page in question. — BRIAN0918 • 2005-12-4 17:47


[edit] Injective map

Shouldn't Gödel mapping be defined as an injective mapping? Though injectiveness is implied by the fact that reference is made to the mapping's inverse (which doesn't exist for non-injective maps), I think injectiveness should be stated explicitly.


[edit] Informal proof doesn't make sense

I don't understand the formal account of the proof. Surely the first statement in fact means simply "v cannot be proved"? Where does this "type" thing come into it?

Then does not the next statement say "it cannot be proved that v cannot be proved"? Which doesn't condense into anything, I don't see how the "v" can disappear out of the equation. It seems to say nothing more than that "v" is undefined, which seems reasonable, since we didn't define it (although just because a statement says something doesn't make it true).

82.41.211.70 22:18, 25 April 2006 (UTC)A.W.

I agree--the sketch here doesn't seem correct. I don't believe you can construct the required sentence using the R defined here--you need a statement form that describes self-unprovability, not just provability. The proof sketch in Godel's incompleteness theorem is more accurate. --Rictus 20:21, 2 September 2006 (UTC)

There shouldn't be a proof of the undecidability theorem here anyway. This article is linked from several articles on computation theory, and anyone following the links is going to be horribly confused as the discussion gets into needless detail on Gödel's own application and says nothing about the connection between numberings and programming languages. Gazpacho 08:24, 27 September 2006 (UTC)

[edit] Confusing

I'm not convinced that the {{confusing}} notice is helpful, nor that this article belongs in Category:Wikipedia articles needing clarification which is the result of this tag.

Certainly the subject is a confusing one, particularly to non-specialists. Even many specialists are still trying to figure out exactly what the consequences are, both for Mathematics and for Formal logic. I'm not familiar with the consequences for computing, I even wonder whether that's at least partly an urban myth, based on the (misleading IMO) connections to Alan Turing and Turing machines.

But if the subject is a newsy and confusing one on which many are already misinformed before they come here, that's not the fault of the article.

What are the specific ways in which the article can be improved? Bear in mind that if it were to make this subject look simple to a non-specialist, that would be very good evidence that the article was then inaccurate. Andrewa 20:33, 24 October 2006 (UTC)

The tag was removed without comment here. Either someone agrees with me, or they feel that the confusing material has been removed.

Please, if you tag an article, give us some idea why you are tagging it. Andrewa 04:28, 7 September 2007 (UTC)

[edit] Definition

The current definition (without the vandalism) is nonsense. Does anybody have a definition that satisfies these characteristics?

  • Correct
  • More general than just formulas of an effective first-order language
  • Used in print

I would remove the Definition section and replace it with a discussion of the various specific settings where the phrase is used. CMummert 20:14, 7 December 2006 (UTC)

I agree with Carl here. As far as I'm aware, there is no agreed abstract definition of what a Gödel numbering is in general, mainly because the need for such a definition has never been felt. Ordinarily one doesn't treat Gödel numberings in general, so why bother to define them in general? That's not to say someone hasn't published a general definition of "Gödel numbering", but unless that definition is in common use (which it certainly isn't), it shouldn't be presented here as the default. --Trovatore 03:59, 7 January 2007 (UTC)

[edit] History

It may be helpful to relate the history for the Gödel numbering concept for the readers, such as its use in Georg Cantor's transfinite numbers, in Gödel's theorems, and in Church's expositions. --Ancheta Wis 06:06, 13 January 2007 (UTC)

[edit] Example

Ok, let's use base-4 mapping: 'x' => 0, 'n' => n 1s, '+' => 2, '=' => 3 The formula F(x)=x+1 will be encoded by sequence 0, 2, 1 or number 1204 or in decimal notation= 1*42+ 2*41 + 0*40 = 16 + 8 = 2410=#F. Here #F is the number of the form F(x). The statements are derived by inserting constant numbers instead of x in the form. For instance #F(1) would be 25 and #F(2) would be 1*43+2*42+ 1*41 + 1*40. Generally, the number of the statement for constant n will be

\#F(n)=\sum_{i=0}^{n-1}{4^i} + 2*4^n + 1*4^{n+1} .

Now, I want to get the Gödel number for the statement F(n=#F). However, the equation

\#F(\#F)=g=\sum_{i=0}^{g-1}{4^i} + 2*4^g + 1*4^{g+1}

have no solutions in natural numbers! So, the Gödel number depends on encoding and may be irrational or not exist if encoding is wrong. What is the proper encoding? Getting the number I want to decode it and look at the statement F(#F). --Javalenok 16:22, 15 January 2007 (UTC)

Rebecca Goldstein (2005), Incompleteness ISBN 0-393-05169-2 uses base 10: pp.172-3
Basic sign Gödel number meaning
~ 1 not
→ 2 if .. then ..
x 3 variable
= 4 equals
0 5 zero
s 6 successor of
( 7 l-paren
) 8 r-paren
' 9 prime

--Ancheta Wis 00:07, 16 January 2007 (UTC)

Can you give the Gödel number G=#F(#F) for F(x)=~x? The [] tells that the Gödel number for the Gödel sentence is 'precisely defined'. How do they derive it if the provability predicate P is not known? --Javalenok 10:21, 16 January 2007 (UTC)

[edit] From a non-expert

I am a music theorist with and intrest in logical systems. From a layperson's perspective our English page is woefully inadequate on this topic. "Goedel lite" is not very helpful even if the mapping concept is properly conveyed. For more useful articles on this topic, see the German and Chinese versions.

68.19.242.28 07:50, 25 April 2007 (UTC)

Do you read those languages? Can you convey to other editors what might be useful to add? The essential idea of mapping concepts to counting numbers is already in the article. --Ancheta Wis 10:57, 25 April 2007 (UTC)
Perhaps we could appeal to the relevant Wikipedia embassies to give us, perhaps not a complete translation, but some idea of what the content of the other articles is. I'm not inclined to, but it's an idea. Hmmm, German, English, Chinese, formal logic, music... an interesting combination. Andrewa 04:58, 7 September 2007 (UTC)
By Chinese, I assume you mean the article at zh:哥德尔数. There's also one at zh-yue:Gödel號數 in Cantonese, but it's very short. Andrewa 03:59, 8 September 2007 (UTC)

The German article at de:Gödelnummer is also short, but it does look in some (not all) ways a better article than ours. Ours rambles and speculates. The German article, by comparison, has only the following sections:

  • Formal definition
  • Example
  • Gödel numbering of zahlentheoretischen Aussagen (which Babelfish translates as pay-theoretical statements but I think may mean well-formed formulas or number theory proofs or something like that - that's what should be there)
  • Gödel numbering of Turing machines
    • Example
  • see also

I speak no German to mention, but even I can tell it's not a perfect article in German. But food for thought, and they do have the advantage that much of Gödel's work on this was originally published in German. Andrewa 04:33, 8 September 2007 (UTC)

[edit] Add Simple Example(s)

Why not add a simple example or two near the beginning. Assign numbers to symbols as in one of the comments below and do a formula-to-number and a number-to formula example.

~reader —Preceding unsigned comment added by 207.195.244.207 (talk) 18:51, 6 September 2007 (UTC)

I fear that this would just look silly. The whole idea of Gödel numbers is fairly esoteric. You need to know quite a lot of mathematics before you'd have the slightest clue that they were useful. The things that they are used to prove seem nonsensical to the uninitiated.
I'm not trying to be elitist here. But you wouldn't try to define just intonation in a way that would make sense to someone who doesn't know what a musical scale is. I feel that some of the edits to this article, while I hope well-intentioned, are equally misguided.
The problem is, Gödel's incompleteness theorems are fascinating to the uninitiated, so we do need to do our best. But we musn't stray into inaccuracy for the sake of simplicity. It's not a simple topic.
My advice is, be aware that many who do come here do not have the understanding needed to make sense of what they read, but will acquire it, and among those who struggle hardest at this may be the next Einstein or Heisenberg, both of whom struggled famously with the tensor calculus that undergirded their most famous work. So for the sake of these strugglers, I commend all those struggling with this article. Andrewa 04:47, 7 September 2007 (UTC)

[edit] Very different meaning?

Current article reads There is a very different meaning of the term Gödel numbering relating to numberings of the class of computable functions. I think (if this is true) that we should find this meaning and include it in the article. Andrewa 04:14, 7 September 2007 (UTC)

I followed the links you highlighted and discovered that the keyword assignment occurs in the all of the supposedly 'different' meanings. What was intriguing to me was the idea that a 'computation' might be replaced by an 'assignment' in the sense of a telephone switchboard operator, who would physically connect a conductive plug into a socket. Thus we will have come full circle in the history of computing hardware where telephone operators were replaced by computerized telephone switches, right back to a condition where selection of one element from a set of answers is a 'computation'; the difficulty is that you need a 'recognizer' to figure out how to make the selection. That's probably the reason there was no citation for the statements made in the linked articles. The statements don't stand up. There is no current theory of recognition for such a recognizer of an answer in some requested computation. If you already knew the answer, you wouldn't need to ask the question. If you didn't know the answer and the telephone switch connected to a wrong number you still would be stuck; we would still have the Wikipedia conundrum -- how do you know an answer is right, unless you already know the answer?
To follow-up with the encoding analogy, a telephone number is a code for a person. Dial the number and talk to the person. We do not yet have a technology to connect remotely with another person without that code. There are technologies such as the content-addressable memory where the name of a 'person' connects you right to the 'person' without the code, but the idea has been around for over 30 years with no commercial product in sight, for the moment. --Ancheta Wis 09:46, 7 September 2007 (UTC)
I'm afraid I don't think any of that has much to do with Gödel numbering. The only use I know of these numbers is to establish that things such as solutions to the halting problem don't exist. They have no practical application, only this theoretical use in indirect proof. The general approach is to establish a contradiction by assuming that something does exist, and then showing that this means that it both does and doesn't have a Gödel number. I fear that these other applications aren't Gödel numbers at all. Happy to be proved wrong, that means I learn something. Andrewa 02:44, 8 September 2007 (UTC)
Based on this I am commenting out said statement in the article. --Ancheta Wis 03:02, 8 September 2007 (UTC)

[edit] Another different meaning

There's an article at Gödel numbering for sequences which has only one principle author, no links to other languages, no talk page yet, notes which give some sources (but nothing online unless you read Hungarian) but no other citations, and reads to me very much like original research. It may be the cause of some of the confusion here. Other comments? Andrewa 04:43, 8 September 2007 (UTC)

Thanks for the link. My heart warmed as I read the article, which is clear, easy to read, has citations, and uses standard concepts such as the integer sequence. What came to mind immediately is a useful coding system promulgated by AT& T Research [online encyclopedia of integer sequences] which shows clearly that codes, of which a Gödel code (a redirect to this article) is an example, are arbitrary in spite of being well defined. My inclination is to let the article live in peace in the encyclopedia. We need more like it, in my opinion. --Ancheta Wis 09:02, 8 September 2007 (UTC)
Here is a poster for the OEIS, which has over 130,000 sequences at the moment. See the article: On-Line Encyclopedia of Integer Sequences --Ancheta Wis 09:24, 8 September 2007 (UTC)
I'm familiar with OEIS. But what has this to do with Gödel numbering? Andrewa 03:00, 9 September 2007 (UTC)
Only Gödel's use of natural numbers as a code, and the use of the codes of OEIS to denote sequences of natural numbers. --Ancheta Wis 10:38, 9 September 2007 (UTC)
OK. I'm unconvinced, but I don't intend to take it any further. Mainly I just wanted some other people to have a look at the issues I raised. Glad you like the article. Andrewa 00:36, 11 September 2007 (UTC)