Two Serious Questions

1. How can one prove that a Godel sentence can or cannot be found in principle by us? Despite reading TENM, Shadows, Beyond the Doubting of a Shadow,some of the FOM archives, and talking to a few people, my knowledge is running dry. I would be most pleased if someone here could outline a positive or negative proof of such a premise.

2. We are on the verge of having 200 members! What would you like the future of this group to be? What features would you like to increase or decrease?

I am sure we would like to increase our power.  Soon the world will be ours!

Conquistador, do you mean more team matches and vote chess?

I think we should open team games for our members.When I invite people I tell them that we like chess and science as well.We have a lot of scientific topics on the forums but less games.We should open a few and see what happens.(I'm sending invites right now and I'm positive that tomorrow we'll hit the 200 mark)

I forgot about a team tournament. That's a possiblility. OK I'll pay attention to the team matches (not that I haven't been before). Thanks.

I see that we are outmatched in one of our team matches that is about to start...maybe we should try to open smaller games with 15-20 players and set rating limits so they will be more balanced.What do you think?

That sounds fine. Should we abort our current one?

For me it's ok to play...I play with anybody but my opponent is 1900+ so it is highly likely that I  loose...however I have a strange habit of loosing to weak players and beating stronger ones.In my oppinion we should play for fun but it is highly possible that we'll get our ass kicked.

I say we should play this match. I got pushed down due to the withdrawals, but I'll go up if you wait. Depends on our strategy.

Meaning a) I play on the last boards getting safe 2 wins (unless I get a very underrate opponent too) or b) we wait for me to get to 1900 (about 1 week should be). we can also wait for new members.

In answer to the original question, a pretty good way of showing we can find a Godel sentence is to find one! Doesn't the usual proof of the incompleteness theorem actually exhibit such a sentence? I am pretty sure such a sentence can be exhibited in any incomplete theory (subject to usual conditions).

Kacparov and Ripper: Thank you for your input, I will not abort the match. The plan is to get more new members in the match by another news item.

Elroch: I think the concern is whether a Godel sentence would stump an intelligent computer. It can be easily programmed for a computer to recognize as accepting its Godel sentence is true; but how do we know we have the resources to make a Godel sentence in the first place? Must such a human algorithm be able to understand itself? If it does, does it need to have a complete representation of itself?

strangequark, by its definition, a Godel sentence needs to be considered with two theories in mind. One is the theory in which it is a statement that is undecideable, the other is the theory in which it is proved to be true. The second theory is stronger than the first theory, but can be easily mechanised as well. I feel it is too anthropomorphic to use the words "intelligent", "stump and "understand" for the computer, but it could be programmed to perform the logical steps necessary.

As I indicated above, explicit Godel sentences can be generated for any theory powerful enough to be able to deal with the natural numbers (with some mild conditions).

I know that strictly there are two of Godel's proofs...but I am not sure the point is being adressed. "but it could be programmed to perform the logical steps necessary."; yes, this is what we are dealing with more precisely but I used those words for a comparison.

But really, do we know that both humans and computers have sufficient resources for constructing such sentences if they are contained in the program?

I would be interested in hearing the details of "Godel sentences can be generated for any theory powerful enough to be able to deal with the natural numbers (with some mild conditions)."....

It's there in the usual proof of Godel's (first) incompleteness theorem, which generates an explicit Godel sentence. The proof is well worth studying for enlightenment.

But how does this transfer to a mind or algorithm with finite resources? Surely this sentence as originally formulated did not give such an example of a human's sentence?

Yes. It is a finite thing which can be precisely described. I may elaborate a little if I have some time.

ok, a high level sketch proof (all technical details omitted)

Pick a theory T  chosen to be capable of modeling the natural numbers, with a formal language L. Find a way of expressing in L the following self-referential statement S:

"this statement does not have a proof within the  theory T"

Prove rigorously that S may not be proved within the theory T. But observe that S is true, in that it indeed does not have a proof, even though we cannot prove this within the theory T. This provides us with a statement that is true but unprovable.

QED

[We can also show that S may not be proved false within T either, so it also provides an example of an undecidable statement in the theory T ]

Yes I know this (although I don't know very well how to do the technical yoking between metamathematical statements and mathematical statements such that I make them stand or fall together). I am left scratching my head wondering if my question was one with an obvious answer and whether or not I missed something.

Your question was absolutely not obvious (without being familiar with the subject). This is undeniable, since one of the most talented mathematicians ever (David Hilbert) posed the problem that led to this in 1900, and it took until 1931 for Godel's genius to realise the surprising truth, and prove it.

Although the proof is not so easy to grok, the only real difficulty is in the interpretation side. The proofs involved are rather simple, once to make the right definitions.

Sketching the proof at a slightly lower level from recollection:

(1) Define a formal system including a simple formal language able to represent all the theorems and proofs of number theory.

(2) Show there are computer programs able to identify a valid equation, a valid statement, and a valid proof (sequence of statements each following from the last).

(3) Find injective mappings from the set of valid statements and the set of valid proofs to the natural numbers.

(4) Define the Godel statement G.

(5) Prove easily that that there is no proof of the statement in the system

(6) Observe the interpretation of the statement is true.

(7) As an extra, show that the negation of the Godel statement cannot be proved.

All except (6) and maybe (7) are computable. I think the proof of (7) I have seen is not computable in the same sense, but not sure if there is another one.