Loading ...
Sorry, an error occurred while loading the content.

Re: [aima-talk] Re: Quantifying over functions in first-order logic

Expand Messages
  • Joe Hendrix
    ... This is a useful technique. I ve also seen it called currifying in other papers, however it doesn t let you achieve the full power of second-order logic,
    Message 1 of 9 , Jun 14, 2006
    • 0 Attachment
      > On 6/8/06, cedricstjl <cedricstjl@> wrote:
      > couldn't it be achieved equivalently by reifying functions and
      > predicates?

      This is a useful technique. I've also seen it called currifying in
      other papers, however it doesn't let you achieve the full power of
      second-order logic, much less higher-order logic.

      A basic first-order logic result is that finiteness is not
      expressible. That is there is no sentence P such that M is a model of
      P iff. M is finite. However, in second order logic one can express
      finiteness. Specifically, if P is the statement that all injective
      functions are surjective, then M is a model of P iff. M is finite.

      The wikipedia article on second-order logic discusses some of the
      differences between first-order and second-order logic at more length
      than this email.

      Joe
    • cedricstjl
      Hmmm, I ve got a hard time translating your example, or those from the Wikipedia article into logical sentences (I have no idea how to express that a model is
      Message 2 of 9 , Jun 15, 2006
      • 0 Attachment
        Hmmm, I've got a hard time translating your example, or those from the
        Wikipedia article into logical sentences (I have no idea how to
        express that a model is finite, for instance). I guess I should pick
        up a book on the subject; my only background in logic is from AIMA and
        Hofstadter's book.

        Thanks for the info!

        Cedric

        --- In aima-talk@yahoogroups.com, Joe Hendrix <jhendrix@...> wrote:
        >
        > > On 6/8/06, cedricstjl <cedricstjl@> wrote:
        > > couldn't it be achieved equivalently by reifying functions and
        > > predicates?
        >
        > This is a useful technique. I've also seen it called currifying in
        > other papers, however it doesn't let you achieve the full power of
        > second-order logic, much less higher-order logic.
        >
        > A basic first-order logic result is that finiteness is not
        > expressible. That is there is no sentence P such that M is a model of
        > P iff. M is finite. However, in second order logic one can express
        > finiteness. Specifically, if P is the statement that all injective
        > functions are surjective, then M is a model of P iff. M is finite.
        >
        > The wikipedia article on second-order logic discusses some of the
        > differences between first-order and second-order logic at more length
        > than this email.
        >
        > Joe
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.