Archives of: Boise Set Theory Seminar

Sam Dworetzky: The classification problem for models of Peano Arithmetic

Tuesday, February 14 from 3 to 4pm
Room: MB 124
Speaker: Sam Dworetzky (BSU)
Title: The classification problem for models of Peano Arithmetic

Abstract: It is well known that the countable models of Peano Arithmetic (PA) are complicated to classify. In this talk we will make this precise using the language of Borel complexity theory. We will use a construction of Gaifman to show there is a Borel reduction from the isomorphism relation on linear orders to the isomorphism relation on models of PA.

Stephanie Potter: Classification of vertex-transitive structures

Tuesday, January 31 from 3 to 4pm
Room: MB 124
Speaker: Stephanie Potter (BSU)
Title: Classification of vertex-transitive structures

Abstract: In this talk we will consider the Borel complexity of the isomorphism relation on two natural classes of objects: countable, connected, vertex-transitive graphs and countable, vertex-transitive partial orders. We will first discover that the isomorphism relation on vertex-transitive graphs has maximal complexity or, in other words, is Borel complete. This result will then allow us to show that the isomorphism relation on countable, vertex-transitive partial orders is also Borel complete.

Marion Scheepers: Playing an infinitely long game when you have limited memory III

Tuesday, January 17 from 3 to 4pm
Room: MB 124
Speaker: Marion Scheepers (BSU)
Title: Playing an infinitely long game when you have limited memory (III)

Abstract: We consider a class of infinite games in which player TWO has a winning strategy (based on perfect memory). In prior talks in this series we considered the effect of a limited memory where TWO remembers only the most recent move of ONE and of TWO. We now discuss the effect of TWO for a fixed positive integer k remembering only the most recent k or fewer moves of ONE.

Randall Holmes: Constructing proofs with a dependent type checker

Tuesday, October 25 from 3 to 4pm
Room: MB 124
Speaker: Randall Holmes (BSU)
Title: Constructing proofs with a dependent type checker

Abstract: I’ll discuss my latest theorem proving work, and present examples. I’ll explain what dependent type theory is and how a type checker for a dependent type theory can be a theorem prover. The talk should be accessible to students.

John Clemens: The recursion theorem in set theory

Tuesday, September 27 from 3 to 4pm
Room: MB 124
Speaker: John Clemens (BSU)
Title: The Recursion Theorem in Set Theory

Abstract: Kleene’s Recursion Theorem is a simple yet powerful result about computable functions, which asserts the existence of functions which “know their own code” in some suitably nice enumeration of the computable functions. It can be used to find fixed points for operations on computable functions. Less well-known is that the Recursion Theorem can be applied to other Polish spaces (instead of the integers) to produce fixed points for set operations. I will give a brief introduction to the theory of computable functions and the original Recursion Theorem, and then discuss the basics of effective descriptive set theory necessary to extend it to more general Polish spaces. As time permits I will sketch some of the consequences in descriptive set theory, such as finding least fixed points of monotone set operations and Moschovakis’s Coding Lemma.

Samuel Coskey: Classifying automorphisms of countable trees

Tuesday, September 13 from 3 to 4pm
Room: MB 124
Speaker: Samuel Coskey (BSU)
Title: Classifying automorphisms of countable trees

Abstract: We summarize some of the results from Kyle Beserra’s master’s thesis. In Serre’s study of trees and their automorphisms, he observed that the automorphisms all lie in one of three classes: invert an edge, shift a bi-infinite path, or fix a subtree pointwise. But of course there are many types of automorphisms within each of these classes. So it is natural to ask just how complex is the classification of tree automorphisms? And what is the complexity of each of Serre’s three classes? We can make these questions formal using the language Borel complexity theory. In this talk we answer the question for regular trees.

Marion Scheepers: Ramsey theory and the Borel Conjecture

Boise Set Theory Seminar
Wednesday, April 20 from 3 to 4pm
Room: MB 124
Speaker: Marion Scheepers (BSU)

Title: Ramsey theory and the Borel Conjecture

Abstract: The Borel Conjecture states that certain measure zero sets of real numbers are countable. This statement can be converted to a statement that a set of real numbers is one of these special measure zero sets if, and only if, a special associated structure satisfies a version of Ramsey’s Theorem. We discuss this connection, and explore a range of statements equivalent to the alluded to version of Ramsey’s Theorem.

Shehzad Ahmed: Jónsson successors of singular cardinals

Wednesday, March 2 from 3 to 4pm
Room: MB 124
Speaker: Shehzad Ahmed (Ohio University)
Title: Jónsson successors of singular cardinals

Abstract: We say that a cardinal $\lambda$ is a Jónsson cardinal if it satisfies the following weak Ramsey-type property: given any coloring $F:[\lambda]^{<\omega}\to \lambda$ of the finite subsets of $\lambda$ in $\lambda$-many colors, there exists a set $H\in[\lambda]^\lambda$ such that the range of $F\upharpoonright [H]^{<\omega}$ is a proper subset of $\lambda$. One of the big open questions in combinatorial set theory is whether or not the existence of a singular cardinal $\mu$ such that $\mu^+$ is a Jónsson cardinal is even consistent. The goal of this talk is to explain why this problem has proven so difficult, and to (time permitting) briefly survey ongoing research in the area.

Randall Holmes: Consistency of New Foundations

Wednesday, December 9 from 3 to 4pm
Room: MP 207
Speaker: Randall Holmes (BSU)
Title: Consistency of New Foundations

Abstract: This will be the first of three or four talks which will give an account of my consistency proof for Quine’s system of set theory New Foundations (proposed by W. v.O. Quine in 1937). The first talk will cover preliminaries about the typed theory of sets (an unproblematic variant of the usual set theory), the modification of the definition of the typed theory of sets to give New Foundations, and the relevant known results about the model theory of NF and the relative consistency of related systems. The construction is via a Fraenkel-Mostowski construction of a model of ZFA (the usual set theory with atoms) without Choice, so the next point will be a discussion of this kind of construction, with an example relevant to the eventual main construction. All work done in the talk will actually be done in the usual set theory or variants (give or take the existence of atoms or the assumption of the axiom of choice).

John Clemens: Relative primeness of equivalence relations

Wednesday, November 11 from 3 to 4pm
Room: MP 207
Speaker: John Clemens (BSU)

Title: Relative primeness of equivalence relations

Abstract: Let $E$ and $F$ be equivalence relations on the spaces $X$ and $Y$. We say that $E$ is prime to $F$ if: whenever $\varphi: X \rightarrow Y$ is a homomorphism from $E$ to $F$, there is a continuous embedding $\rho$ from $E$ to itself so that the range of $\varphi \circ \rho$ is contained in a single $F$ class. That is to say, $\varphi$ is constant (up to $F$-equivalence) on a set on which $E$ maintains its full complexity with respect to Borel reducibility. When $E$ is prime to $F$, $E$ fails to be Borel-reducible to $F$ in a very strong way. I will discuss this notion and show that many non-reducibility results in the theory of Borel equivalence relations can be strengthened to produce primeness results. I will also discuss the possibility of new types of dichotomies involving the notion of primeness.