Algebra and Logic Seminar

The next meeting of the seminar will be held on November 7, 2014 (Friday), at 11:00, in Room 578 of the Institute of Mathematics and Informatics.

A talk on

On a hitherto unexploited nonstandard extension of the finitary standpoint

will be delivered by Prof. Sam Sanders, Ghent University, Belgium.

Everybody is invited.

Abstract.
The primitive recursive functions are the class of number-theoretic functions obtained by dropping “unbounded search” from the definition of recursion. This class forms a strict subclass of the recursive functions definable in Peano Arithmetic, the usual axiomatization of arithmetic. Goedel famously proved that primitive recursion *in all finite types* exactly captures the recursive functions definable in Peano Arithmetic, i.e. extending primitive recursion to a larger class of objects yields a much larger class of recursive functions. Now, the bar recursive functionals form a strict extension of the primitive recursive functionals in all finite types, and it is a natural question if one can capture bar recursion by extending primitive recursion to a larger class of objects.
In this talk, we show that primitive recursion in all finite types *with nonstandard number parameters* captures bar recursion.