PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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