Logic and Probability

In mathematical logic people study all kinds of problems connected to formal reasoning, and in probability theory one studies formalizations of such notions as randomness, chance, probability, and expectation. There are numerous ways in which these two subjects are connected and can be combined. For example in the mathematical foundations of probability and measure theory, the study of induction and theories of learning, in computational theories of probability, or in the study of formal systems capturing various parts of probabilistic reasoning. In this project we plan to study one probability logic in particular, namely a logic founded on a well-known model of induction: Valiants pac-model. In doing so, our concern is not so much the modelling of induction, but the fundamental mathematical properties of the logic, such as the structure of its models and its proof-theoretic and computational properties. Another topic of interest in this context is the study of algorithmic randomness. This combination of computability theory and probability theory emerged in the 1960`s in various forms, exhibiting several magnificent interactions between the various basic intuitions surrounding probability and randomness, for example between the intuition that a random object is not compressible (leading to the field of Kolmogorov complexity) and the intuitions that are behind classical measure theory. In recent years this area has become very lively again, with numerous new fundamental insights from computability theory. We plan to continue the study of algorithmically random sequences and their applications in computability theory.