Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > sci.logic > #165566 > unrolled thread

Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory

Started byCharlie-Boo <shymathguy@gmail.com>
First post2017-10-23 09:06 -0700
Last post2017-10-27 21:50 +0100
Articles 11 — 4 participants

Back to article view | Back to sci.logic

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Charlie-Boo <shymathguy@gmail.com> - 2017-10-23 09:06 -0700
    Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory peteolcott <peterolcott2@gmail.com> - 2017-10-23 09:42 -0700
      Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-23 21:11 +0100
        Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-23 15:32 -0500
          Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-24 01:36 +0100
            Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-23 20:49 -0500
              Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-24 12:01 +0100
                Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-24 08:43 -0500
                  Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-25 02:33 +0100
                    Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-27 10:49 -0500
                      Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-27 21:50 +0100

#165566 — Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory

FromCharlie-Boo <shymathguy@gmail.com>
Date2017-10-23 09:06 -0700
SubjectRe: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory
Message-ID<eda75d70-8fd0-4573-9609-65f044b598dc@googlegroups.com>
On Sunday, October 22, 2017 at 3:00:30 PM UTC-4, Pete Olcott wrote:
> http://liarparadox.org/index.php/2017/10/22/godels-1931-incompleteness-theorem-summed-as-a-single-line-of-minimal-type-theory/
> 
>     
> 
>     Gödel’s 1931 Incompleteness Theorem
> 
>     http://jacqkrol.x10.mx/assets/articles/godel-1931.pdf
> 
>     
> 
>     Gödel’s 1931 Incompleteness Theorem summed as a
>         single line of Minimal Type Theory
> 
>     G @ ∃X ~Provable(X, G)
> 
>     (1) The above sentence says that it is not provable.
> 
>     (2) The above sentence is indeed not provable.
> 
>     (3) However the above sentence is not true (see graph below).
> 
>     
> 
>     Sentence translated into a Directed Acyclic Graph by the MTT
>       compiler:
> 
>     [00] ROOT         (01)
> 
>       [01] G            (02)(04)
> 
>       [02] THERE_EXISTS (03)
> 
>       [03] X
> 
>       [04] NOT          (05)
> 
>       [05] Provable     (03)(01) // cycle indicate
>         infinite evaluation loop

Truth is not recursively enumerable.

F.I.

C-B

[toc] | [next] | [standalone]


#165578

Frompeteolcott <peterolcott2@gmail.com>
Date2017-10-23 09:42 -0700
Message-ID<f71a62df-983c-47b0-b1f9-020a890e7894@googlegroups.com>
In reply to#165566
On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
> On Sunday, October 22, 2017 at 3:00:30 PM UTC-4, Pete Olcott wrote:
> > http://liarparadox.org/index.php/2017/10/22/godels-1931-incompleteness-theorem-summed-as-a-single-line-of-minimal-type-theory/
> > 
> >     
> > 
> >     Gödel’s 1931 Incompleteness Theorem
> > 
> >     http://jacqkrol.x10.mx/assets/articles/godel-1931.pdf
> > 
> >     
> > 
> >     Gödel’s 1931 Incompleteness Theorem summed as a
> >         single line of Minimal Type Theory
> > 
> >     G @ ∃X ~Provable(X, G)
> > 
> >     (1) The above sentence says that it is not provable.
> > 
> >     (2) The above sentence is indeed not provable.
> > 
> >     (3) However the above sentence is not true (see graph below).
> > 
> >     
> > 
> >     Sentence translated into a Directed Acyclic Graph by the MTT
> >       compiler:
> > 
> >     [00] ROOT         (01)
> > 
> >       [01] G            (02)(04)
> > 
> >       [02] THERE_EXISTS (03)
> > 
> >       [03] X
> > 
> >       [04] NOT          (05)
> > 
> >       [05] Provable     (03)(01) // cycle indicate
> >         infinite evaluation loop
> 
> Truth is not recursively enumerable.
> 
> F.I.
> 
> C-B

Prolog is able to express Truth in a recursively enumerable way.

[toc] | [prev] | [next] | [standalone]


#165596

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-23 21:11 +0100
Message-ID<87zi8hipzj.fsf@bsb.me.uk>
In reply to#165578
peteolcott <peterolcott2@gmail.com> writes:

> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
<snip>
>> Truth is not recursively enumerable.
<snip>
> Prolog is able to express Truth in a recursively enumerable way.

Prolog has no choice -- that's the best is can do.  However, the set of
true sentences of any interesting axiomatic system is not an R.E. set.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#165599

FromPete Olcott <Pete@NoEmail.address>
Date2017-10-23 15:32 -0500
Message-ID<UoCdne51A-l3zHPEnZ2dnUU7-TXNnZ2d@giganews.com>
In reply to#165596
On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
> peteolcott <peterolcott2@gmail.com> writes:
> 
>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
> <snip>
>>> Truth is not recursively enumerable.
> <snip>
>> Prolog is able to express Truth in a recursively enumerable way.
> 
> Prolog has no choice -- that's the best is can do.  However, the set of
> true sentences of any interesting axiomatic system is not an R.E. set.
> 

https://en.wikipedia.org/wiki/Recursively_enumerable_set
Your statement depends upon the assumption that the Halting Problem proof is correct?

-- 
Defining Tarski’s ∀x True(x) ↔ φ(x)
True(x) ↔ ∃y Provable(y, x)

[toc] | [prev] | [next] | [standalone]


#165610

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-24 01:36 +0100
Message-ID<87inf5idp3.fsf@bsb.me.uk>
In reply to#165599
Pete Olcott <Pete@NoEmail.address> writes:

> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>> peteolcott <peterolcott2@gmail.com> writes:
>>
>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>> <snip>
>>>> Truth is not recursively enumerable.
>> <snip>
>>> Prolog is able to express Truth in a recursively enumerable way.
>>
>> Prolog has no choice -- that's the best is can do.  However, the set of
>> true sentences of any interesting axiomatic system is not an R.E. set.
>>
>
> https://en.wikipedia.org/wiki/Recursively_enumerable_set
> Your statement depends upon the assumption that the Halting Problem
> proof is correct?

No.  I don't know which proof you are thinking of but it's correctness
or otherwise has no bearing on the validity of the statement it may or
may not prove.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#165613

FromPete Olcott <Pete@NoEmail.address>
Date2017-10-23 20:49 -0500
Message-ID<9pydnYZj4tqIAXPEnZ2dnUU7-YHNnZ2d@giganews.com>
In reply to#165610
On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>> peteolcott <peterolcott2@gmail.com> writes:
>>>
>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>> <snip>
>>>>> Truth is not recursively enumerable.
>>> <snip>
>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>
>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>
>>
>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>> Your statement depends upon the assumption that the Halting Problem
>> proof is correct?
> 
> No.  I don't know which proof you are thinking of but it's correctness
> or otherwise has no bearing on the validity of the statement it may or
> may not prove.
> 

OK I misread the link.
There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.

Prolog is unable to exhaustively list all of the members of the set of sentences based on its axioms that evaluate to true?

It seems to me that Prolog could exhaustively list its finite set of atomic true sentences.

-- 
Defining Tarski’s ∀x True(x) ↔ φ(x)
True(x) ↔ ∃y Provable(y, x)

[toc] | [prev] | [next] | [standalone]


#165628

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-24 12:01 +0100
Message-ID<8760b4izde.fsf@bsb.me.uk>
In reply to#165613
Pete Olcott <Pete@NoEmail.address> writes:

> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>
>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>> <snip>
>>>>>> Truth is not recursively enumerable.
>>>> <snip>
>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>
>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>
>>>
>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>> Your statement depends upon the assumption that the Halting Problem
>>> proof is correct?
>>
>> No.  I don't know which proof you are thinking of but it's correctness
>> or otherwise has no bearing on the validity of the statement it may or
>> may not prove.
>>
>
> OK I misread the link.

I'm not sure that's the problem.  From what you write, I think you've
misunderstood the ideas.

> There is an algorithm that enumerates the members of S. That means
> that its output is simply a list of the members of S: s1, s2, s3,
> ... . If necessary, this algorithm may run forever.

