slideshow 3

Logic seminar

usually takes place each Monday at 13:30 temporarily on Zoom starting at 15:30, normally in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.

Definability in (discretely) ordered integrally divisible modules

Petr Glivický
Institute of Mathematics
Monday, 10. November 2014 - 13:30
An ordered R-module M with a distinguished element 1 > 0 is called integrally divisible if for each scalar 0 < r in R, any m from M can be divided by r with a remainder (i.e. m = rn + i for some n, i from M with 0 <= i < r1). I show that all definable sets in such a module M are "protoperiodic" and therefore M satisfies quantifier elimination up to bounded formulas. This result is particularly interesting if understood in a wider context of model theory of linear arithmetics. I will try to give a brief survey of this arithmetical background.

The PCP theorem in Bounded Arithmetics, Part 2

Ján Pich
Charles University
Monday, 28. April 2014 - 13:30
We will prove the exponential PCP theorem in the theory APC_1, the PCP theorem in PV_1, assuming certain facts about (n,d,lambda)-graphs, and will discuss the possibility of deriving the PCP theorem in S^1_2 unconditionally.

Fermat's Last Theorem and Catalan's conjecture in Weak Exponential Arithmetics

Petr Glivický
Institute of Mathematics, AS CR
Monday, 7. April 2014 - 13:30
Wiles's proof of Fermat's Last Theorem (FLT) has stimulated a lively discussion on how much is actually needed for the proof. Despite the fact that the original proof uses set-theoretical assumptions unprovable in Zermelo-Fraenkel set theory with axiom of choice (ZFC), it is widely believed that much less is needed in principle. Harvey Friedman even conjectured that Fermat's Last Theorem is provable in so called elementary function arithmetic (EFA) (which is just ISigma_0 + "2^x is total" in a different language). Smith has showed that EFA proves Fermat's Last Theorem for some small even exponents n (e.g. for n = 4, 6, 10). On the other hand Shepherdson and recently Kolodziejczyk constructed models of IOpen and T^0_2 respectively, where FLT does not hold for n=3. I will present a joint work with Vítězslav Kala. We consider structures and theories in the language L^e=(0,1,+,*,e,

The PCP theorem in Bounded Arithmetics

Ján Pich
Charles University
Monday, 10. March 2014 - 13:30
We will prove the exponential PCP theorem in the theory $APC_1$, the PCP theorem in $PV_1$, assuming certain facts about $(n,d,lambda)$-graphs, and will discuss the possibility of deriving the PCP theorem in $S^1_2$ unconditionally.

Pages