Re: Why halt deciders can't be "interesting" programs. (Gödel's G is unsound)

[olcott]

On 9/24/2020 11:12 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 9/24/2020 10:11 AM, Mike Terry wrote:
>>> On 24/09/2020 15:07, olcott wrote:
>>>> On 9/24/2020 4:42 AM, Malcolm McLean wrote:
>>>>> On Wednesday, 23 September 2020 at 21:52:14 UTC+1, olcott wrote:
>>>>>> On 9/23/2020 3:40 PM, Malcolm McLean wrote:
>>>>>>>
>>>>>>> Ah, so mathematicians have made a fundamental mistake in what they
>>>>>>> regard as truth, therefore in what they accept as a proof.
>>>>>>> The claims get larger.
>>>>>>> Of course this opens the door to showing that certain established
>>>>>>> proofs
>>>>>>> are invalid. If the basics about what constitutes a "proof" have been
>>>>>>> misunderstood, then it's hardly surprising that many famous and
>>>>>>> generally
>>>>>>> accepted proofs don't pass the new standard.
>>>>>>>
>>>>>>> But you don't actually come up with the alternative system.
>>>>>>>
>>>>>> The alternative system is the sound deductive inference model where true
>>>>>> is provable(x) & true_premises(x).
>>>>>>
>>>>> So this is a bit above my head. It sounds on the face of it reasonable
>>>>> that
>>>>> you'd regard something as true if the premises are true and the proof
>>>>> follows
>>>>> from the premises. You're saying that this is something different to what
>>>>> mathematicians do.
>
> Mathematicians distinguish between the symbol-shuffling of a proof and
> the truth of a formula. This is their syntax/semantics distinction.
> Truth depends on an interpretation for the language the formula is
> written in -- basically an assignment of values from some set to the
> elements in the language.
>
> A valid proof is sound (and therefore the theorem is true) is the
> premises are true. Usually, the premises are no more than the axioms.
>
> PO thinks that this distinction between validity and soundness has some
> bearing on Gödel's incompleteness theorem. It doesn't. The theorem
> itself is simply about provability, but it applies to formal systems
> where provability and truth coincide.
>

Within the sound deductive inference model the conclusion is only true
if the argument is sound.

The argument is only sound when it begins with true premises and the
argument is valid.

Within the sound deductive inference model to say that the argument is
valid means that it is provable, thus Within the sound deductive
inference model to say that the conclusion is true and unprovable would
mean that the argument sound and invalid. Within the sound deductive
inference model this is not possible.

When the 1931 incompleteness theorem derives a conclusion that is true
and unprovable this result diverges from the sound deductive inference
model.

>>>> Yes this is different.
>>>
>>> @MM:  I hope you're not assuming that because PO says something, that
>>> he must have a clue what he's talking about - he doesn't.  :)
>>
>> The key thing to discredit is ad homimen attacks like this one, they
>> are specifically named errors of reasoning.
>> https://en.wikipedia.org/wiki/Ad_hominem
>
> You are making a very common mistake. MT is not making an argument, so
> there is no logical fallacy. He is pointing out that you don't know
> what you are talking about. Obviously, that is essentially an opinion,
> but he is not trying to refute some argument of yours by saying it. He
> is advising someone against taking your comments at face value.
>
> Unless you have finally worked though Mendelson's explanation of truth,
> I suspect you still don't know what mathematicians mean by it, so no one
> should take what you say about it as in any way authoritative.
>


--
Copyright 2020 Pete Olcott

[olcott]

On 9/28/2020 3:09 AM, Alan Mackenzie wrote:
> olcott <No...@nowhere.com> wrote:
>> On 9/24/2020 3:08 PM, David Kleinecke wrote:
>>> On Thursday, September 24, 2020 at 10:58:05 AM UTC-7, olcott wrote:
>>>> On 9/24/2020 11:42 AM, David Kleinecke wrote:

>>>>>>>>> Yes this is different.
>
>>>>>>>> @MM:? I hope you're not assuming that because PO says something,
>>>>>>>> that he must have a clue what he's talking about - he doesn't.?

>>>>>>>> :)
>
>>>>>>> The key thing to discredit is ad homimen attacks like this one,
>>>>>>> they are specifically named errors of reasoning.
>>>>>>> https://en.wikipedia.org/wiki/Ad_hominem
>
>>>>>> You are making a very common mistake. MT is not making an
>>>>>> argument, so there is no logical fallacy. He is pointing out that
>>>>>> you don't know what you are talking about. Obviously, that is
>>>>>> essentially an opinion, but he is not trying to refute some
>>>>>> argument of yours by saying it. He is advising someone against
>>>>>> taking your comments at face value.
>
>>>>>> Unless you have finally worked though Mendelson's explanation of
>>>>>> truth, I suspect you still don't know what mathematicians mean by
>>>>>> it, so no one should take what you say about it as in any way
>>>>>> authoritative.
>

