Saturday, March 5, 2011

Gloryholes In Columbus, Ohio

in the demonstration of Gödel (Part 5) The self-referential

( A Part 4 - Part 6 A )

Gödel coding

Let's start the first demonstration of Gödel's Incompleteness Theorem. Imagine going to give us a system of axioms for recursive arithmetic is consistent, and that it allows to prove all true finitary statements. We will have to demonstrate that a statement P such that both it and its negation are provable from these axioms. [For reasons teaching are not going to assume that we work with a set of general axioms, but we have given a specific system and let's play it the demonstration of Gödel.]

say I speak in the future and "will give us a axiom system "because the first step of the proof of Gödel (and this is important to emphasize) does not depend system of axioms that will give us.

This first step is to assign each statement and each finite sequence of statements a natural number, the code will call the of that statement or that finite sequence of statements. There are many ways of defining this allocation, but no matter how we choose to do so, it must always comply with the following conditions:

1. Each object (either a sentence, whether a sequence of statements) you must be a corresponding natural number different.
2. There must be an algorithm that, given a statement or a series of statements, allows us to calculate what number it belongs.
3. There must be an algorithm that, given a natural number, let us determine if this number is. or not, the code of a statement or a succession, and, if yes it is, determine corresponds exactly to what purpose. (1)

When we speak of "algorithm" we are talking about a syntactic procedure, therefore the codes are assigned to the set or succession of statements as long as these objects are written in formal language.

As I said before, there are many ways to assign the codes. Raymond Smullyan in his book Gödel's Incompleteness Theorems, works with a language of 13 symbols (including a special symbol to separate the statements which form part of a series), and translating each symbol to a "digit" makes every statement (or sequence of statements) in a natural number written in base 13. In Gödel for All the procedure is similar, but using strings of binary digits. Gödel himself used in his original demo products of powers of primes (2) . Here avoid giving details of how to do the assignment, simply assume that the allocation has been defined.

In some talks (and perhaps also some input from this blog) have said that, for example, the statement "2 is even" is assigned a natural number. However, this language, which has the virtue of simplicity, contains the germ of a mistake: confusing the concepts of syntactic with semantic concepts.

As I said before, the assignment of codes is a purely syntactic. How do we translate "2 is even" formal language? There are actually many different ways to do so, for example (in what follows we use the "E" light indicator "there"):

x E ((1 + 1) = (1 + 1). x )
x E ((1 + 1). x = (1 + 1))
and E ((1 + 1) = (1 + 1). and )
x E ((1 + 1). and = (1 + 1))

... and many more.

Syntactically four written statements above are different and, therefore, to each of them carries a different code . There is no code for "2 is even", there are different codes for each of the infinite ways it can be translated into formal language. Therefore, we should not think the codes assigned to words as written in Castilian, but syntactic objects called "set" or "sequences of statements."

observation above may seem trivial, but it is not. Semantic concepts are more familiar to us that the syntactic and so we tend to think, speak, explain, and even writing books making the syntactic logic in semantics (to be more "palatable"), but this conversion can lead to confusion.

Here's another example that clearly shows the difference between semantic and syntactic concepts (including mathematical concepts and meta-mathematics). Suppose we take as axioms the statements A1, .., W (which, I hasten to clarify, do not meet the assumptions of Gödel's theorem) and we say that statement "1 + 1 = 1" is provable from these axioms. Should we conclude that A1 ,..., An is an inconsistent system? The answer is no. The axioms could form a coherent system. (Recall that consistently means that P and not-P are at the same time never proven.)

How is it possible that "1 + 1 = 1" is demonstrable, but the system is consistent? If one makes that question is that is confusing "demonstrably" to "true" (syntax with semantics).

What does A1, .., An to demonstrate the statement "1 + 1 = 1? A: means that there is a finite sequence of statements whose final statement is "1 + 1 = 1" in which each is either one of the A1, .., An, or follows from previous statements by applying the modus ponens. Note that this response is based on syntactic concepts and that it does not fit the concept of "truth" (or "false"). Note also that this demonstration of "1 + 1 = 1", as any finite sequence of statements, has been assigned (by way of code) a natural number.

If the axioms met the assumption that every statement is demonstrably true finitary, then we form inconsistent system. In fact, "- (1 + 1 = 1) (a" - "indicates negation) is a finitary statement true and if the hypothesis is fulfilled, then that statement would be provable. As well as "1 + 1 = 1" is provable then the system would be inconsistent.

However, it is possible that A1, .., An (that said, does not meet the assumptions of Gödel) does not support a show for the statement "- (1 + 1 = 1)" and that So be a consistent system.

continued ...

Notes:

(1) clarification of language Two: For the purposes of this series of entries, natural numbers are 1, 2, 3, 4, 5, 6, etc. and algorithm mean a mechanical process is completed in a finite number of steps.

(2) Gödel assigned to each symbol of the language an odd number. If a set E consists of the symbols s1, s2, s3, ... then it is the number 2 ^ c (s1) .3 ^ c (s2) .5 ^ c (s3) .7 ^ c (s4 ).... Count c () is the code for each symbol. A succession of statements E1, E2, E3, ... code corresponds to 2 ^ c (E1) .3 ^ c (E2 )....

( A Part 4 - Part 6 A )

0 comments:

Post a Comment