Sy David Friedman's 60th-Birthday Conference

Abstracts

Arrigoni, Tatiana: The Hyperuniverse Program from a philosophical point of view

The Hyperuniverse Program is a new approach to set-theoretic truth due to Sy D. Friedman, leading to the resolution of many questions independent from $ZFC$. In this talk I will sketch the program briefly with a special focus on its philosophical implications and open questions.

Baldwin, John: Categoricity and Completeness: Formalization without Foundationalism

Formalization has three roles: 1) a foundation for an area (perhaps all) of mathematics, 2) a resource for investigating problems in 'normal' mathematics, 3) a tool to organize various mathematical areas so as to emphasize commonalities and differences. We focus on the use of theories and syntactical properties of theories in roles 2) and 3). Formal methods enter both into the classification of theories and the study of definable set of a particular model. We regard a property of a theory (in first or second order logic) as virtuous if the property has mathematical consequences for the theory or for models of the theory. We rehearse some results of Marek Magidor, H. Friedman and Solovay to argue that for second order logic, 'categoricity' has little virtue. For first order logic, categoricity is trivial. But 'categoricity in power' illustrates the sort of mathematical consequences we mean. One can lay out a schema with a few parameters (depending on the theory) which describes the structure of any model of any theory categorical in uncountable power. Similar schema for the decomposition of models apply to other theories according to properties defining the stability hierarchy. We describe arguments using properties, which essentially involve formalizing mathematics, to obtain results in 'mainstream' mathematics. We consider discussions on method by Kashdan, and Bourbaki as well as such logicians as Hrushovski and Shelah.

Beckmann, Arnold: Parity Games and Resolution

Parity games are two player games which are played by moving a token around a finite graph. Parity games have important applications in automata theory, logic, and verification. It is a long-standing open problem whether the winner in a parity game can be decided in polynomial time.

In the talk, we will relate this problem to weak automatizability of resolution using bounded arithmetic. A propositional proof system is weakly automatizable if there is a polynomial time algorithm which separates satisfiable formulas from formulas which have a short refutation in the system, with respect to a given length bound. Namely, we will show that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time.

This is joint work with Pavel Pudlak and Neil Thapen.

Beklemishev, Lev: Positive provability logic

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant 'true' by conjunction and diamonds only. Positive modal logics, axiomatizing the logical consequence between such restricted positive formulas, turn out to be much simpler than the usual modal logics, both semantically and computationally, and yet expressive enough to capture interesting information.

Brendle, Jörg: Maximality and definability

Families of sets of natural numbers satisfying certain maximality properties typically are rather non-definable objects. For example an ultrafilter is neither measurable nor has the property of Baire, and thus cannot be (co)analytic. Mathias proved there are no analytic mad families, and Miller showed there are no analytic maximal independent families.

However, on the next level of the projective hierarchy, such families may exist (and do exist in the constructible universe $L$). In fact, one may consider the non-existence of such families as transcendence statements over $L$, similar to the statement, say, that all $\Delta^1_2$ sets are measurable (which is equivalent to saying that there is a random real over every $L[x]$). We will survey some results on implications and non-implications between such transcendence statements, and mention a number of open problems.

Buss, Sam: On Clause Learning Algorithms for Satisfiability

Conflict directed clause learning (CDCL) algorithms have been remarkably successful for solving large-scale instance of satisfiability that arise in industrial applications. This talk will give an overview of CDCL algorithms, and discuss the propositional proofs which are implicitly generated by CDCL. It is an open question whether CDCL without restarts can polynomially simulate resolution, and we will discuss recent progress on this problem.

Parts of this work are joint with M. Bonet, J. Johannsen, and L. Kolodziejczyk.

Conley, Clinton: Local complexity among treeable equivalence relations, part 1

Group-theoretic rigidity techniques such as Zimmer and Popa cocycle superrigidity have been instrumental in works of Adams-Kechris, Thomas, and Hjorth (among others) in realizing complexity in the partial order of Borel reducibility among countable Borel equivalence relations. We introduce an alternative elementary notion of rigidity which interacts favorably with Borel reducibility, allowing us to localize various complexity results to just above measure hyperfinite in the class of treeable equivalence relations. Part 2 will be given by Ben Miller.

Dobrinen, Natasha: Sliders

We begin by reminiscing about Sy's introducing indiscernibles to me when I was a new a postdoc at KGRC. Indiscernibles not only slide around, they slide between different fields of mathematics. We trace how indiscernibles have been a key recurrent theme in my work with Sy on co-stationarity of the ground model and in my recent work in Ramsey theory.

Enayat, Ali: Mathematics meets Poetry: Omar Khayyam

This talk introduces the enigmatic Persian mathematician, astronomer, philosopher, and poet Omar Khayyam (1048–1131), whose fame in the west is mostly due to the translations of his four-line verses (quatrains) in late 19^th century by the English poet and writer, Edward FitzGerald.

Flum, Jörg: Some remarks on a 60-year old model-theoretic method

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as the P-NP-problem no progress has been achieved using the games. We show that for these problems it is already hard to get the board for the corresponding Ehrenfeucht-Fraisse game.

Golshani, Mohammad: Violating $GCH$ everywhere by a cofinality-preserving forcing

Easton's classical result showed that over any model of $GCH$, one can force any reasonable pattern of the power function $\lambda\mapsto 2^\lambda$ on the regular cardinals $\lambda$, preserving cardinals and cofinalities. Subsequently, much work has been done on the singular cardinal problem, whose aim is to characterise the patterns of the power function on all cardinals, including the singular ones. Typically in this work, large cardinals are used to obtain patterns of power function behaviour at singular cardinals after applying subtle forcings which change cofinalities or even collapse cardinals. This leads one to ask: Is it possible to obtain a failure of $GCH$ everyhwere by forcing over a model of $GCH$ without changing cofinalities? If so, can one have a fixed finite gap in the resulting model, meaning that $2^\lambda=\lambda^{+n}$ for some finite $n>1$ for all $\lambda$?

In this talk we give a positive answer to these questions by proving the following:

Assume $GCH+$ there exists a $(\kappa+4)-$strong cardinal $\kappa$. Then there is a pair $(V_1,V_2)$ of models of $ZFC$ such that:

$(a)$ $V_1$ and $V_2$ have the same cardinals and cofinalities,

$(b)$ $GCH$ holds in $V_1$,

$(c)$ $V_{2} \models "\forall \lambda, 2^{\lambda} = \lambda^{+3}$".

This is joint work with Sy David Friedman.

Harizanov, Valentina: Effective Categoricity of Injection Structures

We study computability-theoretic properties of computable injection structures and the complexity of isomorphisms between these structures. An injection structure is a structure $\mathcal{A} = (A; f )$ with a single unary $1$--$1$ function $f$. The orbit of $a \in A$ is $\mathcal{O}_{f}(a) = \{ b \in A : ( \exists n \in \mathbb{N} )[f^{n}(a) = b \lor f^{n}(b) = a ] \} $. We prove that a computable injection structure is computably categorical if and only if it has finitely many infinite orbits. A computable injection structure is $ \Delta^{0}_{2}$-categorical if and only if it has finitely many orbits of type $ \omega $ or finitely many orbits of type $Z$. Furthermore, every computably categorical injection structure is relatively computably categorical, and every $ \Delta^{0}_{2}$-categorical injection structure is relatively $ \Delta^{0}_{2}$-categorical. We also establish various index set results. The index set of infinite computably categorical injection structures is a $\Sigma^{0}_{3}$-complete set. The index set of infinite $\Delta^{0}_{2}$-categorical injection structure is a $\Sigma^{0}_{4}$-complete set.

This is joint work with Doug Cenzer and Jeff Remmel.

Ida, Tetsuo: Graphs for Computational Origami - formalism and algorithms

We discuss graphs in computational origami (paper fold). We study the structure of an origami as well as the algorithmic aspects of the construction of the origami with the assistance of computers. The computational origami is closely linked to paper craft, traditional art, industrial design, geometry of all levels, and furthermore to computer science.

The origami construction is a sequence of fold steps, each consisting in folding an origami paper along a line. We, first, formalize the origami construction by modeling an origami by a structure called abstract origami, consisting of a set of faces together the binary relations superposition and adjacency over the set of faces. By the fold along the fold line, the abstract origami is transformed. Some faces are divided and rotated, and new faces are created. The set of faces and the two relations change accordingly.

When we give geometrical attributes to the faces, we naturally obtain a special graph well suited to representing, transforming and analyzing the origami. The graph we are led to define is a particular instance of a labeled hyper graph, where its vertex set is the set of faces. The hyper edges are used to connect the face to its adjacent faces in an order determined by the geometry of the face. The transformation of the abstract origami is formalized as a graph rewriting. The labeled hyper graph is the combination of two kinds of graphs. One is the graph derived from the structure of the set of faces and the adjacency relation, and the other is a face layer graph. The face layer graph is derived from the quotient set of the faces and the overlay relations (defined via the superposition relations) over the quotient set. The one step fold corresponds to a single step graph rewriting of the hyper graph.

We show some origami constructions as illustrative applications of our formalism. They exhibit non-trivial propertied of origamis. Furthermore, from the graphs, we extract algebraic relations describing geometrical properties of the origami. Using the algebraic relations, we can prove geometrical theorems about the constructed origami by automated proof methods such as Gröbner bases and cylindrical decomposition.

