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.

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

Refuting random 3-CNFs using polynomials requires large proof space

Nicola Galesi
Sapienza University Rome
Monday, 6. March 2017 - 13:30 to 15:00
A main tool in proving (space) lower bounds​ for refuting random k-CNF formulas is the well-known expansion property of incidence graph of the formula. Nevertheless, for k=3 the expansion is no longer sufficient to prove proof space lower bounds for Polynomial Calculus (PCR), a proof system working with polynomials. In the talk we first give an overview of a general technique for proving prove space lower bounds for random CNFs. Then we present a variant of Hall's theorem stating that in bipartite graphs G=(L, R) with left-degree at most 3, L can be covered by certain families of disjoint paths, provided that L expands in R by a factor of (2 − ε), for ε<1/5. With this tool in hand we can capture the space lower bound for the case k=3 for random k-CNFs.

Pages