# Logic Seminar

The Logic seminar is held on Wednesdays, usually at 12-14. During the spring 2022 we continue alternating between online and on campus talks.

The permanent Zoom room for the seminar is: https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09 (Meeting ID: 628 9140 0777, Passcode: 164195)

**PLEASE NOTE: Due to the prevalence of zoom talks given by scholars based in various time zones, the times that the seminar meets will occasionally ****change from the usual 12-14 slot.**

The seminar is led by prof. Juha Kontinen and Juliette Kennedy.

## Schedule of the spring term 2022

Wednesday 19.1.2022 12-14, C124: **Seminar is cancelled**

Wednesday 26.1.2022 12-14, **Online**

Miika Hannula

Title: "A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys", PART 1

Abstract: "In recent years, significant progress has been made in the problem of Consistent Query Answering (CQA) with respect to primary keys. In this problem, the input is a database instance that may violate one or more primary key constraints. A repair is defined as a maximal subinstance that satisfies all primary keys. Given a Boolean query q, the question then is whether q holds true in every repair.

So far, theoretical research in this field has not addressed the combination of primary key and foreign key constraints, despite the importance of referential integrity in database systems. We study CQA with respect to both primary keys and foreign keys, considering the case where foreign keys are unary, and queries are conjunctive queries without self-joins. In this setting, it is natural to adopt the notion of symmetric-difference repairs, since foreign keys can be repaired by adding new tuples. We characterize the boundary between those CQA problems that admit a first-order rewriting, and those that do not. This work is closely connected with dependence logic, since primary and foreign keys correspond respectively to dependence and inclusion atoms.

This is joint work with Jef Wijsen.

Wednesday 2.2.2022 12-14, Online

Pietro Galliani

Title: The Unsafety of Constancy

Abstract: Constancy atoms are among the simplest dependency atoms, and adding them only to First Order Logic yields a language ("Constancy Logic") that is not more expressive than First Order Logic itself. However, adding them to First Order Logic together with other atoms can yield surprising results. In this talk, I will discuss the consequences of adding constancy atoms to logics based on Team Semantics.

Wednesday 9.2.2022 12-14, Online

Menachem Magidor: Large cardinals and properties of generalized logics

Abstract:

This is a joint work with Will Boney, Stamis Dimipoulos and Victoria Gitman

It is well known that many large cardinals properties and schemata can be phrased as regularities properties of generalized logics. (Typical examples are Skolem-Lōwenheim and compactness properties ). In this talk we shall present some additional such characterizations.

An example is the connection between subtle cardinals and the existence of weak compactness for every abstract logic or the characterization of various virtual cardinals in terms of variations of compactness properties appropriate for the context of virtual large cardinals.

The basic definitions will be provided, so the talk should be accessible to a large group of logicians.

Wednesday 16.2.2022 12-14

Miika Hannula

Title: "A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys", PART 2

Abstract: "In recent years, significant progress has been made in the problem of Consistent Query Answering (CQA) with respect to primary keys. In this problem, the input is a database instance that may violate one or more primary key constraints. A repair is defined as a maximal subinstance that satisfies all primary keys. Given a Boolean query q, the question then is whether q holds true in every repair.

So far, theoretical research in this field has not addressed the combination of primary key and foreign key constraints, despite the importance of referential integrity in database systems. We study CQA with respect to both primary keys and foreign keys, considering the case where foreign keys are unary, and queries are conjunctive queries without self-joins. In this setting, it is natural to adopt the notion of symmetric-difference repairs, since foreign keys can be repaired by adding new tuples. We characterize the boundary between those CQA problems that admit a first-order rewriting, and those that do not. This work is closely connected with dependence logic, since primary and foreign keys correspond respectively to dependence and inclusion atoms.

This is joint work with Jef Wijsen.

Wednesday 23.2.2022 Minisymposium (with support from the European Research Council and the Academy of Finland) starting 12:15, C124 **IN PERSON**

12:15-13:15 Gabe Goldberg: Around the Ultrapower Axiom.

**Abstract: **The Ultrapower Axiom (UA) is a set theoretic principle with strong consequences in the theory of large cardinals, a principle that seems to capture a fragment of the large cardinal structure of canonical inner models for supercompact cardinals, though constructing such models remains one of the major open problems in modern set theory. This talk will survey the basic theory of UA and some of its applications to set theoretic problems with no obvious connection to UA or inner model theory.

13:15-14:15 Andres Villaveces: On the Internal Logic of an Abstract Elementary Class.

**Abstract (Link)**

14:15-14:30 Coffee break in Chemicum

14:45-15:45 David Aspero

**Abstract**: I will define a local version of Woodin’s $\Omega$-logic in terms of initial fragments of forcing extensions of models of the form $L(V_\delta)$ and will present a completeness theory for this logic in line with the $\Omega$-conjecture for $\Omega$-logic.

15:45-16:45 Miguel Moreno: Kappa - colorable linear orders and unsuperstable theories

**Abstract**: One of the most important questions in generalized descriptive set theory is whether there is a generalized Borel-reducibility counterpart of Shelah's main gap theorem? (i.e. for any classifiable theory T and non-classifiable theory T', is the isomorphism relation of T Borel reducible to the isomorphism relation of T' ?) Some progress has been made by Friedman, Hyttinen, Kulikov, Motto Ros and others. It has been proved that it is a consistent statement and can be obtained by forcing diamond. It has been proved that for any classifiable theory T and stable unsuperstable theory T', the isomorphism relation of T is Borel reducible to the isomorphism relation of T'. The proof uses colorable trees to construct models of T'. In this talk we will extend this result to unstable theories by introducing the notion of K-colorable linear orders to construct generalized Ehrenfeucht-Mostowski models.

16:45-17:45 Asaf Karagila: Distributive and Sequential Forcings

**Abstract**: We define the notion of a sequential forcing as a forcing not adding

new ground model sequences. Working in ZFC this is the same as distributive

forcing, but surprisingly, perhaps, the two notions are not equivalent in ZF. We

will talk about what we can and can't prove with regards to these two

properties. This is a joint work with Jonathan Schilhan.

Wednesday 2.3.2022 12-14, C124

Cancelled

Wednesday 9.3.2022 12-14, C124

Exam week, no seminar

Wednesday 16.3.2022 12-14, C124 **IN PERSON**

Joni Puljujärvi: Compactness Theorem for Independence Logic

**Abstract**: In first-order logic, the following two formulations of the compactness theorem are equivalent: 1) "every set of *sentences *that is finitely satisfiable is satisfiable", and 2) "every set of *formulas* that is finitely satisfiable is satisfiable". From the translation to existential second-order logic, one gets the first formulation of compactness for independence logic. In logics based on team semantics, however, these two formulations are, a priori, distinct because of the different role of free variables. In this talk we present a proof of the second formulation of compactness for independence logic. Time permitting, we will also discuss types in the team semantical setting.

This is joint work with Davide Quadrellaro.

Wednesday 23.3.2022 12-14, C124 **IN PERSON**

Jouko Väänänen: Dependence logic: Some recent developments

Wednesday 30.3.2022 12-14, C124 **IN PERSON**

Rémi Jaoui: Counting the number of models of the solution sets of differential equations.

Abstract: In his seminal paper in 1973, Shelah showed that the theory of differentially closed fields of characteristic zero (despite being omega-stable) admits the maximal number of models in every uncountable cardinal.

I will describe some local versions of this result for classical families of differential equations and the relationship between this approach and certain transcendence properties identified by Painlevé in the end of the XIXth century.

Wednesday 6.4.2022 12-14, C124

Minna Hirvonen: The implication problem for functional dependencies and variants of marginal distribution equivalences

