Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: =?UTF-8?Q?Re=3A_G=C3=B6del=27s_actual_proof_and_deriving_all_of_the?= =?UTF-8?Q?_digits_of_the_actual_G=C3=B6del_numbers?= Date: Fri, 1 Nov 2024 06:43:44 -0500 Organization: A noiseless patient Spider Lines: 284 Message-ID: References: <040cd8511c02a898516db227faa75dbc5f74a097@i2pn2.org> <17cad36a46956f00484737183121e8a2c9e742ef@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 01 Nov 2024 12:43:46 +0100 (CET) Injection-Info: dont-email.me; posting-host="c99c96db3ca54ad7ebeb53cde955872b"; logging-data="3397431"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+tbdjVar/+z79XBHEeYhVC" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:AVyWa9IIS/cpC7gwRIKLldg68aQ= X-Antivirus-Status: Clean Content-Language: en-US In-Reply-To: X-Antivirus: Norton (VPS 241101-0, 10/31/2024), Outbound message Bytes: 15272 On 11/1/2024 3:34 AM, Mikko wrote: > On 2024-10-31 12:15:42 +0000, olcott said: > >> On 10/31/2024 4:45 AM, Mikko wrote: >>> On 2024-10-30 12:13:43 +0000, olcott said: >>> >>>> On 10/30/2024 4:57 AM, Mikko wrote: >>>>> On 2024-10-29 13:25:34 +0000, olcott said: >>>>> >>>>>> On 10/29/2024 2:38 AM, Mikko wrote: >>>>>>> On 2024-10-28 14:04:24 +0000, olcott said: >>>>>>> >>>>>>>> On 10/28/2024 3:35 AM, Mikko wrote: >>>>>>>>> On 2024-10-27 14:29:22 +0000, olcott said: >>>>>>>>> >>>>>>>>>> On 10/27/2024 4:02 AM, Mikko wrote: >>>>>>>>>>> On 2024-10-26 13:57:58 +0000, olcott said: >>>>>>>>>>> >>>>>>>>>>>> On 10/25/2024 11:07 PM, Richard Damon wrote: >>>>>>>>>>>>> On 10/25/24 7:06 PM, olcott wrote: >>>>>>>>>>>>>> On 10/25/2024 5:17 PM, Richard Damon wrote: >>>>>>>>>>>>>>> On 10/25/24 5:52 PM, olcott wrote: >>>>>>>>>>>>>>>> On 10/25/2024 10:52 AM, Richard Damon wrote: >>>>>>>>>>>>>>>>> On 10/25/24 9:31 AM, olcott wrote: >>>>>>>>>>>>>>>>>> On 10/25/2024 3:01 AM, Mikko wrote: >>>>>>>>>>>>>>>>>>> On 2024-10-24 14:28:35 +0000, olcott said: >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> On 10/24/2024 8:51 AM, Mikko wrote: >>>>>>>>>>>>>>>>>>>>> On 2024-10-23 13:15:00 +0000, olcott said: >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> On 10/23/2024 2:28 AM, Mikko wrote: >>>>>>>>>>>>>>>>>>>>>>> On 2024-10-22 14:02:01 +0000, olcott said: >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> On 10/22/2024 2:13 AM, Mikko wrote: >>>>>>>>>>>>>>>>>>>>>>>>> On 2024-10-21 13:52:28 +0000, olcott said: >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>> On 10/21/2024 3:41 AM, Mikko wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>> On 2024-10-20 15:32:45 +0000, olcott said: >>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>> The actual barest essence for formal systems >>>>>>>>>>>>>>>>>>>>>>>>>>>> and computations >>>>>>>>>>>>>>>>>>>>>>>>>>>> is finite string transformation rules >>>>>>>>>>>>>>>>>>>>>>>>>>>> applied to finite strings. >>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>> Before you can start from that you need a >>>>>>>>>>>>>>>>>>>>>>>>>>> formal theory that >>>>>>>>>>>>>>>>>>>>>>>>>>> can be interpreted as a theory of finite >>>>>>>>>>>>>>>>>>>>>>>>>>> strings. >>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>> Not at all. The only theory needed are the >>>>>>>>>>>>>>>>>>>>>>>>>> operations >>>>>>>>>>>>>>>>>>>>>>>>>> that can be performed on finite strings: >>>>>>>>>>>>>>>>>>>>>>>>>> concatenation, substring, relational operator ... >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>> You may try with an informal foundation but you >>>>>>>>>>>>>>>>>>>>>>>>> need to make sure >>>>>>>>>>>>>>>>>>>>>>>>> that it is sufficicently well defined and that >>>>>>>>>>>>>>>>>>>>>>>>> is easier with a >>>>>>>>>>>>>>>>>>>>>>>>> formal theory. >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>> The minimal complete theory that I can think >>>>>>>>>>>>>>>>>>>>>>>>>> of computes >>>>>>>>>>>>>>>>>>>>>>>>>> the sum of pairs of ASCII digit strings. >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>> That is easily extended to Peano arithmetic. >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>> As a bottom layer you need some sort of logic. >>>>>>>>>>>>>>>>>>>>>>>>> There must be unambifuous >>>>>>>>>>>>>>>>>>>>>>>>> rules about syntax and inference. >>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> I already wrote this in C a long time ago. >>>>>>>>>>>>>>>>>>>>>>>> It simply computes the sum the same way >>>>>>>>>>>>>>>>>>>>>>>> that a first grader would compute the sum. >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> I have no idea how the first grade arithmetic >>>>>>>>>>>>>>>>>>>>>>>> algorithm could be extended to PA. >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> Basically you define that the successor of X is X >>>>>>>>>>>>>>>>>>>>>>> + 1. The only >>>>>>>>>>>>>>>>>>>>>>> primitive function of Peano arithmetic is the >>>>>>>>>>>>>>>>>>>>>>> successor. Addition >>>>>>>>>>>>>>>>>>>>>>> and multiplication are recursively defined from >>>>>>>>>>>>>>>>>>>>>>> the successor >>>>>>>>>>>>>>>>>>>>>>> function. Equality is often included in the >>>>>>>>>>>>>>>>>>>>>>> underlying logic but >>>>>>>>>>>>>>>>>>>>>>> can be defined recursively from the successor >>>>>>>>>>>>>>>>>>>>>>> function and the >>>>>>>>>>>>>>>>>>>>>>> order relation is defined similarly. >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> Anyway, the details are not important, only that >>>>>>>>>>>>>>>>>>>>>>> it can be done. >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> First grade arithmetic can define a successor >>>>>>>>>>>>>>>>>>>>>> function >>>>>>>>>>>>>>>>>>>>>> by merely applying first grade arithmetic to the pair >>>>>>>>>>>>>>>>>>>>>> of ASCII digits strings of [0-1]+ and "1". >>>>>>>>>>>>>>>>>>>>>> https://en.wikipedia.org/wiki/Peano_axioms >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> The first incompleteness theorem states that no >>>>>>>>>>>>>>>>>>>>>> consistent system of axioms whose theorems can be >>>>>>>>>>>>>>>>>>>>>> listed by an effective procedure (i.e. an >>>>>>>>>>>>>>>>>>>>>> algorithm) is capable of proving all truths about >>>>>>>>>>>>>>>>>>>>>> the arithmetic of natural numbers. For any such >>>>>>>>>>>>>>>>>>>>>> consistent formal system, there will always be >>>>>>>>>>>>>>>>>>>>>> statements about natural numbers that are true, >>>>>>>>>>>>>>>>>>>>>> but that are unprovable within the system. >>>>>>>>>>>>>>>>>>>>>> https://en.wikipedia.org/wiki/ >>>>>>>>>>>>>>>>>>>>>> G%C3%B6del%27s_incompleteness_theorems >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> When we boil this down to its first-grade >>>>>>>>>>>>>>>>>>>>>> arithmetic foundation >>>>>>>>>>>>>>>>>>>>>> this would seem to mean that there are some cases >>>>>>>>>>>>>>>>>>>>>> where the >>>>>>>>>>>>>>>>>>>>>> sum of a pair of ASCII digit strings cannot be >>>>>>>>>>>>>>>>>>>>>> computed. >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> No, it does not. Incompleteness theorem does not >>>>>>>>>>>>>>>>>>>>> apply to artihmetic >>>>>>>>>>>>>>>>>>>>> that only has addition but not multiplication. >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> The incompleteness theorem is about theories that >>>>>>>>>>>>>>>>>>>>> have quantifiers. >>>>>>>>>>>>>>>>>>>>> A specific arithmetic expression (i.e, with no >>>>>>>>>>>>>>>>>>>>> variables of any kind) >>>>>>>>>>>>>>>>>>>>> always has a well defined value. >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> So lets goes the next step and add multiplication to >>>>>>>>>>>>>>>>>>>> the algorithm: >>>>>>>>>>>>>>>>>>>> (just like first grade arithmetic we perform >>>>>>>>>>>>>>>>>>>> multiplication >>>>>>>>>>>>>>>>>>>> on arbitrary length ASCII digit strings just like >>>>>>>>>>>>>>>>>>>> someone would >>>>>>>>>>>>>>>>>>>> do with pencil and paper). >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> Incompleteness cannot be defined. until we add >>>>>>>>>>>>>>>>>>>> variables and >>>>>>>>>>>>>>>>>>>> quantification: There exists an X such that X * 11 = >>>>>>>>>>>>>>>>>>>> 132. >>>>>>>>>>>>>>>>>>>> Every detail of every step until we get G is >>>>>>>>>>>>>>>>>>>> unprovable in F. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> Incompleteness is easier to define if you also add >>>>>>>>>>>>>>>>>>> the power operator >>>>>>>>>>>>>>>>>>> to the arithmetic. Otherwise the expressions of >>>>>>>>>>>>>>>>>>> provability and >>>>>>>>>>>>>>>>>>> incompleteness are more complicated. They become much >>>>>>>>>>>>>>>>>>> simpler if >>>>>>>>>>>>>>>>>>> instead of arithmetic the fundamental theory is a >>>>>>>>>>>>>>>>>>> theory of finite >>>>>>>>>>>>>>>>>>> strings. As you already observed, arithmetic is easy >>>>>>>>>>>>>>>>>>> to do with >>>>>>>>>>>>>>>>>>> finite strings. The opposite is possible but much >>>>>>>>>>>>>>>>>>> more complicated. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> The power operator can be built from repeated >>>>>>>>>>>>>>>>>> operations of ========== REMAINDER OF ARTICLE TRUNCATED ==========