Logic Seminar
Matthew Harrison-Trainor
UIC
The back-and-forth tree of a structure
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.
Tuesday August 29, 2023 at 4:00 PM in 636 SEO