Mathematical Sciences Research Institute

Home » DDC - Computability Theory: Cohesive powers of linear orders

Seminar

DDC - Computability Theory: Cohesive powers of linear orders October 30, 2020 (09:00 AM PDT - 10:00 AM PDT)
Parent Program: Decidability, definability and computability in number theory: Part 1 - Virtual Semester MSRI: Online/Virtual
Speaker(s) Paul Shafer (University of Leeds)
Description

Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Video

Cohesive Powers Of Linear Orders

Abstract/Media

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Abstract:

A cohesive power of a computable structure is an effective analog of an ultrapower, where a cohesive set acts as an ultrafilter.  We investigate the following question.  Fix a cohesive set C and a computably presentable structure A, and consider the various computable copies B of A.  How do the cohesive powers of B by C vary as B varies?

Let omega, zeta, and eta denote the respective order-types of (N, <), (Z, <), and (Q, <).  We take omega as our computably presentable structure, and we consider the cohesive powers of its computable copies. If L is a computable copy of omega that is computably isomorphic to the standard presentation (N, <), then all of L’s cohesive powers have order-type omega + (zeta x eta), which is familiar as the order-type of countable non-standard models of PA.

We show that it is possible to realize a variety of order-types other than omega + (zeta x eta) as cohesive powers of computable copies of omega (that are necessarily not computably isomorphic to the standard presentation). For example, we show that if C is a co-c.e. cohesive set, then there is a computable copy L of omega where the cohesive power of L by C has order-type omega + eta.  More generally, we show that it is possible to achieve order-types of the form omega + certain shuffle sums as cohesive powers of computable linear orders of type omega.

This work is joint with Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Alexandra Soskova, and Stefan Vatev.

 Slides 367 KB application/pdf

Cohesive Powers Of Linear Orders

 H.264 Video 25186_28684_8603_Cohesive_Powers_of_Linear_Orders.mp4