SS 2018

Montag, 23. April 2018 um 15:15 Uhr, Oberseminar Mathematische Logik, Mengenlehre und Modelltheorie

Merlin Carl (Universität Konstanz)

Canonical Truth

It is an old logical dream to devise an effectively describable axiomatic system for mathematics that uniquely describes `mathematical reality'; in modern logical language, this should mean at least that it uniquely fixes a model.
It is well-known that this dream is unattainable in first-order logic: By the Löwenheim-Skolem-theorem, we get models of all infinite cardinalities once there is one infinite model; and by Gödel's incompleteness theorem, if the theory is strong enough to express elementary arithmetic, it will have different models that are not even elementary equivalent.

In this talk, we investigate `canonically necessary' statements, by which we mean statements that hold in all `canonical' models of ZFC, i.e. in all transitive class models that are uniquely fixed by some extension of ZFC by finitely many extra statements.
It turns out that the realistic mindset is indeed mathematically informative: Examples of canonically necessary statements that do not follow from ZFC are Reitz´ ground model axiom and the non-existence of measurable cardinals.

This is joint work with Philipp Schlicht from Auckland.

Montag, 14. Mai 2018 um 15:15 Uhr, Oberseminar Mathematische Logik, Mengenlehre und Modelltheorie

Lothar Sebastian Krapp (Universität Konstanz)

NIP, o-Minimality and Neural Networks

Let $T$ be a complete theory. A formula $\varphi(\underline{x};\underline{y})$ has the independence property (IP) if in every $\mathcal{M}\models T$ for every $n<\omega$ there exist families of tuples $(\underline{a}_i)_{i < n}$ and $(\underline{b}_J)_{J\subseteq \{0,\ldots,n-1\}}$ such that $\mathcal{M} \models \varphi(\underline{a}_i;\underline{b}_J)$ if and only if $i \in J$. If $\varphi$ does not have IP, it is called NIP. A complete theory in which every formula is NIP is called an NIP theory. Several well-studied classes of complete theories are NIP, most notably any o-minimal theory (cf. [3]).

The notion of NIP theories was introduced by Shelah in [4]. In the same year [1], a paper on statistical learning theory which established the concept of VC dimensions, was published. The connection between NIP and VC dimensions was only found 21 years later in [2]. Surprisingly this connection gave an interesting application of a purely model theoretical and combinatorial concept to neural network learning.

In my talk I will firstly give an introduction to NIP theories and VC dimensions and explain the key steps in the proof that any o-minimal theory is NIP. Secondly I will present the basic concepts of neural network learning and sketch how neural networks and NIP are connected via o-minimality.

References

[1] A. Ya. Chervonenkis and V. N. Vapnik, `The uniform convergence of frequencies of the appearance of events to their probabilities', Teor. Verojatnost. i Primenen. 16 (1971) 264-279 (Russian), Theor. Probability Appl. 16 (1971) 264-280 (English).
   
[2] M. C. Laskowski , `Vapnik-Chervonenkis classes of definable sets', J. London Math. Soc. (2) 45 (1992) 377-384.

[3] A. Pillay and C. Steinhorn, `Definable sets in ordered structures', I, Trans. Amer. Math. Soc. 295 (1986) 565-592.

[4] S. Shelah, `Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory', Ann. Math. Logic 3 (1971) 271-362.

Montag, 4. Juni 2018 um 15:15 Uhr, Oberseminar Mathematische Logik, Mengenlehre und Modelltheorie

Pablo Andújar Guerrero (Universität Konstanz)

Definable topological spaces in o-minimal structures

In model theory a topological space can be interpreted naturally as a second order structure,  namely a set and the unary relation of subsets that corresponds to the topology.  A different approach is that of a first order structure in which there exists a topological space with a basis that is (uniformly) definable.  We call this a definable topological space.  A natural example corresponds to the order topology on any linearly ordered structure.
During this talk I'll present results on definable topological spaces in an o-minimal structure $\mathcal{R}=(R,...)$.  In particular we will classify Hausdorff  definable  topological  spaces  $(X,\tau)$  where $X\subseteq R$.  We'll consider a number of first order properties of these spaces that resemble topological properties and note how, in the o-minimal setting, the induced framework, which we might call "definable topology", resembles general topology.  This is joint work with Margaret Thomas and Erik Walsberg.

Freitag, 8. Juni 2018 um 15:15 Uhr, Oberseminar Reelle Geometrie und Algebra

Jose Capco (RISC Linz)

(Gast von Claus Scheiderer)

An overview of mathematical problems in robotics

In this talk I am going to introduce you to some basic mathematical objects in theoretical kinematics. I am going to introduce dual quaternions and the Study quadric in real 7-dimensional projective space, and I will discuss how some linear spaces in the Study quadric relate to mechanisms. We shall see how some problems in inverse kinematics of manipulators can be solved using linear algebra and classical algebraic geometry. We will roughly discuss Kempe's Universality Theorem and a modern approach in constructing linkages that can trace some types of real algebraic curves. We will finally discuss problems that relate the study of kinematic singularity of mechanisms with real geometry.

Montag, 11. Juni 2018 um 15:15 Uhr, Oberseminar Reelle Geometrie und Algebra

Michael Dritschel (Newcastle University)

(Gast von Maria Infusino)

Factoring Non-negative Matrix Valued Trigonometric Polynomials in Two Variables

It is shown, using Schur complement techniques, that a non-negative matrix valued trigonometric polynomial in two variables can be written as a finite sum of hermitian squares of analytic polynomials. In analogy with the Tarski transfer principle in real algebra, the proof lifts the problem to an ultraproduct, solves it there, and then shows that this implies the existence of a solution in the original context. While the proof is non-constructive, it nevertheless implies a constructive algorithm for the factorization.

Donnerstag, 14. Juni 2018 um 17:00 Uhr, Allgemeines Kolloquium

Michael Joswig (TU Berlin)

(Gast von Claus Scheiderer)

Tropische Geometrie und (lineare) Optimierung

Im Vortrag wird die tropische Geometrie als ein Bindeglied zwischen klassischer algebraischer Geometrie und Optimierung vorgestellt. Sie erlaubt es beispielsweise, Fragen zur algorithmischen Komplexität in Beziehung zu geometrischen Eigenschaften zu setzen.

Freitag, 22. Juni 2018 um 13:30 Uhr, Oberseminar Reelle Geometrie und Algebra

Adam Kurpisz (ETH Zürich)

(Gast von Markus Schweighofer)

The Lasserre/Sum-of-Squares hierarchy for 0/1 optimization problems

The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels. We start with characterizing the set of 0/1 problems that might not still converge at level n-1. These problems are the hardest for the hierarchy in this sense. Moreover, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points and believed that the Lasserre/SoS rank is n-1. We disprove this and derive lower and upper bounds for the rank. We do this by introducing a method for proving Lasserre/SoS bounds when the initial problem formulation exhibits a high degree of symmetry. Finally, we show applications of this technique in 0/1 polynomial optimization.

Montag, 9. Juli 2018 um 15:15 Uhr, Oberseminar Mathematische Logik, Mengenlehre und Modelltheorie

Sandra Müller (Kurt Gödel Research Center, Wien)

(Gast von Merlin Carl)

Large cardinals from the determinacy of games

We will study infinite two player games and the large cardinal strength corresponding to their determinacy. In particular, we will consider mice, which are sufficiently iterable models of set theory, and outline how they play an important role in measuring the exact strength of determinacy hypotheses. After summarizing the situation within the projective hierarchy for games of length $\omega$, we will go beyond that and consider the determinacy of even longer games. In particular, we will sketch the argument that determinacy of analytic games of length $\omega \cdot (\omega+1)$ implies the consistency of $\omega+1$ Woodin cardinals. This part is joint work with Juan P. Aguilera.

Freitag, 13. Juli 2018 um 13:30 Uhr, Oberseminar Reelle Geometrie und Algebra

Mario Kummer (TU Berlin)

Rational representations of plane spectrahedra

A central open question in convex algebraic geometry is whether every hyperbolicity region is a spectrahedron, i.e. defined by a linear matrix inequality. It follows from a theorem by Helton and Vinnikov that this is true in the plane. However the entries of the matrices resulting from their construction are typically algebraic numbers of large degree. We construct a representation with rational matrices provided that the hyperbolic polynomial is defined over the rational numbers. This is joint work with Simone Naldi and Daniel Plaumann.

Montag, 16. Juli 2018 um 15:15 Uhr, Oberseminar Mathematische Logik, Mengenlehre und Modelltheorie

David Schrittesser (Kurt Gödel Research Center, Wien)

(Gast von Merlin Carl)

Maximal discrete sets and their definability

Let $R$ be a relation on the real numbers, or a similar space, such as the space of functions from the natural numbers to the natural numbers with the product topology (Baire space). By a maximal $R$-discrete set, we mean a set $A$ all of whose points are not related by $R$, and so that no proper superset of $A$ has this property. For instance, a basis of the real numbers as a vector space over the rationals (a Hamel basis) is a maximal discrete set for the relation of being linearly independent.

For many relations $R$ one can show that such maximal discrete sets can never have a simple definition: For instance a Hamel basis cannot be measurable, and hence if such a basis is definable at all, the definition cannot be very simple (it is in fact independent from the axioms of set theory whether there is a definable Hamel basis).

In 2016, Horowitz and Shelah surprised everyone by showing that for the relation $R_{ed}$ on Baire space given by $f R_{ed}  g$ iff $\{n | f(n)=g(n)\}$ is finite, there is a maximal discrete set (a "maximal eventually different family") with a simple definition. Later I showed there even is a (topologically) closed such set. While this set must have size continuum, recently and in joint work with Vera Fischer we showed that it is consistent with ZFC that there is a maximal eventually different family with a not too complicated definition and of size smaller than the continuum.

Freitag, 20. Juli 2018 um 13:30 Uhr, Oberseminar Reelle Geometrie und Algebra

Tillmann Weisser (LAAS-CNRS, Toulouse)

(Gast von Markus Schweighofer)

A moment approach to nonlinear hyperbolic PDEs

We propose to solve numerically polynomial scalar hyperbolic conversation laws using tools from polynomial optimization. The approach is based on a very weak notion of solution to the differential equation, so-called measure-valued (mv) solutions. Imposing additional entropy conditions, one can prove that the entropy mv solution can be identified with the classical entropy solution. We show that the entropy mv solution can be characterized as the solution to an instance of the Generalized Moment Problem, an infinite dimensional linear problem on Borel measures. Results from real algebraic geometry allow to efficiently approximate such solutions via semi definite programming. This gives rise to an alternative numerical scheme to compute solutions to polynomial scalar hyperbolic conversation laws. The effectiveness of our approach is demonstrated on the Riemann problem for Burgers equation. This is joint work with S. Marx, D. Henrion and J. B. Lasserre.