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.