# Logic Seminar

The Logic seminar is held on Wednesdays, usually at 12-14. During the fall 2023 we will have both on-site and online talks, and we try to keep the page updated on when we have which kind.

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. Also, if not separately specified, the talks always start at a quarter past.

The seminar is led by prof. Juha Kontinen and Ulla Karhumäki.

## Schedule of the spring term 2024

Wed 17.01.2024 12-14, C124

Miguel Moreno: On the Borel reducibility Main Gap

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510

Wed 24.01.2024 12-14, C124

Miguel Moreno: On the Borel reducibility Main Gap (continuation of last week)

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510

Wed 31.01.2024 12-14, C124

Teemu Hankala: From Neural Network Training to Tarski's Exponential Function Problem

For simple network architectures, the weights and biases of a neural network can be trained to optimal values in polynomial time. However, in a general setting the decision variant of the training problem is known to be NP-hard, and gradient descent is often used in the training phase. In 2021 it was shown by Abrahamsen, Kleist and Miltzow that the training problem with piecewise algebraic activation functions is polynomial-time reducible to the satisfiability problem of the existential theory of the real numbers and, in addition, that it is polynomial-time bireducible to this satisfiability problem even if restricted to the identity activation function. In this talk, the connection between neural network training and real numbers is extended to arbitrary activation functions. In particular, the standard logistic function leads to a training problem that is polynomial-time equivalent to Tarski's exponential function problem, whereas neural activations using the sine function lead to undecidability.

This talk is based on joint work with Miika Hannula, Juha Kontinen and Jonni Virtema.

Wed 07.02.2024 12-14, C124

Fausto Barbero: Probabilistic counterfactuals in multiteam semantics

An appropriate generalization of multiteams can be used as semantics for probabilistic intrventionist counterfactuals, e.g. expressions of the form:

"If X were set to value x, then the probability of Y taking value y is e"

In joint works with G. Sandu and J. Virtema, we have studied the properties of languages of causal inference under this interpretation, and considered extensions with infinitary Boolean operators and with strict tensor.

On the model-theoretic side, we see that the infinitary language displays an interesting type of expressive completeness. Understanding the much less expressive finitary languages involves the identification of four classes of linear inequalities and an understanding of their geometry in simplexes. The characterization results can be sharpened into a strict hierarchy of expressivity (of the languages and, in parallel, of the classes of inequalities) and serve as a basis for undefinability results.

On the proof-theoretic side, we provide strongly complete, infinitary axiom systems for both the finitary and infinitary languages. The latter problem led us to the identification of sufficient criteria for the truth of Lindenbaum lemmas.

Wed 14.02.2024 12-14, C124

Miika Hannula: Query output size, entropic inequalities, and conditional independence

We consider the following problem: given an open formula over a relational vocabulary, and size bounds for relations, determine the least upper bound for the number variable assignments satisfying the formula. Even for simple logical formulae, such as conjunctive queries, this problem is non-trivial. The problem also occurs in practice, as estimating the output sizes of intermediate joins (i.e., conjunctive queries) is a critical component of the database query execution plan. Entropic inequalities, in turn, govern the laws of Shannon entropy, and in this talk we consider how these topics connect to one another.We also discuss how entropic inequalities relate to logical entailment through the notion of conditional independence, and, time permitting, explore howconditional independence generalizes in semiring semantics.

Wed 21.02.2024 12-14, C124

Ulla Karhumäki: Small supersimple pseudofinite groups

A simple group is pseudofinite if and only if it is isomorphic to a (twisted) Chevalley group over a pseudofinite field. This celebrated result mostly follows from the work of Wilson in 1995 and heavily relies on the classification of finite simple groups (CFSG). It easily follows that any simple pseudofinite group G has a supersimple theory and that the SU-rank of G is finite. In particular, if SU(G)=3 then G is isomorphic to PSL_2(F) for some pseudofinite field F. In this talk we discuss `small’ pseudofinite groups with supersimple theory. In particular, we will see that the classification G \cong PSL_2(F) above does not require CFSG. This is joint work with F. O. Wagner.

Wed 28.02.2024, No seminar (most of the group not in Helsinki)

Wed 06.03.2024, Exam week (no seminar)

Wed 13.03.2024 12-14, No seminar (most of the group not in Helsinki)

Wed 20.03.2024 12-14, C124

Miguel Moreno: On the Borel reducibility Main Gap (continuation of weeks 1-2)

One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:

If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.

In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:

Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.

If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.

This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510

Wed 27.03.2024 12-14, C124

Minna Hirvonen: Axiomatization of implication for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence

A set of atoms S is said to logically imply another atom s if every suitable object (e.g. a database or a distribution) that satisfies all of the atoms in S also satisfies the atom s. An implication problem is the task of deciding whether a given set of atoms S logically implies another given atom s.

In this talk, we consider the implication problem for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. I will present a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.

Slides of the talk are here.

Wed 03.04.2024, 12-14, C124

Kai Sauerwald: A Semantic Perspective of AGM Belief Revision in Tarskian Logics

Changing theories according to new information minimally is axiomatically captured by the famous approach to revision from Alchourrón, Gärdenfors, and Makinson (AGM). We studied and characterized this notion of change in a very general framework on the ground of Tarskian logics semantically. Our starting point is the approach by Katsuno and Mendelzon (K&M), who provided such a characterization for propositional logic over finite signatures. We generalize K&M's approach to the setting of AGM-style revision over bases in arbitrary Tarskian logics, where base may refer to one of the various ways of representing an agent's beliefs (such as belief sets, arbitrary or finite sets of
sentences, or single sentences). The first result is a representation theorem providing a two-way correspondence between AGM-style revision operators and specific
assignments: functions associating every base to a "preference" relation over interpretations, which must be total but is - in contrast to prior approaches - not always transitive.  The second contribution presented is a characterization of all Tarskian logics for which our result can be strengthened to assignments that produce transitive preference relations
(as in K&M's original work).

Wed 10.04.2024, 12-14, C124

Ville Salo: Automatic structures and some applications

We define automatic structures and discuss some of their applications in logic (Presburger arithmetic), group theory (Cayley graph (bi-)automatic groups), combinatorics on words (Thue-Morse word and the Fibonacci word) and symbolic dynamics (the domino problem and dynamics of cellular automata).

Wed 17.04.2024, 12-14, C124

Werner Mérian: Logical characterization of complexity classes for enumeration problems

The problems related to complexity theory most commonly studied are the so-called decision problems. They consist in deciding whether, given an input instance, a certain condition is verified or not. Most often, these problems raise the question of whether there exists a solution or not. For their part, enumeration problems are interested in enumerating all solutions. Enumeration problems have been studied in the context of computational complexity theory, and several complexity classes have been introduced for these problems (for tractable ones, we can cite EnumP, TotalP, IncP, DelayP). Our work aims to bring the mission of descriptive complexity to the world of enumeration. The ultimate goal is to successfully capture a tractable enumeration complexity class (namely IncP) with a certain logic. We will then be able to say that an enumeration problem is in this complexity class if and only if there is a formula from the logic associated to this complexity class which characterizes this problem. Our trip will lead us to study fragments of third-order logic and to capture natural enumeration problems.

Wed 24.04.2024, 12-14, C124

Sándor Kisfaludi-Bak: TBA

Tue 30.04.2024, 12-14, D123 (note unusual time and place)

Tuomas Hakoniemi: TBA

Wed 08.05.2024, Exam week (no seminar)

Talks of the fall term 2023

#### Older talks (2011-2012)

Laboratory of dependence logic