arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: Ross A. Finlayson on 27 Apr 2005 20:08 Hi, In doing only cursory research, I'm apparently not the first person to suggest a theory with no non-logical axiomatization, i.e. truths enforced vs. inferred. For example, and I only yesterday saw this from searching for eliminable definitions, Owen Holden, with whom I agree, presented a similar notion years ago, "Set Theory Without Axioms." http://groups-beta.google.com/group/sci.math/browse_thread/thread/cb67edabc2fd84c8/ About the consistency and completeness coconsistency, you know I'm happy to grasp at straws, for gusto. While that is so, I still think those are true statements, for example about the proper class and how it equates itself to the dually minimal and maximal ur-element. Basically I've arrived at that there is one consistent, complete, and concrete theory. Ross
From: Bhupinder Singh Anand on 27 Apr 2005 22:48 On Apr 26, 10:09 pm, Babylonian wrote: B>> No, it means the natural numbers are not a model of PA+[~(Ax)R(x, p)]. <<B You're right, thanks for pointing out the mistake. B>> That is merely a consequence of using the law of excluded middle over infinite sets ... <<B How so? B>> ... 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. <<B I am not familiar with intuitionistic truth. My impression is that it involves belief in a priori, absolute, mathematical truths. However, I believe that such beliefs could inhibit effective communication of mathematically expressed concepts, and it should be possible to, alternatively, define semantic truth effectively, in an interpretation M of a formal system P, by linking it to P-provability, say as follows: (i) Uniform (algorithmic) truth: A formula S of a formal system P is uniformly (algorithmically) true under an interpretation M if, and only if, S is provable in P. (ii) Individual truth: A formula S of a formal system P is individually (instantiationally) true under an interpretation M if, and only if, every instantiation of its interpretation in M is the interpretation of a formula that is provable in P. (iii) Truth: A formula S of a formal system P is true under an interpretation M if, and only if, it is either uniformly (algorithmically), or individually (instantiationally), true under the interpretation M. Clearly, the Law of the Excluded Middle does not hold unequivocally, since the negation of 'S is true under the interpretation M' is not 'S is false under the interpretation M'. In this sense, the above definitions support the Intuitionistic objections to beliefs in an unrestricted applicability of the Law. (Note that, for an interpreted proposition R in M, we may still have that either R is true or R is false provided there is some effective method for determining every proposition of M as either true or false.) Note that, under the above definitions, Goedel's reasoning can also be interpreted as having established that there is a PA-formula that is individually true, but not uniformly - i.e., collectively - true under the standard interpretation. In other words, such an interpretation suggests that there may be a number-theoretic function whose range is not a set in ZF, contradicting the separation axiom of ZF. (Cf. http://alixcomsi.com/An_arguable_inconsistency_in_ZF.htm) Hence, viewed as a Boolean function, the arithmetical interpretation of Goedel's 'undecidable' proposition is not Turing-computable, even though its instantiationally-equivalent primitive recursive relation is! For this, and some other consequences of such an interpretation, and of an effective definition of semantic truth, see: http://alixcomsi.com/CTG_06_Consequences.htm B>> 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. <<B True. That appears to be a widely accepted interpretation of Tarski's definitions of semantic truth. However, I find that Tarski's definitions, when applied to the semantic truth of the propositions of a formal language under a well-defined interpretation, gain in significance if we interpret them as implicitly implying the existence of some effective method for determining that 'for all x in the domain of M, Rx'. We can, then, extend them to distinguish further between uniform (algorithmic) effective methods, and individual (non-algorithmic) effective methods, as suggested above, B>> The Church-Turing thesis has nothing directly to do with determining the truth of arithmetic sentences.<<B You're right, not directly. However, Church's Thesis is that a number-theoretic function is computable if, and only if, it is recursive. Since every recursive function is, both, instantiationally computable and representable in a Peano Arithmetic, it follows that every number-theoretic proposition (in the common, standard, interpretation M of Arithmetic), when treated as a Boolean function, is effectively decidable - either uniformly or individually - from the standard interpretations of the axioms of a Peano Arithmetic. So, in a sense, Church's Thesis can be viewed as the implicit effective method of Tarski's definitions when applied to an arithmetic such as PA. Regards, Bhup
From: Keith Ramsay on 28 Apr 2005 02:29 Babylonian wrote: [...] |> 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. I don't think it's customary to define "truth for" an axiom system anyway. Truth for sentences in the language of PA or ZF is a different story. Truth for sentences of first-order arithmetic can be defined with essentially the same definition as Tarski's, for an intuitionist. An intuitionist doesn't regard the same sentences as true, but depending on exactly what one wants to do with the resulting theory, this can be patched up by applying a translation from sentences classically interpreted to sentences interpreted as the intuitionist does. An intuitionist can consider, for example, those sentences whose double-negation translations hold in the natural numbers. That's a set containing the theorems of PA, since the double-negation translations of theorems of PA are theorems of HA (Heyting arithmetic), and HA is as far as I know generally acceptable to intuitionists. Defining truth for sentences in the language of ZF is more precarious for intuitionism. I'm doubtful whether many intuitionists would agree that the cumulative hierarchy of sets is well enough defined to serve as the basis for defining truth and falsity for sentences in the language of ZF. I don't really know, however. I suspect some constructivists would consider it okay, and maybe even agree that the double-negation translations of theorems of ZF hold there. Keith Ramsay
From: Babylonian on 28 Apr 2005 13:25 Keith Ramsay wrote: > Babylonian wrote: > [...] > |> 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. > > I don't think it's customary to define "truth for" an > axiom system anyway. Truth for sentences in the language > of PA or ZF is a different story. Ok, not "truth for PA or ZF". Truth for sentences of PA or ZF. Truth for sentences of > first-order arithmetic can be defined with essentially > the same definition as Tarski's, for an intuitionist. That was actually part of my point, to wit: he appears to think that Tarskian theory makes the notion of truth "non-algorithmic and essentially unverifiable constructively", and it doesn't. > > An intuitionist doesn't regard the same sentences as true, > but depending on exactly what one wants to do with the > resulting theory, And, what he wants to do is none other than define truth! Read his post; here is a quote: "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. " Obviously, ZF-provability includes provability by means of LEM, so reconcile that if you can with this: "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." You do of course understand that an intuitionist will not define the class of true PA sentences as the class of sentences whose double-negation translation holds in the natural numbers. That is a classical equivalence exclusively.
From: Babylonian on 28 Apr 2005 13:37
Bhupinder Singh Anand wrote: > > B>> That is merely a consequence of using the law of excluded middle > over infinite sets ... <<B > > How so? Classicaly, if we assume ~(Ex)Px and prove p&~p, we can infer (Ex)Px. THIS inference leads to belief in objects whose existence is "non-algorithmic and essentially unverifiable constructively", and it is equivalent to adding LEM as an axiom. > > I am not familiar with intuitionistic truth. My impression is that it > involves belief in a priori, absolute, mathematical truths. A sentence p is nontrue until a proof of p is found, whereupon p becomes true. ~p is the statement that there can never be a proof of p. p is false if and only if ~p is true. This states a time-dependence of truth in terms of the construction of formal OR informal proofs, while your definitions appear to state time-independence of truth in terms of nonconstructive existence of *formal* proofs: > > However, I believe that such beliefs could inhibit effective > communication of mathematically expressed concepts, and it should be > possible to, alternatively, define semantic truth effectively, in an > interpretation M of a formal system P, by linking it to P-provability, > say as follows: > > (i) Uniform (algorithmic) truth: A formula S of a formal system P is > uniformly (algorithmically) true under an interpretation M if, and only > if, S is provable in P. (ia) Then if S is (i)-true, there is an algorithm to prove it, but what if S is NOT (i)-true? The set of (i)-true sentences is not decidable, and others have pointed this out. (ib) definition (i) makes vacuous reference to M; the (i)-truth of S depends solely on the axioms and inferences of P. > > (ii) Individual truth: A formula S of a formal system P is individually > (instantiationally) true under an interpretation M if, and only if, > every instantiation of its interpretation in M is the interpretation of > a formula that is provable in P. (iia) If I understand this, S could have an infinite number of instantiations under M; how do you determine if every such instantiation is the interpretation of a P-provable formula; i.e. a (i)-true formula? > > (iii) Truth: A formula S of a formal system P is true under an > interpretation M if, and only if, it is either uniformly > (algorithmically), or individually (instantiationally), true under the > interpretation M. How can you say this defines truth "effectively"? You have defined truth in terms of the existence of proofs, not the existence of algorithms. > > Clearly, the Law of the Excluded Middle does not hold unequivocally, > since the negation of 'S is true under the interpretation M' is not 'S > is false under the interpretation M'. In this sense, the above > definitions support the Intuitionistic objections to beliefs in an > unrestricted applicability of the Law. > The negation of "S is true under M" is "S is not (i)-true and S is not (ii)-true under M". Then there is no proof of S, and there is some instantiation of S in M which is not the interpretation of a formula that is provable in P. Since you defined truth in terms of the existence of formal proofs, do you not define falsehood in terms of non-existence of formal proofs? > (Note that, for an interpreted proposition R in M, we may still have > that either R is true or R is false provided there is some effective > method for determining every proposition of M as either true or false.) > Where did that come from? I ask again: where in your definitions is any mention made of effective methods? > > B>> 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. <<B > > True. That appears to be a widely accepted interpretation of Tarski's > definitions of semantic truth. However, I find that Tarski's > definitions, when applied to the semantic truth of the propositions of > a formal language under a well-defined interpretation, gain in > significance if we interpret them as implicitly implying the existence > of some effective method for determining that 'for all x in the domain > of M, Rx'. Then instead of (i), (ii), and (iii), why not just restate Tarski with reference added to effective methods? What you have stated makes no such reference. > > We can, then, extend them to distinguish further between uniform > (algorithmic) effective methods, and individual (non-algorithmic) > effective methods, as suggested above, > > B>> The Church-Turing thesis has nothing directly to do with > determining the truth of arithmetic sentences.<<B > > You're right, not directly. However, Church's Thesis is that a > number-theoretic function is computable if, and only if, it is > recursive. Since every recursive function is, both, instantiationally > computable and representable in a Peano Arithmetic, it follows that > every number-theoretic proposition (in the common, standard, > interpretation M of Arithmetic), when treated as a Boolean function, is > effectively decidable - either uniformly or individually - Myself and others have shown this is not so. IIRC others have made points along similar lines. We can determine if S is (i)-true (independently of M!), but that does NOT mean (i)-truthhood is a decidable predicate, and (ii)-truth is defined in terms of (i)-truth (P-provability). |