[FOM] Turing machines, algorithms, and category theory

Paul Hollander paul at personalit.net
Wed May 3 16:10:22 EDT 2017

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 


Paul Hollander

More information about the FOM mailing list