{{Menu SDF60|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.
[#B_Miller 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 19th 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.
([#Conley 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.