• sime
    1k
    The book "An Introduction to Godel's Theorems" by Peter Smith would be my recommendation for an eager beginner.

    Alternatively, wiki's page on the Halting Problem conveys in the simplest and quickest fashion nearly all of the relevant computational and philosophical implications of Godelian incompleteness without the torture of Godel numbering.

    In fact, the popular misconception of Godel's theorem as amounting to saying that "a sentence is 'true', assuming that it is unprovable" is a more apt (but still ultimately misleading) conception of a weaker form of incompleteness that is directly implied by the undecidablity of the Halting problem, namely that there cannot be a sound and complete axiomatization of the natural numbers, since that would imply the existence of a computation on the natural numbers that halts if it doesn't halt.

    Godel's actual proof, that doesn't appeal to a model or intended interpretation of the axioms of Peano Arithmetic, is a stronger result since it directly proves syntactical incompleteness without appealing to any notion of soundness. His proof can be intuited geometrically and trivially, as showing that the forest of mathematical proofs that constitutes Peano Arithmetic doesn't describe the background that isn't part of the forest of Peano Arithmetic. Is that really an interesting and deep result?

    So the heuristic argument of there being a "true but unprovable statement" that the public use as a heuristic for understanding or remembering Godel's theorem is very misleading. Their catchphrase is more suitable as a moderately misleading heuristic for remembering the proof of the Halting problem (which also doesn't refer to models, but to external assumptions concerning halting conditions, that with much charity might be interpreted as comprising a weak model of something or other).

    Many mathematicians and logicians cannot themselves be bothered to master Godel's incompleteness proof, for there isn't any payoff for doing so, and will probably content themselves with a technical understanding of the weaker version I mentioned above that is straightforward to prove and remember, and loses practically nothing.
  • tim wood
    8.7k
    An Introduction to Godel's Theorems" by Peter Smithsime
    Listed as 402 pages. Godel's paper is 34 pages. Interestingly, I find only one place where (in my translation) Godel uses "true" or variants: section 3, "The following proposition is true: Theorem VII: Every recursive relation is arithmetical." In the rest it's "provable" or "decidable," and variants.

    The usual locution I find is that G is undecidable, but because G says it's undecidable, it's true; this a so-called metamathematical proof being outside the system in which G is created.

    I half-buy that professionals are not interested in mastering the theory, and for the reasons you mention. The theory itself, though, is built up from logical building blocks themselves not so difficult, thus only a challenge to a professional as an investment in time and energy. And not insurmountable for a merely interested layperson, that layperson simply needing to remind him- or herself that they don't have to eat all the thistles in the field.
  • FrancisRay
    400
    Thanks for trying, it's much appreciated, but I can't see the mathematical significance of a self-referential statement that states 'This sentence' is false'. What sentence?

    It would help if I could find a statement that is true but provably undecidable, but I've never seen one. Do you have an example?

    Your piece of paper example doesn't do it for me since the two statements make contradictory claims and clearly cannot both be true. We can invent these paradoxical circular arguments easily enough but where do they occur naturally?

    .
  • sime
    1k
    Listed as 402 pages. Godel's paper is 34 pages. Interestingly, I find only one place where (in my translation) Godel uses "true" or variants: section 3, "The following proposition is true: Theorem VII: Every recursive relation is arithmetical." In the rest it's "provable" or "decidable," and variants.tim wood

    Yes, that would be because Godel wanted to reinforce the point that his theorems have entirely constructive proofs, that don't appeal to the law of excluded middle or to meta-mathematical assumptions. Unfortunately, that point was lost on Douglas Hofstadter, who only caused misunderstanding of the theories, by linking them to the meta-mathematical concept of self-reference that isn't of any proof-theoretic relevance to the theorems.

    Peter Smiths book is much longer because it also covers related topics that developed after Godel that are of relevance to his now ancient theorems, even if the book is badly outdated in certain respects and unhelpfully assumes a background of classical logic for presumably historical reasons.

    The usual locution I find is that G is undecidable, but because G says it's undecidable, it's true; this a so-called metamathematical proof being outside the system in which G is created.tim wood

    Well syntactical incompleteness does at least imply that any system of mathematical logic is an unfinishable open-system, such that any sufficiently expressive axiomatic system can be consistently extended in an infinite number of mutually inconsistent ways, leading to an infinite number of conflicting rival interpretations with respect to any theory of arithmetic. A problem with your meta-mathematical heuristic however, aside from the fact that it isn't relevant to Godel's constructive proof of the theorems, is that it assumes the existence of mathematical truth prior to system construction - which might or might not be epistemically appropriate in a given situation.

    Essentially, if one accepts Godel's completeness conjecture , namely the conjecture that first order logic is sound and complete with respect to the theorems that are tautologies, i.e. the theories that are satisfied by every model of the logic, then either a theorem is syntactically provable in such a logic or there must exist a model in which the theorem is false. So the heuristic you mention is a potentially useful heuristic for automated theorem proving - if the completeness conjecture is assumed, which is generally appropriate for classical logic, then a theorem can be disproved by merely showing that it's negation is satisfiable in a model of the logic, meaning that one can "observe" the theory to be false, without having to laboriously work "within the system" to produce a syntactical proof of the negated theorem.

    Syntactically however, G is merely the fixed-point of an alternating fix-point equation, whose iteration causes an increase in the number of negation signs at the front of the fixed-point. It is structurally similar to a coalgebra representing a potentially infinite list of oscillating boolean values, objects that are normally called "impredicative" rather than "self-referencing" in the literal sense implied by Hofstadter.
  • Patterner
    553
    Thanks for everyone’s words. I’ll check out Peter Smith if it comes out in e-format. I already have a couple, as well as Hofstadter’s I An a Strange Loop. But the premise is beyond me. Arbitrarily assigning numbers to all the numbers and symbols in equations? If it doesn’t matter what numbers you assign them, how is there any point in doing it at all?
  • tim wood
    8.7k
    I'll give it one more try. If there's a trick, it's realizing there is no magic, and the parts are themselves relatively simple. It's the putting them together that's not-so-easy.

    First, Godel numbering. A small number of symbols can express any proposition (of interest here). They are, in Godel's paper, 0 (zero), s (successor), ~ (negation, also Neg.), V (or), Π (for all), (, and ) (open and close parentheses). They are assigned respectively the numbers 1,3,5,7,9,11,13. And for plain numbers themselves, for example, 1=s0, 2=ss0, 3=sss0, and so forth. Variables, such as x, y, z, and so forth, are each represented by the next prime number, starting with 17. E.g., x=17, y=19, z=23, and so forth. Thus every proposition can be mapped to a unique number, and back again, and also with any sequence of propositions. You can research the exact details of how.

    More simply, one can visualize a very, very large telephone-book-like listing of all the propositions, each numbered. Thus the "proposition" that 7+5=12, if its Godel number were 192, could be referred to simply as "192."

    Second, recursion. Recursion here can be considered as the mathematician's way of saying, "You can get there from here," the recursion being the exhibition of the way itself. Godel troubles to offer 45 recursive definitions (which look difficult, but are not too hard to learn to read). And there is a 46th, "is provable," (abbrev. "Bew") which Godel says, "cannot be asserted to be recursive." Which if you're very alert, you will recognize as being the whole ball game right there! That is, there is no schema, recursive method, methodology, algorhithm - call it what you will - by which you can get there, to the proof, from here!

    Godel uses the expression "relationship." We shall only understand this as meaning that if something can be said about two numbers, then they can be said to be related at least to that extent. For example, if Q stands for the relation "less than," then Q(x.y) would be the proposition "x < y". "Sub" is a recursive function Godel defines as substituting into a proposition a number for a free variable. Thus in our example, Sub Q( x:4, y:7) we might read as, substitute into the relation x < y, 4 < 7. He also will Sub in Z numbers, like this: Sub Q( x:z(4), y:z(7)). And this would be Q(ssss0, sssssss0) or ssss0 < sssssss0.

    Godel argues that all recursive relations are decidable, by which he means that given any recursive relation Q and appropriate substitutions, then either Q or ~Q is provable. And here the significance of his assertion about provability comes into play.

    Third, now for the ride itself! Godel uses four expressions, "Bew" meaning is provable as described above. Sub, as described above. "B" meaning proves. And Z meaning the substitution, for example, of ssss0 for 4. Thus Z(y) is the number y, whatever that is, replaced by the same number expressed as sss...sss0. All a little strange, but simple.

    Consider a relationship Q(x.y) which says that ~(x B (Sub (y 19:Z(y))). This reads as,
    "it is not the case that x (whatever x is) proves y (whatever y is) when into y for the free variable 19 (if there is such in y) is substituted the Z number for y."

    Because this Q(x,y) has been shown to be recursive, that means that the following hold:
    1. ~(x B (Sub (y 19:Z(y)))) ---> Bew (Sub (Q 17:Z(x), 19:Z(y)))
    2. (x B (Sub (y 19:Z(y)))) ---> Bew (Neg (Sub (Q 17:Z(x), 19:Z(y))))

    Simply, if x does not prove.., then Q with the indicated substitutions is provable. And if x did prove.., then the negation of Q, etc., would be provable. Thus this Q(x,y) would be decidable.

    Set p = 17 gen Q. P is simply the expression Q(x, y) for all x.

    Set r = Sub (Q 19:Z(p)). That is, r is simply the expression of substituting into Q for the free variable 19 the Z number of the expression for p.

    And it's perfectly ok if your head is spinning a little. These inside-outisms are a little dizzying. The trick is to work through them a step at a time.

    Now consider Sub (p (19:Z(p))). And Godel manipulates it.

    Sub (p (19:Z(p))) = Sub ((17 Gen Q) 19:Z(p) = 17 gen (Sub Q (19:Z(p)) = 17 Gen r.

    Stay with it, here - almost done!

    Now substitute p for y in 1. and 2. above. You get

    4. ~(x B (17 Gen r)) ---> Bew ( Sub (r, 17:Z(x))) 5.
    6. x B (17 Gen r) ---> Bew (Neg Sub (r, 17:Z(x))) 7.

    Suppose 17 Gen r provable, then there is an x that proves r. But then 7. would hold, meaning that the negation of r for all x is provable.

    Suppose 17 Gen r not provable, meaning for all x, r is not proved. Then 5. holds, and r is provable for some x. QED.

    And there in skeletal form, and I hope without too many typos, you have it. And nearly all of this is direct from Godel's paper, excepting some typography.
  • EricH
    581
    Nice explanation. :cheer:
  • Patterner
    553

    Thank you very much for your effort. I'll read that many times, and see if I can understand. But, honestly, the very first step makes no sense to me. I could say automobiles are 1, bicycles are 2, airplanes are 3, etc. Why would I think that makes any sense?
  • tim wood
    8.7k
    Why does the house you live in have a number? Of course it's an address, an aid to an organized ordering. Which if you're Japanese you probably wouldn't understand - in many places they don't have addresses as such.

    As to why, he wishes to "encode" propositions and proofs as numbers so that he can say, e.g., x B y, meaning that there is a relationship between the variables x and y, such that the argument encoded by x proves the proposition encoded by y, when appropriate substitutions are made for x and y. And as x B y is recursive (built up from more fundamental relationships), we know that it is decidable.

    In my opinion you're doing well if you get the general ideas involved and "get" the main formulas of the proof well enough so that you can step through them and explain them to yourself. And if you read the paper itself, which by then won't be too difficult, you will see that there are further and darker devils in the details, which need not be too much a matter of concern. There is also in the paper the proof that the consistency of arithmetic cannot be proved within arithmetic, which follows a short, similar kind of argument, worth a walk-through and that will leave you in a kind of awe..

    And give it a while; it takes a while. Like hitting a baseball or playing tennis, until you get into the rhythm of it, it's difficult; then comes a day when you start to get it and it's not so difficult.
  • FrancisRay
    400
    Thank you to all those who've spent time explaining this but for me it's probably a lost cause. I'm unable to make sense of it.

    My interest is in the philosophical implications, but there is a variety of views on this and I have no way to distinguish the wheat from the chaff.
  • Patterner
    553
    As to why, he wishes to "encode" propositions and proofs as numbers so that he can say, e.g., x B y, meaning that there is a relationship between the variables x and ytim wood
    Why is this a reasonable idea? I can assign numbers to anything. "Leaves" is 3. "Are" is 4. "Green" is 5. "Leaves are green" is 3 4 5. Now apply those numbers to the first primes, and multiply:
    2^3 x 3^4 x 5^5 = 2,025,000.
    Now I have a relationship between leaves and green.

    Why would I think I've done something useful or significant? As the saying (adjusted for inflation) goes, that and $3 will get me a cup of coffee.

    And why would I be surprised if something weird, like Gödel's incompleteness theorem, shows up? I would expect any number of inconsistencies and oddities to show up when I'm doing something unnatural like this. Why is it not equally unnatural for Gödel to assign number values to things like "and", "negation", and "all"?

    I guess there's no hope for me in this.
  • EricH
    581

    You might find this helpful: https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

    If nothing else it's a great read.
  • Patterner
    553

    It is, indeed, a great read. At least the few hundred pages I managed to read many years ago.
  • FrancisRay
    400
    Thanks. I read GEB many years ago and enjoyed it but was unable to see its importance. This may or may not be because it went over my head. I did like the idea of strange loops. The idea was not new to me but t liked the name he gave them. I'd been thinking of them as feedback loops, being a guitarist.who likes to use them. The world seems to be made out of these loops.

    I never quite grasped what Hofstaedter was trying to say, however, and this may be directly connected with my inability to see what Godel was saying. . .

    . .
  • tim wood
    8.7k
    Let's suppose you want to put a box inside of itself. Probably impossible with boxes. But self-reference is a little like that. How do you get a sentence to be inside of itself? Or, what Godel did, was to get a number to refer to itself while at the same time referring to propositions and arguments. A two-step process. First, figure out a way to map expressions into numbers, then a way to encode those numbers so they don't "infinitely" refer to themselves. Godel numbering is the first step, and that is pretty straightforward. And then convert that number into a Z number, e;g., sss...sss0. And all this recursively so that there is no question that you "can get there from here."

    The result is a sentence/number usually called G, which says of itself that it is undecidable. The way that it does that is to say that the sentence with the Godel number G is undecidable. And the magic, so to speak, is that the Godel number of G is just G itself.
  • jgill
    3.6k
    Many mathematicians and logicians cannot themselves be bothered to master Godel's incompleteness proof, for there isn't any payoff for doing so, and will probably content themselves with a technical understanding of the weaker version I mentioned above that is straightforward to prove and remember, and loses practically nothingsime

    Yes. Most of us are content with knowing a consistent system is incomplete. And most of us never encounter this situation.
  • Patterner
    553
    How do you get a sentence to be inside of itself?tim wood
    That's easy. Our language allows for sentences to refer to themselves, as Hofstadter demonstrated:
    '“Is white” is white.'
    '"Preceded by itself in quote marks yields a full sentence” preceded by itself in quote marks yields a full sentence.'


    Or, what Godel did, was to get a number to refer to itself while at the same time referring to propositions and arguments.tim wood
    This is what's tripping me up. Take the number 144. It doesn't refer to itself. Although it is the square of 12, it doesn't mean the square of 12, or refer to squares in general. 144 is also the sum of the the primes 47 and 97, but it doesn't mean the sum of those two primes, or refer to the idea of even numbers > 2 being the sum of two primes. And it doesn't refer anything else.

    Fibonacci numbers are be derived from a certain process. But that doesn't mean they are about that process. How are Godel numbers otherwise? Yes, a given equation can only produce one specific number. But that doesn't mean that number is about that equation, any more than 25 is about 4!+1.

    What am I not understanding? How did Godel make numbers self-referential?
  • tim wood
    8.7k
    That's easy. Our language allows for sentences to refer to themselves, as Hofstadter demonstrated:
    '“Is white” is white.'
    Patterner

    Not quite. What is your original sentence?

    What am I not understanding? How did Godel make numbers self-referential?Patterner
    The answer is just 30-odd pages away, actually in the first five pages, sec. 1, in sketch form, with some effort on your part. And not some three- or four-hundred page book.
  • Patterner
    553
    Not quite. What is your original sentence?tim wood
    Ok, I guess that's not referring to itself. Maybe, "This sentence is referring to itself." Or, in a more informative way, "This sentence has five words." Incorrectly, "This sentence had eighty three words."


    The answer is just 30-odd pages away, actually in the first five pages, sec. 1, in sketch form, with some effort on your part. And not some three- or four-hundred page book.tim wood
    I assume you mean his original paper? Any particular translation?
  • tim wood
    8.7k

    https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf
    The paper starts on page 173, or page 43 of the PDF.

    I find it very tiresome to read online. In my opinion this is the book to look for, The Undecidable, Ed. Martin Davis,
    https://www.abebooks.com/servlet/SearchResults?kn=the%20undecidable%2C%20ed.%20martin%20davis&sts=t&cm_sp=SearchF-_-topnav-_-Results&ds=20

    With luck maybe available through your library system. And it could be that by the time you get through p. 5, to sec. 2, you decide you've got enough.
  • Patterner
    553

    Thank you very much. I'll try these kindle version.

    Possibly no ebook of Davis. We'll see what happens.
  • TonesInDeepFreeze
    2.3k
    In context of proofs of incompleteness, we don't have numbers referring to themselves. Rather, numbers are used to refer to symbols, to strings of symbols (such as formulas) and to strings of strings of symbols (such as proofs).

    Context:

    (1) Godel's theorem was strengthened by Rosser. Subsequently, when we say 'Godel's incompleteness theorem' we usually actually mean the Godel-Rosser theorem. And Godel's notation is old-fashioned and hardly used anymore. And we now have much more streamlined expositions of the proof. For those reasons, to best understand the theorem, it is much better not to first study the original proof but rather more modern expositions of it. (Though, of course, after understanding the proof, we can deepen our appreciation and understanding, both mathematically and historically, by also going back to study the original proof).

    (2) A proper understanding of Godel-Rosser requires understanding basic symbolic logic and mathematical logic. For that I recommend this sequence of books:

    Logic: Techniques of Formal Reasoning - Kalish, Montague and Mar. For basic symbolic logic.

    Elements Of Set Theory - Enderton. For understanding the set theoretic rubrics and methods of mathematical logic.

    A Mathematical Introduction To Logic - Enderton. For a systematic treatment that works up to and includes a proof of Godel-Rosser.

    /

    Without at this juncture going into the proof of Godel-Rosser, I will outline (in rough oversimplifications that would need to be made rigorous for a truly proper exposition) some starting points, and pleading that I am rusty on the subject myself. This will at least clear up the matter of numbers and referring and give some crucial overall context.

    (3) We have formal languages (I'll just say 'languages'). A language has a set of symbols, a classification of the kinds of symbols, and rules for concatenating symbols into sequences of symbols that are the terms (names, both definite and indefinite) and the formulas (open statements, i.e. expressions that would be sentences if we filled in definite names for the variables). Certain of the formulas are sentences. The symbols, terms, formulas and sentences have no meaning merely by themselves.

    Some of the symbols are logical symbols: the sentential connectives (representing 'not', 'and', 'or' and 'implies') and the quantifiers ('all' and 'some'). Also, usually '='. The logical symbols are in every language. Non-logical symbols (such as '0', '+', etc.) are not in every language.

    In this context, we restrict discussion to languages such that there is an algorithm to determine whether any given symbol is a symbol of the language, whether any given sequence of symbols is a term, whether any given sequence of symbols is a formula, and whether any given formula is a sentence.

    (4) For a given language, we may provide an interpretation to give denotations for the symbols, meanings for the formulas, and a specification of what it means for a sentence to be true or to be false per the interpretation. Such interpretations are called 'models for the language'.

    (5) A set of axioms is a set of sentences from a given language. Some of the axioms are logical axioms, in the sense that they are true per every interpretation. Some of the axioms are non-logical axioms, in the sense that it is not the case that they are true per every interpretation.

    A proof system (I'll just say 'system') for a language is a specification of a set of axioms and a set of rules for proofs, which are certain finite sequences of formulas.

    In this context, we restrict discussion to systems such that there is an algorithm to determine whether any given sequence of formulas is a proof.

    Any sentence that is the last entry in a proof is called a 'theorem' of the set of axioms.

    A theory is a set of all theorems of a set of axioms.

    (6) A model is a model of a given theory if an only if every member of the theory is true in the model.

    (7) For every formula P, there is the formula ~P, which is the negation of P. With an interpretation, a sentence P is either true or false and not both, and ~P is true if and only if P is false.

    A theory is consistent if and only if there is no sentence P such that both P and ~P are in the theory.

    A theory is complete if and only if, for every sentence P, either P is in the theory or ~P is in the theory. A theory is incomplete if and only if it is not complete.

    A system is complete if and only if, for every sentence P that is true in every interpretation, P is a theorem of the axioms of the system. A system is complete if and only if it is not complete.

    So note that there are two different senses of 'complete', and two different senses of 'incomplete'.

    We talk about theories that are "sufficient to express a certain amount of arithmetic". However, usually, that is not given as a rigorous notion. Instead, in any exact context, we would specify which particular theory we mean.

    (8) Godel-Rosser is a theorem of mathematics about mathematical systems. It is usually presented with some rubrics and methods of set theory, but actually it can be carried out within merely the rubrics and methods of arithmetic. Moreover, it can be carried out within merely finitistic and constructive arithmetic. So, it is impeccable arithmetical reasoning that in principle could be reduced to primitive reckoning about finite sequences of stroke marks on a page. I don't know of any mathematical methods that a person would trust but that would leave the reasoning of Godel-Rosser as not trusted.

    (9) Godel-Rosser is the theorem that any consistent theory sufficient to express a certain amount of arithmetic is incomplete. Note that thereby any consistent extension of such a theory is incomplete.

    But rather than rely on the unrigorous notion "sufficient to express a certain amount of arithmetic", instead we mention particular theories such as PA (first order Peano arithmetic), Q (Robinson arithmetic), etc. Here I'll discuss PA.

    (10) The non-logical symbols for PA are:

    0 (intuitively, zero)
    S (inutivively, the successor of a number)
    + (intuitigely, addition)
    * (intuitively, multiplication)

    The non-logical axioms of PA (stated here semi-formally) are:

    For all n and m,

    0 is not Sn (intuitively, 0 is not a successor)

    If Sn = Sm, then n = m (intuitively, successor is one-to-one)

    n+0 = n

    n+Sm = S(n+m)

    n*0 = 0

    n*Sm = (n*m)+n

    For every formula P, if P(0) and for all n, if P(n) then P(n+1), then for all n, P(n). (intuitively if 0 has property P, and if for every n, n having property P implies that the successor of n has property P, then every number has property P)

    (11) One model of PA is called 'the standard model'. With the standard model:

    the universe of discourse is the set of natural numbers

    '0' stands for zero

    'S' stands for the successor operation

    '+' stands for addition

    '*' stands for multiplication

    When we say 'true' in context of arithmetic, that can be understood formally as 'true in the standard model'.

    (12) PA is one of theories that is incomplete by Godel-Rosser. So there is a sentence in the language of PA such that neither it nor its negation is a theorem. But either the sentence or its negation is true in the standard model. So there is a true sentence of arithmetic that is not true in PA. And note, that any consistent extension of PA is incomplete. But to do basic mathematics, we would want to have at least PA, so Godel-Rosser provides that in a common sense, we can't even a complete basic arithmetic, let alone a complete comprehensive mathematics (such as includes calclus, etc.) that subsumes arithmetic.

    (13) The proof of Godel-Rosser uses the arithmetization of syntax, which maps each symbol of PA to a different number. Then it maps each finite sequence of symbols to yet another number. Then it maps each finite sequence of finite sequences of symbols to yet another number. Such numbers are called 'Godel numbers'.

    So, each sentence in the language is mapped to a different Godel number.

    So, with the incompleteness proofs, numbers are used to refer to (to "code") symbols, strings of symbols, and strings of strings of symbols.

    Without going further into the proof at this juncture, we can preview by saying that the Godel sentence named 'G' is a sentence in the language of PA that has a Godel number n such that G "says" that the sentence with Godel number n is not provable in PA.

    So G "says": G is not provable in PA.

    That is the "self-reference" in play.

    The number n is the Godel number of G. And G mentions its own Godel number. So, the number of the sentence G is n and G also mentions n. This is not a number referring to itself. It is a sentence referring to its own Godel number.

    So we can dispense with inapposite puzzlements about "numbers referring to themselves".
  • TonesInDeepFreeze
    2.3k
    I'll pick some highlights in this thread.

    Either G is provable or not provableTheMadFool

    Either G is provable in T or G is not provable in T.

    1. G is provable. So G is unprovable
    2. G is not provable

    So, there is G in the theory T

    Have I got it right?
    TheMadFool

    No.
  • TonesInDeepFreeze
    2.3k
    For me the problem starts with 'This sentence is not provable'. This is meaningless. It does not state what is not provable.FrancisRay

    And the incompleteness proof doesn't say "this sentence". It's more complicated than that, and thoroughly rigorous.
  • TonesInDeepFreeze
    2.3k
    G is a number constructed following explicit rules.tim wood

    G is not a number. G is a formula. Then G is also coded by a number, which is its Godel number. The formula G and the number that codes G are two different things, though they can, in a certain sense, serve interchangeably in the particular context of the arithmetization of syntax.
  • TonesInDeepFreeze
    2.3k
    I need to find a professor of mathematics to sit down with me and help me understand it.Patterner

    You need to read a textbook. Then you could ask about what you don't understand. A few chats with a mathematician might give you an overview, but to actually understand the actual content, you need to study it.
  • TonesInDeepFreeze
    2.3k
    "The statement on the list at location G is not provable."tim wood

    No. As an illustration, it should be "The statement on the list at location n is not provable" and the location on the list for that statement is n.

    G is not a location nor a number. You are conflating the sentence G with the Godel number for the sentence G.
  • TonesInDeepFreeze
    2.3k
    It would help if I could find a statement that is true but provably undecidable, but I've never seen one. Do you have an example?FrancisRay

    Yes, the one that we show in the proof of incompleteness.

    By the way, it is not undecidable in every theory. It is undecidable in particular theories.

    Also, earlier in this thread, there were mentioned more substantive statements. They are usually mentioned in overviews, such as in encyclopedia articles, of incompleteness. Moreover, there is the major result about Diophantine equations.
  • TonesInDeepFreeze
    2.3k
    Godel's completeness conjecturesime
    [italics in original]

    The completeness theorem is not a mere conjecture. It is a theorem of mathematics. For any given consistent theory in a countable language, the proof of completeness provides a construction of a model of the theory. For an uncountable language (which is an unusual situation and not relevant to the languages for theories of which the incompleteness theorem pertains), still we have a model for each consistent theory though the proof of that is not constructive.
  • TonesInDeepFreeze
    2.3k
    I guess there's no hope for me in this.Patterner

    Sure there is. Just read a textbook on the subject. But if you're not interested in doing that, then indeed there's little hope that you'll understand the subject.

    This is a technical subject. It requires study. Just as, say, microbiology is a technical subject and you can't expect to understand results in microbiology without knowing at least the basics.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment