Re: Second order arithmetic and higher order arithmetic

On Feb 27, 6:04 pm, "teca...@xxxxxxxxx" <teca...@xxxxxxxxx> wrote:
On Feb 25, 9:53 pm, kleptomaniac6...@xxxxxxxxxxx wrote:

The title is a bit vague and so is the question (or questions) I have
to ask. There are canonical axioms for full second order arithmetic
(Peano axioms with second order induction and comprehension), like for
ZF set theory. However there is little talk of third order arithmetic.
What would the canonical axioms for third order arithmetic be? Would
it just be taking the axioms for second order arithmetic and extending
the comprehension axiom to third-order formulas? Could this then be
extended to incorporate arithmetic of the nth order for each n into
one formal system? If so, how is this related to existing formal
systems?

Roughly speaking, at the first order you cannot quantifiate over
predicates. In higher order logic you can do such quantification.
The idea is that a predicate of the first order logic has order 1.
Then in a logic of order N you can quantifiate over predicate of order
strictly lower than N. From this, you can define whatever
aximatization you want.

For further detail you can read the classics
Recursion Theory for Metamathematics. RM Smullyan (my favorite)
Introduction to metamathematics. SC Kleene
Theory of recursive functions and effective computability. H Rogers
Introduction to Mathematical Logic. A. Church

Then the different orders are of interest. For exemple in term
rewrinting, the matching at the 3rd order is an NP complete problem,
at the 4th order it is a decidable problem... I don't remember if it
is decidable at the 5th order but I know that the proof is really
complicated
--
MK

I know about what nth order quantification allows. I'm not sure what
you mean by "term rewriting". My question was more about, how does
second order arithmetic relate to higher order arithmetic, and to ZF
set theory? Second order arithmetic can only cover the first two
levels of the cumulative hierarchy, which starts with numbers, then
sets of numbers, then sets of sets of numbers, and so on. Now probably
most mathematics of interest to most mathematicians takes place in the
first few levels of this hiearchy. It's hard to imagine an interesting
9th-order statement, say. But there must be third-order notions found
in mainstream mathematics which cannot be expressed in lower order
terms. Could you have a formal system expressed in terms of the
cumulative hierarchy which covers all levels? Based on the hierarchy
got from iterating "set of", starting with numbers. I guess some kind
of axiom schemata would be needed to cover all the types. Maybe such a
formal system already exists. But how would it relate to second order
arithmetic and to ZF? Basically what I am thinking of is "extending"
second order to arithmetic to cover all orders.
.

Relevant Pages

  • Re: Some questions on logic
    ... > construct set theory, then arithmetic. ... There are many different logics. ... non-logical axioms such as those governing the predicate "is an element ... Also you might take second order logic, let's call it SOL, and build ...
    (sci.logic)
  • 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: 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: Turing completeness of the functional paradigm?
    ... sets of axioms which uniquely define the natural numbers: the second order Peano axioms do this. ... and second-order languages ... the (second order) PA axioms were categoric, which meant that there was essentially only one model. ... is the whole of N) not to give uniqueness except that ...
    (sci.logic)