An inner model from stationary logic

Speaker: 

Jouko Vaananen

Institution: 

University of Helsinki

Time: 

Monday, November 28, 2022 - 4:00pm to 5:30pm

Host: 

Location: 

RH 440 R

Godel's constructible universe uses first order logic to build a model of ZFC containing all of the ordinals and where the GCH holds.  This talk describes a method of building analogous models using Stationary Logic. These are well-founded inner models of stronger axioms than ZFC that retain elements of fine structure. 

Stationary Logic is a stronger logic than first order logic, but retains desirable model theoretic aspects. 

Paths and Boundaries in Locally Finite Graphs

Speaker: 

Garrett Ervin

Institution: 

Carnegie Mellon University

Time: 

Monday, June 7, 2021 - 4:00pm to 5:30pm

Location: 

Zoom

There are many duality theorems in both finite and infinite graph theory that relate the maximum number of disjoint paths through a given graph G to the minimum size of a cut-set disconnecting G. The quintessential example is Menger's theorem, which says that the maximum number of vertex disjoint paths between two vertices x and y in a finite graph G is equal to the minimum size of a vertex cut disconnecting x and y.

We present a general approach to proving path/cut-set duality theorems for locally finite graphs. As one consequence of this approach, we give novel proofs of Menger's theorem and another classical duality result due to Halin. As another, we prove the following general existence theorem, which can be viewed as a maximal extension of König's lemma: given an infinite, locally finite connected graph G and a vertex x in G, there is a pruned tree T contained in G and rooted at x that, in a precise sense, splits as early and as often as possible.

Fields interpretable in the free group

Speaker: 

Rizos Sklinos

Institution: 

Stevens Institute of Technology

Time: 

Monday, April 5, 2021 - 4:00pm to 5:30pm

After Sela and Kharlampovich-Myasnikov proved that nonabelian free groups share the same common theory, a model theoretic interest for the theory of the free group arose. Moreover, maybe surprisingly, Sela proved that this common theory is stable. Stability is the first dividing line in Shelah's classification theory and it is equivalent to the existence of a nicely behaved independence relation - forking independence. This relation, in the theory of the free group, has been proved (Ould Houcine-Tent and Sklinos) to be as complicated as possible (n-ample for all n). This behavior of forking independence is usually witnessed by the existence of an infinite field. We prove that no infinite field is interpretable in the theory of the free group, giving the first example of a stable group which is ample but does not interpret an infinite field.

Quantitative structure of finite stable subsets in arbitrary groups

Speaker: 

Gabriel Conant

Institution: 

University of Cambridge

Time: 

Monday, April 12, 2021 - 4:00pm to 5:30pm

Location: 

Zoom

In 2011, Malliaris and Shelah proved that finite stable graphs satisfy a strengthened version of Szemeredi’s Regularity Lemma, with polynomial bounds and no irregular pairs. In 2017, Terry and Wolf proved an analogue of this for stable subsets of finite abelian groups, based on Green’s “arithmetic regularity lemma". Roughly speaking, they showed that stable subset of a finite abelian group can be approximated by a union of cosets of a subgroup whose index is bounded by a exponential function depending only on the stability constant and approximation error. These results for abelian groups were qualtitatively generalized to all finite groups by C., Pillay, and Terry, and then to finite subsets of arbitrary groups by Martin-Pizarro, Palacin, and Wolf. However, the generalizations for non-abelian groups used model-theoretic techniques involving ultraproducts, and thus produced no explicit quantitative bounds. In this talk, I will discuss a new proof of these results, which avoids the use of ultraproducts and yields effective bounds. These techniques also improve the bound in the abelian case from exponential to polynomial, and yield the Polynomial Freiman-Ruzsa Conjecture for finite stable subsets of arbitrary groups.
 

Embeddings of HOD

Speaker: 

Gabriel Goldberg

Institution: 

UC Berkeley

Time: 

Monday, May 3, 2021 - 4:00pm to 5:30pm

Location: 

Zoom

Jensen's covering lemma states that either every uncountable set of ordinals is covered by a constructible set of ordinals of the same size or else there is an elementary embedding from the constructible universe to itself. This talk takes up the question of whether there could be an analog of this theorem with constructibility replaced by ordinal definability. For example, we answer a question posed by Woodin: assuming the HOD conjecture and a strongly compact cardinal, there is no nontrivial elementary embedding from HOD to HOD.

What does logic have to do with AI/ML for computational science? (Part 2)

Speaker: 

Eric Mjolsness

Institution: 

UC Irvine

Time: 

Monday, April 26, 2021 - 4:00pm to 5:50pm

Location: 

Zoom

