Transfinite recursion and computation in the iterative conception of set

Benjamin Rin

pp. 2437-2462

in: History and philosophy of infinity, Synthese 192 (8), 2015.

Abstract

Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles.