Seminar talks spring 2022
Talks during 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.
Wednesday 8.6.2022 12-14, C124 + zoom
David Forsman (UCLouvain): Basic category theory and monoidal semantics for predicate logic
Abstract:
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
- 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.
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.