Seminar talks spring 2022

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.

17

18

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 (% style="color: inherit;" %)respectively(%%) to dependence and inclusion atoms.

19

20

This is joint work with Jef Wijsen.

\\

Wednesday 2.2.2022 12-14, (% style="color: rgb(255,0,0);" %)Online

Pietro Galliani

Title: The Unsafety of Constancy

29

30

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, (% style="color: rgb(255,0,0);" %)Online(%%)

35

Menachem Magidor: Large cardinals and properties of generalized logics

Abstract:

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

40

41

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.

42

43

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.

44

45

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

54

55

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.

56

57

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 (% style="color: inherit;" %)respectively(%%) to dependence and inclusion atoms.

58

59

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 (% style="color: rgb(255,0,0);" %)**IN PERSON**

64

65

(% style="margin-left: 40.0px;" %)

66

12:15-13:15 Gabe Goldberg: (% style="color: rgb(96, 96, 96); text-decoration: none; color: rgb(34, 34, 34); text-decoration: none" %)Around the Ultrapower Axiom.(% style="color: rgb(96,96,96);text-decoration: none;" %)

67

68

69

(% style="margin-left: 80.0px;" %)

70

(% style="color: rgb(96,96,96);text-decoration: none;" %)**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.

71

72

(% style="margin-left: 40.0px;" %)

73

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

74

75

(% style="margin-left: 80.0px;" %)

76

**Abstract [[(Link)>>url:http://www.math.helsinki.fi/logic/AbstractHelsinki.pdf||shape="rect"]]**

77

78

(% style="margin-left: 40.0px;" %)

79

14:15-14:30 Coffee break in Chemicum

80

81

(% style="margin-left: 40.0px;" %)

82

14:45-15:45 David Aspero

83

84

(% style="margin-left: 80.0px;" %)

85

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

\\

(% style="margin-left: 40.0px;" %)

90

15:45-16:45 Miguel Moreno: K(% style="color: rgb(0,0,0);text-decoration: none;" %)appa - colorable linear orders and unsuperstable theories

91

92

(% style="margin-left: 80.0px;" %)

93

(% style="color: rgb(0,0,0);text-decoration: none;" %)**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.

94

95

(% style="margin-left: 40.0px;" %)

96

16:45-17:45 Asaf Karagila: (% style="color: rgb(34,34,34);text-decoration: none;" %)Distributive and Sequential Forcings

97

98

(% style="margin-left: 80.0px;" %)

99

(% style="color: rgb(34,34,34);text-decoration: none;" %)**Abstract**: We define the notion of a sequential forcing as a forcing not adding (%%)

100

(% style="color: rgb(34,34,34);text-decoration: none;" %)new ground model sequences. Working in ZFC this is the same as distributive (%%)

101

(% style="color: rgb(34,34,34);text-decoration: none;" %)forcing, but surprisingly, perhaps, the two notions are not equivalent in ZF. We (%%)

102

(% style="color: rgb(34,34,34);text-decoration: none;" %)will talk about what we can and can't prove with regards to these two (%%)

103

(% style="color: rgb(34,34,34);text-decoration: none;" %)properties. This is a joint work with Jonathan Schilhan.

\\

Wednesday 2.3.2022 12-14, C124

Cancelled

\\

Wednesday 9.3.2022 12-14, C124

113

Exam week, no seminar

\\

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

118

Joni Puljujärvi: Compactness Theorem for Independence Logic

119

120

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

121

\\This is joint work with Davide Quadrellaro.

\\

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

126

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

\\

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

131

(% style="color: rgb(0,0,0);text-decoration: none;" %)Rémi Jaoui: (%%)Counting the number of models of the solution sets of differential equations.

132

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

133

134

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

139

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

140

141

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

146

Tapio Saarinen: The categoricity of second-order theories

147

148

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

153

Easter break, no seminar

\\

Wednesday 27.4.2022 12-14, C124

158

Otto Rajala: Stationary tower and C*

159

160

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

165

Philip Welch: Free subsets of structures

166

167

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-- (% style="color: rgb(255,0,0);" %)**--POSTPONED TWO WEEKS-- CANCELLED**(%%)

172

Joint talk: Jean Luis Gastaldi, Luc Pellesier

173

174

(% style="color: rgb(32,31,30);text-decoration: none;" %)From Realisability to Distributional Syntax: Towards a New Logic-Language Correspondence

175

176

(% style="color: rgb(32,31,30);text-decoration: none;" %)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 (% style="color: rgb(255,0,0);" %)**PLEASE NOTE CHANGE OF TIME **

181

182

Philip Welch: (% style="color: rgb(32,31,30);text-decoration: none;" %)Quasi-Inductive Definitions

183

184

(% style="color: rgb(32,31,30);text-decoration: none;" %)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

189

190

Informal lecture by Philip Welch

191

192

Title: Reworking Kleene's Higher Type Recursions

193

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

\\

Wednesday 8.6.2022 12-14, C124 + zoom

198

199

David Forsman (UCLouvain): Basic category theory and monoidal semantics for predicate logic

200

\\Abstract:

201

The constructions of category theory are based on the notion of universal properties, which are encapsulated by so called initial/terminal objects. Critical concepts related to categorical constructions are

202

203

* Initial and terminal objects

* Limit and colimit

* Adjoint functor

* Kan extension

During the seminar talk, we are going to talk about the needed definitions of category theory to converse about categorical products and sums, which are directly generalized by limits of category theory. Categorical product gives a category the structure of a abelian monoid, but only up to a natural isomorphism. Category equipped with such a product, usually called a tensor product by category theorists, is called a monoidal category.

209

\\The second part of the talk will be about the syntax of predicate logic and its modification for more general context. We modify predicate logic to be more suitable for implementation in any monoidal category. This opens the door, for example, to talk about models satisfying the theory of monoids in the category of monoids, which, of course, are abelian monoids. The natural questions that arise are how do morphisms between L-models preserve/reflect truth and how monoidal functors between monoidal categories respect models of different alphabets and theories. We do not answer these questions, but we try to get to the point where we can ask these questions.

210

211

\\

Wiki source code of Seminar talks spring 2022

Navigation