Wiki source code of Seminar

Version 31.1 by Ulla Karhumäki on 2024/02/15 14:44
Show last authors
1 {{layout}}
2 {{layout-section ac:type="single"}}
3 {{layout-cell}}
4 = (% style="color:#000000" %)Logic Seminar(%%) =
5
6 (% style="color:#000000" %)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.
7
8
9 (% style="color:#000000" %)The permanent Zoom room for the seminar is: (%%)[[https:~~/~~/helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09>>url:https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09||shape="rect" class="moz-txt-link-freetext"]] (Meeting ID: 628 9140 0777, Passcode: 164195)
10
11 (% style="color:#ff0000" %)**PLEASE NOTE**(% style="color:#000000" %)**: 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.
12
13
14 (% style="color:#000000" %)The seminar is led by prof. Juha Kontinen and Ulla Karhumäki.
15
16 == Schedule of the spring term 2024 ==
17
18
19 (% class="p3" %)
20 **Wed 17.01.2024 12-14, C124**
21
22 (% class="p3" %)
23 **Miguel Moreno: **On the Borel reducibility Main Gap
24
25 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:
26
27 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'.
28
29 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:
30
31 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.
32
33 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.
34
35 This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility ([[https:~~/~~/arxiv.org/abs/2308.07510>>url:https://arxiv.org/abs/2308.07510]]
36
37
38 (% class="p3" %)
39 **Wed 24.01.2024 12-14, C124**
40
41 (% class="p3" %)
42 **Miguel Moreno: **On the Borel reducibility Main Gap (continuation of last week)
43
44 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:
45
46 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'.
47
48 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:
49
50 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.
51
52 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.
53
54 This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility ([[https:~~/~~/arxiv.org/abs/2308.07510>>url:https://arxiv.org/abs/2308.07510]]
55
56
57 (% class="p3" %)
58 **Wed 31.01.2024 12-14, C124**
59
60 (% class="p3" %)
61 **Teemu Hankala: **From Neural Network Training to Tarski's Exponential Function Problem
62
63 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.
64
65 This talk is based on joint work with Miika Hannula, Juha Kontinen and Jonni Virtema.
66
67
68 (% class="p3" %)
69 **Wed 07.02.2024 12-14, C124**
70
71 (% class="p3" %)
72 **Fausto Barbero: **Probabilistic counterfactuals in multiteam semantics
73
74 An appropriate generalization of multiteams can be used as semantics for probabilistic intrventionist counterfactuals, e.g. expressions of the form:
75
76 "If X were set to value x, then the probability of Y taking value y is e"
77
78 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.
79
80 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.
81
82 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.
83
84
85 (% class="p3" %)
86 **Wed 14.02.2024 12-14, C124**
87
88 (% class="p3" %)
89 **Miika Hannula: **Query output size, entropic inequalities, and conditional independence
90
91 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.
92
93
94 (% class="p3" %)
95 **Wed 21.02.2024 12-14, C124**
96
97 (% class="p3" %)
98 **Ulla Karhumäki: **Small supersimple pseudofinite groups
99
100 (% class="p3" %)
101 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.
102
103
104 (% class="p3" %)
105 **Wed 28.02.2024, No seminar (most of the group not in Helsinki)**
106
107
108 (% class="p3" %)
109 **Wed 06.03.2024, Exam week (no seminar)**
110
111
112 (% class="p3" %)
113 **Wed 13.03.2024 12-14, No seminar (most of the group not in Helsinki)**
114
115
116 (% class="p3" %)
117 **Wed 20.03.2024 12-14, TBA**
118
119
120 (% class="p3" %)
121 **Wed 27.03.2024 12-14, TBA**
122
123
124 (% class="p3" %)
125 **Wed 03.04.2024, Easter break (no seminar)**
126
127
128 (% class="p3" %)
129 **Wed 10.04.2024, 12-14, TBA**
130
131 (% class="p3" %)
132 **Ville Salo: TBA**
133
134
135 (% class="p3" %)
136 **Wed 17.04.2024, 12-14, TBA**
137
138
139 (% class="p3" %)
140 **Wed 24.04.2024, 12-14, TBA**
141
142
143 (% class="p3" %)
144 **Wed 01.05.2024, 12-14, TBA**
145
146
147 (% class="p3" %)
148 **Wed 08.05.2024, Exam week (no seminar)**
149
150
151
152 **[[doc:Logic.Home.Seminar.Talks of the fall term 2023.WebHome]]**
153
154 ==== [[doc:Logic.Home.Seminar.Talks of the spring term 2023.WebHome]] ====
155
156 ==== [[Talks of the fall term 2022>>doc:Logic.Home.Seminar.Seminar talks fall 2022.WebHome]] ====
157
158 ==== (% style="color:#000000" %)[[Talks of the spring term 2022>>doc:Logic.Home.Seminar.Seminar talks spring 2022.WebHome]](%%) ====
159
160 ==== (% style="color:#000000" %)[[Talks of the fall term 2021>>doc:Logic.Home.Seminar.Seminar talks fall 2021.WebHome]](%%) ====
161
162 ==== (% style="color:#000000" %)[[Talks of the spring term 2021>>doc:Logic.Home.Seminar.Seminar talks spring 2021.WebHome]](%%) ====
163
164 ==== (% style="color:#000000" %)[[Talks of the fall term 2020>>url:https://wiki.helsinki.fi/display/Logic/Seminar+talks+fall+2020||shape="rect"]](%%) ====
165
166 ==== (% style="color:#000000" %)[[Talks of the spring term 2020>>doc:Logic.Home.Seminar.Seminar talks spring 2020.WebHome]](%%) ====
167
168 ==== (% style="color:#000000" %)[[Talks of the fall term 2019>>doc:Logic.Home.Seminar.Seminar talks fall 2019.WebHome]](%%) ====
169
170 ==== (% style="color:#000000" %)[[Talks of the spring term 2019>>doc:Logic.Home.Seminar.Seminar talks spring 2019.WebHome]](%%) ====
171
172 ==== (% style="color:#000000" %)Talks of the fall term 2018[[doc:Logic.Home.Seminar.Seminar talks fall 2018.WebHome]](%%) ====
173
174 ==== (% style="color:#000000" %)Talks of the spring term 2018[[doc:Logic.Home.Seminar.Seminar talks spring 2018.WebHome]](%%) ====
175
176 ==== (% style="color:#000000" %)Talks of the fall term 2017[[doc:Logic.Home.Seminar.Seminar talks fall 2017.WebHome]](%%) ====
177
178 ==== (% style="color:#000000" %)Talks of the spring term 2017[[doc:Logic.Home.Seminar.Seminar talks spring 2017.WebHome]](%%) ====
179
180 ==== (% style="color:#000000" %)Talks of the fall term 2016[[doc:Logic.Home.Seminar.Seminar talks fall 2016.WebHome]](%%) ====
181
182 ==== (% style="color:#000000" %)Talks of the spring term 2016[[doc:Logic.Home.Seminar.Seminar talks spring 2016.WebHome]](%%) ====
183
184 ==== (% style="color:#000000" %)Talks of the fall term 2015[[doc:Logic.Home.Seminar.Seminar talks fall 2015.WebHome]](%%) ====
185
186 ==== (% style="color:#000000" %)Talks of the spring term 2015[[doc:Logic.Home.Seminar.Seminar talks spring 2015.WebHome]](%%) ====
187
188 ==== (% style="color:#000000" %)Talks of the fall term 2014[[doc:Logic.Home.Seminar.Seminar talks fall 2014.WebHome]](%%) ====
189
190 ==== (% style="color:#000000" %)Talks of the spring term 2014[[doc:Logic.Home.Seminar.Seminar talks spring 2014.WebHome]](%%) ====
191
192 ==== (% style="color:#000000" %)Talks of the fall term 2013[[doc:Logic.Home.Seminar.Seminar talks fall 2013.WebHome]](%%) ====
193
194 ==== (% class="confluence-link" style="color:#000000" %)Talks of the spring term 2013(% style="color:#000000" %)[[doc:Logic.Home.Seminar.Seminar talks spring 2013.WebHome]](%%) ====
195
196 ==== (% style="color:#000000" %)Talks of the fall term 2012[[doc:Logic.Home.Seminar.Seminar talks fall 2012.WebHome]](%%) ====
197
198 ==== (% style="color:#000000" %)[[(% style="color: rgb(0, 0, 0); color: rgb(0, 0, 0)" %)Older talks (2011-2012)>>url:http://www.helsinki.fi/~~kluosto/mat.log.sem/talks.txt||shape="rect"]](%%) ====
199
200 (% style="color:#000000" %)[[(% style="color: rgb(0, 0, 0); color: rgb(0, 0, 0)" %)Laboratory of dependence logic>>url:http://wiki.helsinki.fi/display/mathstatKurssit/Dependence+logic%2C+fall+2012||shape="rect"]]
201 {{/layout-cell}}
202 {{/layout-section}}
203
204 {{layout-section ac:type="single"}}
205 {{layout-cell}}
206
207 {{/layout-cell}}
208 {{/layout-section}}
209 {{/layout}}