The Logic and Computation Group is composed of faculty and graduate students from the Computer and Information Science, Mathematics, and Philosophy departments, and participates in the Institute for Research in the Cognitive Sciences. The Logic and Computation group runs a weekly seminar. The seminar is open to the public and all are welcome.
The seminar meets regularly during the school year on Mondays at 3:30 p.m. in room DRL 4C8 on the fourth (top) floor of the David Rittenhouse Laboratory (DRL), on the Southeast corner of 33-rd and Walnut Streets at the University of Pennsylvania. Directions may be found here. Any changes to this venue or schedule will be specifically noted.
A classical (complete) type over a set X consists of a set of formulas, potentially involving parameters from X, that can be thought of as a comprehensive description of a possible element of a model containing X. In more general contexts, where dependence on logic and formulas is to be avoided, Galois types offer an elegant alternative: the type of an element a over a model M is identified as the orbit of a under automorphisms of a very large universal model C that fix M pointwise. In recent work, I have tried to transpose Galois types and some of the associated theory and results, to model-like categories which are, nonetheless, not concrete. In particular, I have had success in the context of accessible categories with directed colimits.
It is well-known that the fundamental group of a finite, connected graph is a finitely generated free group, where one can take the chords of a spanning tree as a set of free generators. Diestel and Sprussel tried to give a similar combinatorial characterization of the end compactification of an infinite, locally finite, connected graph. They showed that the fundamental group embeds into a group of reduced words, where the words can have arbitrary countable order type and the notion of reduction is non-wellordered. Furthermore, they show that this group of reduced words embeds into an inverse limit of finitely generated free groups. In this talk, I will present a much simpler approach to this problem by showing how the fundamental group of the end compactification of a locally finite, connected graph embeds into the internal fundamental group of a hyperfinite (in the sense of nonstandard analysis) graph, which is then a hyperfinitely generated free group. I will discuss some applications of this result, including a simple proof that certain loops in the end compactification are non-nullhomologous.
This is joint work with Alessandro Sisto.