Re: Turing completeness of the functional paradigm?

Chris Menzel wrote:
On Mon, 18 Jul 2005 17:42:09 +0100, Robert Low <mtx014@xxxxxxxxxxxxxx> said: 
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. 

Nope, I wasn't even aware of my ignorance in this regard :-(

Hence, so interpreted, second-order PA has nonstandard
models. 

So where do they live? I was under the impression that
the (second order) PA axioms were categoric, which meant
that there was essentially only one model. Do you have to
play in a different universe to get the different models?

I can't see any other way for the inductive axiom
(any set containing zero and closed under successor
is the whole of N) not to give uniqueness except that
'any set' doesn't mean what I think it ought to. But
I've got used to the idea that my intuition isn't
always all that reliable.

> 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.


I'm sure I was taking that for granted; I didn't even
realise I had any choice in the matter...
.

Relevant Pages

  • Re: Set Theory: Should you believe?
    ... "second order theory", i.e., one which is couched in a formal language ... a set of first order axioms asserting that any first order definable subset ... NOT "confused" for you to intuit one thing and me to intuit another ... IN FIRST-order PA and if ANYbody fails to bother, ...
    (sci.logic)
  • Re: Second order arithmetic and higher order arithmetic
    ... There are canonical axioms for full second order arithmetic ... ZF set theory. ... most mathematics of interest to most mathematicians takes place in the ...
    (sci.logic)
  • Re: What is the 1st order formal system known as PA?
    ... common to see Peano arithmetic as having axioms not including those for the operations of addition and multiplication. ... These axioms can be expressed straightforwardly in the second order language with a symbol S for the successor function. ... the Paris-Harrington independence result mentioned is about first order Peano arithmetic. ... The function symbol S is only applicable to a natural number and produces a natural number; the function symbols + and * are only applicable to natural numbers and produce a natural number; the relation symbol "in" holds between a natural numner and a set. ...
    (sci.logic)
  • Re: Very easy problem but I am a stupid non-logician idiot
    ... wikipedia in case you think I mean something else). ... clearly induction has to be used somewhere to define addition. ... the system of second order wikipedia arithmetic doesn't ... mention anything about + or x or> in the axioms or language. ...
    (sci.logic)
  • Re: Very easy problem but I am a stupid non-logician idiot
    ... But how would you do it based on the induction axiom and the ... mention anything about + or x or> in the axioms or language. ... I was under the impression that induction ... I still forgot the uniqueness of the function. ...
    (sci.logic)