Re: Quantifying over functions in first-order logic
- 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!
--- In email@example.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.