## Re: Quantifying over functions in first-order logic

Expand Messages
• 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 1 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

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.