Logic Seminar

Given a structure, one can form a tree whose nodes are tuples from the structure, ordered by extension, and with each tuple labeled by its atomic type. This structure encodes the back-and-forth information of the structure and hence, by a back-and-forth argument, its isomorphism type. The tree of tuples appeared implicitly in the seminal Friedman-Stanley paper on Borel reducibility. With Montalban I showed that there are structures which cannot be recovered computably from their tree of tuples. I will talk about why we care about the tree of tuples, and about this result and what it has to say about coding and Borel reducibility.
Speaker(s): Matthew Harrison-Trainor (UM)