Oberseminar
Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in Raum 134 des Gebäudes INF 294.
(The talks are usually on Tuesday at 4 p.m. in Room 134 of building INF 294.)
2. November 2010, 16 Uhr c.t., HS 134, AM Kai Hauser, Technische Universistät Berlin 9. November 2010, 16 Uhr c.t., HS 134, AM Vadim Puzarenko, Sobolev Institute of Mathematics, Novosibirsk 16. November 2010, 16 Uhr c.t., HS 134, AM Jason Teutsch, Universität Heidelberg 23. November 2010, 16 Uhr c.t., HS 134, AM Leonid Levin, Boston University, Universität Heidelberg, Humboldt Foundation 30. November 2010, 16 Uhr c.t., HS 134, AM Jason Teutsch, Universität Heidelberg 14. Dezember 2010, 16 Uhr c.t., HS 134, AM Frank Stephan, National University of Singapore 17. Dezember 2010, 13 Uhr c.t., HS  111, AM Kai Hauser, TU Berlin 21. Dezember 2010, 16 Uhr c.t., HS 134, AM Victor Selivanov, Novosibirsk 18. Januar 2011, 16 Uhr c.t., HS 134, AM Wei Wang, Sun Yatsen University, Guangzhou 15. Februar 2011, 16 Uhr c.t., HS 134, AM Chunlai Zhou, Renmin University, Peking 


2. November 2010 
Incomparable, NonContrived, Strong Axioms of Infinity The Axiom of Infinity stipulates the existence of infinite sets. One of the most distinctive and intriguing developments of modern set theory has been the realization that, despite widely divergent incentives for postulating more powerful axioms of infinity, there is essentially only one way of ascending the higher reaches of infinity. To the mathematical realist the unexpected convergence suggests that all these axiomatic extensions describe different aspects of the same underlying reality. That interpretation has come under attack by antirealists seeking to explain the convergence as an artefact of the language of set theory. Here we show that this reductionist view is flawed by exhibiting examples of arguably natural strong axioms of infinity that are demonstrably incomparable. This is joint work with Hugh Woodin. The talk is selfcontained and does not presuppose any particular expertise in mathematical logic. 

9. November 2010 
Real Numbers and Admissible Structures In this talk we will discuss the following aspects:


16. November 2010 
An incomplete set of shortest descriptions In this talk I will demonstrate the power of making (domain) random strings to be (Kolmogorov) random. The truthtable degree of the set of shortest programs is a outstanding problem in recursion theory. I will discuss two related sets, the set of shortest descriptions and the set of domainrandom strings, whose truthtable degrees depend on the underlying acceptable numbering. It is possible to achieve a priorityfree construction of bttchains and bttantichains inside the truthtable complete degree by identifying an acceptable set of domainrandom strings within each degree. 

23. November 2010 
Kolmogorov Complexity, Information, and Foundations of Probability Theory While fundamental to many sciences, the concept of Randomness is quite paradoxical. Kolmogorov's analysis clarified it greatly by revealing its computational nature.
[See more in Survey: (T.Probab.& Appl. 3/32, 1987) Kolmogorov and Uspenskii. Algorithms and Randomness.] 

30. November 2010 
How powerful are integervalued martingales? The classical randomness notions of Schnorr and Kurtz permit gamblers to bet any amount of money within their means. In this talk, we consider a more realistic paradigm in which gamblers must place a minimum bet of one dollar. The corresponding randomness notion turns out to be incomparable with the classical notions mentioned above. Most casinos operate by exploiting the law of large numbers, however, by examining an even more restrictive model in which we ban wagers greater than a million dollars, we obtain an alternate principle through which an online casino might operate profitably. The open questions at the end of this talk should be accessible to a general audience. 

14. Dezember 2010 
Automatic Structures and Model Theory Joint Work with: Pavel Semukhin


17. Dezember 2010 
Intuition and Mathematical Objects One very widespread assumption in philosophy has been that empiricism entails materialism: if all knowledge reaches us through our senses, then the only things we can know something about are material objects. We therefore have no basis for believing that there are any nonmaterial objects, and even if there were, we cannot know anything about them. I will examine and develop a view first set forth by the AustrianGerman philosopher Edmund Husserl (18591938), who argued that there are nonmaterial objects and that they can be recognized in a process very closely related to ordinary perception. In fact, the perception of physical objects is just a special case of this more universal way of recognizing objects of any kind. 

21. Dezember 2010 
The fine hierarchy of omegaregular kpartitions We extend the Wagner hierarchy of omegaregular sets to the omegaregular kpartitions, i.e. to ktuples of pairwise disjoint omegaregular sets exhausting the Cantor space. The notions of CAreducibility (by continuous functions) and DAreducibility (by deterministic asynchronous transducers) are extended to kpartitions in a straightforward way. We extend also the notion of Muller acceptor to the notion of Muller kacceptor in such a way that they recognize precisely the omegaregular kpartitions. Then, using an extension of our fine hierarchy to the fine hierarchy of kpartitions, we extend the main results of K. Wagner to the case of kpartitions. In particular we characterize the structures of CA and DAdegrees of omegaregular kpartitions up to isomorphism and show that from given two Muller kacceptors one can compute whether the corresponding omegaregular kpartitions are in the relation CA (or DA). 

18. Januar 2011 
The fine hierarchy of omegaregular kpartitions In Reverse Mathematics, people formulate mathematics in second order arithmetic and study strength of theorems with respect to provability or consistency. Among reverse mathematical topics, the strength of Ramsey like combinatorial principles has continuously attracted recursion theorists for decades and some hard questions remain open. In a very recent work, Csima and Mileti presented a new proof of Rainbow Ramsey Theorem for pairs, which is some kind of a dual of Ramsey Theorem for pairs. This new proof is relating to algorithm randomness. Using results in randomness, they proved some interesting reverse mathematical results of Rainbow Ramsey Theorem for pairs. We combine the techniques from CsimaMileti's work with some early techniques and results relating to Ramsey Theorem for pairs and show that Rainbow Ramsey Theorem for triples is weaker than the Arithmetic Comprehension Axioms. 

15. Februar 2011 
Probability Logic for Harsanyi Type Spaces Probability logic has been an important approach to investigate belief types in gametheoretical economics. In this talk, I will first present a probability logic for Harsanyi Type spaces, and show its completeness and unique extension theorem. Next I prove the relative complexity of multiplayer interactive epistemology when compared with oneplayer epistemology by showing that, if the probability indices of the language is restricted to a finite set of rationals, the canonical space for probabilistic beliefs with one player is countable while the canonical one with at least two players has the cardinality of the continuum. In the final part of this talk, I generalize the three notions of definability: implicit definability, reducibility and explicit definability in multimodal logic to the setting of logics of probabilistic belief and knowledge, and show that S5knowledge can be implicitly defined by probabilistic belief but not reduced 