Past Logic Seminar

16 October 2008
17:00
Kobi Peterzil
Abstract
<p> (joint work with E. Hrushovski and A. Pillay)<br /> <br /> If G is a definably compact, connected group definable in an o-minimal structure then, as is known, G/Z(G) is semisimple (no infinite normal abelian subgroup).<br /> <br /> We show, that in every o-minimal expansion of an ordered group: </p> <p> If G is a definably connected central extension of a semisimple group then it is bi-intepretable, over parameters, with the two-sorted structure (G/Z(G), Z(G)). Many corollaries follow for definably connected, definably compact G.<br /> Here are two: </p> <p> 1. (G,.) is elementarily equivalent to a compact, connected real Lie group of the same dimension. </p> <p> 2. G can be written as an almost direct product of Z(G) and [G,G], and this last group is definable as well (note that in general [G,G] is a countable union of definable sets, thus not necessarily definable).<br /> <br /> </p>
9 October 2008
17:00
Amador Martin-Pizarro
Abstract
In 2006, a bad field was constructed (together with Baudisch, Hils and Wagner) collapsing Poizat's green fields. In this talk, we will not concentrate on the general methodology for collapsing specific structures, but more on a specific result in algebraic geometry, a weaker version of the Conjecture on Intersection with Tori (CIT). We will present a model theoretical proof of this result as well as discuss the possible generalizations to positive characteristic. We will try to make the talk  self-contained and aimed for an audience with a basic acquaintance with Model Theory.<br /> <br />
23 July 2008
14:30
Bart Kastermans
Abstract
Cofinitary groups are subgroups of the symmetric group on the natural numbers (elements are bijections from the natural numbers to the natural numbers, and the operation is composition) in which all elements other than the identity have at most finitely many fixed points. We will give a motivation for the question of which isomorphism types are possible for maximal cofinitary groups. And explain some of the results we achieved so far.
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.
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.

Pages