You should make it clear when you are quoting material.  When something
is in your own words, your readers can use that to try ro work out if
you know what you are talking about.  The above is just a quote from a
website, so there is no way to know how much of it you understand.

> Prolog is unable to exhaustively list all of the members of the set of
> sentences based on its axioms that evaluate to true?

Prolog is a programming language.  If that does not answer your
question, you are very, very confused.

> It seems to me that Prolog could exhaustively list its finite set of
> atomic true sentences.

Did you mean to say that the Prolog system could list any program's
finite set of facts?

That seems unlikely for two reasons.  First, it's a boring fact (a
simple subset of the program's sentences constitute such a list), and
second, it looks like you think the last two sentences are talking about
the same things.  It seems likely that you don't know much about Prolog
so the words you use end up being muddled.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#165633

FromPete Olcott <Pete@NoEmail.address>
Date2017-10-24 08:43 -0500
Message-ID<LJ-dnev0QKbs3nLEnZ2dnUU7-W3NnZ2d@giganews.com>
In reply to#165628
On 10/24/2017 6:01 AM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>>
>>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>>> <snip>
>>>>>>> Truth is not recursively enumerable.
>>>>> <snip>
>>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>>
>>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>>
>>>>
>>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>>> Your statement depends upon the assumption that the Halting Problem
>>>> proof is correct?
>>>
>>> No.  I don't know which proof you are thinking of but it's correctness
>>> or otherwise has no bearing on the validity of the statement it may or
>>> may not prove.
>>>
>>
>> OK I misread the link.
> 
> I'm not sure that's the problem.  From what you write, I think you've
> misunderstood the ideas.
> 
>> There is an algorithm that enumerates the members of S. That means
>> that its output is simply a list of the members of S: s1, s2, s3,
>> ... . If necessary, this algorithm may run forever.
> 
> You should make it clear when you are quoting material.  When something
> is in your own words, your readers can use that to try ro work out if
> you know what you are talking about.  The above is just a quote from a
> website, so there is no way to know how much of it you understand.
> 
>> Prolog is unable to exhaustively list all of the members of the set of
>> sentences based on its axioms that evaluate to true?
> 
> Prolog is a programming language.  If that does not answer your
> question, you are very, very confused.
> 
>> It seems to me that Prolog could exhaustively list its finite set of
>> atomic true sentences.
> 
> Did you mean to say that the Prolog system could list any program's
> finite set of facts?
> 
> That seems unlikely for two reasons.  First, it's a boring fact (a
> simple subset of the program's sentences constitute such a list), and
> second, it looks like you think the last two sentences are talking about
> the same things.  It seems likely that you don't know much about Prolog
> so the words you use end up being muddled.
> 

You said: Prolog is able to express Truth in a recursively enumerable way. -
I did some more research.

https://en.wikipedia.org/wiki/Recursively_enumerable_set
Every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive. For recursive sets, the algorithm must also say if an input is not in the set – this is not required of recursively enumerable sets.

Prolog is able to determine and report whether or not an expression is provably true (within its specified axioms) for the exhaustive set of Prolog expressions. (A set of Prolog axioms define a language).

Prolog is able to determine and report whether or not an expression is not provably true (within its specified axioms) for the exhaustive set of Prolog expressions.

Thus for a set of axioms defining a language in Prolog, Prolog can determine whether or not any finite string is in the set of provably true Prolog expressions or not in the set of provably true Prolog expressions, thus making this set of Prolog axioms a recursive language with respect to provably true.

-- 
Defining Tarski’s ∀x True(x) ↔ φ(x)
True(x) ↔ ∃y Provable(y, x)

[toc] | [prev] | [next] | [standalone]


#165685

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-25 02:33 +0100
Message-ID<87k1zk2eq4.fsf@bsb.me.uk>
In reply to#165633
Pete Olcott <Pete@NoEmail.address> writes:

