For more information about this meeting, contact Jason Rute, Stephen Simpson, Jan Reimann.

Title: | The Muchnik topos |

Seminar: | Logic Seminar |

Speaker: | Sankha Basu, Penn State |

Abstract: |

A. A. Muchnik in his 1963 paper titled "Strong and weak reduciblity of algorithmic problems" described how mass problems under weak reduciblity form a model for intuitionistic propositional calculus. This interpretation formalized the well known 'Calculus of problems' introduced by Kolmogorov in 1932.
A recent paper, submitted for publication, authored by the speaker and Stephen Simpson, discusses an extension of this semantics to higher-order intuitionistic logic and mathematics. This model has been named as the Muchnik topos. The paper also introduces a new class of intuitionistic real numbers, called the Muchnik reals, which are different from the Cauchy and the Dedekind reals. Within the Muchnik topos, we obtain a choice principle (\forall x\exists y A(x,y))\implies(\exists w\forall x A(x,wx)) and a bounding principle (\forall x\exists y A(x,y))\implies(\exists z\forall x\exists y (y\le_{\mathrm{T}}(x,z)\land A(x,y)), where x,y,z range over Muchnik reals, w ranges over functions from Muchnik reals to Muchnik reals, and A(x,y) is a formula not containing w or z. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 10 / 07 / 2014 |

Time: | 02:30pm - 03:45pm |