Computability learning seminar

Wednesday, August 1, 2012 3:40 pm - 3:40 pm EDT (GMT -04:00)

Matthew Harrison-Trainor, Pure Mathematics, University Of Waterloo

"Pairs of computable structures"

We will begin by finishing the proof of the meta-theorem on n-systems, and then we will look at an application of back-and-forth relations and n-systems.
Let A and B be two structures over the same language. We consider the question of which sets S can be coded by those structures as follows: there is a uniformly computable sequence of structures (Cn)n∈ω such that Cn is isomorphic to A if n ∈ S and to B otherwise. We will give some examples, and then show that Πn sets can be coded by structures which are n-friendly and satisfy the nth back-and-forth relation.