Which structures can constitute the foundations of mathematics?

[kfx]

It is a well known view that mathematical logic together with set theory can be used as a foundation for the whole the rest of mathematics. Category theory also has been mentioned as a candidate for this, as an alternative of set theory.

But recently I heard (from a non-mathematician) a view that whole of mathematics could be based on recursive functions instead. Recursive functions as in theory of computations (aka. computable functions).

I have an intuitive notion that recursive functions cannot be used in such way, but I cannot think of the exact reasons why. It seems that using them for foundations would purge out of mathematics computably not representable structures, such as real numbers (leaving only algebraic numbers and some more like e and pi ), but I do not want use this as a counterargument, because of the obvious counter-counter argument: that "true" mathematics is only what is computable and the rest "is made up by man".

Are set theory elements used in an implicit way in theory of recursive functions? If they are, cannot the theory be rephrased in such a way that they are not being used? Take in account that functions like s(x) (i.e. the successor function) would be primitive element of such theory. What about lambda calculus, Turning machine algorithms and other formalizations equivalent to recursive functions?

This whole discussion is related to the Max Tegmark's paper The mathematical universe.

 

[JSuarez]

But recently I heard (from a non-mathematician) a view that whole of mathematics could be based on recursive functions instead. Recursive functions as in theory of computations (aka. computable functions).

This would lead to a very long discussion but, in fact, that position is held only by a minority group of extreme constructivists that, so far, have yet to produce convincing arguments that computation in the Turing's sense (all other maximal models of computation may be reduced to it) should be taken as a basis for (more than a small part of) Mathematics. In fact, there are far more convincing arguments that restrictions of that sort, mandated by philosophical concerns, are crippling and misplaced; a Princeton philosopher (with strong interests in Mathematics and Logic) compared such type of attempts (of regulating what mathematics is correct by philosophical argument) as "trying to bring down the Eiffel tower by trowing feather pillows at it".

This is not to say that the foundational question of ascertaining how much extralogical postulates do we need to have a sufficient amount of workable mathematics is not interesting: it is. In fact, most of Set Theory seems to be "too much" to everyday mathematics, and a lot can be done with weaker assumptions, but the main point is that this should not be dictated (unless in extreme cases) by weaker system than mathematics itself.