> On 10/24/2017 6:01 AM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>
>>>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>>>
>>>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>>>> <snip>
>>>>>>>> Truth is not recursively enumerable.
>>>>>> <snip>
>>>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>>>
>>>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>>>
>>>>>
>>>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>>>> Your statement depends upon the assumption that the Halting Problem
>>>>> proof is correct?
>>>>
>>>> No.  I don't know which proof you are thinking of but it's correctness
>>>> or otherwise has no bearing on the validity of the statement it may or
>>>> may not prove.
>>>>
>>>
>>> OK I misread the link.
>>
>> I'm not sure that's the problem.  From what you write, I think you've
>> misunderstood the ideas.
>>
>>> There is an algorithm that enumerates the members of S. That means
>>> that its output is simply a list of the members of S: s1, s2, s3,
>>> ... . If necessary, this algorithm may run forever.
>>
>> You should make it clear when you are quoting material.  When something
>> is in your own words, your readers can use that to try ro work out if
>> you know what you are talking about.  The above is just a quote from a
>> website, so there is no way to know how much of it you understand.
>>
>>> Prolog is unable to exhaustively list all of the members of the set of
>>> sentences based on its axioms that evaluate to true?
>>
>> Prolog is a programming language.  If that does not answer your
>> question, you are very, very confused.
>>
>>> It seems to me that Prolog could exhaustively list its finite set of
>>> atomic true sentences.
>>
>> Did you mean to say that the Prolog system could list any program's
>> finite set of facts?
>>
>> That seems unlikely for two reasons.  First, it's a boring fact (a
>> simple subset of the program's sentences constitute such a list), and
>> second, it looks like you think the last two sentences are talking about
>> the same things.  It seems likely that you don't know much about Prolog
>> so the words you use end up being muddled.
>>
>
> You said: Prolog is able to express Truth in a recursively enumerable way. -

I said it can do no other.  Since it's a programming language everything
it can "express" must be R.E.  One might like some of these things to be
recursive, but we often settle for R.E.

As I said above, the set of true sentences of any interesting axiomatic
system is /not/ R.E. so whatever it is that Prolog expresses, it is not
truth as Tarski would have it.

> I did some more research.
>
> https://en.wikipedia.org/wiki/Recursively_enumerable_set
> Every recursive set is recursively enumerable, but it is not true that
> every recursively enumerable set is recursive. For recursive sets, the
> algorithm must also say if an input is not in the set – this is not
> required of recursively enumerable sets.
>
> Prolog is able to determine and report whether or not an expression is
> provably true (within its specified axioms) for the exhaustive set of
> Prolog expressions. (A set of Prolog axioms define a language).
>
> Prolog is able to determine and report whether or not an expression is
> not provably true (within its specified axioms) for the exhaustive set
> of Prolog expressions.
>
> Thus for a set of axioms defining a language in Prolog, Prolog can
> determine whether or not any finite string is in the set of provably
> true Prolog expressions or not in the set of provably true Prolog
> expressions, thus making this set of Prolog axioms a recursive
> language with respect to provably true.

Pick an unsolved arithmetic conjecture (I suggest the Goldbach
conjecture), write it out as a Prolog expression and find out the
answer!

Hmm... that does not seem right...  Maybe

(A) No one has thought of this yet.  Quick, do it now before I publish
a paper solving 30 arithmetic conjectures before you do.

(B) Prolog can't even express simple arithmetic facts as expressions to
be proved.  If so, what use is it's notion of "provable", especially to
you?

(C) You are wrong.

Any ideas?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#165830

