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.