Re: Turing completeness of the functional paradigm?

On Mon, 18 Jul 2005 17:42:09 +0100, Robert Low <mtx014@xxxxxxxxxxxxxx> said:
> Babylonian wrote:
>> PA does not define a unique notion of natural numbers. No formalism
>> ever will.
>
> By 'formalism' do you mean 'first order'? Because there are certainly
> sets of axioms which uniquely define the natural numbers: the second
> order Peano axioms do this.

Assuming, of course, a standard model theory for second-order languages.
As I'm sure you know, though, there is also a "general" model theory for
second-order languages that Henkin introduced in proving the
completeness of simple type theory, and second-order languages
interpreted by this model theory are no more expressive than first-order
languages. Hence, so interpreted, second-order PA has nonstandard
models. But standard, second-order *model theory* is no more forced
upon us by the axioms of second-order PA alone than is the standard
*model* forced upon us by the axioms of first-order PA. In this sense,
anyway, it seems to me that Babs is right; the formalism alone isn't
enough. You also need to make an assumption about the background model
theory relative to which you are defining what it is for a theory to
define a certain class.

Chris Menzel

.