Jump to content

User talk:AxelBoldt/Archive December 2004 - December 2006

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
< User talk:AxelBoldt

This is an old revision of this page, as edited by LittleDan (talk | contribs) at 02:36, 14 April 2003. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Older talk can be found in User_talk:AxelBoldt/Archive.

Hi Axel: I am trying to find out who originated the page for the Goedel's incompleteness theorem. My interpretation of its History page suggested to me that it was User:Maveric149, but he said he thought it might be you.

I am thinking about making a change to what appears to be something that has been there since the beginning of that page, and if you are the originator, I would like to first ask your opinion about this. I find that the notation under the proof sketch to be a little awry. In particular, for example, the notation G(F) should be G(F(x)). I don't want to go into a lot of detail here if you are not the right person, so I would appreciate it if you would clarifiy that for me first.

Best wishes, User:BuzzB Apr 3, 2003

Hello Axel,

Thank you for correcting the PMBOK entry.

I'm looking for volunteers to develop a GNU Free Documentation License Project Management Standard (just like the PMBOK, but possibly better). What do you think about it? User:Mkoval Apr 3, 2003.

Hi Axel:

Thank you for your reply to my previous message. It is not my intention to be predantic, but I think my proposed changes make the sketch slightly easier to understand. In addition to notational changes, and the adding of some clarifying text, I changed "proven" and "unproven" to "proved" and "unproved" because I could not find "unproven" in my dictionary. I will reply on your opinion about whether my proposed changes are useful before making them. My proposed revision is below. I have underlined my changes to highlight them.

By the way, I am currently working on a short paper which reconsiders the incompleteness theorem in the context of a three valued system where the three truth vlaues may be interpreted as TRUE, FALSE, and PARADOX. I wonder if you might be interested in reading it.

Proof sketch for the first theorem

The main problem in fleshing out the above mentioned proof idea is the following: in order to construct a statement p that is equivalent to "p cannot be proven", p would have to somehow contain a reference to p, which could easily end in an infinite regress. Gödel's ingenious trick, which was later used by Alan Turing to solve the Entscheidungsproblem, will be described below.

First of all, every formula or statement that can be formulated in our system gets a unique number, called its Gödel number . This is done in such a way that it is easy to mechanically convert back and forth between formulas and Gödel numbers. Because our system is strong enough to reason about numbers, it is now also possible to reason about formulas.

A formula F(x) that contains exactly one free variable x is called a statement form. As soon as x is replaced by a specific number, the statement form turns into a bona fide statement, and it then is either provable in the system, or not. Statement forms themselves are not statements and therefore cannot be proved or disproved. But every statement form F(x) has a Gödel number which we will denote by G(F). The choice of the free variable used in the form F(x) is not relevant to the assignment of the Gödel number G(F).

By carefully analyzing the axioms and rules of the system, one can then write down a statement form P(x) which embodies the idea that x is the Gödel number of a statement which can be proven in our system. Formally: P(x) can proved if and only if x is the Gödel number of a statement that can be proved. (While this is good enough for this proof sketch, it is technically not completely accurate. See Gödel's paper for the problem and Rosser's paper for the resolution. The key word is "omega-consistency".)

Now comes the trick: a statement form F(x) is called self-unprovable if ~P(F(G(F))), i.e. the form F applied to its own Gödel number, is not provable. This concept can be defined formally, and therefore we can construct a statement form SU(y) which embodies the concept: SU(y) is provable if and only if y is the Gödel number of a self-unprovable statement form. That is, y = G(F) for some particular form F(x), and ~P(F(G(F))). Then define the statement p = SU(G(SU)). This is the statement p that was mentioned above.

Intuitively, we are now asking the question: "Is the property of being self-unprovable itself self-unprovable?" This is very reminiscent of the Barber paradox: the barber who shaves precisely those people who don't shave themselves, does he shave himself?

If p were provable, then SU(G(SU)) would be true, and by definition of SU, that would make y = G(SU) the Gödel number of a self-unprovable statement form, hence SU would be self-unprovable, which by definition of self-unprovable means that SU(G(SU)) is not provable, but this was our p: p is not provable. This contradiction shows that p cannot be provable.

If the negation of p were provable, then, assuming our system to be consistent, p cannot also be provable, i.e. SU(G(SU)) is not provable, and by definition of SU this means that y = G(SU) is not the Gödel number of a self-unprovable form, which implies that SU is not self-unprovable. By definition of self-unprovable, we conclude that SU(G(SU)) is provable, hence p is provable. Again a contradiction. This one shows that the negation of p cannot be provable either.

Best wishes, User:BuzzB

Hi Alex:

I uploaded a revision in which I accepted your suggestion to leave the text with G(F) rather than G(F(x)), but I added some explanatory text.

I just printed out a copy of the Goedel proof from the web page reference, but I haven't had time to re-read it yet. Off hand, I tend to agree that the "only if" should be removed. I'm not sure I get the connection with inconsistancy, although if there is a connection then of course every statement would be provable.

Regarding my paper on a three valued interpretation, it is a work in progress. I don't expect to have a complete draft for a while yet, but if you would like me to send yoi a sketch of what I have in mind, I would be happy to do that.

Best wishes, BuzzB

Hi Alex:

I think your edit to the proof sketch is a very good improvement.

I finally got my personal web site up. There is a link on my User page. I would appreciate any comments you would care to make about anything I have there. When I complete a draft of the paper on a three valued re-intepretation of the Goedel theorem, I will post it there.

Best wishes, BuzzB

Many of your math entries (I was reading the one on the Open mapping theorem) can't be understood unless one is already studying that field of mathematics, or a similar topic. Could you define some of the terms that you use in the article? LittleDan

Retrieved from "https://en.wikipedia.org/w/index.php?title=User_talk:AxelBoldt/Archive_December_2004_-_December_2006&oldid=833455"