arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: george on 22 Apr 2005 17:21 Bhupinder Singh Anand wrote: > 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. No, I did NOT note this. The domains, of EVERY theory of the kind we are talking about (recursively axiomatizable, first-order), MUST be "in" ZF, because ZF IS THE *DEFAULT* model-description language! This is a habit of the community! IF YOU WANT to talk about a model for something, you FIRST talk about a SET that is THE DOMAIN of the model! EXCEPT when you are talking about ZF itself, the domain of your model IS ALWAYS, BY DEFAULT, a set in ZF. THAT'S WHAT ZF IS *for*, that's its primary raison d'etre and its primary contribution to humanity, is to give us some lingo for DEFINING MODELS. You can, if you're perverse enough, EVEN use ZF to define the domain of A MODEL OF ZF, but you risk confusing yourself about what level you're on, if you do. Moreover, if you do that, then you KNOW that the domain you've chosen IS NOT the "real" domain of ZF; you know that much larger domains are possible. >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). OK. In that case you would be doing your model theory in NBG instead of ZF and you would be trying to insist that you could define a model whose domain was a proper class as opposed to a set. Or maybe you could even come up with a definition of model-in-NBG where the domain was ALWAYS a class and whether it was-or-wasn't-proper didn't even matter. BUT I DOUBT IT. I think if you tried to do model theory in NBG, it would AGAIN turn out that you NEED the domains-of-models to actually be sets. My point in any case is that trying to take some union of all the domains of all the possible models of ZF simply is not going to work. There are philosophical issues in "possible models". The Tarskian paradigm defining "model" doesn't actually say what a domain is (only that it "has" elements), and it certainly doesn't say what an ELEMENT of a domain is (that is INTENTIONALLY wholly untranslated; we WANT you to be free to pick, literally, anything). There is no way to fit that totality of possible "interpretands" into ANYbody's set theory. More to the point, suppose you DID have a domain whose elements weren't set-theoretic, and you had a model using that domain: that model is isomorphic to ANOTHER model whose domain- elements ARE sets. So why even bother?
From: Bhupinder Singh Anand on 26 Apr 2005 22:53 On Apr 21, 10:22 am, george wrote: G>> 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. ... 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. <<G Interesting. The above appears to hold that every set is denumerable!? Is this intentional? G>> We have somewhat lost the original thrust of your argument, which was, basically, that by translating PA into ZF,we can decide arithmetic. <<G Not merely by 'translating', but by defining a domain in which the ZF translations of PA formulas can be effectively defined as 'true' or 'false'. G>> You were apparently hoping that some individual model of ZF would decide the sentences that PA didn't prove or disprove. <<G The problem that I find in every individual model of ZF is that we need some effective method for deciding whether a ZF proposition is 'true' or 'false' in the model. If the domain of every model of ZF is, again, a ZF set - as I understand you to suggest - then there seems to be an element of circularity involved in such decidability. I was seeking to avoid such circularity by attempting to define the 'truth' and 'falsity' of PA propositions in terms of ZF-provability in a model of PA, not in terms of ZF-truth in some model of ZF. G>> 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. ... 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. <<G These, no doubt, reflect accepted interpretations of Goedel's incompleteness theorem. However, the questions arise: Are such interpretations definitive, and are there substantive grounds for seeking alternative interpretations of Goedel's reasoning? For instance, consider Goedel's 'unprovable but true' PA formula [(Ax)R(x, p)]. This is unprovable from the axioms of Peano Arithmetic, but such that [R(n, p)] is provable for any given numeral [n]. Hence, under the standard interpretation, the corresponding arithmetical proposition, R(x, p), is true for any given natural number n. (Here, [R(x, y)] is a PA-representation of Goedel's primitive recursive relation ~xB(Sb(y 19|Z(y))), and p is the Goedel-number of the PA-formula [(Ax)R(x, y)].) Now, by definition, the arithmetical relation R(x, p) is instantiationally equivalent to the primitive recursive relation ~xB(Sb(p 19|Z(p))). Further, again by Goedel's definitions, the primitive recursive relation, ~xB(Sb(p 19|Z(p))), symbolically expresses the assertion that: (*) x is not the Goedel number of a PA-proof of [(Ax)R(x, p)]. Since Goedel has shown that R(x, p) is true for all natural numbers - as also is ~xB(Sb(p 19|Z(p))) - it follows that the assertion (*) is true for all natural numbers, and, so, there is no proof of the PA-proposition [(Ax)R(x, p)] from the axioms of PA. Now, if we add [~(Ax)R(x, p)] as an additional axiom to PA, we would get a system PA+[~(Ax)R(x, p)]. Under its standard interpretation, [~(Ax)R(x, p)] would interpret as asserting that ~R(x, p) is true for some natural number n. Hence nB(Sb(p 19|Z(p))) would hold, and so n would be the Goedel number of a PA-proof of [(Ax)R(x, p)]. Since this is false, it follows that PA+[~(Ax)R(x, p)] has no model and is, therefore, inconsistent. ========= On Apr 22, 2:21 pm, george wrote: G>> There are philosophical issues in "possible models". <<G Actually, I was considering all possible models of ZF in the sense in which Goedel's completeness theorem refers to them. G>> The Tarskian paradigm defining "model" doesn't actually say what a domain is (only that it "has" elements), and it certainly doesn't say what an ELEMENT of a domain is (that is INTENTIONALLY wholly untranslated ... suppose you DID have a domain whose elements weren't set-theoretic, and you had a model using that domain: that model is isomorphic to ANOTHER model whose domain-elements ARE sets. So why even bother?<<G I see the omissions - whether intentional or implicit - in the Tarskian paradigm as resulting in significant limitations in classical interpretations of the formal reasoning, and conclusions, of standard, first order, theory. Such interpretations - based primarily on the work of Cantor, Gödel, Tarski, and Turing - argue that the truth (satisfiability) of the propositions of a formal mathematical language, under an interpretation, is, both, non-algorithmic and essentially unverifiable constructively. However, if mathematics is to serve as a universal language of precise expression and unambiguous communication - I feel that such interpretations need to be balanced by an alternative, constructive and intuitionistically unobjectionable, interpretation - of classical foundational concepts - in which non-algorithmic truth (satisfiability) is defined effectively. More precisely, I believe that some foundational concepts - implicitly accepted as intuitively unexceptionable in the classical interpretations of Cantor's, Gödel's, Tarski's and Turing's reasoning - may be explicated effectively in non-Platonic interpretations that consider, for instance, whether, and, if so, when, and how, we may, within classical logic and without inviting inconsistency, define mathematical truth (satisfiability) effectively; Thus, Tarski defines a formula, say [R(x)], of a formal language L, as true under an interpretation M if, and only if, the interpreted relation, R(s), is satisfied by every s in the domain of M. We seem to accept this definition as definitive, ignoring the fact that it is silent on how the satisfiability of R(s), in M, is to be effectively determined. Since, if L is a formal Arithmetic, we are willing to accept Church's - as also Turing's - Thesis for determining the truth of interpreted propositions in the standard model of the Arithmetic, it seems odd that such a lacuna should be allowed to persist in an arbitrary model. Regards, Bhup
From: Ross A. Finlayson on 27 Apr 2005 01:02 I think it's intentional, and also intensional. Cantor's primary results, about the set and its powerset, are strong enough that the mathematical community at large adopted them as truths. When, as is being increasing qualitatively seen on this and other newsgroups catering to discussion by skilled enthusiasts, objections to those results are put forward, then it is obvious that they are not universally acceptable. For some's perception of standards of truth, the powerset result, to begin as applied to infinite sets, does not hold (true). In some senses the Cantorian results can be seen as rudimentary. They're simple and easily explained. Thus they have gained widespread use, it takes only a minimum of background to present them. While that is so, we see that among more advanced researchers that problems arise. Among the reasons that the powerset results hold importance to mathematicians is that they are used in various statements about the foundations, the foundations of mathematical logic or foundations of mathematics. Where for many mathematics is the ultimate science, and basically all questions resolve to at some level questions of mathematical logic, various schools of the examination of mathematical foundations are seen as deeply profound. This profundity is seen as the anchor, the bedrock, the foundations of mathematical logic. I'm quite egotistical and vain, I think that over the past several years I've been able to derive a variety of mathematical truths, or to some extent fundamental truths, that otherwise have escaped mathematicians and logicians throughout history, or rather were not stated in the language of modern, mathematical logic. I say that because it's mostly true, and to the extent it's not, it's to show weakness. Furthermore, some of these statements directly impact modern, taught, foundations of mathematical logic, in rigorously, to some extent, and yes formally, contradicting them. As I learn these things, I tend to write directly to you, to share, because I'd like you to think that too. Consider. a. The proper class would be necessarily unique. b. Quantification over sets implies a a universal set. c. To theories with no non-logical axioms, of which there is obviously only one, the results of Goedelian incompleteness do not apply. d. An incomplete theory is inconsistent. e. An inconsistent theory does not contain any truths. It has long and should ever be a goal to resolve the mathematical paradoxes, or to discover them. The paradox is a vicious stumbling block in the pursuit of mathematics. Sometimes they are also the Carrollian rabbit hole, Alice's gateway. That is to say, the discovery of the paradox is a key event in the expansion and betterment of the pursuit of mathematical logic, because to resolve them requires, to some extent in the reverse mathematics sense, the deconstruction of the existing mathematical framework, towards the reconstruction and betterment of formalized, modern, mathematical foundations. That is to some extent because 2+2=4 is true. It is absolutely true, there is no shade of doubt upon it, it is universally accepted. While that is so, as long as there remain paradoxes in the logical system underlying it, the mathematical foundations, it is suspect as are all other mathematical facts. That is largely not acceptable, 2+2=4 is true. To reach a point, if ZF is inconsistent with regards to any truth, then it is not acceptable as the foundation of mathematical logic. ZF, a set of axioms describing what a set is, represents the combined, sincere, effort of many and is a powerful and yes, even living monument. While that is so, it can only be seen as a vehicle for exploring truth values as part of a more comprehensive system. Thanks for some interesting dialog on this thread, George and Bhup et alia. Ross
From: Babylonian on 27 Apr 2005 01:09 Bhupinder Singh Anand wrote: > However, the questions arise: Are such interpretations definitive, and > are there substantive grounds for seeking alternative interpretations > of Goedel's reasoning? > > For instance, consider Goedel's 'unprovable but true' PA formula > [(Ax)R(x, p)]. > > This is unprovable from the axioms of Peano Arithmetic, but such that > [R(n, p)] is provable for any given numeral [n]. Hence, under the > standard interpretation, the corresponding arithmetical proposition, > R(x, p), is true for any given natural number n. > > (Here, [R(x, y)] is a PA-representation of Goedel's primitive recursive > relation ~xB(Sb(y 19|Z(y))), and p is the Goedel-number of the > PA-formula [(Ax)R(x, y)].) > > Now, by definition, the arithmetical relation R(x, p) is > instantiationally equivalent to the primitive recursive relation > ~xB(Sb(p 19|Z(p))). > > Further, again by Goedel's definitions, the primitive recursive > relation, ~xB(Sb(p 19|Z(p))), symbolically expresses the assertion > that: > > (*) x is not the Goedel number of a PA-proof of [(Ax)R(x, p)]. > > Since Goedel has shown that R(x, p) is true for all natural numbers - > as also is ~xB(Sb(p 19|Z(p))) - it follows that the assertion (*) is > true for all natural numbers, and, so, there is no proof of the > PA-proposition [(Ax)R(x, p)] from the axioms of PA. > > Now, if we add [~(Ax)R(x, p)] as an additional axiom to PA, we would > get a system PA+[~(Ax)R(x, p)]. > > Under its standard interpretation, [~(Ax)R(x, p)] would interpret as > asserting that ~R(x, p) is true for some natural number n. Hence > nB(Sb(p 19|Z(p))) would hold, and so n would be the Goedel number of a > PA-proof of [(Ax)R(x, p)]. > > Since this is false, it follows that PA+[~(Ax)R(x, p)] has no model and > is, therefore, inconsistent. No, it means the natural numbers are not a model of PA+[~(Ax)R(x, p)]. > > I see the omissions - whether intentional or implicit - in the Tarskian > paradigm as resulting in significant limitations in classical > interpretations of the formal reasoning, and conclusions, of standard, > first order, theory. > > Such interpretations - based primarily on the work of Cantor, Gödel, > Tarski, and Turing - argue that the truth (satisfiability) of the > propositions of a formal mathematical language, under an > interpretation, is, both, non-algorithmic and essentially unverifiable > constructively. That is merely a consequence of using the law of excluded middle over infinite sets, it is not the fault of Tarskian theory. > > However, if mathematics is to serve as a universal language of precise > expression and unambiguous communication - I feel that such > interpretations need to be balanced by an alternative, constructive and > intuitionistically unobjectionable, interpretation - of classical > foundational concepts - in which non-algorithmic truth (satisfiability) > is defined effectively. If you want to be an intuitionist, forget about defining truth for PA or ZF. Intuitionistic truth cannot be defined for these systems, period, because they are based on a logic which admits the law of excluded middle. > > More precisely, I believe that some foundational concepts - implicitly > accepted as intuitively unexceptionable in the classical > interpretations of Cantor's, Gödel's, Tarski's and Turing's > reasoning - may be explicated effectively in non-Platonic > interpretations that consider, for instance, whether, and, if so, when, > and how, we may, within classical logic and without inviting > inconsistency, define mathematical truth (satisfiability) effectively; > > Thus, Tarski defines a formula, say [R(x)], of a formal language L, as > true under an interpretation M if, and only if, the interpreted > relation, R(s), is satisfied by every s in the domain of M. > > We seem to accept this definition as definitive, ignoring the fact that > it is silent on how the satisfiability of R(s), in M, is to be > effectively determined. A "definition of truth" in the sense of Tarskian theory is nothing more or less than a definition of meaning. So, (Ax)Rx is true in M if and only if, for all x in the domain of M, Rx. That's all Tarskian theory is. > > Since, if L is a formal Arithmetic, we are willing to accept Church's > - as also Turing's - Thesis for determining the truth of interpreted > propositions in the standard model of the Arithmetic, it seems odd that > such a lacuna should be allowed to persist in an arbitrary model. > The Church-Turing thesis has nothing directly to do with determining the truth of arithmetic sentences.
From: Bhupinder Singh Anand on 27 Apr 2005 01:12
On Apr 26, 7:53 pm, Bhupinder Singh Anand wrote: BSA>> Since this is false, it follows that PA+[~(Ax)R(x, p)] has no model and is, therefore, inconsistent. <<BSA Sorry, this is wrong, and all we can deduce is that PA+[~(Ax)R(x, p)] has no model whose domain is the natural numbers. Regards, Bhup |