Calendar

Sep
10
Mon
Logic Seminar: Kameryn Williams
Sep 10 @ 2:30 pm – 3:20 pm

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.

Sep
17
Mon
Logic Seminar: Kameryn Williams
Sep 17 @ 2:30 pm – 3:20 pm

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.

Oct
29
Mon
Logic seminar: The number of maximally complex languages
Oct 29 @ 2:30 pm – 3:30 pm

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

Nov
5
Mon
Jake Fennick: Probabilistic logic @ Keller 314
Nov 5 @ 2:30 pm – 3:30 pm

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

Nov
19
Mon
David Ross: Conditional sets
Nov 19 @ 2:30 pm – 3:30 pm
Nov
26
Mon
David Ross: Conditional sets II
Nov 26 @ 2:30 pm – 3:30 pm
Dec
3
Mon
David Webb: Inescapable dimension
Dec 3 @ 2:30 pm – 3:30 pm
Jan
24
Thu
Kameryn Williams: Logic seminar @ Keller 313
Jan 24 @ 2:30 pm – 3:20 pm

Title: Amalgamating generic reals, a surgical approach
Location: Keller Hall 313
Speaker: Kameryn Williams, UHM

The material in this talk is an adaptation of joint work with Miha Habič, Joel David Hamkins, Lukas Daniel Klausner, and Jonathan Verner, transforming set theoretic results into a computability theoretic context.

Let $\mathcal D$ be the collection of dense subsets of the full binary tree coming from a fixed countable Turing ideal. In this talk we are interested in properties of $\mathcal D$-generic reals, those reals $x$ so that every $D \in \mathcal D$ is met by an initial segment of $x$. To be more specific the main question is the following. Fix a real $z$ which cannot be computed by any $\mathcal D$-generic. Can we craft a family of $\mathcal D$-generic reals so that we have precise control over which subfamilies of generic reals together compute $z$?

I will illustrate a specific of this phenomenon as a warm up. I will show that given any $\mathcal D$-generic $x$ there is another $\mathcal D$-generic $y$ so that $x \oplus y$ can compute $z$. That is, neither $x$ nor $y$ can compute $z$ on their own, but together they can.

The main result for the talk then gives a uniform affirmative answer for finite families. Namely, I will show that for any finite set $I = \{0, \ldots, n-1\}$ there are mutual $\mathcal D$-generic reals $x_0, \ldots, x_{n-1}$ which can be surgically modified to witness any desired pattern for computing $z$. More formally, there is a real $y$ so that given any $\mathcal A \subseteq \mathcal P(I)$ which is closed under superset and contains no singletons, that there is a single real $w_\mathcal{A}$ so that the family of grafts $x_k \wr_y w_\mathcal{A}$ for $k \in A \subseteq I$ can compute $z$ if and only if $A \in \mathcal A$. Here, $x \wr_y w$ is a surgical modification of $x$, using $y$ to guide where to replace bits from $x$ with those from $w$.