Re: An instance of Russell's paradox?


A.T. wrote:
> Hello,
> I have been studying Prolog for a while,
> and stumbled across several
> difficulties which I seem to be unable to
> overcome on my own. Since I
> am doing it all solely for the purpose
> of understanding FOL

Prolog is seriously not a good choice for that.
"Negation-as-failure", "operational semantics",
and a host of further caveats are relevant.
On the plus side, if you actually understand
all of these, you will understand more than
"solely" FOL.

> (and Russell's PM straight after that)

Russell's PM is NOT the same thing as classical
FOL and there IS A REASON why modern treatments
DON'T look like PM! Seriously, unless you have
to write a paper on the history of science or something,
PM is simply not worth bothering with.

> I have let myself choose Sci.Logic as
> the addressee of my questions.

I pity the f__....

> 1. Can all algorithms be enumerated,

Yes, but that depends on a definition of "algorithm"
due to Church and Turing, NOT Prolog or PM. It also
depends on a broad natural definition of "can" (this
field invites a narrower technical definition).

> or will that be another
> formulation of Russell's paradox

only if you can formulate the enumeration algorithmically.
But precisely because that assumption (that there is an
algorithm for performing the enumeration) leads to
contradiction, you canNOT "effectively" enumerate the
algorithms (even though it must in some sense be abstractly
possible to enumerate them, since they are all finite and
there are therefore only a denumerable number of them).
In Turing-speak, they are denumerable but not "recursively"
enumerable.

> (with the list of all algorithms being
> another way of expressing the set of all sets)?

Sort of, yes. If you could list all the algorithms
by using an algorithm, then, yes, you would have a
Russellian paradox. But the class of all sets is
not a set, and the list of algorithms (despite the
fact that it exists) is not the output of one of
those algorithms.

> 2. Can all predicates be generalized as having
> infinite arity, e.g. a
> predicate "philosopher(socrates)." as being
> "philosopher(socrates, ..., ...)."

No. The classical paradigm admits only finite
arities. Given that there is no finite bound
upon these finite arities, it might
seem that allowing denumerable arities wouldn't
hurt anything, but it does. Even in some infinitary
logics, arities are still restricted to being finite.

.

Relevant Pages

  • Re: An instance of Russells paradox?
    ... > Prolog is seriously not a good choice for that. ... Can all algorithms be enumerated, ... > only if you can formulate the enumeration algorithmically. ... > upon these finite arities, ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... Can all algorithms be enumerated, ... >Diagonalize out of your enumeration to prove that not all functions are ... list of total functions will be another total function which is ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... Can all algorithms be enumerated, ... >>language. ... >>Diagonalize out of your enumeration to prove that not all functions are ... and there is no diagonalisation problem with that. ...
    (sci.logic)
  • Re: An instance of Russells paradox?
    ... > difficulties which I seem to be unable to overcome on my own. ... Can all algorithms be enumerated, ... Diagonalize out of your enumeration to prove that not all functions are ... > another way of expressing the set of all sets)? ...
    (sci.logic)
  • Re: Matrices implementations
    ... I think you are perfectly right about the need for C/C++ algorithms. ... it is in my expectation that Prolog systems could advance ... is "extract all substrings from a string, ... extract_substring(String, SubString):- ...
    (comp.lang.prolog)
Loading