Jack Yoon will continue his explication of Proof Mining.

David Webb will speak at 1:00-2:00 in Keller 402

Title: Every Function Can be Computable

Abstract: I will relay an interesting result of Joel David Hamkins: that
there is an algorithm which can compute any function f of natural
numbers, if it is carried out in the right model of arithmetic
(corresponding to f). In particular, I will construct the necessary
models using Rosser sentences and describe the algorithm.

This semester the Logic Seminar will meet on Thursdays, 2:50 – 3:40 pm in Keller 402.

This Thursday we will have a (probably brief) organizational meeting.

Title: Some nonstandard remarks about Egyptian fractions

Abstract: An Egyptian fraction is a finite sum of fractions of the form $1/n$, where $n$ is a natural number. I’ll give simple proofs of some results about such fractions (also about Znám fractions). The proofs only require the compactness theorem from first order logic, though I’ll use the language of nonstandard analysis.

Title: A Simple Proof of a Theorem of Woodin

Abstract: In a similar spirit as my talk last semester about computing
and non-standard models, I will relay Joel David Hamkins’ new proof of a
theorem of Woodin: that there is a function that enumerates any finite
set (if computed in the correct model M of arithmetic), and which can
enumerate any extension of that set (if run in the correct end-extension
of M).

Title: Measure-Risking Arguments in Recursion Theory

Abstract: By way of introducing the idea of measure-risking, I will present a proof of Kurtz’s theorem that the Turing upward closure of the set of 1-generic reals is of full Lebesgue measure. Then I will show how a stronger form of the theorem (due originally to Kautz) can be obtained by framing the proof as a “fireworks argument”, following a recent paper of Bienvenu and Patey.

Continuation of last week’s talk

Title: Borel Determinacy I
Speaker: Umar Gaffar

We’re going through Ross Bryant’s presentation of Martin’s theorem (in ZFC) that Borel games are determined.

David Webb will present a new notion of effective dimension, inescapable dimension, which is in a sense dual to complex packing dimension.

The latter was introduced by Freer and Kjos-Hanssen in 2013 in the context of trying to show that the reals of effective Hausdorff dimension 1 are not Medvedev above the bi-immune sets.

Webb will show that the two notions are incomparable, among other results.

Speaker : Michael Yampolsky (University of Toronto)

Title : Computability of Julia sets.

Abstract : Informally speaking, a compact set in the plane is computable if there exists an algorithm to draw it on a computer screen with an arbitrary resolution. Julia sets are some of the best-known mathematical images, however, the questions of their computability and computational complexity are surprisingly subtle. I will survey joint results with M. Braverman and others on computability and complexity of Julia sets.

This semester the Logic Seminar continues at a new day and time, Fridays at 2:30 in Keller 314.

For the first meeting this Friday I will (probably) speak about _Skolem polynomials_:

Abstract:
Over 100 years ago Hardy proved that a certain large class of real functions
was linearly ordered by eventual domination. In 1956 Skolem asked
whether the subclass of integer exponential polynomials is *well*-ordered
by the Hardy ordering, and conjectured that its order type
is epsilon_0. (This class is the smallest containing 1, x, and closed
under +, x, and f^g.) In 1973 Ehrenfeucht proved that the class is
well-ordered, and since then there has been some progress on the order
type.

The proof of well-ordering is rather remarkable and very short, and I
will attempt to expose it (which is to say, cover it) in the hour.

David Ross

Mushfeq Khan will speak on amenability and symbolic dynamics.
As usual the seminar is in Keller 314.

Continuing the theme of symbolic dynamics, I will demonstrate a proof of Simpson’s result that “Entropy = Dimension” for N^d and Z^d, and discuss some of Adam Day’s work generalizing these results to amenable groups.

This week Umar Gaffar will give Shelah’s proof of the following result:

Let $\lambda$ be the cardinality of an ultraproduct of finite sets. If $\lambda$ is infinite then $\lambda=\lambda^{\aleph_0}$.

David Webb will continue to discuss results from Adam Day’s paper on amenability and symbolic dynamics.

