Archives of: Kurt Godel Research Center

Alberto Marcone: Some results about the higher levels of the Weihrauch lattice

KGRC Research Seminar – 2017‑04‑27 at 4pm

Speaker: Alberto Marcone (Università di Udine, Italy)

Abstract: In the last few years Weihrauch reducibility and the ensuing Weihrauch lattice have emerged as a useful tool for studying the complexity of mathematical statements viewed as “problems” or multi-valued functions. This approach complements nicely the reverse mathematics approach, and has been very successful for statements which are provable in ${\mathsf{ACA}_0}$. The study the Weihrauch lattice for functions arising from statements laying at higher levels, such as ${\mathsf{ATR}_0}$, of the reverse mathematics spectrum is instead in its infancy. We will present some results (work in
progress with my graduate student Andrea Cettolo).

In some cases we obtain the expected finer classification, but in other we observe a collapse of statements that are not equivalent with respect to provability in subsystems of second order arithmetic. This is in part due to the increased syntactic complexity of the statements. Our preliminary results deal with comparability of well-orderings, $\Sigma^1_1$-separation, and
$\Delta^1_1$-comprehension.

Matteo Viale: Useful axioms

KGRC Research Seminar – 2017‑04‑26 at 4pm

Speaker: Matteo Viale (Università di Torino, Italy)

Abstract: I overview several aspects of forcing axioms which (in my eyes) give solid mathematical arguments explaining why these axioms are so useful in establishing new (consistency) results and/or theorems.

  • The first aspect outlines that forcing axioms are natural strengthenings not only of Baire’s category theorem, but also of the axiom of choice (these are two of the most useful non-constructive principles in mathematics), and also strengthenings of most large cardinal axioms (at least for cofinally many of them).
  • The second aspect outlines that Shoenfield’s absoluteness, Cohen’s forcing theorem, and Los theorem for standard ultrapowers of a first order structure by a non principal ultrafilter are all specific instances of a more general form of Los theorem which can be declined for what I call boolean ultrapowers.
  • The third aspect outlines how strong forcing axioms and Woodin’s generic absoluteness results are two sides of the same coin and will try to explain how stronger and stronger forms of generic absoluteness can be obtained by asserting stronger and stronger forcing axioms. In this context category theoretic ideas start to play a role and we are led to analyze forcings whose conditions are (certain classes of) forcing notions and whose order relation is given by (certain classes of) complete embeddings.

There is a surprising analogy between the theory of these class forcings, the theory of towers of normal ideals, and many of the classical arguments yielding generic absoluteness results. For what concerns the first two aspects of my talk, I do not claim authorship of essentially none of the result I will be talking about, nonetheless it is hard to attribute correctly the relevant results.

Peter Holy: Small embedding characterizations for large cardinals, and internal large cardinals

KGRC Research Seminar – 2017‑04‑06 at 4pm

Speaker: Peter Holy (University of Bonn, Germany)

Abstract:

Many notions of large cardinals are characterized in terms of the existence of certain elementary embeddings with the large cardinal in question as their critical point. A small embedding characterization of a large cardinal notion is one that requires the existence of certain elementary embeddings that map their critical point to the relevant large cardinal. One classic example of such a small embedding characterization is Magidor’s small embedding characterization of supercompactness. We show that many other large cardinal notions have small embedding characterizations, in particular also large cardinal notions for which no embedding characterizations have been known to exist at all.

In the second part of this talk, I will then sketch an application of small embedding characterizations, that yields what we call internal large cardinals, which essentially describe what is left of large cardinals after they have been destroyed or collapsed by sufficiently nice forcing. The basic idea is to lift the small embeddings that characterize the initial large cardinals.

This is joint work with Philipp Lücke.

Luca Incurvati: Metalogic and the Overgeneration Argument

KGRC Friday seminar – 2017‑03‑31 at 12pm

Speaker:  Luca Incurvati (University of Amsterdam, North Holland, Netherlands)

Abstract:

A prominent objection against the logicality of second-order logic is the so-called Overgeneration Argument. However, it is far from clear how this argument is to be understood. In the first part of the article, we examine the argument and locate its main source, namely the alleged entanglement of second-order logic and mathematics. We then identify various reasons why the entanglement may be thought to be problematic. In the second part of the article, we take a metatheoretic perspective on the matter. We prove a number of results establishing that the entanglement is sensitive to the kind of semantics used for second-order logic. These results provide evidence that, by moving from the standard set-theoretic semantics for second-order logic to a semantics which makes use of higher-order resources, the entanglement either disappears or may no longer be in conflict with the logicality of second-order logic.

This is joint work with Salvatore Florio.

Luca Motto Ros: Ultrametric spaces, isometry, and isometry groups

KGRC Research Seminar – 2017-03-30 at 4pm

Speaker: Luca Motto Ros (University of Turin, Italy)

Abstract:

Gao and Kechris proposed in 2003 two somewhat related problems concerning ultrametric spaces, namely:

1) Determine the complexity of the isometry relation on locally compact Polish ultrametric spaces.

2) Characterize the Polish groups that are isomorphic (as topological groups) to the isometry group of some Polish ultrametric space.

We will present a construction strictly relating ultrametric spaces and a special kind of trees which helps in tackling these two problems. This technique applies to both separable and non-separable complete ultrametric spaces, and allows us to e.g. show that they are unclassifyiable up to isometry even when considering only discrete spaces. (Joint work with R. Camerlo and A. Marcone.)

Michał Tomasz Godziszewski: Computable quotient presentations of models of arithmetic and set theory

KGRC Research Seminar – 2017-03-23 at 4pm

Speaker: Michał Tomasz Godziszewski (University of Warsaw, Poland)

Abstract:

A computable quotient presentation of a mathematical structure
$\mathbb{A}$ consists of a computable structure on the natural numbers
$(\mathbb{N}, \star, \ast, \ldots)$ (meaning that the operations and
relations of the structure are computable) and an equivalence relation
$E$ on $\mathbb{N}$, not necessarily computable but which is a
congruence with respect to this structure, such that the quotient
$(\mathbb{N}, \star, \ast, \ldots)_{/E}$ is isomorphic to the given
structure $\mathbb{A}$. Thus, one may consider computable quotient presentations
of graphs, groups, orders, rings and so on, for any kind of mathematical
structure.

In 2016 Bakhadyr Khoussainov discussed some questions and results in this area.
Part of this concerns the investigation, for a fixed equivalence relation $E$ or type
of equivalence relation, which kind of computable quotient presentations
are possible with respect to quotients modulo $E$.

We address two conjectures that Khoussainov had made and prove
various extensions of the Tennenbaum phenomenon to the case of
computable quotient presentations of models of arithmetic and set
theory. Specifically, no nonstandard model of arithmetic has a
computable quotient presentation by a c.e. equivalence relation. No
$\Sigma_1$-sound nonstandard model of arithmetic has a computable
quotient presentation by a co-c.e. equivalence relation. No nonstandard
model of arithmetic in the language $\{+, \cdot, \leq\}$ has a
computably enumerable quotient presentation by any equivalence relation
of any complexity. No model of ZFC or even much weaker set theories has
a computable quotient presentation by any equivalence relation of any
complexity. And similarly no nonstandard model of finite set theory has
a computable quotient presentation. Concluding from that, we indicate
how the program of computable quotient presentations has difficulties
with purely relational structures (as opposed to algebras).
This is joint work with Joel David Hamkins, GC CUNY.