Archives of: Carnegie Mellon Logic Seminar

Rick Statman: Completeness of BCD for an operational semantics; forcing for proof theorists

Mathematical logic seminar – Feb 13 2018
Time: 3:30pm – 4:30 pm

Room: Wean Hall 8220

Speaker: Rick Statman
Department of Mathematical Sciences
CMU

Title: Completeness of BCD for an operational semantics; forcing for proof theorists

Abstract:

Intersection types provide a type discipline for untyped λ-calculus. The formal theory for assigning intersection types to lambda terms is BCD (Barendregt, Coppo, and Dezani). We show that BCD is complete for a natural operational semantics. The proof uses a primitive forcing construction based on Beth models (similar to Kripke models).

Jing Zhang: Rado’s Conjecture and its Baire Version II

Mathematical logic seminar – Jan 30 2018
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Jing Zhang
Department of Mathematical Sciences
CMU

Title:     Rado’s Conjecture and its Baire Version II

Abstract:

Rado’s Conjecture is a reflection/compactness principle formulated by Todorčević, who also showed its consistency relative to the existence of strongly compact cardinals. One of its equivalent forms asserts that any nonspecial tree of height ω1 has a nonspecial subtree of size less or equal to ℵ1. Although it is incompatible with Martin’s Axiom, Rado’s Conjecture turns out to imply a lot of consequences of forcing axioms, for example Strong Chang’s Conjecture, failure of square principles, the semi-stationary reflection principle, the Singular Cardinal Hypothesis etcetera. In fact, almost all known consequences of Rado’s Conjecture are consequences of a weaker statement, the Baire version of it which asserts any Baire tree of height ω1 has a nonspecial subtree of size less or equal to ℵ1.

We will show that in the forcing extension by countable support iteration of Sacks forcing of strongly compact length, the Baire version of Rado’s Conjecture holds. Using a classical Mitchell style model, we show Rado’s conjecture along with not-CH does not imply ω2 has the super tree property, answering a question by Torres-Pérez and Wu. We will also see that in general the Baire version of Rado’s Conjecture does not imply Rado’s Conjecture.

Jing Zhang: Rado’s Conjecture and its Baire Version

Mathematical logic seminar – Jan 23 2018
Time:     3:30pm – 4:30 pmRoom:     Wean Hall 8220

Speaker:         Jing Zhang
Department of Mathematical Sciences
CMU

Title:     Rado’s Conjecture and its Baire Version

Abstract:

Rado’s Conjecture is a reflection/compactness principle formulated by Todorčević, who also showed its consistency relative to the existence of strongly compact cardinals. One of its equivalent forms asserts that any nonspecial tree of height ω1 has a nonspecial subtree of size less or equal to ℵ1. Although it is incompatible with Martin’s Axiom, Rado’s Conjecture turns out to imply a lot of consequences of forcing axioms, for example Strong Chang’s Conjecture, failure of square principles, the semi-stationary reflection principle, the Singular Cardinal Hypothesis etcetera. In fact, almost all known consequences of Rado’s Conjecture are consequences of a weaker statement, the Baire version of it which asserts any Baire tree of height ω1 has a nonspecial subtree of size less or equal to ℵ1.

We will show that in the forcing extension by countable support iteration of Sacks forcing of strongly compact length, the Baire version of Rado’s Conjecture holds. Using a classical Mitchell style model, we show Rado’s conjecture along with not-CH does not imply ω2 has the super tree property, answering a question by Torres-Pérez and Wu. We will also see that in general the Baire version of Rado’s Conjecture does not imply Rado’s Conjecture.

Clinton Conley: Unfriendly colorings of measure-preserving graphs of finite cost

Mathematical logic seminar – Jan 16 2018
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Clinton Conley
Department of Mathematical Sciences
CMU

Title:     Unfriendly colorings of measure-preserving graphs of finite cost

Abstract:

We show that any measure-preserving Borel graph on a standard probability space with finite average degree admits a Borel unfriendly coloring on a conull set. This generalizes the results for group actions discussed last semester, and is joint work with Omer Tamuz.

Clinton Conley: Measure-theoretic unfriendly colorings II

Mathematical logic seminar – Nov 14 2017
Time:     3:30pm – 4:30 pmRoom:     Wean Hall 8220

Speaker:         Clinton Conley
Department of Mathematical Sciences
CMU

Title:     Measure-theoretic unfriendly colorings II

Abstract:

Given a graph with vertices painted red and blue, we say the coloring is unfriendly if every red vertex has at least as many blue neighbors as red, and vice versa. Every finite graph admits an unfriendly coloring, but (ridiculously) it remains open whether every countable graph does. Rather than tackle that problem, we consider measure-theoretic analogs associated with probability-measure-preserving actions of finitely generated groups. We don’t really answer any questions here, either, but we do obtain such colorings up to weak equivalence of actions. Time permitting, we also discuss recent constructions of unfriendly colorings of acyclic hyperfinite graphs. The talk may include joint work with Kechris, Marks, Tucker-Drob, and Unger.

