slideshow 3

Logic seminar

usually takes place each Monday at 13:30 in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen
More information on the old seminar web page. The programme is announced via the mailing list.

Unprovability of circuit upper bounds in Cook's theory PV

Igor Oliveira
Charles University
Wednesday, 19. April 2017 - 13:30 to 15:00
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.

Is Bolzano's theory of infinity consistent?

Kateřina Trlifajová
Faculty of Information Technology, Czech Technical University, Prague
Monday, 10. April 2017 - 13:30 to 15:00
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?

Nonstandard methods in Ramsey-type combinatorics, part II

Petr Glivicky
University of Economics & Charles University
Friday, 31. March 2017 - 13:30 to 15:00
Recently, nonstandard methods have been successfully applied in many areas of combinatorics. The nonstandard methodology provides an extension of the universe of mathematics by new ideal (nonstandard) objects such as "an infinitely large natural number", "an infinitely small neighborhood of a point", and many more. The rich structure of relations between the original (standard) and the new (nonstandard) objects enables the standard objects and their standard properties to be described and studied by means of nonstandard concepts. It turns out that this nonstandard description is in many cases more elegant and the nonstandard proofs clearer and shorter than their standard alternatives. In this series of two talks, I outline a nonstandard approach to Ramsey-type combinatorics. I prove two nonstandard Ramsey-type principles of the following common form (vaguely): "If, in a coloring of finite subsets of natural numbers, certain nonstandard object (a witness)... more

Nonstandard methods in Ramsey-type combinatorics, part I

Petr Glivicky
University of Economics & Charles University
Monday, 13. March 2017 - 13:30 to 15:00
Recently, nonstandard methods have been successfully applied in many areas of combinatorics. The nonstandard methodology provides an extension of the universe of mathematics by new ideal (nonstandard) objects such as "an infinitely large natural number", "an infinitely small neighborhood of a point", and many more. The rich structure of relations between the original (standard) and the new (nonstandard) objects enables the standard objects and their standard properties to be described and studied by means of nonstandard concepts. It turns out that this nonstandard description is in many cases more elegant and the nonstandard proofs clearer and shorter than their standard alternatives. In this series of two talks, I outline a nonstandard approach to Ramsey-type combinatorics. I prove two nonstandard Ramsey-type principles of the following common form (vaguely): "If, in a coloring of finite subsets of natural numbers, certain nonstandard object (a witness)... more

Pages