Abstract: This talk considers functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables x and y are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable x is the same as the corresponding multiset for y. I will present a sound and complete axiomatization and a polynomial-time algorithm for the implication problem for the class of these dependencies.

Wednesday 13.4.2022 12-14, C124

Tapio Saarinen: The categoricity of second-order theories

Abstract: We discuss the question of categoricity of complete second-order theories and its independence from ZFC. In particular, we show how to force categoricity for complete second-order theories with a model of (a certain) singular cardinality.

Wednesday 20.4.2022 12-14, C124

Easter break, no seminar

Wednesday 27.4.2022 12-14, C124

Otto Rajala: Stationary tower and C*

Abstract: I will talk about some basic properties of stationary tower forcing and how it's applied to C* (the \omega-cofinality model)

Wednesday 4.5.2022 12-14, hybrid: C124 + zoom

Philip Welch: Free subsets of structures

Abstract: If A is a first order structure, a subset X of dom(A) is *free* if no element of X can be defined in A from other elements of X. In general, finding infinite free subsets of infinite structures, requires large cardinals. We survey the field here, and examine extensions of this property due to Pereira, distilled from his work on the pcf conjecture, and recently another due to Adolf and Ben Neria. Work of the latter now establishes, with older work of the speaker, an equiconsistency between inner models with sequences of measures and their extension of Pereira's "Approachable Free Subset Property".

~~Wednesday 11.5.2022 12-14, C124~~ ~~POSTPONED TWO WEEKS~~ CANCELLED

Joint talk: Jean Luis Gastaldi, Luc Pellesier

From Realisability to Distributional Syntax: Towards a New Logic-Language Correspondence

Through abstract machines, the project of classical realisability revealed a dynamic from which significant aspects of logic can be derived from the interaction of pure computational terms. At the heart of this dynamic lies a notion of orthogonality informing a typing procedure which also plays a central role in the multiple approaches to the linear logic program. Significantly, the same tools have been developed independently in the framework of empirical approaches to formal grammars in computational linguistics. All of which suggests the possibility of a novel connection between logical systems and the treatment of natural language. After introducing the main aspects of these approaches, we will propose a way to understand this new correspondence between logic and linguistics and present some experimental empirical results from our current work in progress.

MONDAY 16.05, 12-14 SPECIAL LECTURE, C129 **PLEASE NOTE CHANGE OF TIME **

Philip Welch: Quasi-Inductive Definitions

Abstract: Such definitions extend the well researched theory of monotone inductive definitions by allowing non-monotone processes that are structured by liminf rules at limits rather than simple unions. Much of the Moschovakian theory of induction over abstract structures can be performed in this context, resulting in certain Spector classes of sets. Whereas the theory of inductive definitions leads to the idea of the least admissible set over a structure A, here one constructs the least 'strongly Sigma_2-admissible set' over A. Just as Sigma^0_1-Determinacy is associated with HYP(N), and Kleene's higher type recursion, so there are connections to be explored here with a higher type form of quasi-inductive recursion for a q-HYP(N).

Wednesday 25.5.2022 12-14, B121 + Zoom

Informal lecture by Philip Welch

Title: Reworking Kleene's Higher Type Recursions

Abstract: In the late 50's and early 60's Kleene wrote four papers on recursion in finite types. In two of them he gave an equation theoretic basis for such recursions, making it look rather like extensions of Goedel-Herbrand recursion. These two papers were very influential. In the other two papers he gave an alternative definition using Turing machines and showed their equivalence. The latter papers seem not to have had any substantial consequences, or indeed readership. Nevertheless they produce in type 2, a notion of computation whereby the 'halting problem' in this context is a complete Pi^1_1 set of integers, or equivalently a complete GSIgma^0_1 set. By taking Kleene's idea and reworking it for infinite time Turing machines (ITTM's) one has a halting problem that is a complete GSIgma^0_3 set, thereby neatly tying in ITTM's with classical descriptive set theory.