FromPete Olcott <Pete@NoEmail.address>
Date2017-10-27 10:49 -0500
Message-ID<p4KdnQ0woqMdyG7EnZ2dnUU7-Y_NnZ2d@giganews.com>
In reply to#165685
On 10/24/2017 8:33 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 10/24/2017 6:01 AM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>>
>>>>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>>>>
>>>>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>>>>> <snip>
>>>>>>>>> Truth is not recursively enumerable.
>>>>>>> <snip>
>>>>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>>>>
>>>>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>>>>
>>>>>>
>>>>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>>>>> Your statement depends upon the assumption that the Halting Problem
>>>>>> proof is correct?
>>>>>
>>>>> No.  I don't know which proof you are thinking of but it's correctness
>>>>> or otherwise has no bearing on the validity of the statement it may or
>>>>> may not prove.
>>>>>
>>>>
>>>> OK I misread the link.
>>>
>>> I'm not sure that's the problem.  From what you write, I think you've
>>> misunderstood the ideas.
>>>
>>>> There is an algorithm that enumerates the members of S. That means
>>>> that its output is simply a list of the members of S: s1, s2, s3,
>>>> ... . If necessary, this algorithm may run forever.
>>>
>>> You should make it clear when you are quoting material.  When something
>>> is in your own words, your readers can use that to try ro work out if
>>> you know what you are talking about.  The above is just a quote from a
>>> website, so there is no way to know how much of it you understand.
>>>
>>>> Prolog is unable to exhaustively list all of the members of the set of
>>>> sentences based on its axioms that evaluate to true?
>>>
>>> Prolog is a programming language.  If that does not answer your
>>> question, you are very, very confused.
>>>
>>>> It seems to me that Prolog could exhaustively list its finite set of
>>>> atomic true sentences.
>>>
>>> Did you mean to say that the Prolog system could list any program's
>>> finite set of facts?
>>>
>>> That seems unlikely for two reasons.  First, it's a boring fact (a
>>> simple subset of the program's sentences constitute such a list), and
>>> second, it looks like you think the last two sentences are talking about
>>> the same things.  It seems likely that you don't know much about Prolog
>>> so the words you use end up being muddled.
>>>
>>
>> You said: Prolog is able to express Truth in a recursively enumerable way. -
> 
> I said it can do no other.  Since it's a programming language everything
> it can "express" must be R.E.  One might like some of these things to be
> recursive, but we often settle for R.E.
> 
> As I said above, the set of true sentences of any interesting axiomatic
> system is /not/ R.E. so whatever it is that Prolog expresses, it is not
> truth as Tarski would have it.
> 
>> I did some more research.
>>
>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>> Every recursive set is recursively enumerable, but it is not true that
>> every recursively enumerable set is recursive. For recursive sets, the
>> algorithm must also say if an input is not in the set – this is not
>> required of recursively enumerable sets.
>>
>> Prolog is able to determine and report whether or not an expression is
>> provably true (within its specified axioms) for the exhaustive set of
>> Prolog expressions. (A set of Prolog axioms define a language).
>>
>> Prolog is able to determine and report whether or not an expression is
>> not provably true (within its specified axioms) for the exhaustive set
>> of Prolog expressions.
>>
>> Thus for a set of axioms defining a language in Prolog, Prolog can
>> determine whether or not any finite string is in the set of provably
>> true Prolog expressions or not in the set of provably true Prolog
>> expressions, thus making this set of Prolog axioms a recursive
>> language with respect to provably true.
> 
> Pick an unsolved arithmetic conjecture (I suggest the Goldbach
> conjecture), write it out as a Prolog expression and find out the
> answer!
> 
> Hmm... that does not seem right...  Maybe
> 
> (A) No one has thought of this yet.  Quick, do it now before I publish
> a paper solving 30 arithmetic conjectures before you do.
> 
> (B) Prolog can't even express simple arithmetic facts as expressions to
> be proved.  If so, what use is it's notion of "provable", especially to
> you?
> 

Prolog can express simple arithmetic facts as expressions to be proved and conventional counter-examples to the contrary can be detected and reported as erroneous by unify_with_occurs_check/2.

-- 
Defining Tarski’s ∀x True(x) ↔ φ(x)
True(x) ↔ ∃y Provable(y, x)

[toc] | [prev] | [next] | [standalone]


#165841

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-27 21:50 +0100
Message-ID<87a80ciad9.fsf@bsb.me.uk>
In reply to#165830
Pete Olcott <Pete@NoEmail.address> writes:

