Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Peano Axioms anchored in First Grade Arithmetic on ASCII Digit
 String pairs
Date: Thu, 24 Oct 2024 19:23:52 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <822145c623a1edb8f6af7632e117c24ba02ec176@i2pn2.org>
References: <ves6p1$2uoln$1@dont-email.me> <vesemu$2v7sh$1@dont-email.me>
 <a9fb95eb0ed914d0d9775448c005111eb43f2c5b@i2pn2.org>
 <veslpf$34ogr$1@dont-email.me>
 <647fe917c6bc0cfc78083ccf927fe280acdf2f9d@i2pn2.org>
 <vetq7u$3b8r2$1@dont-email.me>
 <522ecce215e636ddb7c9a1f75bff1ba466604cc5@i2pn2.org>
 <veuvt9$3hnjq$1@dont-email.me>
 <87634d01e18903c744d109aaca3a20b9ce4278bb@i2pn2.org>
 <vev8gg$3me0u$1@dont-email.me>
 <eb38c4aff9c8bc250c49892461ac25bfccfe303f@i2pn2.org>
 <vf051u$3rr97$1@dont-email.me>
 <e3f28689429722f86224d0d736115e4d1895299b@i2pn2.org>
 <vf1hun$39e3$1@dont-email.me>
 <dedb2801cc230a4cf689802934c4b841ae1a29eb@i2pn2.org>
 <vf1stu$8h0v$1@dont-email.me>
 <592109c757262c48aaca517a829ea1867913316b@i2pn2.org>
 <vf37qt$fbb3$1@dont-email.me> <vf5430$sjvj$1@dont-email.me>
 <vf5mat$v6n5$4@dont-email.me> <vf7jbl$1cr7h$1@dont-email.me>
 <vf8b8p$1gkf5$3@dont-email.me> <vfa8iu$1ulea$1@dont-email.me>
 <vfassk$21k64$4@dont-email.me> <vfdjc7$2lcba$1@dont-email.me>
 <vfdlij$2ll17$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 24 Oct 2024 23:23:52 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3525407"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
In-Reply-To: <vfdlij$2ll17$1@dont-email.me>
Bytes: 6566
Lines: 105

On 10/24/24 10:28 AM, olcott wrote:
> 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.
> 

Yes, Incompleteness requires a certain degree of suffistication in the 
operations allowed, but that is all part of the "properties of the 
Natural Numbers".

There is a critical boundary, beyound which if a logic system supports 
it, it must be incomplete. Simple system can be complete.

I wouldn't be surprized if part of that line is the ability to create 
concepts over a certain size of infinity.

Note, that while the Natural Numbers themselves are a countable 
infinity, there are operations on them (like computing the number of 
possible mappings of N to N) that can create uncountable infinities, and 
that might be part of what makes the system incomplete.

That or the ability to make countable infinite sets, that you need to 
confirm that All or None of the memebers have a property.