# 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.

Mar 30

#### Logic Seminar, Reed Solomon (UConn): 'Revisiting EM and ADS'

04:45 pm

Abstract: In this talk, I will present recent work by Ludovic Patey which simplifies and extends the proof that the Erdos-Moser principle (that every infinite tournament has an infinite transitive sub tournament) does not imply ADS (that every linear order contains either an infinite ascending sequence or an infinite descending sequence).