[FOM] Turing machines, algorithms, and category theory

[Paul Hollander]

On 5/1/17 00:08, Patrik Eklund wrote:
> Recursion resides in set theory, and cannot easily be abstracted away 
> from it.

Recursively definable sets reside in set theory for sure.

But recursively generated syntax is a linguistic fact, independently of 
set theory.  It is representable in the lambda calculus, for example, 
and in theories of arithmetic and logic.

I would say that recursion is used by a theory, not that it resides in a 
theory.

Cheers,

Paul Hollander