Seminars and Colloquia

Logic Seminar

Oct 2

Logic Seminar

04:45 pm

Sep 26

Logic Seminar

04:45 pm

Philip Scowcroft, Wes: " Abelian lattice-ordered groups with at most finitely many pairwise disjoint elements." Abstract : Conrads characterization (1960) of the lattice-ordered groups with at most finitely many pairwise disjoint elements yields model-completions for various theories of such groups. A corresponding Nullstellensatz, and various quantifier-elimination results, assume stronger forms when restricted to special groups in the class.

Nov 9

Logic Seminar, Bill Calhoun (Bloomsburg University): "Triviality and lowness for K-reducibility and related reducibilities"

04:45 pm

n 2 !, where K is prefix-free Kolmogorov complexity. The set A is low for K if KA(y) = K(y)+O(1) for y 2 2<!. These definitions seem quite different. K-triviality indicates that initial segments of A have the lowest possible complexity, while lowness for K indicates that A is too weak as an oracle to reduce the complexity of any string. The remarkable equivalence of the two definitions was shown by Nies [2]. Replacing prefix-free complexity by monotone complexity in the definition of K-trivial, we obtain the Km-trivial sets. Every K-trivial set is Km-trivial and all Turing degrees _ 00 contain a Km-trivial set [1]. Yet, not every Turing degree contains a Km-trivial set. We obtain a superset of the Km-trivial sets by defining A to be almost-K-trivial if there is a real number a such that K(A _ n) _+ aK(n). Every Km-trivial set is almost-K-trivial. However, the Turing degree of a computably dominated ML-random cannot contain any almost-K-trivial set. An interesting question is to determine which Turing degrees contain Km-trivial sets (or almost-K-trivial sets). Recently, this question has been considered for minimal Turing degrees. We also consider lowness for monotone and a priory complexity. References 1. Calhoun, W.C.: Triviality and minimality in the degrees of monotone complexity, Journal of Logic and Computation 22, 197-206 (2012). 2. Nies, Andre: Lowness properties and randomness, Advances in Mathematics 197, 274-305 (2005).

Nov 2

Logic Seminar, Philip Scowcroft (Wes): Infinitely generic Abelian lattice-ordered groups

04:45 pm

Abstract: This talk will survey current knowledge of the infinitely generic Abelian lattice-ordered groups as well as the mysteries that remain.

Sep 21

CT Logic Seminar, Vincent Guingona (Wes): "A Local Characterization of VC-Minimality"

04:45 pm

Abstract : ( Joint work with Uri Andrews ) This talk is in the intersection of computable model theory and neostability theory. I discuss VC-minimality, a model-theoretic notion of complexity for theories that generalizes o-minimality and is generalized by dp-minimality and NIP. Unlike o-minimality and dp-minimality, a priori , it is difficult to determine if a given theory is VC-minimal. In computability terms, the definition of VC-minimality, in its original form, is Sigma_1^1. However, my coauthor and I show that VC-minimality is, in fact, Pi^0_4-complete by giving a local characterization (for countable languages). This leads to a list of examples of theories whose VC-minimality is determined.

Sep 14

Logic Seminar, Reed Solomon (UConn): "Strong reducibilities, RT^1_3 and SRT^2_2"

04:45 pm

Abstract: Various strong reductions between Pi^1_2 principles have been used in recent years to shed light on difficult problems in reverse mathematics. I will introduce some of these reductions and discuss their connection to reverse math. The main theorem of the talk is that RT^1_3 is not strongly computably reducible to SRT^2_2. This result is joint work with Damir Dzhafarov, Ludovic Patey and Linda Brown Westrick.

Apr 27

Logic Seminar, Petr Glivicky (Charles University): 'Definability in linear fragments of Peano Arithmetic'

04:45 pm

Abstract: In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal k, the k-linear arithmetic (LAk) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild. I will present a quantifier elimination result for LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible). There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.