Notions of Finiteness for Nominal Sets

Speaker(s)

Andrew Pitts

Affiliation

University of Cambridge

Date

Oct. 11, 2012, 2:30 p.m.

Room

room 5820

Seminar

Seminar Automata Theory

---

In the generalised version of nominal sets developed by the group in
Warsaw, the property of a structure having only finitely many orbits
plays a central role. I will discuss the relationship between
"orbit-finiteness" and other notions of finiteness that have been used
in connection with nominal sets---particularly order-theoretic ones.
This leads to a "full abstraction" result (joint work with Steffen
Loesch) for a symmetric version of the Ershov-Scott-Plotkin
extensional theory of computable functions of higher type, which I
will sketch. All this is with respect to the "equality symmetry"---the
version of nominal sets that I know best. The extent to which these
results extend to other data symmetries is open.

---