details re Z-R |- PA consistent
in [Logic]
|
Prev: geometry template for infinite-line-ray to precision define infinite-number in Peano Axioms #627 Correcting Math
Next: The Necessary vs Contingent Distinction
From: MoeBlee on 5 Jul 2010 14:42 On Jul 5, 10:57 am, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > But how do we know ~"Z-R theorem" isn't provable in Z-R? Iow, how do we > know Z-R is _syntactically_ consistent? (Otherwise it'd would be fruitless > to prove the formula "Z-R theorem" above!) Of course, if Z-R is inconsistent, then Z-R proves anything in the language of Z-R. My point is simply that whether Z-R is inconsistent or consistent at least we see that the above is an informal outline of a formal Z-R proof. If Z-R is inconsistent, then the above is an outline of a Z-R proof. And if Z-R is consistent, then the above is an outline of a Z-R proof. For that immediate purpose, that's all that I need to say. It is yet another discussion whether Z-R is consistent, what basis we might have for believing that Z-R is consistent or inconsistent, and what EPISTEMOLOGICAL import Z-R theorems have in case Z-R is consistent or in case Z-R is inconsistent. But for the mere purpose of showing that there is such and such a formal Z-R proof, my original post here does suffice. As to basis for believing Z-R is consistent, I've discussed that in other posts in the past (also recommended is Franzen's incompleteness book) and I don't wish to sidetrack with you on the matter. MoeBlee
From: Nam Nguyen on 5 Jul 2010 14:52 MoeBlee wrote: > On Jul 5, 10:57 am, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > >> But how do we know ~"Z-R theorem" isn't provable in Z-R? Iow, how do we >> know Z-R is _syntactically_ consistent? (Otherwise it'd would be fruitless >> to prove the formula "Z-R theorem" above!) > > Of course, if Z-R is inconsistent, then Z-R proves anything in the > language of Z-R. My point is simply that whether Z-R is inconsistent > or consistent at least we see that the above is an informal outline of > a formal Z-R proof. If Z-R is inconsistent, then the above is an > outline of a Z-R proof. And if Z-R is consistent, then the above is an > outline of a Z-R proof. For that immediate purpose, that's all that I > need to say. Well, then, PA is consistent can be proven in T = {(x=x) /\ ~(x=x)}, which I did mention already. That should settle the issue of formal proof of PA's consistency! Why bother with any thing as complicated as Z-R or ZFC, or what have we?
From: William Hale on 5 Jul 2010 14:58 In article <c0b94c40-c6c0-4edf-916d-7fc31f2490bf(a)x27g2000yqb.googlegroups.com>, MoeBlee <jazzmobe(a)hotmail.com> wrote: > Hi William, > > First a note: Just to be clear, when I listed certain symbols in my > post, I mean that those are AMONG the symbols of those languages; It > is not to be construed that those lists exhaust the symbols of those > languages. > > Some items from your post: > > > One subgoal is to define a set in Z-R that represents the wffs of PA. > > Or, we can be more definite and say not just that we find a set to > "represent" PA, but rather we actually define a specific set that IS > PA. Yes, I meant that. > > > We > > must first agree on an alphabet of characters that we will use in these > > wffs. > > Yes, except I say 'symbols'. At least in my view, the particular > typographic shapes we use merely indicate the actual symbols, as the > symbols themselves are abstract set-theoretic objects. (See Enderton's > remarks on what symbols are, as I adopt one of the options he allows.) I am not talking about the physical or typographic shapes of symbols. Just like we say the natural number 0 corresponds to the set {}, I want to say the char 'i' corresponds to the set 105 and the char 'f' corresponds to the set 102 and the symbol "if" corresponds to the function {<0,105>, <1,102>}, etc. Without going into details, I just wanted to confirm that symbols, wffs, etc are really just sets in Z-R. I am working at a very low level of what I am talking about, but I am talking at a very hight level, saying what the actual low level things are. Your comment above about "typographic shapes" never entered my consideration. I am trying to remain at a high level description of what we would be doing at a low level. > > But let's not get bogged down in that. Let's just agree that we have > some notion of a certain set of symbols. > > The symbols for set theory are the logical symbols (the quantifier, > connectives), the variables (denumerably many), and the predicate > symbols ('=' and 'e' (for 'e' read as the epsilon symbol)). That is given. But, that does not say what the symbols of PA in Z-R are. In fact, I am saying that the symbols of PA in Z-R must be sets. The symbol 'e' is not a set. > > > Let say we stipulate an alphabet of 255 characters (probably 50 > > would suffice). > > Actually, we have denumerably (countably infinite) many symbols., as I > mentioned above. But, those symbols in Z-R are not the symbols in what we want to call PA in Z-R. > > > We associate distinct concrete sets with each of these > > 255 characters. For example, we call the set 97 'a', 98 'b', etc > > No, throw that out. It doesn't work that way at all. If I throw that out, then I will have to go back to square one. Are you sure you want me to throw that out? > > > We > > then define the set of all finite sequences of characters of the > > alphabet. > > Yes, the set of finite sequences of symbols of the alphabet. > > > A subset of these we will define to be PA_Wffs, > > Right. > > > namely those > > sentences that are well-formed according to the normal rules. > > The set of sentences is a proper subset of the set of wffs. The > sentences are the wffs that have no free variables. I was trying to be precise. I am taking sentences to be strings like "===Sx Syy z zz" (that is, any list of characters to be used in our PA within Z-R). > > > We also > > want to define the set PA_Theorems of all PA_Wffs that can be derived > > using the rules of deduction in Z-R. All this can be done in Z-R of > > course. > > Right. > > > Then we want to prove the following theorem in Z-R: > > > > Theorem. It is false that there is some wff p in PA_Wffs such that (p > > and not p) is an element of PA_Theorems. > > Since we have a more exact notion of falsehood in play in the proof, > just to be very clear, let's leave out the word 'false' in this > particular place. But, this is exactly one of the points that I am not clear about. The "false" that I am using here is a Z-R terminology, not something about what we are doing for PA within Z-R. I could say: Theorem 1. It is false that {} in {}. By that I mean: Theorem 1. not ( {} in {} ) Again, I am not trying to be precise. But, in Z-R, I don't have any concept or definition of what "true" or "false" is. Do I need to introduce these concepts at square one? I haven't even mentioned anything about proving anything consistent or not. I am just working with sets, whether one set is an element of another set. > Instead: > > Z-R theorem: There does not exist a formula P such that both P and ~P > are in PA. (Remember, PA IS the set of theorems, in the language, from > a certain set of axioms). > > > I see that I need a Z-R function that takes wffs x and y and maps it to > > a wff that represents "x and y". Like, I need a Z-R function that takes > > a wff x and maps it to a wff that represents "not x". I believe that > > these things can be done in Z-R. > > Forget about that. It's not the way it works. I don't won't to forget about it. If I do, then I will have to go back to square one. Just like for Golbach's conjecture, given a number, I need to be able to say it is even. Likewise, given a wff Q, I need to be able to say that it is the negation of another wff R. > > The overall plan is this (all in Z-R): > > We define 'model of a theory'. This is exactly one of the points I am trying to figure out. I was hoping to do a portion of the setup of stating and proving PA consistent in the framework of Z-R. In your terminology, I was trying to set up the apparatus to define what a 'theory' is as an object in Z-R. I was hoping that "model" would not be needed up to that point. For example, with the set up that I presented, couldn't I prove in Z-R that there is no proof of less that 100 symbols that would prove a contradiction "P and ~P" for some wff P? That is, I just enumerate the 255^100 proofs, select the proofs composed of wff sentences, filter out the invalid proofs, and see if any of the valid proofs of what remains has a last sentence of the form "P and ~P"? > Very roughly, a model of a theory T is > a model FOR the language of T such that every member of T is mapped to > the value 1 (1 for true, 0 for false) by a function that maps all > sentences of the language of T to either 0 or 1 and as stipulated by > the ordinary "Tarski method". > > We also prove (trivially) that if a theory has a model then the theory > is consistent. > > We also prove (quite trivially) that if all the axioms of a theory are > true in a given model then that model is a model of the theory that is > the entailment-closure of those axioms. (And PA is the entailment- > closure of a certain set of axioms.) > > Then we construct a specific model for the language of PA and show > that that model is model of PA. We show that by showing that all the > axioms of PA are true in said model. > > MoeBlee
From: MoeBlee on 5 Jul 2010 15:48 On Jul 5, 11:58 am, William Hale <h...(a)tulane.edu> wrote: > In article > <c0b94c40-c6c0-4edf-916d-7fc31f249...(a)x27g2000yqb.googlegroups.com>, > > MoeBlee <jazzm...(a)hotmail.com> wrote: > > Hi William, > > > First a note: Just to be clear, when I listed certain symbols in my > > post, I mean that those are AMONG the symbols of those languages; It > > is not to be construed that those lists exhaust the symbols of those > > languages. > > > Some items from your post: > > > > One subgoal is to define a set in Z-R that represents the wffs of PA. > > > Or, we can be more definite and say not just that we find a set to > > "represent" PA, but rather we actually define a specific set that IS > > PA. > > Yes, I meant that. > > > > > > We > > > must first agree on an alphabet of characters that we will use in these > > > wffs. > > > Yes, except I say 'symbols'. At least in my view, the particular > > typographic shapes we use merely indicate the actual symbols, as the > > symbols themselves are abstract set-theoretic objects. (See Enderton's > > remarks on what symbols are, as I adopt one of the options he allows.) > > I am not talking about the physical or typographic shapes of symbols. > Just like we say the natural number 0 corresponds to the set {}, I wish to be pedantic in some of these matters, since we are in an area of fine-grained analysis. So, in Z-R, the natural number 0 IS the empty set. (Not just corresponds to the empty set.) > I want > to say the char 'i' corresponds to the set 105 and the char 'f' > corresponds to the set 102 I'd put it even STRONGER. But, first, I'm going to move past characters, and talk instead about symbols. Second, I'm going to go past "corresponds" and talk instead about "IS". We may (emphasis on 'may') elect to take the symbols of the language to BE natural numbers (and I'm not conflating with Godel numbering, though that too is consistent with what I'm saying here). > and the symbol "if" corresponds to the > function {<0,105>, <1,102>}, etc. You might set up all kinds of ways. Personally, I take the symbol indicated by '->' (for simplicity, I'll just say "the '->' symbol") to be a natural number. In my own treatment (and the specifics of the proof in this thread don't depend on such particulars), I take the symbols to be natural numbers (and I work it out so that what KIND of symbol is from a DECIDABLE subset of the set of natural numbers), then I take expressions to be finite sequences of symbols, then wffs to be a special kind of expression. > Without going into details, I just > wanted to confirm that symbols, wffs, etc are really just sets in Z-R. Yes, indeed. But to be clear, the symbols of OBJECT languages (such as PA) discussed "IN" Z-R are sets. But, also to make Z-R itself a formal theory (and with the symbols of Z-R being sets) we have a meta-theory for Z-R (usually, to start, the meta-theory for Z-R is an informal meta-theory). > > The symbols for set theory are the logical symbols (the quantifier, > > connectives), the variables (denumerably many), and the predicate > > symbols ('=' and 'e' (for 'e' read as the epsilon symbol)). > > That is given. But, that does not say what the symbols of PA in Z-R are. > In fact, I am saying that the symbols of PA in Z-R must be sets. The > symbol 'e' is not a set. Right. And I'm a bit guilty of having gone off as to what the symbols of Z-R are, when the more pressing matter for our purposes here is what the symbols of PA are. Indeed, in this analysis, the symbols of PA are themselves sets. > > > Let say we stipulate an alphabet of 255 characters (probably 50 > > > would suffice). > > > Actually, we have denumerably (countably infinite) many symbols., as I > > mentioned above. > > But, those symbols in Z-R are not the symbols in what we want to call PA > in Z-R. Sorry, right. But, still, there are denumerably many symbols for the langauge of PA too, since the language of PA, as any first order language, has denumerably many variables. > > > We associate distinct concrete sets with each of these > > > 255 characters. For example, we call the set 97 'a', 98 'b', etc > > > No, throw that out. It doesn't work that way at all. > > If I throw that out, then I will have to go back to square one. Are you > sure you want me to throw that out? I see where I got off your track. I took you too literally. You said we associate sets with characters. It's the other way around: We "associate" characters (better, symbols) with sets.So it's not as if each set has a corresponding symbol, but rather that each symbol has a corresponding set. But, and I grant this is pedantic, we don't just associate symbols with sets, rather the symbols ARE sets. > > > The set of sentences is a proper subset of the set of wffs. The > > sentences are the wffs that have no free variables. > > I was trying to be precise. I am taking sentences to be strings like > "===Sx Syy z zz" (that is, any list of characters to be used in our PA > within Z-R). In, say, Enderton's terminology, the set of strings on the alphabet is the set of expressions. Then there is a proper subset of the set of expressions that is the set of wffs. Then there is a proper subset of the set of wffs that is the set of sentences. Note: For certain technical reasons, my treatment is different from Enderton's in one respect: He takes expressions to be n-tuples of symbols, while I take expressions to be actual sequences (actual functions). se that there is some wff p in PA_Wffs such that (p > > > and not p) is an element of PA_Theorems. > > > Since we have a more exact notion of falsehood in play in the proof, > > just to be very clear, let's leave out the word 'false' in this > > particular place. > > But, this is exactly one of the points that I am not clear about. The > "false" that I am using here is a Z-R terminology, not something about > what we are doing for PA within Z-R. > > I could say: > > Theorem 1. It is false that {} in {}. That's only okay informally. To be more correct: Theorem 1: { } not in { }. Leave the words 'true' and 'false' out of the Z-R theorems unless we are talking about actual formal model theoretic truth and falsehood, and where we're taking Z-R as a meta-theory to talk about truth or falsehood in models for object languages. > By that I mean: > > Theorem 1. not ( {} in {} ) Sure, and informally that's fine. But, since we're also getting into formal truth and falsehood per models, it's better to keep to the pure: Theorem 1: not { } in { } or Theorem 1: ~ 0e0 or, even more pedantically (though not necessary to be so pedantic): Theorem 1: ~e00 > Again, I am not trying to be precise. But, in Z-R, I don't have any > concept or definition of what "true" or "false" is. Do I need to > introduce these concepts at square one? I haven't even mentioned > anything about proving anything consistent or not. I am just working > with sets, whether one set is an element of another set. No, let's put aside for the time being 'true' and 'false' for Z-R. (But we will talk, IN Z-R about 'true' and 'false' for PA.) So, in this context, as to Z-R, lets just talk about its THEOREMS and Z-R proofs of theorems. (Later, we will say that every theorem of Z-R is true in every model of Z-R. But we don't need that for the purpose of this thread.) > > Z-R theorem: There does not exist a formula P such that both P and ~P > > are in PA. (Remember, PA IS the set of theorems, in the language, from > > a certain set of axioms). > > > > I see that I need a Z-R function that takes wffs x and y and maps it to > > > a wff that represents "x and y". Like, I need a Z-R function that takes > > > a wff x and maps it to a wff that represents "not x". I believe that > > > these things can be done in Z-R. > > > Forget about that. It's not the way it works. > > I don't won't to forget about it. Sorry, but I can't make sense of it, and I don't see what it has to do with my proof. Meanwhile, if you are using it to make sense for yourself of something, then I very strongly recommend seeing how Enderton develops things in his book; I think that will provide you the context to make sense better. > > The overall plan is this (all in Z-R): > > > We define 'model of a theory'. > > This is exactly one of the points I am trying to figure out. See Enderton's mathematical logic book. He explains it beautifully. > I was > hoping to do a portion of the setup of stating and proving PA consistent > in the framework of Z-R. Yes, in Z-R, we do not just a portion, but the whole thing. > In your terminology, I was trying to set up the apparatus to define what > a 'theory' is as an object in Z-R. Right. We do that. > I was hoping that "model" would not be needed up to that point. Actually, the way Enderton does it, we need structures (models) for a language to define 'theory', since we define a theory in terms of entailment while entailment is defined in terms of models. However, for FIRST order, you could define 'theory' without models by instead of using entailment use derivability. > For example, with the set up that I presented, couldn't I prove in Z-R > that there is no proof of less that 100 symbols that would prove a > contradiction "P and ~P" for some wff P? That is, I just enumerate the > 255^100 proofs, select the proofs composed of wff sentences, filter out > the invalid proofs, and see if any of the valid proofs of what remains > has a last sentence of the form "P and ~P"? Yes. But let's not say 'invalid proof'. Instead say 'sequence not a proof' (or something else other than 'invalid proof' which is terminology that tends to confuse certain things). MoeBlee
From: MoeBlee on 5 Jul 2010 15:56
On Jul 5, 11:52 am, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > Well, then, PA is consistent can be proven in T = {(x=x) /\ ~(x=x)}, Sure, but with the one technical quibble that the language for T provides a formulation of "PA is not consistent". But, yes, on the basic point, we agree. > which I did mention already. That should settle the issue of formal > proof of PA's consistency! Why bother with any thing as complicated > as Z-R or ZFC, or what have we? Exactly! I mean that NOT sarcastically. This is part of what we've been saying ALL ALONG (in other threads, in various books, especially as well explained in Franzen's incompleteness book). My proof in this thread is NOT AT ALL intended as a means to convince anyone who already has serious doubts as to the consistency of PA. But the proof in this thread DOES settle the mere, pure question of whether Z-R proves ('prove' in the mere formal sense of a certain kind of sequence of formulas) the statement that PA is consistent. This is a point that I and other people have been making FOR YEARS in certain threads. MoeBlee |