Clinton Conley: Measure-theoretic unfriendly colorings

Mathematical logic seminar – Oct 31 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Clinton Conley
Department of Mathematical Sciences
CMU

Title:     Measure-theoretic unfriendly colorings

Abstract:

Given a graph with vertices painted red and blue, we say the coloring is unfriendly if every red vertex has at least as many blue neighbors as red, and vice versa. Every finite graph admits an unfriendly coloring, but (ridiculously) it remains open whether every countable graph does. Rather than tackle that problem, we consider measure-theoretic analogs associated with probability-measure-preserving actions of finitely generated groups. We don’t really answer any questions here, either, but we do obtain such colorings up to weak equivalence of actions. Time permitting, we also discuss recent constructions of unfriendly colorings of acyclic hyperfinite graphs. The talk may include joint work with Kechris, Marks, Tucker-Drob, and Unger.

Vahagn Aslanyan: Ax-Schanuel and related problems

Mathematical logic seminar – Oct 24 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Vahagn Aslanyan
Department of Mathematical Sciences
CMU

Title:     Ax-Schanuel and related problems

Abstract:

Ax proved a functional analogue of Schanuel’s conjecture in 1971. I will show how one can use it to axiomatise the first-order theory of the exponential differential equation in analogy with Zilber’s pseudo-exponentiation. Then I will discuss the possibility of Ax-Schanuel type results for other functions (differential equations), and some related problems. If time permits, I will show how Ax-Schanuel can be applied to prove a weak version of the Conjecture on Intersections with Tori.

Vahagn Aslanyan: Schanuel’s conjecture, pseudo-exponentiation, and Ax’s theorem

Mathematical logic seminar – Oct 17 2017

Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Vahagn Aslanyan
Department of Mathematical Sciences
CMU

Title:     Schanuel’s conjecture, pseudo-exponentiation, and Ax’s theorem

Abstract:

Schanuel’s conjecture captures the transcendence properties of the complex exponential function, and is considered out of reach. An interesting, novel approach to it was given by Zilber which led to the construction of pseudo-exponentiation. This gave rise to more conjectures related to Schanuel’s conjecture and the complex exponential field C_exp. One of those, known as Zilber-Pink, is purely number theoretic and generalises many known conjectures (and results) in diophantine geometry such as Mordell-Lang and Andree-Oort. I will describe Zilber’s construction and the Zilber-Pink conjecture. If time permits, I will also discuss a functional analogue of Schanuel’s conjecture proven by Ax in 1971.

Chris Lambie-Hanson: A forcing axiom deciding the generalized Souslin Hypothesis

Mathematical logic seminar – Oct 3 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Chris Lambie-Hanson
Department of Mathematics
Bar-Ilan University

Title:     A forcing axiom deciding the generalized Souslin Hypothesis

Abstract:

Given a regular, uncountable cardinal $\kappa$, it is often desirable to be able to construct objects of size $\kappa^+$ using approximations of size less than $\kappa$. Historically, such constructions have often been carried out with the help of a $(\kappa,1)$-morass and/or a $\diamondsuit(\kappa)$-sequence.
We present a framework for carrying out such constructions using $\diamondsuit(\kappa)$ and a weakening of Jensen’s $\square_\kappa$. Our framework takes the form of a forcing axiom, $\textrm{SDFA}(\mathcal P_\kappa)$. We show that $\textrm{SDFA}(\mathcal P_κ)$ follows from the conjunction of $\diamondsuit(\kappa)$ and our weakening of $\square_\kappa$ and, if $\kappa$ is the successor of an uncountable cardinal, that $\textrm{SDFA}(\mathcal P_\kappa)$ is in fact equivalent to this conjunction. We also show that, for an infinite cardinal $\lambda$, $\textrm{SDFA}(\mathcal P_{\lambda^+})$ implies the existence of a $\lambda^+$-complete $\lambda^{++}$-Souslin tree. This implies that, if $\lambda$ is an uncountable cardinal, $2^\lambda =\lambda^+$, and Souslin’s Hypothesis holds at $\lambda^{++}$, then $\lambda^{++}$ is a Mahlo cardinal in $L$, improving upon an old result of Shelah and Stanley. This is joint work with Assaf Rinot.

Garrett Ervin: The Cube Problem for linear orders II

Mathematical logic seminar – Sep 26 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Garrett Ervin
Department of Mathematical Sciences
CMU

Title:     The Cube Problem for linear orders II

Abstract:

In the 1950s, Sierpiński asked whether there exists a linear order that is isomorphic to its lexicographically ordered Cartesian cube but not to its square. The analogous question has been answered positively for many different classes of structures, including groups, Boolean algebras, topological spaces, graphs, partial orders, and Banach spaces. However, the answer to Sierpinski’s question turns out to be negative: any linear order that is isomorphic to its cube is already isomorphic to its square, and thus to all of its finite powers. I will present an outline of the proof and give some related results.