Path: csiph.com!tncsrv06.tnetconsulting.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail NNTP-Posting-Date: Sat, 11 Jul 2020 19:24:56 -0500 Subject: =?UTF-8?Q?Re=3a_Simply_defining_G=c3=b6del_Incompleteness_and_Tarsk?= =?UTF-8?Q?i_Undefinability_away_V24_=28Are_we_there_yet=3f=29?= Newsgroups: comp.theory,comp.ai.philosophy,comp.ai.nat-lang,sci.lang.semantics References: <87k0zc8ps5.fsf@nosuchdomain.example.com> <8d2dnRULA_sojpTCnZ2dnUU7-X_NnZ2d@giganews.com> From: olcott Date: Sat, 11 Jul 2020 19:24:56 -0500 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit Message-ID: Lines: 196 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-8Rl0cnjxE7bw0pEM4VWhKFfPlbO6B45FayKFWi8IsO8ODfumZIdwqPpPKkIe0A1mAP0vXei/tTHd3tR!Ml7Hw0W9GoMzacVCajh3PfCXBixOv6YbggpMEIhYLBsOpXR2xLtOXWwWyD9oItpzf/0mLeTMZrI= X-Complaints-To: abuse@giganews.com X-DMCA-Notifications: http://www.giganews.com/info/dmca.html X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 10792 Xref: csiph.com comp.theory:21579 comp.ai.philosophy:21899 comp.ai.nat-lang:2328 On 7/11/2020 5:20 AM, André G. Isaak wrote: > On 2020-07-10 19:19, olcott wrote: >> On 7/10/2020 4:00 PM, André G. Isaak wrote: >>> On 2020-07-10 14:42, olcott wrote: >>>> On 7/10/2020 3:27 PM, André G. Isaak wrote: >>>>> On 2020-07-10 14:11, olcott wrote: >>>>>> On 7/10/2020 1:12 PM, André G. Isaak wrote: >>>>>>> On 2020-07-10 12:04, olcott wrote: >>>>>>>> On 7/10/2020 12:27 PM, André G. Isaak wrote: >>>>>>>>> On 2020-07-10 11:16, olcott wrote: >>>>>>>>>> On 7/10/2020 11:55 AM, André G. Isaak wrote: >>>>>>>>>>> On 2020-07-10 09:54, olcott wrote: >>>>>>>>>>>> On 7/10/2020 10:42 AM, André G. Isaak wrote: >>>>>>>>>>>>> On 2020-07-10 08:29, olcott wrote: >>>>>>>>>>>>>> Correction >>>>>>>>>>>>>> >>>>>>>>>>>>>> On 7/10/2020 8:41 AM, olcott wrote: >>>>>>>>>>>>>> ∃x ∃y (Q ⊢ "x + y = y + x") would seem to be unsatisfiable >>>>>>>>>>>>>> in Q. >>>>>>>>>>>>>> ∃x ∃y ¬(Q ⊢ "x + y = y + x") would also seem to be >>>>>>>>>>>>>> unsatisfiable in Q. >>>>>>>>>>>>>> ∴ Q is incomplete relative to the commutative property of >>>>>>>>>>>>>> addition. >>>>>>>>>>>>>> >>>>>>>>>>>>>> The only aspect of this that I am unsure of is whether or >>>>>>>>>>>>>> not my use of the technical term unsatisfiable corresponds >>>>>>>>>>>>>> to its conventional use. >>>>>>>>>>>>> >>>>>>>>>>>>> Since you clearly don't understand the term, why insist on >>>>>>>>>>>>> using it? >>>>>>>>>>>>> >>>>>>>>>>>>> It makes sense to ask whether some proposition φ is >>>>>>>>>>>>> satisfiable. It makes no sense to ask whether ⊢φ is >>>>>>>>>>>>> satisfiable. >>>>>>>>>>>>> >>>>>>>>>>>>> André >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> Because when I ask: >>>>>>>>>>>> >>>>>>>>>>>> Is this expression true in Q? >>>>>>>>>>>> ∃x ∃y (Q ⊢ "x + y = y + x") people generally tell me that I >>>>>>>>>>>> am saying it incorrectly as if there is no such thing as >>>>>>>>>>>> true in Q until we say it using model theory. >>>>>>>>>>> Who are 'most people'? Are you true they aren't pointing out >>>>>>>>>>> that what you are actually trying to say is: >>>>>>>>>>> >>>>>>>>>>> Q ⊢ (∃x ∃y (x + y = y + x)) >>>>>>>>>>> >>>>>>>>>>> (with the ⊢ actually in the correct place and without the >>>>>>>>>>> meaningless quotation marks)? >>>>>>>>>>> >>>>>>>>>>> Except that presumably isn't what you're trying to say >>>>>>>>>>> because that is trivially provable in Q, and we were talking >>>>>>>>>>> about statements that weren't provable in Q. >>>>>>>>>> >>>>>>>>>> This means that either your paraphrase or my statement or both >>>>>>>>>> does not express this meaning: >>>>>>>>> >>>>>>>>> Mine wasn't a paraphrase. It was a syntactic correction, which >>>>>>>>> apparently you ignored since you keep putting the Q ⊢ in the >>>>>>>>> wrong place. >>>>>>>>> >>>>>>>>>> https://math.stackexchange.com/questions/998359/robinson-arithmetic-and-its-incompleteness >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> Wikipedia in Italian has a sketch-of-proof that Robinson >>>>>>>>>> arithmetic is not complete, since commutativity of addition is >>>>>>>>>> undecidable. >>>>>>>>>> >>>>>>>>>> This seems much closer: >>>>>>>>>> ∃x ∈ N ∃y ∈ N (Q ⊢ (x + y = y + x)) >>>>>>>>>> ∃x ∈ N ∃y ∈ N (Q ⊢ (x + y != y + x)) >>>>>>>>> >>>>>>>>> Why don't you actually *think* about things instead of just >>>>>>>>> randomly making minor changes to your formulae. If you want to >>>>>>>>> express the fact that commutativity is not provable in Q, the >>>>>>>>> correct expression would be: >>>>>>>>> >>>>>>>>> Q ⊬ (∀x ∀y (x + y = y + x)) >>>>>>>> Yes that makes sense. That is a good way to say it. >>>>>>>> I need to translate that into this form: ∃φ (φ ↔ T ⊬ φ) >>>>>>>> >>>>>>>> φ = (∀x ∀y (x + y = y + x)) >>>>>>>> Q ⊬ φ // This is true in Q >>>>>>>> ∴ φ ↔ Q ⊬ φ is not true in Q >>>>>>> >>>>>>> Here's a suggestion. You keep mentioning Mendelson. While I am >>>>>>> not sure, I am assuming that this is a reference to Elliot >>>>>>> Mendelson's Intro to Mathematical Logic, which suggests you have >>>>>>> access to a copy of this. >>>>>>> >>>>>>> Why don't you actually try reading this book STARTING AT THE >>>>>>> BEGINNING. You will notice that most chapters contain exercises. >>>>>>> When you reach such exercises, do not continue further until you >>>>>>> can actually successfully do all of those exercises and are >>>>>>> confident you have done them correctly. (I'm sure you can find a >>>>>>> key online to verify your solutions). >>>>>>> >>>>>>> This way you might actually learn how to use logical notation >>>>>>> correctly, as well as learning some actual logic in the process. >>>>>>> Once you have completed the entire book, then perhaps you will be >>>>>>> able to say exactly what it is that you are trying to say in a >>>>>>> way that will be comprehensible to others. >>>>>>> >>>>>>> André >>>>>>> >>>>>> >>>>>> It all boils down to two key things: >>>>>> (1) I need to express ideas that are inexpressible in conventional >>>>>> notation >>>>> >>>>> Since you don't know the conventional notation, you have no basis >>>>> for saying that. >>>>> >>>>>> (2) I need to express ideas of mathematical logic at a very much >>>>>> higher level of abstraction than can be expressed using >>>>>> conventional notion. >>>>>> >>>>>> These are better than Mendelson's definitions because his do not >>>>>> simultaneously apply to every level of logic and every notion of a >>>>>> formal system. >>>>>> >>>>>>      Satisfiability >>>>>>      A formula is satisfiable if it is possible to find an >>>>>> interpretation >>>>>>      (model) that makes the formula true. >>>>>>      https://en.wikipedia.org/wiki/Satisfiability >>>>>> >>>>>>      Interpretation (logic) >>>>>>      An interpretation is an assignment of meaning to the >>>>>>      [non-logical] symbols of a formal language. >>>>>>      https://en.wikipedia.org/wiki/Interpretation_(logic) >>>>>> >>>>>>      Model theory >>>>>>      A model of a theory is a structure (e.g. an interpretation) >>>>>>      that satisfies the sentences of that theory. >>>>>>      https://en.wikipedia.org/wiki/Model_theory >>>>>> >>>>>> Within the above definitions: >>>>>> This sentence ∃φ (φ ↔ T ⊬ φ) really is unsatisfiable in every >>>>>> model including every model of arithmetic. >>>>>> >>>>>> When you tried to provide a counter-example you chopped off the >>>>>> existential quantifier making the strawman error. >>>>> >>>>> if φ ↔ T ⊬ φ is provable, than ∃φ (φ ↔ T ⊬ φ) is also provable. The >>>>> first implies the second. I don't know what magic you think that >>>>> existential quantifier performs, but it isn't whatever you think it >>>>> is. >>>> >>>> φ ↔ T ⊬ φ is provably unprovbale in the meta theory simply because >>>> this: ∃φ (φ ↔ T ⊬ φ) is false in the theory. >>> >>> φ ↔ T ⊬ φ *isn't* "provably unprovable" in the metatheory or anywhere >>> else. >>> >>> ∃φ (φ ↔ T ⊬ φ) is *true* in the metatheory because there is some φ >>> such that φ ↔ T ⊬ φ is *true*, also in the metatheory. That's because >>> φ is true in the theory, but not provable in the theory. >>> >> >> Try and show any concrete example of φ such as: 5 > 3 such that >> ∃φ (φ ↔ T ⊬ φ) is true. >> >> Concrete examples are where the rubber hits the road. > > You've been GIVEN a concrete example. Numerous times. > > (x + y = y + x) ↔ Q ⊬ (x + y = y + x) > > The RHS is true. The LHS is true. Therefore the entire equation is true. > Therefore ∃φ (φ ↔ Q ⊬ φ) is true. > > André > > You do come up with some very superb concrete examples. The example of the lack of the commutativity of addition in Q was the best example of actual incompleteness that I can imagine. Examples such as these make it much easier to continue to build a mutual understanding. φ = (∀x ∀y (x + y = y + x)) (Q ⊬ φ ∧ Q ⊬ ¬φ) Means that φ is neither true nor false in Q. If φ is neither true nor false in Q then it cannot be logically equivalent to anything in Q. It is easy to see that "ice cream is a dairy product" in neither true nor false in first order logic because it is not even expressible in first order logic. -- Copyright 2020 Pete Olcott