Re: A couple of book questions...(one of them about Completeness)
Jim Choate wrote: Complete means that we can take any and all -legal- strings within that formalism and assign them -one of only two- truth values; True v False. Getting much closer. Complete means we can, within the formalism, _prove_ that all universally valid statements within the formalism are true. That's it. Little more to say. Except that at the time (1930)(in his doctoral thesis, later The completeness of the axioms of the functional calculus of logic, in which he proved the completeness of FOL) Godel only proved that such proofs exist, and it was much later (1965?-ish) that a constructive procedure for proof generation was published... though he did also prove (for FOL, and the usual suspect logics, and some other logics) that that is the only way a logic _could_ be complete - and that, in those cases, the earlier disputed meanings of complete are identical/the differences are irrelevant; - and that his definition (above) is sufficient, eg (but not ie) that proof of negation is not required. -- Peter Fairbrother
Re: A couple of book questions...(one of them about Completeness)
On Tue, 3 Dec 2002, Tyler Durden wrote: Well, this is quite a post, and I agree with most of it. As for the Godel stuff, there's a part of it with which I disagree (or at least as far as I take what you said). -I- didn't say this stuff, the people who did the original work did. Go read their work. If you want to compare something mathematically you -must- use the same axioms and rules of derivation. The -only- discussion there is one of two parts: Is the sequence of applications/operators valid? (ie Proof) Is the sequence terminal, does it leave room for more derivation? (ie Publish or Perish) Well, not necessarily, unless I misunderstand you. Take the Fermat's last theorem example I gave (a^n+b^n=c^n for a,b,c,n integers but n2). And let's say I want to prove (or disprove) the statement This has no solution for n2. There are two 'distinct' methods of determining the validity of the statement. One is by what is normally considered a proof. In other words, by building up from axioms using the logical rules of the system. The other is to actually find a solution for a,b,c and n. That is -also- considered a proof, it's correct name is Proof by Exhaustion. Just about anybody who follows this approach will become exhausted too ;) More importantly, they have to use the same base axioms as any other proof. So your distinction is specious. As to the bigger question, you are of course welcome to your opinion. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
Jim Choate wrote: Complete means that we can take any and all -legal- strings within that formalism and assign them -one of only two- truth values; True v False. Getting much closer. Complete means we can, within the formalism, _prove_ that all universally valid statements within the formalism are true. That's it. Little more to say. Except that at the time (1930)(in his doctoral thesis, later The completeness of the axioms of the functional calculus of logic, in which he proved the completeness of FOL) Godel only proved that such proofs exist, and it was much later (1965?-ish) that a constructive procedure for proof generation was published... though he did also prove (for FOL, and the usual suspect logics, and some other logics) that that is the only way a logic _could_ be complete - and that, in those cases, the earlier disputed meanings of complete are identical/the differences are irrelevant; - and that his definition (above) is sufficient, eg (but not ie) that proof of negation is not required. -- Peter Fairbrother
Re: A couple of book questions...(one of them about Completeness)
On Mon, 2 Dec 2002, Tyler Durden wrote: That any particular string can be -precisely- defined as truth or false as required by the definition of completeness, is what is not possible. Here we come down to what appears to be at the heart of the confusion as far as I see it. True, depending on who's saying it (even in a discussion of Godelian Completeness), may be different. Mathematical types may define true as being provably true, meaning something like this statement can be derived from the other statements in my system by building up from logic plus the fundamental axioms. If you're using different definitions of 'true' then you're not using the same mathematics. You're in fact comparing apples and oranges. If you want to compare something mathematically you -must- use the same axioms and rules of derivation. The -only- discussion there is one of two parts: - Is the sequence of applications/operators valid? (ie Proof) - Is the sequence terminal, does it leave room for more derivation? (ie Publish or Perish) And no, there is zero confusion on what true means under Godel or Cauchy. An individual (or a large group of them) may not understand it, but that speaks to them, not it. I find that when I just can't 'get it' instead of bitching about how hard it is or how little sense it makes, I look inward. I ask myself what personality trait, learned behavior, or mode of thinking is blocking my advancement? And then I try to deal with that. When I think I've made progress I come back to the problem and take a crack at it again. The reality is that most people have problems grasping concepts or ideas because there is a conflict with other ideas/concepts they hold dear and near. In most cases of mental block it is an emotional issue not an intellectual one. People have a hard time learning not because they are stupid but because they don't deal with their emotional landscape effectively. The biggest problem most people have is lack of self-confidence [1]. Western society is training their citizens to be victims of authority (which is inherently against too rapid change as it effects their stability via the law of unintended consequences, they never grasp that simply because you 'own' something today is no right to own it tomorrow. Nor does authority provide a rational for 'breaking eggs'. They are afraid of uncertainty and chaos and want to control 'you' to minimize it, to 'their' best interests.). Eastern society has already been there and done that. Learning is auto-catalytic and iterative, it requires the ability to question the most basic assumptions. Decarte's comments about open minds being one which at least once questions everything comes to mind (though to be clear I lean toward Hobbes myself). Freedom -is- Security. [1] Ruckers Rules 1 Yes, there is a better way 2. Yes, -you- can do it 3. Seek the Gnarl! -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
Well, this is quite a post, and I agree with most of it. As for the Godel stuff, there's a part of it with which I disagree (or at least as far as I take what you said). If you want to compare something mathematically you -must- use the same axioms and rules of derivation. The -only- discussion there is one of two parts: Is the sequence of applications/operators valid? (ie Proof) Is the sequence terminal, does it leave room for more derivation? (ie Publish or Perish) Well, not necessarily, unless I misunderstand you. Take the Fermat's last theorem example I gave (a^n+b^n=c^n for a,b,c,n integers but n2). And let's say I want to prove (or disprove) the statement This has no solution for n2. There are two 'distinct' methods of determining the validity of the statement. One is by what is normally considered a proof. In other words, by building up from axioms using the logical rules of the system. The other is to actually find a solution for a,b,c and n. In this case the statement will have been disproven, but not by a series of logical statements and axioms. It is now seen to be untrue, but not via the methods of proof. Thus, the statement is untrue, and (possibly) unprovably untrue (which is the same thing as saying the statement's negation is unprovably true). Now if subsequent truths need to be made but require the statement above (a^n+b^n=c^n has no solution for n2), even though we know that it is true (or untrue, in my example above), to build subsequent truths we need to include this statement as an axiom even though we know it's true. It's true, but unprovable. But perhaps this is what you meant. And no, there is zero confusion on what true means under Godel or Cauchy. Yes, I agree, and the confusion to which I referred had to do with the term true as it seemed to be used by various parties in the conversation. From this alone I think a big take away here is that true in the Godelian sense means something probably quite different from what many believe it to be. The reality is that most people have problems grasping concepts or ideas because there is a conflict with other ideas/concepts they hold dear and near. In most cases of mental block it is an emotional issue not an intellectual one. People have a hard time learning not because they are stupid but because they don't deal with their emotional landscape effectively. Couldn't agree more. Reason is the whore of desire. Well, not always, but its clear to me that most of the time we start with the conclusion we want and then work backwards! Most human beings seem to stumble upon some little piece of flotsam and then cling onto it for dear life, not knowing they can actually swim (or perhaps they don't need to!). I don't consider myself an exception, except for the fact that knowing this, I constantly try to expose myself to information and experiences that do not correspond to what I currently believe. As the spanish mystic St John of the Cross wrote: To come to be what you are not, you must go by a way in which you are not. To come to know what you know not, you must go by a way in which you know not. _ Tired of spam? Get advanced junk mail protection with MSN 8. http://join.msn.com/?page=features/junkmail
Re: A couple of book questions...(one of them about Completeness)
On Mon, 2 Dec 2002, Tyler Durden wrote: That any particular string can be -precisely- defined as truth or false as required by the definition of completeness, is what is not possible. Here we come down to what appears to be at the heart of the confusion as far as I see it. True, depending on who's saying it (even in a discussion of Godelian Completeness), may be different. Mathematical types may define true as being provably true, meaning something like this statement can be derived from the other statements in my system by building up from logic plus the fundamental axioms. If you're using different definitions of 'true' then you're not using the same mathematics. You're in fact comparing apples and oranges. If you want to compare something mathematically you -must- use the same axioms and rules of derivation. The -only- discussion there is one of two parts: - Is the sequence of applications/operators valid? (ie Proof) - Is the sequence terminal, does it leave room for more derivation? (ie Publish or Perish) And no, there is zero confusion on what true means under Godel or Cauchy. An individual (or a large group of them) may not understand it, but that speaks to them, not it. I find that when I just can't 'get it' instead of bitching about how hard it is or how little sense it makes, I look inward. I ask myself what personality trait, learned behavior, or mode of thinking is blocking my advancement? And then I try to deal with that. When I think I've made progress I come back to the problem and take a crack at it again. The reality is that most people have problems grasping concepts or ideas because there is a conflict with other ideas/concepts they hold dear and near. In most cases of mental block it is an emotional issue not an intellectual one. People have a hard time learning not because they are stupid but because they don't deal with their emotional landscape effectively. The biggest problem most people have is lack of self-confidence [1]. Western society is training their citizens to be victims of authority (which is inherently against too rapid change as it effects their stability via the law of unintended consequences, they never grasp that simply because you 'own' something today is no right to own it tomorrow. Nor does authority provide a rational for 'breaking eggs'. They are afraid of uncertainty and chaos and want to control 'you' to minimize it, to 'their' best interests.). Eastern society has already been there and done that. Learning is auto-catalytic and iterative, it requires the ability to question the most basic assumptions. Decarte's comments about open minds being one which at least once questions everything comes to mind (though to be clear I lean toward Hobbes myself). Freedom -is- Security. [1] Ruckers Rules 1 Yes, there is a better way 2. Yes, -you- can do it 3. Seek the Gnarl! -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
Well, this is quite a post, and I agree with most of it. As for the Godel stuff, there's a part of it with which I disagree (or at least as far as I take what you said). If you want to compare something mathematically you -must- use the same axioms and rules of derivation. The -only- discussion there is one of two parts: Is the sequence of applications/operators valid? (ie Proof) Is the sequence terminal, does it leave room for more derivation? (ie Publish or Perish) Well, not necessarily, unless I misunderstand you. Take the Fermat's last theorem example I gave (a^n+b^n=c^n for a,b,c,n integers but n2). And let's say I want to prove (or disprove) the statement This has no solution for n2. There are two 'distinct' methods of determining the validity of the statement. One is by what is normally considered a proof. In other words, by building up from axioms using the logical rules of the system. The other is to actually find a solution for a,b,c and n. In this case the statement will have been disproven, but not by a series of logical statements and axioms. It is now seen to be untrue, but not via the methods of proof. Thus, the statement is untrue, and (possibly) unprovably untrue (which is the same thing as saying the statement's negation is unprovably true). Now if subsequent truths need to be made but require the statement above (a^n+b^n=c^n has no solution for n2), even though we know that it is true (or untrue, in my example above), to build subsequent truths we need to include this statement as an axiom even though we know it's true. It's true, but unprovable. But perhaps this is what you meant. And no, there is zero confusion on what true means under Godel or Cauchy. Yes, I agree, and the confusion to which I referred had to do with the term true as it seemed to be used by various parties in the conversation. From this alone I think a big take away here is that true in the Godelian sense means something probably quite different from what many believe it to be. The reality is that most people have problems grasping concepts or ideas because there is a conflict with other ideas/concepts they hold dear and near. In most cases of mental block it is an emotional issue not an intellectual one. People have a hard time learning not because they are stupid but because they don't deal with their emotional landscape effectively. Couldn't agree more. Reason is the whore of desire. Well, not always, but its clear to me that most of the time we start with the conclusion we want and then work backwards! Most human beings seem to stumble upon some little piece of flotsam and then cling onto it for dear life, not knowing they can actually swim (or perhaps they don't need to!). I don't consider myself an exception, except for the fact that knowing this, I constantly try to expose myself to information and experiences that do not correspond to what I currently believe. As the spanish mystic St John of the Cross wrote: To come to be what you are not, you must go by a way in which you are not. To come to know what you know not, you must go by a way in which you know not. _ Tired of spam? Get advanced junk mail protection with MSN 8. http://join.msn.com/?page=features/junkmail
Re: A couple of book questions...(one of them about Completeness)
That any particular string can be -precisely- defined as truth or false as required by the definition of completeness, is what is not possible. Here we come down to what appears to be at the heart of the confusion as far as I see it. True, depending on who's saying it (even in a discussion of Godelian Completeness), may be different. Mathematical types may define true as being provably true, meaning something like this statement can be derived from the other statements in my system by building up from logic plus the fundamental axioms. In Godel, in any formal system there are statements that are true but unprovable in that system. This would seem to render the notion of true above meaningless. But what it means in a practical sense is that there may be truisms (such as, there exists no solution to the problem of a^n + b^n = c^n, where a,b,c and n are integers and n2), which are true (and let's face it, this statement is either true or false) but which can not be proven given the fundamental axioms of the system. Thus, in order to build more mathematics with this truth, it must be incoroprated as an axiom. (Godel also says that after this incoporation is done, there will now be new unprovable statements.) I originally mentioned Godel in the context of the notion of the dificulty of factoring large numbers. My point was that its possible that... 1) Factoring is inherently difficult to do, and no mathematical advances will ever change that. and 2) We may never be able to PROVE 1 above. Thus, we may have to forever live with the uncertainty of the difficulty of factorization. _ The new MSN 8: smart spam protection and 2 months FREE* http://join.msn.com/?page=features/junkmail
Re: A couple of book questions...(one of them about Completeness)
That any particular string can be -precisely- defined as truth or false as required by the definition of completeness, is what is not possible. Here we come down to what appears to be at the heart of the confusion as far as I see it. True, depending on who's saying it (even in a discussion of Godelian Completeness), may be different. Mathematical types may define true as being provably true, meaning something like this statement can be derived from the other statements in my system by building up from logic plus the fundamental axioms. In Godel, in any formal system there are statements that are true but unprovable in that system. This would seem to render the notion of true above meaningless. But what it means in a practical sense is that there may be truisms (such as, there exists no solution to the problem of a^n + b^n = c^n, where a,b,c and n are integers and n2), which are true (and let's face it, this statement is either true or false) but which can not be proven given the fundamental axioms of the system. Thus, in order to build more mathematics with this truth, it must be incoroprated as an axiom. (Godel also says that after this incoporation is done, there will now be new unprovable statements.) I originally mentioned Godel in the context of the notion of the dificulty of factoring large numbers. My point was that its possible that... 1) Factoring is inherently difficult to do, and no mathematical advances will ever change that. and 2) We may never be able to PROVE 1 above. Thus, we may have to forever live with the uncertainty of the difficulty of factorization. _ The new MSN 8: smart spam protection and 2 months FREE* http://join.msn.com/?page=features/junkmail
Re: CDR: Re: A couple of book questions...(one of them about Completeness)
hi, --- Jim Choate [EMAIL PROTECTED] wrote: hi, On Sat, 30 Nov 2002, Peter Fairbrother wrote: Godel didn't invent the term though, and may not have said this is the/my definition of completeness. I haven't read them for some time, and can't remember. He may well have assumed his readers would already know it. We can't define completeness. Of course he didn't, he just made it irrelevant since you can't prove the truthfullness of all the propositions requird to prove completeness. Bottom line, mathematics may be complete but until somebody invents a meta-mathematics broader than mathematics it will remain -an unprovable proposition within mathematics, even in principle.- Mathametics is always incomplete,always. Regards Sarath. Adios. -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org __ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
Re: A couple of book questions...(one of them about Completeness)
On Sun, 1 Dec 2002, Sarad AV wrote: --- Jim Choate [EMAIL PROTECTED] wrote: On Sun, 1 Dec 2002, Sarad AV wrote: We can't define completeness. We can define it, as has been done. okay,I get what you mean,thank you. How ever how do you 'precisely' define completeness? There were a couple of examples in the message you replied to. There are different sorts of completeness as well. You might also look into some of the references I provided. I intentionaly use the Dover books as much as possible because they are available all over, and they are very inexpensive but high quality. The best example I've seen is the 'Catalog' problem. Basically you have a bunch of books and two catalogs. One catalog has books which don't list themselves, and the other catalog only has books that do list themselves. How do you list the two catalogs? (You probably want to google it for a better description of the exact conditions and boundary values) -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
hi, How ever how do you 'precisely' define completeness? There were a couple of examples in the message you replied to. There are different sorts of completeness as well. You might also look into some of the references I provided. Okay,I ask a legitimate question,how do you argue it is correct and precise,we can't,thats why it is undefinable. Regards Sarath. __ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
Re: A couple of book questions...(one of them about Completeness)
On Sun, 1 Dec 2002, Sarad AV wrote: --- Jim Choate [EMAIL PROTECTED] wrote: On Sun, 1 Dec 2002, Sarad AV wrote: We can't define completeness. We can define it, as has been done. okay,I get what you mean,thank you. How ever how do you 'precisely' define completeness? There were a couple of examples in the message you replied to. There are different sorts of completeness as well. You might also look into some of the references I provided. I intentionaly use the Dover books as much as possible because they are available all over, and they are very inexpensive but high quality. The best example I've seen is the 'Catalog' problem. Basically you have a bunch of books and two catalogs. One catalog has books which don't list themselves, and the other catalog only has books that do list themselves. How do you list the two catalogs? (You probably want to google it for a better description of the exact conditions and boundary values) -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
On Sun, 1 Dec 2002, Sarad AV wrote: We can't define completeness. We can define it, as has been done. What we can't do is -prove- any set of rules of arrangement that describe symbol manipulation as -complete- -within the rules of arrangement-. Complete means that we can take any and all -legal- strings within that formalism and assign them -one of only two- truth values; True v False. The fundamental problem is axiomatic. The rules define -all- statements as being -either true or false-, no other possibility is allowed -by principle-. We create two lists 'true' and 'false', we are -required- to put -any- string (or formula in Godel-speak, or 'sequence' and 'inside or outside' with regard to Cauchy Completeness) we write in one of these two, and only these two lists. However, as Godel shows, we -can- write strings (some of them are quite simple which is what makes it so shocking) that we can't put in -either- of these lists. There is -no- place to write it down. It just hangs there in Limbo. There is no -I don't know- list. There is a parallel (but I don't think fully equivalent) situation with Geometry and Euclid's V Postulate. It turns out not to be so universal after all. One approach to dealing with this situation is Para-Consistent Logic. Time will tell how usefull that is. Personal Note: I don't believe that the value of Godel is really the utility of mathematics as much as demonstrating the imperfect reasoning of -all- human beings. Mankind, all mankind, is on a hunt for universality in a quest for transcending the mortal coil. It's the concept of 'transcendence' that keeps getting us in trouble. Intelligence isn't all it's cracked up to be. We arrive at truth not by reason only, but also by the heart. Blaise Pascal Intellectual brilliance is no guarantee against being dead wrong. David Fasold It is not clear that intelligence has any long-term survival value. Stephen Hawkings -- We don't see things as they are, [EMAIL PROTECTED] we see them as we are. www.ssz.com [EMAIL PROTECTED] Anais Nin www.open-forge.org
Re: A couple of book questions...(one of them about Completeness)
Jim Choate wrote: With regard to completeness, I have Godel's paper (On Formally Undecidable Propositions of Principia Mathematica and Related Systems, K. Godel, ISBN 0-486-66980-7 (Dover), $7 US) and if somebody happens to know the section where he defines completeness I'll be happy to share it. That's* the wrong paper. You want The completeness of the axioms of the functional calculus of logic which is a 1930 rewrite of his doctoral dissertation. This is known as Godel's completeness theorem. Godel didn't invent the term though, and may not have said this is the/my definition of completeness. I haven't read them for some time, and can't remember. He may well have assumed his readers would already know it. Or try Some metamathematical results on completeness and consistency or On completeness and consistency from 1931. Reports of his 1930 lecture would also be useful. Afaik they aren't available on the 'net. Some or all of these are in: From Frege to Gödel, Jean van Heijenoort, Harvard University Press. ISBN 0-674-32450-1 , (recently ?reissued? as ISBN 0-674-32449-8 at around $25, but I haven't seen the new version) which should also give you the history of the term. -- Peter Fairbrother * The one mentioned is available at http://www.ddc.net/ygg/etext/godel/godel3.htm if anyone wants to have a look. It's commonly called his incompleteness theorem paper, but the paper doesn't talk directly about completeness, rather about the existence of undecidable propositions - however the incompleteness name is a bit of a giveaway... if an undecideable proposition exists within a system then the system is incomplete.
Re: A couple of book questions...(one of them about Completeness)
Jim Choate wrote: With regard to completeness, I have Godel's paper (On Formally Undecidable Propositions of Principia Mathematica and Related Systems, K. Godel, ISBN 0-486-66980-7 (Dover), $7 US) and if somebody happens to know the section where he defines completeness I'll be happy to share it. That's* the wrong paper. You want The completeness of the axioms of the functional calculus of logic which is a 1930 rewrite of his doctoral dissertation. This is known as Godel's completeness theorem. Godel didn't invent the term though, and may not have said this is the/my definition of completeness. I haven't read them for some time, and can't remember. He may well have assumed his readers would already know it. Or try Some metamathematical results on completeness and consistency or On completeness and consistency from 1931. Reports of his 1930 lecture would also be useful. Afaik they aren't available on the 'net. Some or all of these are in: From Frege to Gödel, Jean van Heijenoort, Harvard University Press. ISBN 0-674-32450-1 , (recently ?reissued? as ISBN 0-674-32449-8 at around $25, but I haven't seen the new version) which should also give you the history of the term. -- Peter Fairbrother * The one mentioned is available at http://www.ddc.net/ygg/etext/godel/godel3.htm if anyone wants to have a look. It's commonly called his incompleteness theorem paper, but the paper doesn't talk directly about completeness, rather about the existence of undecidable propositions - however the incompleteness name is a bit of a giveaway... if an undecideable proposition exists within a system then the system is incomplete.