Adding the Godel Sentence to the Axioms of PA
in [Logic]
|
From: Charlie-Boo on 30 May 2010 08:59 The class of sets represented by PA wffs is the r.e. sets. We can represent no more. If we add the (true unprovable) Godel sentence G (the wff that expresses It is not provable on itself. applied to itself) to the axioms of PA, which sets can we then represent? Should that class change after adding G to the axioms? It cant contain a superclass of this class. C-B
From: Rupert on 31 May 2010 04:11 On May 30, 10:59 pm, Charlie-Boo <shymath...(a)gmail.com> wrote: > The class of sets represented by PA wffs is the r.e. sets. We can > represent no more. > > If we add the (true unprovable) Godel sentence G (the wff that > expresses It is not provable on itself. applied to itself) to the > axioms of PA, which sets can we then represent? Should that class > change after adding G to the axioms? It cant contain a superclass of > this class. > > C-B Would you be able to clarify exactly what you mean by a set being "representable" in a theory?
From: Charlie-Boo on 31 May 2010 10:25 On May 31, 4:11 am, Rupert <rupertmccal...(a)yahoo.com> wrote: > On May 30, 10:59 pm, Charlie-Boo <shymath...(a)gmail.com> wrote: > > > The class of sets represented by PA wffs is the r.e. sets. We can > > represent no more. > > > If we add the (true unprovable) Godel sentence G (the wff that > > expresses It is not provable on itself. applied to itself) to the > > axioms of PA, which sets can we then represent? Should that class > > change after adding G to the axioms? It cant contain a superclass of > > this class. > > > C-B > > Would you be able to clarify exactly what you mean by a set being > "representable" in a theory? http://groups.google.com/group/sci.logic/msg/e8946bb14f10372f?hl=en
From: George Greene on 31 May 2010 12:19 On May 30, 8:59 am, Charlie-Boo <shymath...(a)gmail.com> wrote: > The class of sets represented by PA wffs is the r.e. sets. This is not true. There are a great many different r.e. classes of sets. The class of sets that are PROVABLE FROM the axioms of PA (i.e., the Theory of PA) is an r.e. class of sets. But it its not the only such class. > We can represent no more. > > If we add the (true unprovable) Godel sentence G (the wff that > expresses It is not provable on itself. applied to itself) to the > axioms of PA, which sets can we then represent? "Represent", as Rupert is already pointing out, is not the verb you want here. Axioms have consequences. They imply things. They are used to PROVE THEOREMS. THE ONLY interesting question, when you add an axiom, is "how many MORE theorems can you prove?", or, in this case, since you are just going from one denumerable r.e. set to a bigger one (of the SAME "class"), which new theorems can you prove. > Should that class change after adding G to the axioms? It will still be r.e. The theory of consequences of ANY recursive axiom-set (under the usual first-order logic) is r.e.; if the axiom-set is simple enough then it can also be recursive. > It cant contain a superclass of this class. OF COURSE it is a superclass of the original class (or a superset -- we are talking about SETS of wffs that are consequences of SETS of axioms). If you add G as an axiom, you get all the theorems you had before PLUS the ones that follow from G. But both the old set and the new superset are r.e. You really shouldn't be talking about "classes" here. Recursive enumerability is a property of INDIVIDUAL infinite sets. It doesn't make much sense to talk about "the class of r.e. sets" because you could have r.e. sets OF literally ANYthing -- that's just too broad a universe. > > C-B
From: Charlie-Boo on 31 May 2010 13:42 On May 31, 12:19 pm, George Greene <gree...(a)email.unc.edu> wrote: > On May 30, 8:59 am, Charlie-Boo <shymath...(a)gmail.com> wrote: > > > The class of sets represented by PA wffs is the r.e. sets. > > This is not true. So is there an r.e. set that PA cannot represent, or is there a non- r.e. set that PA can represent? > There are a great many different r.e. classes of sets. How do you define an r.e. class of sets? I have only heard r.e. applied to sets of natural numbers e.g. Wikipedia: "A set S of natural numbers is called recursively enumerable . . ." > The class of sets that are PROVABLE FROM the axioms of PA How do you prove a set? I thought you only prove wffs - sentences in particular. > (i.e., the Theory of PA) is an r.e. class of sets. I would agree that it is an r.e. set of (the Godel numbers of) the theorems. > But it its not > the only such class. What do you mean by "such class"? > > We can represent no more. > > > If we add the (true unprovable) Godel sentence G (the wff that > > expresses It is not provable on itself. applied to itself) to the > > axioms of PA, which sets can we then represent? > > "Represent", as Rupert is already pointing out, is not the verb you > want here. Quote where he said that. Must I be confined to a verb? What are you saying needs to be reworded? > Axioms have consequences. They imply things. They are used to PROVE > THEOREMS. > THE ONLY interesting question, when you add an axiom, is "how many > MORE theorems > can you prove?", How about, "Is the system now consistent?"? > or, in this case, since you are just going from one > denumerable > r.e. set to a bigger one (of the SAME "class"), which new theorems can > you prove. > > > Should that class change after adding G to the axioms? > > It will still be r.e. > The theory of consequences of ANY recursive axiom-set (under the usual > first-order logic) is r.e.; if the axiom-set is simple enough then it > can also be recursive. > > > It cant contain a superclass of this class. > > OF COURSE it is a superclass of the original class (or a superset -- > we are talking > about SETS of wffs that are consequences of SETS of axioms). If you > add G as an axiom, > you get all the theorems you had before PLUS the ones that follow from > G. So? We are talking about the sets (relations) that can be represented, not the theorems. That is the point of this post. The number of theorems increases, but then does the class of representable sets change? It would seem to be unchangable. I think the truth is that it is simply a syntactic change - what each wff represents changes - but you represent the same sets. What else could it be? C-B > But both the old set and the new superset are r.e. > You really shouldn't be talking about "classes" here. > Recursive enumerability is a property of INDIVIDUAL infinite sets. > It doesn't make much sense to talk about "the class of r.e. sets" If you say so! > because you could have r.e. sets OF literally ANYthing -- that's just > too broad a universe. > > > > > > > C-B- Hide quoted text - > > - Show quoted text -
|
Next
|
Last
Pages: 1 2 3 4 5 Prev: Can Rosser 1936 be Extended? Alan Turing vs. Martin Davis et. al. Next: What are Sets? |