How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
in [Logic]
|
From: herbzet on 29 Jun 2010 23:21 Aatu Koskensilta wrote: > herbzet writes: > > > Hope to hear a reply to you from someone who actually knows > > what he's talking about. > > How did you like my reply? Fine, so far as it went. billh04 distinguished in his post between the consistency of PA being proved in ZFC, and a (meta) proof of the relative consistency of PA with regard to ZFC. You did not address the distinction drawn. * * * * * * Also, I was hoping for a reply from someone who knew what he was talking about. Hyuk, hyuk. * * * * * * As far as I'm concerned, if in theory A you have as theorems the axioms of theory B, then the axioms of B are true as far as theory A is concerned, and hence consistent, again as far as A is concerned. It's a bonus if in addition A proves "B is consistent". But: if A also proves "A is inconsistent", then you punt. -- hz
From: Chris Menzel on 30 Jun 2010 00:18 On Tue, 29 Jun 2010 23:21:49 -0400, herbzet <herbzet(a)gmail.com> said: > Aatu Koskensilta wrote: >> herbzet writes: >> >> > Hope to hear a reply to you from someone who actually knows >> > what he's talking about. >> >> How did you like my reply? > > Fine, so far as it went. > > billh04 distinguished in his post between the consistency of > PA being proved in ZFC, and a (meta) proof of the relative > consistency of PA with regard to ZFC. > > You did not address the distinction drawn. What distinction do you have in mind beyond the fact that they are simply two rather different proofs?
From: Aatu Koskensilta on 30 Jun 2010 12:38 MoeBlee <jazzmobe(a)hotmail.com> writes: > By the way, would you recommend a good (hopefully, fairly easy) > reference on the workaround you mentioned? The best reference is H�jek and Pudl�k's _Metamathematics of First-Order Arithmetic_, where you will learn all you need to know about doing recursion theory in fragments of first-order arithmetic. Alas, it's neither cheap nor easy. But in fact you know enough already to puzzle it out on your own. Recall for example the following theorem of PA: (*) There is no consistent axiomatizable completion of PA. When we assert that (*) is provable in PA we obviously have something more interesting in mind than just the triviality that we find in the ontology of PA no infinitary objects, such as extensions of PA, at all. What we mean is that PA proves: (*') Whenever i is an index of an r.e. set A such that all of the axioms of PA are in A, A is either inconsistent or incomplete. Using similar devices we can in the language of PA quantify over sets definable using arithmetical formulas of restricted quantifier complexity, and state results such as Every consistent Sigma-n set of sentences has a Delta-n+1 model. for a fixed n in the form Whenever A(x) is a Sigma-n formula that defines a consistent set of sentences, there is a Delta-n+1 formula defining a model of the set of sentences defined by A(x). and so on. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 30 Jun 2010 14:27 "R. Srinivasan" <sradhakr(a)in.ibm.com> writes: > If I had wasted my time trying to dig into the rubbish that you have > laid out above, I would not have had much time or energy left to deal > with the kind of stuff that *i* consider worth doing. You're of course free to spend your time and energy however you choose. But why do you think others should take any notice of your interests and inclinations? -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 30 Jun 2010 20:32
MoeBlee <jazzmobe(a)hotmail.com> writes: > Okay, I'm hanging in here. Through coding, we can "talk about" PA > formulas, thus, "talk about" the sets those formulas define, right? Sort of. > (I'm lost about the restricted quantifier complexity part, but > nevermind for now, I'm just trying to get the big picture at this > point). The restriction on quantifier complexity is necessary because truth of sentences of unrestricted quantifier complexity is not arithmetical. In contrast, for any n there is a Sigma-n formula True-n(x) such that o Every instance of the T-schema restricted to Sigma-n sentences provably holds in PA for True-n, i.e. for every Sigma-n sentence P it's provable in PA that P iff True-n("P") o The inductive Tarskian clauses hold for each n, i.e. it's provable in PA that P & Q is True-n iff P is True-n and Q is True-n; (x)P(x) is True-n iff P(a) is True-n for all a; and so on. To translate a statement containing quantifiers over Sigma-n sets ("for all Sigma-n sets X", "there is a Sigma-n set X") into the language of arithmetic we simply replace "for all Sigma-n sets X" with "for all Sigma-n formulas with one free variable x"; "there is a Sigma-n set X" with "there is a Sigma-n formula with one free variable x"; and "x in X" with "substituting the numeral for x in X yields a True-n sentence". (All this holds when we replace "Sigma-n" with "Pi-n.") Now, here's an exercise for you: show that adding to PA a predicate T and all instances of the T-schema for T, and extending the induction schema to cover formulas containing T, yields a conservative extension of PA. (Hint: use compactness, and the observation that for any finite number of instances of the T-schema we can find a restricted truth predicate that satisfies them -- one of the restricted truth predicates from above.) On the other hand, if we also add the usual Tarskian clauses (and extend induction to cover formulas containing the truth predicate) we get a theory equivalent to the subsystem ACA of second-order arithmetic -- essentially by using the truth predicate to translate statements that quantify over sets into quantification over arithmetical formulas, as we did above with the restricted truth predicates. I believe there's a bit about this in Torkel's _Inexhaustibility_. > I know what a Sigma-n set of sentences is. But what's a Delta-n+1 > model? It is a model the parts of which -- domain, relations, functions, ... -- are Delta-n+1 sets, that is, both Pi-n+1 and Sigma-n+1. > A followup question: Is there ANYTHING in mathematical logic you don't > know about? Lots. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |