Past Logic Seminar

13 June 2008
15:15
Alex Prestel
Abstract
We consider finite sequences $h = (h_1, . . . h_s)$ of real polynomials in $X_1, . . . ,X_n$ and assume that the semi-algebraic subset $S(h)$ of $R^n$ defined by $h1(a1, . . . , an) \leq 0$, . . . , $hs(a1, . . . , an) \leq 0$ is bounded. We call $h$ (quadratically) archimedean if every real polynomial $f$, strictly positive on $S(h)$, admits a representation $f = \sigma_0 + h_1\sigma_1 + \cdots + h_s\sigma_s$ with each $\sigma_i$ being a sum of squares of real polynomials. If every $h_i$ is linear, the sequence h is archimedean. In general, h need not be archimedean. There exists an abstract valuation theoretic criterion for h to be archimedean. We are, however, interested in an effective procedure to decide whether h is archimedean or not. In dimension n = 2, E. Cabral has given an effective geometric procedure for this decision problem. Recently, S. Wagner has proved decidability for all dimensions using among others model theoretic tools like the Ax-Kochen-Ershov Theorem.
12 June 2008
16:00
Bjorn Poonen
Abstract
Refining Julia Robinson's 1949 work on the undecidability of the first order theory of Q, we prove that Z is definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points.
12 June 2008
16:00
Bjorn Poonen
Abstract
Refining Julia Robinson's 1949 work on the undecidability of the first order theory of Q, we prove that Z is definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points.
6 June 2008
15:15
Stephan Kreutzer
Abstract
Fixed-point logics are a class of logics designed for formalising recursive or inductive definitions. Being initially studied in generalised recursion theory by Moschovakis and others, they have later found numerous applications in computer science, in areas such as database theory, finite model theory, and verification. A common feature of most fixed-point logics is that they extend a basic logical formalism such as first-order or modal logic by explicit constructs to form fixed points of definable operators. The type of fixed points that can be formed as well as the underlying logic determine the expressive power and complexity of the resulting logics. In this talk we will give a brief introduction to the various extensions of first-order logic by fixed-point constructs and give some examples for properties definable in the different logics. In the main part of the talk we will concentrate on extensions of first-order logic by least and inflationary fixed points. In particular, we compare the expressive power and complexity of the resulting logics. The main result will be to show that while the two logics have rather different properties, they are equivalent in expressive power on the class of all structures.
16 May 2008
15:15
Abstract
In recent years Schanuel’s Conjecture (SC) has played a fundamental role in the Theory of Transcendental Numbers and in decidability issues. Macintyre and Wilkie proved the decidability of the real exponential field, modulo (SC), solving in this way a problem left open by A. Tarski. Moreover, Macintyre proved that the exponential subring of R generated by 1 is free on no generators. In this line of research we obtained that in the exponential ring $(\mathbb{C}, ex)$, there are no further relations except $i^2 = −1$ and $e^{i\pi} = −1$ modulo SC. Assuming Schanuel’s Conjecture we proved that the E-subring of $\mathbb{R}$ generated by $\pi$ is isomorphic to the free E-ring on $\pi$. These results have consequences in decidability issues both on $(\mathbb{C}, ex)$ and $(\mathbb{R}, ex)$. Moreover, we generalize the previous results obtaining, without assuming Schanuel’s conjecture, that the E-subring generated by a real number not definable in the real exponential field is freely generated. We also obtain a similar result for the complex exponential field.
7 March 2008
14:15
Hans Adler
Abstract
I will explain the connection between Shelah's recent notion of strongly dependent theories and finite weight in simple theories. The connecting notion of a strong theory is new, but implicit in Shelah's book. It is related to absence of the tree property of the second kind in a similar way as supersimplicity is related to simplicity and strong dependence to NIP.

Pages