Rutgers Logic Seminar: Mondays

Information

VISITORS SHOULD PICK UP A PARKING PERMIT FROM THE PARKING OFFICE.

Seminar Schedule Spring 2018

5:00-6:00 pm, Room 705, Hill Center, Busch

Title:

Title: The isomorphism and bi-embeddability relations for finitely generated groups. Abstract: I will discuss the isomorphism and bi-embeddability relations for various classes of finitely generated groups. In particular, I will point out a recursion-theoretic obstacle to proving that the isomorphism relation for finitely generated simple groups is complicated.

Title: On-Line Algorithms and Reverse Mathematics

Abstract: Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence \bar{a} and Bob responds with a sequence \bar{b} with no knowledge of Alice’s future requests. A problem P is solvable by an on-line algorithm if Bob has a winning strategy in this game, where Bob wins the game if (\bar{a}, \bar{b}) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is on-line colorable if Bob has a winning strategy in this game. Given a problem P, the corresponding sequential problem SeqP asserts the existence of an infinite sequence of solutions to P. We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in the axiom systems RCA_0, WKL_0, and ACA_0. This is joint work with François Dorais.

Title: Polishable Borel equivalence relations

Abstract: We introduce the notion of Polishable equivalence relations. This class of equivalence relations contains all orbit equivalence relations induced by Polish group actions and is contained in the class of idealistic equivalence relations of Kechris and Louveau. We show that each orbit equivalence relation induced by a Polish group action admits a canonical transfinite sequence of Polishable equivalence relations approximating it. The proof involves establishing a lemma, which may be of independent interest, on stabilization of increasing $\omega_1$-sequences of completely metrizable topologies.

Title: The universal finite set

Abstract: I shall define a certain finite set in set theory $$\{x\mid\varphi(x)\}$$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficient $V_\theta$; the set is empty in any transitive model and others; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines the new set $z$. The definition can be thought of as an idealized diamond sequence, and there are consequences for the philosophical theory of set-theoretic top-extensional potentialism. This is joint work with W. Hugh Woodin

Title: The constructible universe and beyond

Title:

Title: The isomorphism and bi-embeddability relations for countable abelian p-groups

Abstract: I will discuss the relative complexity of the isomorphism and bi-embeddability relations for countable abelian p-groups from the point of view of descriptive set theory. (This is joint work with Filippo Calderoni.)

Title: L(R) with determinacy has no Suslin lines

Abstract: A Suslin line is an unbounded, nonseparable, complete, dense linear ordering with the countable chain condition. If L(R) satisfies the axiom of determinacy, then L(R) has no Suslin lines. This answers a question of Foreman. (This is joint work with Jackson.)

Title: The undecidability of joint embedding for hereditary graph classes, and related problems

Abstract: We will sketch a proof of the undecidability of joint embedding for finitely-constrained hereditary graph classes. Time permitting, we will discuss the analogous question in other classes of structures, such as 3-dimensional permutations.

Title: Definability and decidability in Number Theory

Title: Hilbert's Tenth Problem for Subrings of the Rationals

Abstract: For a ring $R$, Hilbert's Tenth Problem $HTP(R)$ is the set of all polynomials $f\in R[X_1,X_2,\ldots]$ for which $f=0$ has a solution in $R$. In 1970, Matiyasevich completed work by Davis, Putnam, and Robinson to show that the original Tenth Problem of Hilbert, $HTP(\mathbb{Z})$, is undecidable. On the other hand, the decidability of $HTP(\mathbb{Q})$ remains an open question. We will examine this problem for subrings of the rational numbers, viewing these subrings as the elements of a topological space homeomorphic to Cantor space and connecting their Turing degrees and computability-theoretic properties to those of $HTP(\mathbb{Q})$ itself. Some of the work discussed is joint with Kramer, and some with Eisentraeger, Park, and Shlapentokh.

Title: Forcing the pointclass of universally Baire sets to be equal to Delta^1_2

Seminar Schedule F2013

5:00-6:20 pm, Room 705, Hill Center, Busch

Monday 05/05 --

Monday 04/28 --

Monday 04/21 -- Joel Hamkins (College of Staten Island)

Monday 04/14 -- Nam Trang (CMU)

Monday 04/07 -- Paul Larson (Miami University)

Monday 03/31 --

Monday 03/24 --

Monday 03/17 -- Scott Cramer (Rutgers)

Monday 03/10 -- Scott Cramer (Rutgers)

Monday 03/03 -- Scott Cramer (Rutgers)

Monday 02/24 --- Tamar Lando (Columbia)

Monday 02/17 --- Rubin Tucker-Drob (Rutgers)

Monday 02/10 -- Simon Thomas (Rutgers)
Title: Invariant random subgroups of locally finite groups II

Monday 01/27 -- Simon Thomas (Rutgers)
Title: Invariant random subgroups of locally finite groups

5:00-6:20 pm, Room 705, Hill Center, Busch