XPost: comp.theory, sci.math
From: polcott333@gmail.com
On 11/29/2025 9:00 PM, Mike Terry wrote:
> On 30/11/2025 01:37, dart200 wrote:
>> On 11/29/25 4:38 PM, Richard Damon wrote:
>>> On 11/29/25 5:12 PM, dart200 wrote:
>>>> On 11/29/25 1:15 PM, Richard Damon wrote:
>>>>> On 11/29/25 3:48 PM, dart200 wrote:
>>>>>> On 11/29/25 12:24 PM, Richard Damon wrote:
>>>>>>> On 11/29/25 1:57 PM, dart200 wrote:
>>>>>>>> On 11/29/25 6:26 AM, olcott wrote:
>>>>>>>>> On 11/29/2025 2:33 AM, dart200 wrote:
>>>>>>>>>> On 11/29/25 12:00 AM, wij wrote:
>>>>>>>>>>> I just found that Goldbach conjecture may be a (A)NP problem
>>>>>>>>>>> if stated:
>>>>>>>>>>>
>>>>>>>>>>> Q: Given an even integer n, n>2. Is n the sum of two prime
>>>>>>>>>>> numbers?
>>>>>>>>>>>
>>>>>>>>>>> Proof Q∈ANP:
>>>>>>>>>>> v= AKS Primality Test // Ptime algorithm
>>>>>>>>>>> C= {| n=a+b } // card(C)∈ O(|Q|)
>>>>>>>>>>>
>>>>>>>>>>> bool gbf(int n) { // n is an even number
>>>>>>>>>>> int a,b;
>>>>>>>>>>> for(a=3; a>>>>>>>>>> b=n-a;
>>>>>>>>>>> if(v(a)&&v(b)) return true;
>>>>>>>>>>> }
>>>>>>>>>>> return false;
>>>>>>>>>>> }
>>>>>>>>>>> Thus, Q∈ANP (ANP=NP).
>>>>>>>>>>>
>>>>>>>>>>> Goldbach conjecture is likely a NPC problem.
>>>>>>>>>>> If so, from the ℙ≠ℕℙ result of
>>>>>>>>>>> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-
>>>>>>>>>>> proof- en.txt/download
>>>>>>>>>>>
>>>>>>>>>>> We can conclude that no formal proof can solve Goldbach
>>>>>>>>>>> conjecture, if formal
>>>>>>>>>>> proof is a Ptime algorithm.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> boring semantic paradox variant
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>>>>>>>>> I have always assessed that the Goldbach conjecture
>>>>>>>>> to be proven true requires an infinite proof. It seems
>>>>>>>>> best dismissed as insignificant.
>>>>>>>>>
>>>>>>>>
>>>>>>>> i fully believe the goldbach conjecture is a premise about
>>>>>>>> natural numbers that can be proven at some point one way or
>>>>>>>> another,
>>>>>>>>
>>>>>>>> i believe the same is true about the collatz conjecture,
>>>>>>>>
>>>>>>>> and rienmann hypothesis.
>>>>>>>>
>>>>>>>> when we do prove them, it will increase the totality of machines
>>>>>>>> we can compute halting in regards to
>>>>>>>>
>>>>>>>
>>>>>>> Fine thing to beleive, but we do know that there do exists true
>>>>>>> propositions that can not be proven.
>>>>>>
>>>>>> unless you can prove something undecidable, then it cannot just be
>>>>>> supposed to be so
>>>>>>
>>>>>
>>>>> Which Godel did.
>>>>>
>>>>> It may be a highly artificial statement, but he showed that it
>>>>> existed.
>>>>
>>>> it is an incredibly artificial ...
>>>>
>>>> "a truth that exists as true without proof" is mind numbingly
>>>> artificial construct that in fact has a proof, just not in a formal
>>>> system ...
>>>
>>> It is without proof IN THAT SYSTEM.
>>>
>>> It IS proven in a system with extra knowledge, knowledge that was
>>> used to build thee particular form of the relationship that we use to
>>> test the number.
>>>
>>> The key point is that relationship uses only operations in the base
>>> system
>>>
>>>>
>>>> like maybe we just didn't find the formal system robust enough to
>>>> describe what we're doing in godel's proof
>>>
>>> His system is totally formal.
>>>
>>> The point is that the interprestation can't be made in the base
>>> system the statement is expressed in, only a meta-system derived by
>>> adding choices to that original system.
>>>
>>> The point that is made is that in ANY sufficiently expressive system,
>>> there are statements which are true in it that can't be proven.
>>>
>>> Adding certain axioms/knowledge to that system to make it "higher
>>> order" can allow some to be proven and resolved.
>>>
>>> No matter how finitely high you go with this, you will ALWAYS end up
>>> with some statements that can't be proven.
>>>
>>> Only by adding an infinite number of these axioms/knowledge might it
>>> be possible to prove every statement, but then the system doesn't
>>> meet the initial requirements of a Formal Logic system of having a
>>> finite number of axioms.
>>
>> or we just haven't found a robust enough set of axioms to deal with it
>>
> No, you don't understand the result. It's not just a question of
> needing to add a couple more axioms.
>
> GIT [a suitable version of it - I doubt Godel's original proof was
> framed like this] shows that /any/ formal system, which is
> - sufficently powerful [basically, able to express basic arithmetic], and
> - is consistent, and
> - can be /effectively axiomatised/ [basically, there is an algorithm
> that can
> identify whether a statement is an axiom]
> will be incomplete.
>
Provable in meta-math and not provable in PA
are just toy systems with teeny tiny scope.
Not provable in the body of knowledge expressed
in language (where semantics and syntax are fully
integrated in the formal language) means not an
element of this body.
> Something like PA [Peano's Arithmetic axioms in FOL] is effectively
> axiomatisable: we can effectively recognise whether a given sentence is
> or is not one of Peano's axioms. But GIT shows PA to be incomplete
> [assuming it to be consistent of course. In an inconsistent system all
> sentences are provable, making such a system complete, but not
> interesting...]
>
> You are clearly thinking that just by adding a couple more axioms to PA,
> we can achieve completeness. That simply doesn't work - the resulting
> system would still be effectivel axiomatised, so either inconsistent or
> incomplete.
>
> If you added all the true arithmetic statements as axioms, you might
> consider that "robust", and this system would be complete - but it is
> not effectively axiomatisable. [I think some authors /require/ axioms
> to be effectively recognisable (and so would not consider this to be an
> axiomatic system), while others don't require that.]
>
>
> Mike.
>
--
Copyright 2025 Olcott
My 28 year goal has been to make
"true on the basis of meaning" computable.
This required establishing a new foundation
for correct reasoning.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