Kanovei, Vladimir: Surreal numbers from the point of view of nonstandard analysis

A system of foundations of infinitesimal calculus will be proposed and discussed. The system is based on two class-size models, including 1) the surreal numbers, and 2) the Kanovei-Shelah set-size-saturated limit ultrapower model. Some historical remarks will be made, and a few related problems will be discussed, too.

(Andrews, Uri and) Knight, Julia: Strongly minimal theories with computable models

We give effectiveness conditions on a strongly minimal theory $T$ guaranteeing that all models have computable copies. In particular, we show that if $T$ is a strongly minimal and $T \cap \exists_{n+3}$ is $\Delta^{0}_{n}$ uniformly in $n$, then every model has a computable copy. In particular, we answer a long-standing question in computable model theory by showing that if some model of a strongly minimal theory is recursive, then every model is arithmetical; in fact, every model has a copy recursive in $\emptyset^{(4)}$.

Miller, Ben: Local complexity among treeable equivalence relations, part 2

Group-theoretic rigidity techniques such as Zimmer and Popa cocycle superrigidity have been instrumental in works of Adams-Kechris, Thomas, and Hjorth (among others) in realizing complexity in the partial order of Borel reducibility among countable Borel equivalence relations. We introduce an alternative elementary notion of rigidity which interacts favorably with Borel reducibility, allowing us to localize various complexity results to just above measure hyperfinite in the class of treeable equivalence relations. (Part 1 of this talk is given by Clinton Conley.)

Miller, Russell: Local Computability and the ordinal $\omega_1^{ck}\times\omega$

We use local computability to study the extent to which ordinals can be effectively presented (as linear orders). For computable ordinals, the answer is known, but for noncomputable ordinals, the notion of extensionality gives an unexpected result. We will present the definitions of locally computable structures and of $\theta$-extensionality, and show how they apply here.

This work is joint with Johanna Franklin, Asher Kach, and Reed Solomon, and owes much to conversations with Julia Knight.

Mota, Miguel Angel: More applications of the method of "rigid iterations with side conditions"

We show that Weak Club Guessing and the principle mho can be separated in the context of a large continuum. We also include the proof that the natural forcing associated to the set of all the symmetric systems (the subjacent first iterand in all our forcing constructions) preserves $CH$ and generically adds a coherent structure on the second uncountable cardinal.

In the context of provability logic, the weaker language allows for a wider class of arithmetical interpretations, for example, one can interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus proving an analogue of Solovay's arithmetical completeness theorems. This calculus is also shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time.

Motto Ros, Luca: Descriptive Set Theory and Computation Theory

I will survey some recent results which all originated from a joint work with Sy Friedman, where we proved that the embeddability relation on countable structures is invariantly universal (that is: every analytic quasi-order $R$ is Borel bi-reducible with the embeddability relation on the countable models of a corresponding $L_{\omega_1 \omega}$-sentence).

Nies, André: Metric Spaces and Computability Theory

We study similarity of Polish metric spaces. We consider the Scott rank, both for classical and for continuous logic. The former is connected to isometry, the latter to having Gromov-Hausdorff distance zero. In the computable setting, we show that any two isometric compact metric spaces are $ \Delta^{0}_{3}$ isometric.

The various projects we review are joint with many researchers, among them Sy Friedman, Fokina and Koerwien; Ben Yaacov and Tsankov; Melnikov.

Raghavan, Dilip: Combinatorial dichotomies and cardinal invariants

We will describe some recent results on the equivalence between certain combinatorial dichotomies and statements about cardinals invariants of the continuum. These results are part of an ongoing project to calibrate the strength of some consequences of PFA by the largeness of appropriate cardinal invariants. This is done using principles like the P-ideal dichotomy or Rado's conjecture. We will also discuss the connection between this and the models obtained by forcing with a coherent Suslin tree. Some partition relations for Suslin trees will be described.

This is joint work with Todorcevic.

Törnquist, Asger: Analytic eventually different families of functions are not maximal

A well-known result of Mathias says that an infinite maximal almost disjoint family of subsets of $\omega$ is never analytic. The question has been raised if a maximal family of eventually different functions on $\omega$ can be analytic. In this talk, I will present a proof that it can't be. We also obtain a new (and quite different) proof of Mathias' theorem. In the unlikely event that there is time at the end of the talk, I will also discuss how to adapt the proof to show that analytic cofinitary families and groups of permutations of $\omega$ are never maximal.

Wilken, Gunnar: A short introduction to Patterns of Resemblance

Elementary patterns of resemblance were discovered and first investigated by Tim Carlson. I will give an idea of their basic nature and describe some of my contributions, leading me to a conjecture on strong patterns of order 2.