arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: Daryl McCullough on 14 Apr 2005 16:06 george says... >Daryl McCullough wrote: >> Quite often, an algorithm is described as a >> sequence of rules for manipulating figures on a piece >> of paper. > >That is TM-equivalent; the paper is the tape and the >figures are the output. Yes, TM-equivalent in some sense, but not TM-equal. It's an algorithm, and it is not a Turing machine program. So not every algorithm is a Turing machine program. It *can* be turned into a Turing machine program. That's what Church's thesis says---that every algorithm in the more general sense can be converted into an equivalent Turing machine program. >> Or an algorithm can be given in terms >> of abacus moves, or in terms of manipulations >> of index cards or piles of pebbles. > >All of those are so VERY TM-emulatable that it >is meaningful to speak of a TM as running THE SAME >algorithm as OPPOSED to the TM-analogue of the algorithm. Well, I'm not sure what notion of equality you are using for algorithms. >The thesis IS A PROPOSED DEFINITION of ALGORITHM, NOT of >"effectively computable function on naturals into naturals". >DESPITE the fact that Turing's original wording involved functions. Well, if it's a definition, it's boring. If it's a claim about what is effectively computable, then it is interesting, since it could (conceivably) turn out to be false. It turns out that the class of functions that are computable using register machines is exactly the same as the class of function computable using the lambda calculus, which is exactly the same as the class of function computable using Turing machines, which is exactly the same as the class of Godel's partial recursive functions. These were different concepts of "computable function" that turned out to be equivalent. That's an interesting result. -- Daryl McCullough Ithaca, NY
From: Bhupinder Singh Anand on 14 Apr 2005 18:08 On Apr 7, 8:02 am, george wrote: G>> One thing that misled me in that presentation was multiple ways of "interpreting" the act of "interpretation". <<G George ====== My apologies for the delayed response, but you had raised a significant point that, I realised after a while, reflected my own confusion regarding the formal and linguistic uses of the word 'interpretation' in my initial post. Perhaps my refining of the argument - in the light of Herb Enderton's and, more particularly, your comments - may help highlight this issue for a more constructive dialogue. (It may be useful to dustbin my ineffectual attempt to differentiate between recursive enumerability and algorithmic enumerability, although some other, interesting, points have, indeed, been raised as a consequence!) Can ZF define a consistent model for PA? ======================================== Classically, standard, first order PA is interpretable in standard, first order ZF, in the sense that the axioms of PA translate as theorems of ZF, and the rules of inference of PA are preserved under the translation. However, the significant question arises out of your comments: Is such translation also a formal, Tarskian, interpretation? More precisely, can ZF define a consistent model, say Int_ZF, for PA over an appropriately defined domain? If so, then, as a consequence of Tarskian satisfaction and truth in a model under a formal interpretation, the following argument suggests that every Arithmetical proposition should be decidable in the model from the axioms of a consistent ZF. ZF decides all Arithmetical propositions ======================================== Let M be a model of ZF. We denote the domain of M by D_M. DEF1: We define the union of all D_M as the domain, namely D_ZF, of the interpretation, namely Int_ZF, of PA in ZF. (In other words, Int_ZF is the model of PA defined by {D_ZF, ZF}. This should clear up the ambiguity pointed out by you.) DEF2: We say an n-tuple is an n-tuple of similar ZF-elements if all the elements of the n-tuple are from the same domain of a model M of ZF. META-THEOREM: All Arithmetical propositions are decidable from the axioms of ZF. PROOF: (i) Now, standard, first order PA is interpretable in standard, first order ZF, in the sense that the axioms of PA translate as theorems of ZF, and the rules of inference of PA are preserved under the translation. (Classically, this is expressed as the assertion that ZF is an extension of PA.) (ii) Following Tarski's definitions of the satisfaction and truth of a formula (say [R]) of a formal system of Arithmetic (such as PA) under an appropriate interpretation (say Int_ZF, where the domain, D_ZF, of the interpretation is the class of all elements that satisfy the axioms of ZF), we define: An atomic PA-formula, [R], with n free variables (and no quantifiers), is "true" under the interpretation Int_ZF, if, and only if, the corresponding, interpreted, ZF-formula [S] is "satisfied" by every n-tuple of similar ZF-elements in the domain, D_ZF, of the interpretation. (Tarskian definitions of the satisfiability, and truth, of other compound and quantified PA-formulas, follow as usual.) (iii) Clearly, for such conditions of "truth" and "satisfiability" to hold under the interpretation Int_ZF, they must also hold in every domain that satisfies the axioms of ZF (i.e., in every model M of ZF). (iv) By Goedel's completeness theorem for a first order theory, it follows that - assuming ZF is consistent - the PA-formula, [R], is "true" under the interpretation Int_ZF if, and only if, the interpreted ZF-formula, [S], is provable in ZF. (v) Again, following Tarski's definitions, the PA-formula [R] is "false" under the above interpretation Int_ZF, if, and only if, [~R] is "true" under the interpretation Int_ZF; and [R] is "true", under the above interpretation Int_ZF, if, and only if, [~R] is "false" under the interpretation Int_ZF. (In other words, the Tarskian "truth", or "falsity", of a formal proposition, under a well-defined interpretation, is always decidable in the interpretation.) (vi) Hence, if ZF is consistent, then every Arithmetical proposition is syntactically (i.e., independently of the semantic connotations of the above definitions of "truth" and "satisfiability") decidable from the axioms of ZF. CONCLUSION ========== So, either there is a flaw in the above reasoning, or, whilst the set of provable formulas of ZF is recursively enumerable, the sub-set of these that represents the true formulas of Arithmetic is not. (Note that the set of natural numbers is recursively enumerable, but its proper sub-set of the Goedel-numbers of true arithmetical formulas is not.) Regards, and thanks for your comments and observations, Bhup
From: george on 18 Apr 2005 10:31 Bhupinder Singh Anand wrote: > Can ZF define a consistent model for PA? > ======================================== Terminology matters. "Consistent model" is redundant. Every model of a theory, just by existing at all, confirms the consistency of the theory. The issue is not whether the MODEL is consistent (it is almost a grammatical error to apply the adjective "consistent" to the noun "model"), but rather, whether the THEORY that the model is a model OF, is consistent. If any old model of a theory exists, then the theory is consistent. > Classically, standard, first order PA is interpretable > in standard, first order ZF, in the sense that the axioms > of PA translate as theorems of ZF, It bears stressing just what is being translated into what, there. PA and ZF are in completely different languages. ZF only has 1 predicate (e == set-membership). PA is a much more complicated language. It has 0, +, *, either 1 or successor, and <. THESE must FIRST be "interpreted" or "translated" into the language of ZF. THOSE TRANSLATIONS of PA's axioms -- NOT PA's axioms themselves -- will then be provable as theorems from the axioms of ZF. There is more than one possible translation and it is non-trivial to get it right; that's why HE had to ask for the best/right version in renewing the thread. > and the rules of inference of PA Again, application error. You cannot apply "rules of inference" to PA. PA is an axiom-set. It DOESN'T HAVE rules of inference. Rules of inference are had by LOGICs, NOT axiom-sets. The logic that we are using in the context of this discussion is [classical]first- order[predicate] logic. IT has rules of inference. It also has directives defining something called a first- order language (the sentences that this logic's rules of inference are defined-as-inferring-among should be phrased in first-order languages). There are *2nd*-order versions of both of these axiom-sets, but we are here thinking about and dealing with first-order PA and first-order ZF. Since the whole framework of our discussion is first-order logic, that logic's inference rules are being applied to BOTH axiom-sets and BOTH of their corresponding first- order languages. > are preserved under the translation. In the sense that we are translating from one first-order language into another, with intent to apply the same rules of inference to sentences from both languages, yes. > However, the significant question arises out of your > comments: > > Is such translation also a formal, Tarskian, > interpretation? No. That's why I had to pause to mention two possible different meanings of "interpretation". > More precisely, can ZF define a consistent model, > say Int_ZF, for PA over an > appropriately defined domain? ZF can define myriad models for PA. Model-definition is WHAT ZF IS *for*. It's WHY WE CARE about it. ZF is the *default* "model-description-language", or meta- theory, for first-order logic IN GENERAL. > If so, then, as a consequence of Tarskian satisfaction > and truth in a model under a formal interpretation, the > following argument suggests that every Arithmetical > proposition should be decidable in the model > from the axioms of a consistent ZF. It is, but that's not just a property of THAT model: that's a property of ALL models. If you have a theory Th and a candidate model Mc, then Mc is not ACTUALLY a model of Th, the candidate does not WIN election, UNLESS it in fact decides every sentence of the theory. ANYthing that leaves some sentence of the theory undecided is, FOR THAT VERY REASON, NOT a model of the theory. It is at best a partial specification of a model. Of course, sometimes in ZF you can fudge this by saying that, sure, your model decides everything, you just don't YET KNOW HOW it decides SOME sentences. > ZF decides all Arithmetical propositions > ======================================== Well, no, actually, it doesn't. One problem is that the language of arithmetic and the language of ZF are different. The other is that different models of ZF may have different opinions about some of these questions. > Let M be a model of ZF. That's the whole problem: *a* model. Different models are going to give different answers. > We denote the domain of M by D_M. > > DEF1: We define the union of all D_M That is hopelessly ambiguous. D_M is the domain of M, and M was fixed; there was only 1 M, and therefore there is only 1 D_M. If you meant over all M, as over all models of ZF, then you can't do that *in* ZF. > as the domain, namely D_ZF, of the interpretation, you mean the domain of THAT interpretation, of your personal chosen particular interpretation (a great many others are possible) > namely Int_ZF, of PA in ZF. You can't do this in ZF. The problem is that ANY INFINITE SET WHATSOEVER can be a model for PA, and for ZF. It's very dangerous to talk about a model of ZF in ZF. The problem here is that ZF doesn't have a universal set. In every MODEL of ZF, though, the domain IS the universal set FOR THAT MODEL. > > (In other words, Int_ZF is the model of PA defined by {D_ZF, ZF}. D_ZF doesn't exist in ZF; it would have to be the universal set, and ZF doesn't have a universal set.
From: Bhupinder Singh Anand on 18 Apr 2005 17:14 On Apr 18, 7:31 am, george wrote: G>> "Consistent model" is redundant. <<G George ===== You're right. G>> There is more than one possible translation...<<G You're right G>> The logic that we are using in the context of this discussion is [classical]first-order[predicate] logic. <<G OK G>> In the sense that we are translating from one first-order language into another, with intent to apply the same rules of inference to sentences from both languages, yes. <<G Yes, right. G>> That's why I had to pause to mention two possible different meanings of " interpretation". OK, noted. G>> ZF is the *default* "model-description-language", or meta-theory, for first-order logic IN GENERAL. OK. G>> It is, but that's not just a property of THAT model: that's a property of ALL models. OK. G>> One problem is that the language of arithmetic and the language of ZF are different.<<G OK. G>> Different models are going to give different answers. <<G OK. G>> If you meant over all M, as over all models of ZF, then you can't do that *in* ZF. <<G You're right. The domain D_ZF is not a set in ZF. G>> ... you mean the domain of THAT interpretation, of your personal chosen particular interpretation (a great many others are possible) <<G Precisely. G>> You can't do this in ZF. <<G Right, one cannot. G>> It's very dangerous to talk about a model of ZF in ZF. <<G Yes indeed. ZF is not the model, but only the language into which PA is being translated. G>> The problem here is that ZF doesn't have a universal set. <<G You're right, it doesn't. G>> D_ZF doesn't exist in ZF; it would have to be the universal set, and ZF doesn't have a universal set. <<G You're right, D_ZF doesn't exist in ZF since the elements of D_ZF are, collectively, the elements in the various models of ZF. As you have noted, the domains of the models of ZF need not, and, possibly, cannot be in ZF. The domain D_ZF can, perhaps, be viewed as a mathematical object that is similar to a proper class of NBG (in which ZF can be translated co-consistently). The properties of D_ZF that we appeal to are only those that are essential for any of its elements to be a member of some model of ZF; they need not be necessarily set-theoretic. Regards, Bhup
From: george on 21 Apr 2005 13:22
BSA> The domain D_ZF can, perhaps, be viewed as a mathematical > object that is similar to a proper class of NBG (in which ZF can be > translated co-consistently). This is not going to work. ANY infninite set CAN be MADE to be the domain of *a* model of ZF. ZF has a model whose domain is the natural numbers, in which every set, no matter how huge and uncountable it may be, is encoded as a natural number. There is NO SUCH THING as "D_ZF". ANY infinite set can be the domain of *a* model of ZF. > The properties of D_ZF that we appeal to are only those that are > essential for any of its elements to be a member of some model of ZF; Then that is no properties at all; no properties are essential to that. Any infinite set whatever, REGARDLESS OF THE PROPERTIES OF ITS ELEMENTS, can be the domain of a model of ZF. Practically, the only property its elements need to have is that we know countably infinitely many different names for them and can tell them apart. > they need not be necessarily set-theoretic. I don't think you know what you mean by "set-theoretic". Your left big toe becomes set-theoretic as soon as you define a model of ZF that interprets your left big toe as the empty set. We have somewhat lost the original thrust of your argument, which was, basically, that by translating PA into ZF,we can decide arithmetic. You were apparently hoping that some individual model of ZF would decide the sentences that PA didn't prove or disprove. Well, it will, but that is no help, because every individual model of PA *also* decides the sentences that PA itself (as an axiom-set) fails to prove or disprove. What it means for a sentence (over the language of PA) to be undecidable (from PA) is that some models of PA decide it one way, and other models of PA decide it the other way. Translating PA into ZF won't change this. It will simply become the case that some models of ZF decide the (translated) sentences one way and other models of ZF decide them the other way. ZF itself was already incomplete purely by virtue of being more complicated than PA. The interesting question becomes, is there even ONE undecidable sentence of PA that becomes decidable under ZF after you translate it. And even this may not have a clear answer since there is more than one possible translation. In any case, talking about D_ZF as some union of domains of models of ZF is not going to help; if it is big enough to achieve any relevant mode of generality then it is too big to exist (in ZF), and if it is not, then you can get a different answer just by studying the domains that it left out. |