Talk:Gödel number

From Wikipedia, the free encyclopedia

1 Moved
2 Gödel numbering
3 Negation
4 Requesting equivalent statement for Intentionally blank page
5 Injective map
6 Informal proof doesn't make sense
7 Confusing
8 Definition
9 History
10 Example

[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

$\forall$ x, ¬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)

[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 120₄ or in decimal notation= 1*4²+ 2*4¹ + 0*4⁰ = 16 + 8 = 24₁₀=#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*4³+2*4²+ 1*4¹ + 1*4⁰. 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)

Retrieved from "http://en.wikipedia.org../../../g/%C3%B6/d/Talk%7EG%C3%B6del_number_a72d.html"