>>>>> Speaking as a mathematician the problem with trying to do
>>>>> mathematics in what some philosophers whom PO follows have called
>>>>> "deductive inference" is that one cannot do proofs by
>>>>> contradiction.
>
>>>>> Consider the largest prime theorem. It starts out "Assume there is
>>>>> a largest prime called P". But one cannot reason in the "deductive"
>>>>> manner using P because P is false. And the proof fails.
>
>>>>> Somebody may have contrived a way around this difficulty but I do
>>>>> not claim to know all the literature.
>
>
>>>> To the best of my current knowledge provability remains that same
>>>> under valid deductive inference, the only thing that changes is the
>>>> determination of true conclusions under the sound deductive
>>>> inference model. In this case true(x) and unprovable(x) is
>>>> impossible.
>
>>>> Any reasoning the derives True(X) and Unprovable(X) means that the
>>>> argument having X as a conclusion is both sound and invalid.
>
>>>> We can derive that it is true that (x) is unprovable. What we cannot
>>>> derive under the sound deductive inference model is that expressions
>>>> claiming that they themselves are unprovable are true, even though
>>>> they are provably unprovable because provability is an aspect of
>>>> their truth and without it they are not true.
>
>>> Tell me how I can continue the largest prime theorem proof by "Form
>>> the product of all primes less than P" when P is false and therefore
>>> an illegal argument.
>
>
>> I don't really know jack about any of that.
>
> You really ought to. It is a classic piece of our cultural heritage.
>
> A prime number is one like 2, 3, 5, 7, 11, 13, 17, 19, ..... that cannot
> be evenly divided by anything other than itself or 1.
>
> Euclid proved that there is no largest prime number. His argument went
> as follows:
>
> Suppose there is a largest prime number P. Then we can form the number Q
> = 2 x 3 x 5 x 7 x ... x P + 1. (Note the + 1 on the end). Q is not
> divisible by 2 or 3 or 5 or ... or P, since it has a remainder of 1 when
> divided by any of these primes. Since Q is not divisible by any of the
> primes 2, ... , P, it must either be a prime itself or divisible by a
> prime larger than P. Either of these possibilities contradicts the
> supposition that P was the largest prime. Hence we have a proof by
> contradiction that there is no largest prime.
>
>>> You have a reference or anything like that for your assumption that
>>> provability is the same in a deductive context?
>
>> Consider me an aspiring meta-logician, not a mathematician.
>
>> I only really care about the architectural design of the upper
>> ontology of ontological engineering as this directly pertains to the
>> notion of analytical truth formalized syntactically.
>
>> Tarski got it wrong, Gödel, got it wrong, and I will soon show that
>> Turing got it wrong too.
>
> These things seem unlikely. If these mathematicians had "got it wrong",
> that would have been noticed in the many decades between the publishing
> of their papers and now.

I just proved that the simplest possible version of Gödel's G that he
himself referred to in his own paper both meets the definition of
incompleteness:

A theory T is incomplete if and only if there is some sentence φ such
that (T ⊬ φ) and (T ⊬ ¬φ).

and meets this definition only because it is infinitely recursive, thus
ill-formed:

We are therefore confronted with a proposition which
asserts its own unprovability. page 40
https://mavdisk.mnsu.edu/pj2943kt/Fall%202015/Promotion%20Application/Previous%20Years%20Article%2022%20Materials/godel-1931.pdf

This sentence cannot be proved:

G := ~Provable(G)
00 ~
01 Provable (00)

The directed graph is its relations to its constituent parts has an
infinite cycle.

The logical definition operator:
x := y means x is defined to be another name for y
https://en.wikipedia.org/wiki/List_of_logic_symbols

In the same way that the #define of C/C++ can specify self-reference and
thus infinite recursion the logical definition operator can specify
self-reference and thus infinite recursion.

3.10.5 Self-Referential Macros
A self-referential macro is one whose name appears in its definition.
Recall that all macro definitions are rescanned for more macros to
replace. If the self-reference were considered a use of the macro, it
would produce an infinitely large expansion.
...
#define foo (4 + foo)
where foo is also a variable in your program.

Following the ordinary rules, each reference to foo will expand into (4
+ foo); then this will be rescanned and will expand into (4 + (4 +
foo)); and so on until the computer runs out of memory.

https://gcc.gnu.org/onlinedocs/cpp/Self-Referential-Macros.html