Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Keith Thompson Newsgroups: comp.theory,comp.ai.philosophy,comp.ai.nat-lang,sci.lang.semantics Subject: Re: Simply defining =?utf-8?Q?G=C3=B6del?= Incompleteness and Tarski Undefinability away V24 (Are we there yet?) Date: Thu, 16 Jul 2020 11:21:50 -0700 Organization: None to speak of Lines: 81 Message-ID: <87wo33z5fl.fsf@nosuchdomain.example.com> References: <87k0z85tt0.fsf@nosuchdomain.example.com> <87d0505kmk.fsf@nosuchdomain.example.com> <5Lmdnehh4P6hLZbCnZ2dnUU7-LdQAAAA@giganews.com> <87365vnik3.fsf@bsb.me.uk> <87a703lz5c.fsf@bsb.me.uk> <87pn8ykrwq.fsf@bsb.me.uk> <7e-dnQpoj9jkoZPCnZ2dnUU7-UHNnZ2d@giganews.com> <875zapk0bb.fsf@bsb.me.uk> <87lfjkixu6.fsf@bsb.me.uk> <87eepc1cda.fsf@nosuchdomain.example.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: reader02.eternal-september.org; posting-host="02ec520d1b2b3210c7ee6ae74092840a"; logging-data="29417"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ClGOfyeie2qB89AqhDfQe" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) Cancel-Lock: sha1:vjCx+RUCRr0sGzBrufaOxCDXoWc= sha1:bpfU26tZx5AfNCDSQAehi0LFJc8= Xref: csiph.com comp.theory:21704 comp.ai.philosophy:22052 comp.ai.nat-lang:2430 olcott writes: > On 7/15/2020 8:23 PM, Keith Thompson wrote: >> olcott writes: >>> On 7/15/2020 12:32 PM, André G. Isaak wrote: >>>> On 2020-07-15 10:46, olcott wrote: >>>>> On 7/15/2020 10:48 AM, Ben Bacarisse wrote: >>>>>> A formula you've talked a lot about, namely, >>>>>> >>>>>>    ∀x ∈ ℕ ∀x ∈ ℕ x + y = y + x >>>>>> >>>>>> is not, in fact, a well-formed formula of Q (at least not in any version >>>>>> of Q that I know) > so asking about it's provability in Q is pointless. >>>>> >>>>> You may be correct on this. It had been assumed that the above >>>>> expression was a WFF in Q, if this is not the case then the example >>>>> ceases to be useful. >>>> >>>> The example was originally offered by me as x + y = y + x which *is* >>>> a WFF of Q. You are the one who keeps insisting on adding extraneous >>>> symbols to every formula you come across. >>> >>> You know that the "extraneous" symbols are not extraneous at all >>> because they transform the expression into the commutativity of >>> addition and without them the commutativity of addition is not >>> expressed. >> >> If the added symbols are not extraneous, what exactly is ℕ? >> >> Normally (outside the context of Q), ℕ is the set of natural numbers, >> but Q does not assume that such a set exists. Perhaps you can construct >> ℕ from the axioms of Q *and then* make statements about ℕ, but you >> haven't done so. > > Yes I see this now. It does not assume natural numbers it defines them > with its successor function. Right, it doesn't assume natural numbers. Whether the things it defines are natural numbers is another question. It may (or may not, I don't know) be possible for something other than the set of natural numbers to satisfy the Q axioms. More precisely, there may (or may not) be something that satisfies the Q axioms but does not satisfy all the characteristics of the natural numbers. >> You claim that x + y = y + x does not express the commutativity of >> addition. In fact it does. > > If it does express the commutativity of addition and it is provable in > Q then the statement that the commutativity of addition is not > provable in Q is a false statement. Why did you add "and it is provable"? First, as I understand it x + y = y + x *does* express the commutativity of addition. It's pretty much the definition of "commutativity of addition". I believe it's already been established (though I don't think the proof has been posted here) that x + y = y + x is *not* provable in Q. If I understand this correctly (and it's entirely possible that I don't) there are two possibilities: 1. Commutativity of addition is true but unprovable in Q. If this is the case, then it demonstrates that Q is incomplete (in the sense that Gödel uses the term). It would not be possible to construct a model of Q with non-commutative addition. 2. We know that there are models of Q in which addition is commutative. There may also be models in which addition is not commutative. If this is the case, then x + y = y + x would *not* be a demonstration that Q is Gödel-incomplete. >>> In any case it was a great example while it lasted. >>> Do you have another equally simple example that a closed WFF of a >>> formal system and is not provable or disprovable in that system? -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com Working, but not speaking, for Philips Healthcare void Void(void) { Void(); } /* The recursive call of the void */