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.)


Vorträge

2. November 2010, 16 Uhr c.t., HS 134, AM

Kai Hauser, Technische Universistät Berlin
Incomparable, Non-Contrived, Strong Axioms of Infinity


9. November 2010, 16 Uhr c.t., HS 134, AM

Vadim Puzarenko, Sobolev Institute of Mathematics, Novosibirsk
Real Numbers and Admissible Structures


16. November 2010, 16 Uhr c.t., HS 134, AM

Jason Teutsch, Universität Heidelberg
An incomplete set of shortest descriptions


23. November 2010, 16 Uhr c.t., HS 134, AM

Leonid Levin, Boston University, Universität Heidelberg, Humboldt Foundation
Kolmogorov Complexity, Information, and Foundations of Probability Theory


30. November 2010, 16 Uhr c.t., HS 134, AM

Jason Teutsch, Universität Heidelberg
How powerful are integer-valued martingales?


14. Dezember 2010, 16 Uhr c.t., HS 134, AM

Frank Stephan, National University of Singapore
Automatic Structures and Model Theory


17. Dezember 2010, 13 Uhr c.t., HS - 111, AM

Kai Hauser, TU Berlin
Intuition and Mathematical Objects


21. Dezember 2010, 16 Uhr c.t., HS 134, AM

Victor Selivanov, Novosibirsk
The fine hierarchy of omega-regular k-partitions


18. Januar 2011, 16 Uhr c.t., HS 134, AM

Wei Wang, Sun Yat-sen University, Guangzhou
Rainbow Ramsey Theorems and Reverse Mathematics


15. Februar 2011, 16 Uhr c.t., HS 134, AM

Chunlai Zhou, Renmin University, Peking
Probability Logic for Harsanyi Type Spaces



2. November 2010

Incomparable, Non-Contrived, 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 anti-realists 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 self-contained 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:

  • Some basic information about computability on admissible structures.
  • Algorithmic properties of hereditarily finite superstructures over real closed fields. ty and admissible structures.
  • Definability and ∑-definability of the field of real numbers in admissible structures.
  • Model theoretic properties of hereditarily finite superstructures over real closed fields.
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 truth-table 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 domain-random strings, whose truth-table degrees depend on the underlying acceptable numbering. It is possible to achieve a priority-free construction of btt-chains and btt-antichains inside the truth-table complete degree by identifying an acceptable set of domain-random 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.
Talk plan:

  • Paradoxes of Probability.
  • Complexity; Kolmogorov's solution.
  • Universal Probability; Law of Randomness.
  • Information and the Law of Independence.
  • The above Probab. Laws imply all others.
  • Randomness and Independence Conservation Inequalities.
  • Information; Church's Thesis.

[See more in Survey: (T.Probab.& Appl. 3/32, 1987) Kolmogorov and Uspenskii. Algorithms and Randomness.]
30. November 2010

How powerful are integer-valued 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
In the field of Automatic structures, the functions, relations and domains of automatic models have all to be recognisable by finite automata. In the recent years, various approaches from computable model theory have been transferred to the field of automatic structures and questions parallel to those in computable model theory were investigated; in particular one is interested in the questions which of the countable models of a theory can be automatic. Khoussainov and Nerode posed various open questions on automatic structures and model theory. Recently, we made the following progress on the problems of Khoussainov and Nerode.
Talk plan:

  • There is an uncountably categorical but not countably categorical complete theory for which only the prime model is automatic.
  • There are complete theories with exactly 3,4,5,... countable models, respectively, and every countable
  • There is a complete theory for which exactly 2 countable models have an automatic presentation.
  • If LOGSPACE = P then there is an uncountably categorical but not countably categorical complete theory for which the prime model is not automatic but all other models have an automatic presentation.
  • There is a complete theory with countably many countable models including a countable prime model and countable saturated model such that the saturated model has an automatic presentation and the prime model does not have one.
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 non-material objects, and even if there were, we cannot know anything about them. I will examine and develop a view first set forth by the Austrian-German philosopher Edmund Husserl (1859-1938), who argued that there are non-material 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 omega-regular k-partitions

We extend the Wagner hierarchy of omega-regular sets to the omega-regular k-partitions, i.e. to k-tuples of pairwise disjoint omega-regular sets exhausting the Cantor space. The notions of CA-reducibility (by continuous functions) and DA-reducibility (by deterministic asynchronous transducers) are extended to k-partitions in a straightforward way. We extend also the notion of Muller acceptor to the notion of Muller k-acceptor in such a way that they recognize precisely the omega-regular k-partitions. Then, using an extension of our fine hierarchy to the fine hierarchy of k-partitions, we extend the main results of K. Wagner to the case of k-partitions. In particular we characterize the structures of CA- and DA-degrees of omega-regular k-partitions up to isomorphism and show that from given two Muller k-acceptors one can compute whether the corresponding omega-regular k-partitions are in the relation CA (or DA).

18. Januar 2011

The fine hierarchy of omega-regular k-partitions

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 Csima-Mileti'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 game-theoretical 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 multi-player interactive epistemology when compared with one-player 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 S5-knowledge can be implicitly defined by probabilistic belief but not reduced