User:Wvbailey/Explication of Godel's incompleteness theorems

The following is an exploration of how to explain the first Gödel incompleteness theorem (Theorem VI, 1931).

Rosser 1939

I. Notion of "two logics" --

• (1) "logic of ordinary discourse"
• "formal logic L"

"propositions of L" are formulas built per "certain rules of structure"

symbols, interpretations, rules of structure interpretations will be declarative sentences (not necessarily true) of "ordinary discourse" -- "expressions in L".

II. "Amonst the symbols of L must be one, ~, which is interpreted as "not", the 'contradictory' when the symbol is applied before a sentence.

III.1. For each integer, there must be a formula in L which denotes that integer.

III.2 notion of "variables"

III.3 notion of "substitution" or "replacement"

IV. A process whereby certain of the propostions of L are specied as "provable". [notion of simple consistency and ω-consistency]

V. If F and ~F are provable in L, then all propositions of L are provable. The non-provability of any formula whatever of L implies the simple consistency of L. ω-consistency implies simple consistency; but if L is not simply constent then not ω-consistent.

VI. Modus ponens: Symbol ⊃ of L such that if formula A expresses sentence S and formula B expresses sentence T and A ⊃ B expresses "IF S THEN T".

VI.1 "Provable means that if A & A⊃B are provable then so is B.

VII. Notion of arithmetization of formulas: "For every formula, a number is assigned. However, not all numbers are assigned to formulas. If a number is assigned to a formula, the formula can always be found...". (p. 226). Thus, when numbers have been assigned to formulas, statements about formulas can be repalced by statements about numbers. That is, if P is a property of formulas,we can find a property of numbers, Q, such that the formula A has the property P if and only if the number of A has the property Q.

"LEMMA 1. Let "x has the property Q [a property of numbers] " be expressible in L. then for suitable L, there can be found a formula F of L, with a number n, such that F expresses "n has the property Q." That is, F expresses "F has the property P [a property of formulas]." p. 227

VIII. "We now call attention to an extra assumption implicit in the "for suitable L" of Lemma 1, namely that "z=φ(x,x)" be expressible in L, where φ(x,y) is the function [with the following] DEFINITION: φ(x,y) is the number of the formula got by taking the formula with the number x and replacing all occurrences of v in it by the formula of L which denotes the number of y.

• φ is a NUMBER.
• x is a NUMBER.

Registers holding individual numbers of arbitrary size::

010EJZ[E]; 020EJ[E]; 03CLR_P; 04DCR_P; 05INC_P; 06CLRi; 07DCRi; 08INCi; H }. Each instruction is considered to be tally marks, and a zero (blank) separates them. Thus "

or if we had 16 total instructions

0|nop; 1.E|movek_J, 2.E.|JFZi; 3.E.|JF,E; 4.E.|JBZi; 5.E.|JB; 6|clrJ, 7|dcrJ, 8|incJ, 9|clr_P; A|dcr_P; B|inc_P; C|clri; D|dcri; E|inci; F|halt }.

MOVE("3",5): clrP.inc_P.inc_P.inc_P.inc_P.inc_P.clri.inci.inci.inci = 8AAAAABDDD₁₆

JZ(5,*+q): movek_J.5.clrP.inc_P.inc_P.inc_P.inc_P.inc_P.JFZi

DCR(5): dcri.

J (*-r): movek_12.JB = 1+m+1

i.e. clear register 5 can be written without the use of the "clri" command: what would be this "godel" number? the need for absolute numbers screws this up a bit (doesn't allow for just simple fixed-place e.g. 4 bit encoding -- these numbers signify tally marks): 9.B.B.B.B.B.2.4.D.5.10. = 0|||||||||0|||||||||||0|||||||||||0|||||||||||0|||||||||||0|||||||||||0||0||||0||||||||||||||0|||||0||||||||||

clrP

incP

incP

incP

incP

incP

JFZi

4

dcri

JB

10

Example: INC(2) is expressible by x) = 0111011 (in binary written backwards), 14+32+64 = 110₁₀

Formula "x" = INC(v) = 011101^v

Formula "y" = INC^v number in y is CLR(y).INC(y).INC(y)....INC(y) = i.e. the concatenation of these:

[Y]=y =

Formula "x(y=v)" = 01110