This week in the Logic Seminar in Keller 314, David Ross will give an easy proof of a slight extension of a result of Lagarias on the Diophantine equation

       $$ c(1/x_1+cdots+1/x_s)+b/(x_1 x_2cdots x_s)=a$$

The proof will be nonstandard, but really only require a sufficiently-saturated ordered field extension of $mathbb R$.

Mushfeq Khan will coninue to speak on amenability and symbolic dynamics.  The focus will be the Ornstein-Weiss combinatorial
lemmas from Adam Day’s paper.

Title: Universes of sets

Abstract: As is well-known, all mathematical objects can be coded as sets and thereby all of mathematics can be formally founded in set theory. What is perhaps less well-known is that there are many different models of set theory, each of which is powerful enough to function as a universe of sets and found (most) of mathematics, but these models can have very different properties.

This talk will aim to explore the question: what is a model of set theory? We will learn about Skolem’s paradox, that there are countable models of set theory, even though these countable models think they contain uncountable sets like the set of reals. We will be introduced to transitive models, usually considered to be the best behaved, but also meet ill-founded models, such as models which think ZFC is inconsistent. To conclude we will briefly discuss two positions in the philosophy of set theory: universism, the view that there is a unique maximal universe of sets, and multiversism, the view that there are many equally valid universes of sets.

This is an introductory talk, aimed to be understandable by those with little background in set theory. It is a prequel to my next talk, which is in turn a prequel to my talk after that.

Title: A conceptual overview of forcing

Abstract: Paul Cohen—who visited UH Mānoa in the 1990s—introduced the method of forcing to prove that the failure of the continuum hypothesis is consistent with ZFC, the standard base axioms for set theory. Since then it has become a cardinal tool within set theory, being the main method for proving independence results and even enjoys use in proving ZFC results. In this talk I will give an introduction to forcing, focusing on the big picture ideas.

This talk is a sequel to my previous talk and a prequel to my next talk.

Title: Forcing as a computational process

Abstract: In this talk we will consider computable structure theoretical aspects of forcing. Given an oracle for a countable model of set theory $M$, to what extent can we compute information about forcing extensions $M[G]$? The main theorem I will present gives a robustly affirmative answer in several senses.

* Given an oracle for the atomic diagram of a countable model of set theory $M$, then for any forcing notion $\mathbb P \in M$ we can compute an $M$-generic filter $G \subseteq \mathbb P$.

* From the $\Delta_0$ diagram for $M$ we can moreover compute the atomic diagram of the forcing extension $M[G]$, and indeed its $\Delta_0$ diagram.

* From the elementary for $M$ we can compute the elementary diagram of the forcing extension $M[G]$, and this goes level by level for the $\Sigma_n$ diagrams.

On the other hand, there is no functorial process for computing forcing extensions.

* If ZFC is consistent then there is no computable procedure (nor even a Borel procedure) which takes as input the elementary diagram for a countable model $M$ of ZFC and a partial order $\mathbb P \in M$ and returns a generic $G$ so that isomorphic copies of the same input model always result in the same corresponding isomorphic copy of $G$.

This talk is a sequel to my previous talk. The work in this talk is joint with Joel David Hamkins and Russell Miller.

Speaker: B. Kjos-Hanssen (joint work with Lei Liu)
Abstract:
Campeanu and Ho (2004) stated that it is “very difficult” to compute the number $m_n$ of maximally complex languages (in a finite automata sense) consisting of binary words of length $n$. We show that $m_n=O_{i,n}$, the number of functions from $[2^i]$ to $[2^{2^{n-i}}]$ whose range contains $[2^{2^{n-i}}-1]$, for the least $i$ for which $O_{i,n}>0$. Here, $[a]=${1,…,a}.

Title: Logic with Probability Quantifiers

Abstract: This talk is based on chapter XIV of Model-Theoretic Logics
(https://projecteuclid.org/euclid.pl/1235417263#toc). I will first give
a brief review of admissible sets and the infinitary logic which is
necessary for probability quantifiers. Then I will present the language
of probability quantifiers, as well as the proof theory, model theory,
and some examples which indicate the expressive power of the language.
Time permitting, my goal is to work towards the main completeness
theorem in section 2.3