
Igor Oliveira

(Charles University)

Unprovability of circuit upper bounds in Cook's theory PV
 Abstract:

We establish unconditionally that for every integer k>=1 there is a language L in P such that it is consistent with Cook's theory PV that L is not in Size(n^k). Our argument is nonconstructive and does not provide an explicit description of this language.

Kate?ina Trlifajová

(Faculty of Information Technology, Czech Technical University, Prague)

Is Bolzano's theory of infinity consistent?
 Abstract:

Bolzano's theory of infinity which is mostly contained in his Paradoxes of Infinity from 1848 is usually considered as a step in a wrong direction. Both Bolzano and Cantor defended actual infinity in mathematics. But while Cantor based his measuring of infinite sets on the onetoone correspodence Bolzano based it on the partwhole principles: the whole is greater than its part.
We'll demonstrate there are several interpretations of Bolzano's theory. Some of them are based on the framework of nonstandard analysis. An open question remains: is there a meaningful interpretation without ultrafilters? Consequently, was Cantor's theory of infinite numbers inevitable?
Pavel Pudlak, Neil Thapen
organizers