slideshow 3

Logic seminar

usually takes place each Monday at 16:00 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.

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