Progress in artificial intelligence (AI), including machine learning (ML),
is having a large effect on many scientific fields at the moment, with much more to come.
Most of this effect is from machine learning or "numerical AI", 
but I'll argue that the mathematical portions of "symbolic AI" 
- logic and computer algebra - have a strong and novel roles to play
that are synergistic to ML. First, applications to complex biological systems
can be formalized in part through the use of dynamical graph grammars.
Graph grammars comprise rewrite rules that locally alter the structure of
a labelled graph. The operator product of two labelled graph
rewrite rules involves finding the general substitution 
of the output of one into the input of the next - a form of variable binding 
similar to unification in logical inference algorithms. The resulting models
blend aspects of symbolic, logical representation and numerical simulation.
Second, I have proposed an architecture of scientific modeling languages
for complex systems that requires conditionally valid translations of
one high level formal language into another, e.g. to access different
back-end simulation and analyses systems. The obvious toolkit to reach for
is modern interactive theorem verification (ITV) systems e.g. those
based on dependent type theory (historical origins include Russell and Whitehead).
ML is of course being combined with ITV, bidirectionally.
Much work remains to be done, by logical people.

Part II: Current and planned work.
Operator algebra semantics (and the relevant Fock spaces)
for scientific modeling languages based on rewrite rules,
derivation of simulation algorithms,
semantics-approximating transformations using ML;
semantics-preserving transformations using ITV ?,
relation to graph grammar pushout semantics,
verbs vs. nouns vs. expressions and logic of "eclectic types",
compositional and specialization hierarchies,
"Tchicoma" conceptual architecture.

 

What does logic have to do with AI/ML for computational science?

Speaker: 

Eric Mjolsness

Institution: 

UC Irvine

Time: 

Monday, April 19, 2021 - 4:00pm to 5:50pm

Location: 

Zoom

Progress in artificial intelligence (AI), including machine learning (ML),
is having a large effect on many scientific fields at the moment, with much more to come.
Most of this effect is from machine learning or "numerical AI", 
but I'll argue that the mathematical portions of "symbolic AI" 
- logic and computer algebra - have a strong and novel roles to play
that are synergistic to ML. First, applications to complex biological systems
can be formalized in part through the use of dynamical graph grammars.
Graph grammars comprise rewrite rules that locally alter the structure of
a labelled graph. The operator product of two labelled graph
rewrite rules involves finding the general substitution 
of the output of one into the input of the next - a form of variable binding 
similar to unification in logical inference algorithms. The resulting models
blend aspects of symbolic, logical representation and numerical simulation.
Second, I have proposed an architecture of scientific modeling languages
for complex systems that requires conditionally valid translations of
one high level formal language into another, e.g. to access different
back-end simulation and analyses systems. The obvious toolkit to reach for
is modern interactive theorem verification (ITV) systems e.g. those
based on dependent type theory (historical origins include Russell and Whitehead).
ML is of course being combined with ITV, bidirectionally.
Much work remains to be done, by logical people.
 

This is part 1 of a 2 part talk. It will cover background on:
Sketch of background knowledge in typed formal languages, 
Curry-Howard-Lambek correspondence, 
current computerized theorem verification, ML/ITV connections;
scientific modeling languages based on rewrite rules
(including dynamical graph grammars),
with some biological examples.

Iteration, reflection, and singular cardinals

Speaker: 

Dima Sinapova

Institution: 

University of Illinois, Chicago

Time: 

Monday, March 29, 2021 - 4:00pm to 5:30pm

Location: 

Zoom

Two classical results of Magidor are: 

 

(1) from large cardinals it is consistent to have reflection at $\aleph_{\omega+1}$, and

(2) from large cardinals it is consistent to have the failure of SCH at $\aleph_\omega$.

 

These principles are at odds with each other. The former is a compactness type principle. (Compactness is the phenomenon where if a certain property holds for every smaller substructure of an object, then it holds for the entire object.) In contrast, failure of SCH is an instance of incompactness. The natural question is whether we can have both of these simultaneously. We show the answer is yes

 

We describe a Prikry style iteration, and use it to force stationary reflection in the presence of not SCH.  Then we obtain this situation at $\aleph_\omega$. This is joint work with Alejandro Poveda and Assaf Rinot.

Model theory of large fields

Speaker: 

Erik Walsberg

Institution: 

UC Irvine

Time: 

Monday, February 1, 2021 - 4:00am to 5:30am

Location: 

Ether

Model theory of fields is a very successful topic. I believe it is fair to say that most of this subject consists of detailed studies to particular fields (the reals, complex, p-adic, etc...). Largeness is a field-theoretic notion introduced by Pop in the nineties. This notion now plays a very important role in Galois theory and is increasingly being studied for other purposes. A number of people, including myself, have long believed that largeness should play an important role in the model theory of fields. This is mainly because all known model-theoretically tame fields are large, so one hopes that a general model-theoretic study of large fields might have a unifying effect on the model theory of fields. Over the past year we have begun to develop a model theory of large fields and in particular we have proven the stable fields conjecture for large fields. The key tool is a new topology on the K-points of a variety over a large field K.

This talk will involve a little algebraic geometry, but I will try to make it accessible to those with minimal background.

Pages

Subscribe to RSS - Logic Set Theory