Oberseminar Mathematische Logik

Advanced talks on mathematical logic by guests and members of the logic group

Organized by

• Prof. Dr. Peter Koepke
• Philipp Schlicht

Time and location

Mondays 16:30-18:00 at seminar room A, Beringstrasse 4.
The members of the seminar are welcome for coffee and tea at Peter Koepke's office, Room 44, Beringstrasse 4 from 16:00-16:30 before the talks.

Programme

27 October Peter Koepke "The computational strength of infinite time register machines"

We show that a real a∈ ^ω2 is computable by an Infinite Time Register Machine (ITRM) as defined in [1] iff x∈L_{(ω_ω)^CK} where ω_ω^CK = sup_{n < ω} ω_n^CK is the supremum of the first ω admissible ordinals. This corresponds to the fact that an ITRM with 0 input and empty oracle either halts before time ω_ω^CK or it does not halt at all. So the halting times of such machines are cofinal in ω_ω^CK, i.e., ω_ω^CK is the supremum of the ITRM clockable ordinals. Moreover we expect exact dependencies between the number of machine registers and the number of admissible ordinals needed.
[1] Peter Koepke, Russell Miller. An Enhanced Theory of Infinite Time Register Machines. CiE pp.306-315 (2008)
 
 

3 November Wolfgang Thomas (RWTH Aachen) " Die algorithmische Theorie unendlicher Spiele: Kernresultate und aktuelle Entwicklungen"

Die algorithmische Theorie unendlicher Spiele beginnt mit dem Church'schen Syntheseproblem (1957) und seiner Lösung durch Büchi und Landweber (1969): Ist die Gewinnbedingung in der monadischen Theorie zweiter Stufe über (N,+1) ausdrückbar, dann ist das zugehörige (Gale-Stewart-) Spiel determiniert, man kann den Gewinner bestimmen, und ein endlicher Automat genügt für die Ausführung einer Gewinnstrategie. Wir skizzieren einen vereinfachten Beweis des Büchi-Landweber-Theorems und diskutieren dann drei Zweige der Verallgemeinerung, die heute in der theoretischen Informatik studiert werden: einen allgemeinen Zusammenhang zwischen Gewinnbedingung und Gewinnstrategie, die Verschärfung von Gewinnbedingungen durch Optimalitätsforderungen sowie die Betrachtung unendlicher Spielarenen und transfiniter Partien.
 
 

10 November Klaus Ambos-Spies (Universität Heidelberg) "Starke Reduzierbarkeiten und rekursiv aufzählbare Mengen"

Obwohl die Turing (T-)-Reduzierbarkeit, die den Begriff der relativierten Berechenbarkeit erfasst, die meist studierte rekursive Reduzierbarkeit ist, haben die starken Reduzierbarkeiten  bei der Klassifikation der rekursiv aufzählbaren (r.a.) Mengen stets eine wichtige Rolle gespielt. Ein Grund hierfür ist, dass diese im Gegensatz zu der T-Reduzierbarkeit interessante Struktureigenschaften erhalten. So sind z.B. alle many-one-vollständigen r.a.\ Mengen kreativ.
Die starken Reduzierbarkeiten erhält man als Spezialfall der Turingreduzierbarkeit, indem man Anzahl und Größe der zulässigen Orakelfragen einschränkt. In unserem Vortrag diskutieren wir einige neue Ergebnisse über die sogenannte cbT-Reduzierbarkeit, in der die Größe der Orakelfragen (bis auf eine additive Konstante) durch die Eingabengröße beschränkt ist. Unter anderem geben wir einen neuen sehr einfachen Beweis des Satzes von Barmpalias, dass es keine cbT-vollständigen r.a. Mengen gibt. Die cbT-Reduzierbarkeit fand in letzter Zeit viel Beachtung, da sie sich als wichtiges Hilfsmittel bei Anwendungen erwiesen hat, wie z.B. bei der Analyse des Zufallsbegriffs.
 
 

There is no seminar on November 17 and 24.
 
 

1 December René Schipperus (Universität Münster) "Partitions of ω₁"

We give a survey of the known partition relations on ω₁, with some simple proofs. Then the most recent work on open conjectures will be discussed.
 
 

There is no seminar on December 8 and 15.
 
 

22 December Thilo Weinert "Martin's Axiom and the covering number of Marczewski's ideal"

The covering number cov(I) of an ideal I on the set of reals is defined as the smallest cardinality such that there exists a set X subset I of this cardinality with ∪X = R.The ideal of meager sets of reals, I_c can be defined in terms of Cohen forcing. If P denotes Cohen forcing we have I_c = {x ⊂ R | ∀ p ∈ P ∃q ∈P, q ≤ p and [q] ∩ x = 0}. Analogously, using Sacks forcing, here denoted by Q, one can define Marczewski's ideal, I_s := {x ⊂ R| ∀ p ∈ Q ∃ q ∈ Q , q ≤ p and [q] ∩ x = 0}. Unlike many other cardinal invariants, the covering number of Marczewski's ideal can be small, i.e. ω₁ while Martin's axiom holds and the continuum hypothesis fails. This is a result published in 1992 by Judah, Miller and Shelah.
 
 

There is no seminar on January 5.
 
 

12 January Katrin Tent (Universität Münster) "Uniform primitive Permutationsgruppen"

Primitive Permutationsgruppen sind die 'Bausteine' für beliebige Gruppenwirkungen. Allerdings ist die Primitivität einer Gruppenwirkung im Allgemeinen keine Eigenschaft 1. Stufe. Ich werde diese Eigenschaft erklären und dann zeigen, wie die Theorie der pseudoendlichen Körper und Differenzenkörper zu neuen Ergebnissen über primitive Permutationsgruppen führt.
 
 

19 January Antonio Montalbán (University of Chicago) "Equimorphism types of linear orderings"

We analyze the structure of equimorphism types of linear orderings ordered by embeddability. (Two linear orderings are equimorphic if they can be embedded in each other.) Our analysis is mainly from the viewpoints of Computable Mathematics and Reverse Mathematics. But we also obtain results, as the definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.
Here are our main results: Spector proved in 1955 that every hyperarithmetic ordinal is isomorphic to a computable one. We extend his result and prove that every hyperarithmetic linear ordering is equimorphic to a computable one. From the viewpoint of Reverse Mathematics, we look at the strength of Fraïssés conjecture.
From our results, we deduce that Fraïssés conjecture is sufficient and necessary to develop a reasonable theory of equimorphism types of linear orderings.
 
 

26 January Stefan Geschke "Stetige Ramseytheorie, 1"

Der klassische unendliche Satz von Ramsey lässt sich nicht ohne weiteres auf überabzählbare Mengen verallgemeinern. Das beste Resultat ist hier der Satz von Erdös und Rado. Wenn man sich jedoch auf Färbungen einschränkt, die gewisse Stetigkeitseigenschaften haben, erhält man eine interessante Theorie, die auch Bezüge zu anderen Gebieten der Mathematik hat.
 
 

2 February Stefan Geschke "Stetige Ramseytheorie, 2"

 

The seminar will continue in the summer semester.