•  
    • 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 non-constructive and does not provide an explicit description of this language.
    • 19.04.17   13:30
    • 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 one-to-one correspodence Bolzano based it on the part-whole 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 non-standard analysis. An open question remains: is there a meaningful interpretation without ultrafilters? Consequently, was Cantor's theory of infinite numbers inevitable?
    • 10.04.17   13:30

    Pavel Pudlak, Neil Thapen
    organizers

  •