Rutgers Logic Seminar: Mondays

Information

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

Seminar Schedule Fall 2018

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

Title: The universal structure spectrum

Title: The universal structure spectrum

Title: The universal structure spectrum

Title: The universal structure spectrum

Title: The universal structure spectrum

Seminar Schedule Spring 2018

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

Monday 04/30 Dima Sinapova (UIC)

Title: Stronger tree properties, SCH, and successors of singulars Stronger tree properties capture the combinatorial essence of large cardinals. More precisely, for an inaccessible cardinal $\kappa$, $\kappa$ has the super, tree property (ITP) if and only if $\kappa$ is supercompact. An old project in set theory is to get the tree property at every regular cardinal greater than $\omega_1$. Even more ambitiously, can we get ITP at all regular cardinals above $\omega_1$? This would require many violations of the singular cardinal hypothesis (SCH), and leads to the question whether ITP implies SCH above. A positive answer would be an analogue of Solovay's theorem. We will show that consistently we can have ITP at some $\lambda$ together with failure of SCH above $\lambda$, for a non limit singular cardinal. The case of a limit singular cardinal is still open. We will also show that there is a model where ITP holds at the double successor of a singular and there are club many non internally unbounded models. This is another result in the direction of showing that ITP does not imply SCH above. Finally we discuss obtaining ITP at the successor of a singular cardinal. This is joint work with Sherwood Hachtman.

Monday 04/23 Simon Thomas (Rutgers)

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.

Monday 04/16 Seth Harris (Drew University)

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.

Monday 04/09 Slawek Solecki (Cornell)

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.

Monday 04/02 Joel Hamkins (CUNY)

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

Monday 03/26 Grigor Sargsyan (Rutgers)

Title: The constructible universe and beyond

Monday 03/19 No Seminar

Monday 03/12 Spring break

Monday 03/5 Iian Smithe (Rutgers)

Title:

Monday 02/26 Simon Thomas (Rutgers)

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

Monday 02/19 William Chan (UNT)

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

Monday 02/12 Sam Braunfeld (Rutgers)

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.

Monday 02/05 Alexandra Shlapentokh (East Carolina University)

Title: Definability and decidability in Number Theory

Monday 01/29 Russell Miller (Queens College) --

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.

Monday 01/22 Trevor Wilson (Miami University, Ohio)

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

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

Title: Stronger tree properties, SCH, and successors of singulars Stronger tree properties capture the combinatorial essence of large cardinals. More precisely, for an inaccessible cardinal $\kappa$, $\kappa$ has the super, tree property (ITP) if and only if $\kappa$ is supercompact. An old project in set theory is to get the tree property at every regular cardinal greater than $\omega_1$. Even more ambitiously, can we get ITP at all regular cardinals above $\omega_1$? This would require many violations of the singular cardinal hypothesis (SCH), and leads to the question whether ITP implies SCH above. A positive answer would be an analogue of Solovay's theorem. We will show that consistently we can have ITP at some $\lambda$ together with failure of SCH above $\lambda$, for a non limit singular cardinal. The case of a limit singular cardinal is still open. We will also show that there is a model where ITP holds at the double successor of a singular and there are club many non internally unbounded models. This is another result in the direction of showing that ITP does not imply SCH above. Finally we discuss obtaining ITP at the successor of a singular cardinal. This is joint work with Sherwood Hachtman.

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