Matthew Harrison-Trainor : The back-and-forth tree of a structure

Posted by Matthew Harrison-Trainor , part of the Logic Seminar.

At

Aug. 29, 2023, 4 p.m.

In

636 SEO

Abstract

Given a structure $\mathcal{A}$, we can form the back-and-forth tree $T(\mathcal{A})$. The nodes of this tree are the finite tuples from $\mathcal{A}$, ordered by extension. Each node is labeled by its atomic type. The standard back-and-forth argument shows that the tree of tuples is a complete isomorphism invariant, and captures the full theory of the structure in infinitary logic. The tree of tuples was also used to show the Borel-completeness of the class of linear orders. However one cannot compute back a copy of the original structure from the tree. We will talk about this result as well as its consequences.