It seems that there are times when parts of the second order model of a certain structure can be determined to a significant degree using the first order model of the structure and recursion. For example, irrational numbers are a topological construction over $\mathbb{Q}$ and thusly part of its second order model, however we know that every irrational number is the limit of some sequence of rational numbers (the sequences themselves collections of rational numbers and part of the second order model).

Where things become slightly confusing to me is the fact that certain sequences can be cast entirely using finite algebraic expressions of rational numbers (part of the first order model) and recursion, for example we have that for any fixed $q\in\mathbb{Q}$ with $0<q$ the sequence defined by recursion on $\omega$ as $$a_0=1$$ $$a_{n+1}=\frac{1}{2}(a_{n}+\frac{q}{a_n})$$ satisfies $$\lim_{n\rightarrow\infty}a_n=\sqrt{q}.$$ I'm wondering what is 'happening' in situations like this, where pieces of the second order model of some structure can be faithfully cast using the first order model and recursion. It seems to me like recursion allows us to construct sequences out of algebraic expressions which naturally moves us into the second order model, but I was wondering if there was some literature that went deeper than this surface level observation.

EDIT: There is a vote to close this question as unclear; to hopefully provide an additional (but much broader) example of what I'm talking about, see this blog post by Joel David Hamkins: http://jdh.hamkins.org/second-order-transfinite-recursion-is-equivalent-to-kelley-morse-set-theory/. This is an example of a situation where sufficiently powerful recursion allows for the passage from some first order theory (GBC class theory) into a stronger theory with second-order type semantics (MK class theory).

I'm wondering if this phenomenon of sufficiently powerful recursion allowing for passage between first order and second order models has been studied in the context of more algebraic-topological models, like the rational number example given above where limiting notions (a topological property) are introduced in a significant sense via algebra in a first order model together with recursion of some length.

  • 1
    $\begingroup$ What I'll say may be completely off mark, but one notable thing about recursion is that, in a certain sense, it allows us to "condense" infinitary resources using finitary means. For instance, without recursion, it's not possible to define addition in the first-order theory of the naturals with the successor function, as that would require an infinitely long formula. Recursion allows us to "condense" all the infinitely many clauses in a single finitary formula. Maybe there is some relation? $\endgroup$ – Nagase Aug 26 '17 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.