> On 10/24/2017 8:33 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 10/24/2017 6:01 AM, Ben Bacarisse wrote:
>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>
>>>>> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>>>
>>>>>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>>>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>>>>>
>>>>>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>>>>>> <snip>
>>>>>>>>>> Truth is not recursively enumerable.
>>>>>>>> <snip>
>>>>>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>>>>>
>>>>>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>>>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>>>>>
>>>>>>>
>>>>>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>>>>>> Your statement depends upon the assumption that the Halting Problem
>>>>>>> proof is correct?
>>>>>>
>>>>>> No.  I don't know which proof you are thinking of but it's correctness
>>>>>> or otherwise has no bearing on the validity of the statement it may or
>>>>>> may not prove.
>>>>>>
>>>>>
>>>>> OK I misread the link.
>>>>
>>>> I'm not sure that's the problem.  From what you write, I think you've
>>>> misunderstood the ideas.
>>>>
>>>>> There is an algorithm that enumerates the members of S. That means
>>>>> that its output is simply a list of the members of S: s1, s2, s3,
>>>>> ... . If necessary, this algorithm may run forever.
>>>>
>>>> You should make it clear when you are quoting material.  When something
>>>> is in your own words, your readers can use that to try ro work out if
>>>> you know what you are talking about.  The above is just a quote from a
>>>> website, so there is no way to know how much of it you understand.
>>>>
>>>>> Prolog is unable to exhaustively list all of the members of the set of
>>>>> sentences based on its axioms that evaluate to true?
>>>>
>>>> Prolog is a programming language.  If that does not answer your
>>>> question, you are very, very confused.
>>>>
>>>>> It seems to me that Prolog could exhaustively list its finite set of
>>>>> atomic true sentences.
>>>>
>>>> Did you mean to say that the Prolog system could list any program's
>>>> finite set of facts?
>>>>
>>>> That seems unlikely for two reasons.  First, it's a boring fact (a
>>>> simple subset of the program's sentences constitute such a list), and
>>>> second, it looks like you think the last two sentences are talking about
>>>> the same things.  It seems likely that you don't know much about Prolog
>>>> so the words you use end up being muddled.
>>>>
>>>
>>> You said: Prolog is able to express Truth in a recursively enumerable way. -
>>
>> I said it can do no other.  Since it's a programming language everything
>> it can "express" must be R.E.  One might like some of these things to be
>> recursive, but we often settle for R.E.
>>
>> As I said above, the set of true sentences of any interesting axiomatic
>> system is /not/ R.E. so whatever it is that Prolog expresses, it is not
>> truth as Tarski would have it.
>>
>>> I did some more research.
>>>
>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>> Every recursive set is recursively enumerable, but it is not true that
>>> every recursively enumerable set is recursive. For recursive sets, the
>>> algorithm must also say if an input is not in the set – this is not
>>> required of recursively enumerable sets.
>>>
>>> Prolog is able to determine and report whether or not an expression is
>>> provably true (within its specified axioms) for the exhaustive set of
>>> Prolog expressions. (A set of Prolog axioms define a language).
>>>
>>> Prolog is able to determine and report whether or not an expression is
>>> not provably true (within its specified axioms) for the exhaustive set
>>> of Prolog expressions.
>>>
>>> Thus for a set of axioms defining a language in Prolog, Prolog can
>>> determine whether or not any finite string is in the set of provably
>>> true Prolog expressions or not in the set of provably true Prolog
>>> expressions, thus making this set of Prolog axioms a recursive
>>> language with respect to provably true.
>>
>> Pick an unsolved arithmetic conjecture (I suggest the Goldbach
>> conjecture), write it out as a Prolog expression and find out the
>> answer!
>>
>> Hmm... that does not seem right...  Maybe
>>
>> (A) No one has thought of this yet.  Quick, do it now before I publish
>> a paper solving 30 arithmetic conjectures before you do.
>>
>> (B) Prolog can't even express simple arithmetic facts as expressions to
>> be proved.  If so, what use is it's notion of "provable", especially to
>> you?
>>
>
> Prolog can express simple arithmetic facts as expressions to be proved
> and conventional counter-examples to the contrary can be detected and
> reported as erroneous by unify_with_occurs_check/2.

Woosh.

-- 
Ben.

[toc] | [prev] | [standalone]


Back to top | Article view | sci.logic


csiph-web