Carrie Knoll, Pure Math Department, University of Waterloo
"Complexity of classes of structures"
The
main
theme
of
this
thesis
is
classifying
classes
of
structures
relative
to
various
measurements.
We
will
briefly
discuss
the
notion
of
computable
dimension,
while
the
breadth
of
the
paper
will
focus
on
calculating
the
Turing
ordinal
and
the
back-and-forth
ordinal
of
various
theories,
along
with
an
exploration
of
how
these
two
ordinals
are
related
in
general.
Computable
structure
theorists
study
which
computable
dimensions
can
be
realized
by
structures
from
a
given
class.
Using
a
structural
characterization
of
the
computably
categorical
equivalence
structures
due
to
Calvert,
Cenzer,
Harizanov
and
Morozov,
we
prove
that
the
only
possible
computable
dimension
of
an
equivalence
structure
is
1
or
!.
In
1994,
Jockusch
and
Soare
introduced
the
notion
of
the
Turing
ordinal
of
a
class.
It
was
unknown
whether
every
computable
ordinal
was
the
Turing
ordinal
of
some
class.
Following
the
work
of
Ash,
Jocksuch
and
Knight,
we
show
that
the
answer
is
yes,
but,
as
one
might
expect,
the
axiomatizations
of
these
classes
are
complex.
In
2009,
Montalban
defined
the
back-and-forth
ordinal
of
a
class
using
the
back-and-forth
relations.
Montalban,
following
a
result
of
Knight,
showed
that
if
the
back-and-forth
ordinal
is
n
+
1,
then
the
Turing
ordinal
is
at
least
n.
We
extend
this
result
to
infinite
ordinals,
and
show
that
if
the
back-and-forth
ordinal
is
(infinite)
then
the
Turing
ordinal
is
at
least
.
It
is
conjectured
at
present
that,
if
a
class
of
structures
is
finitely
axiomatizable,
then
the
Turing
ordinal
and
the
back-and-forth
ordinal
of
the
class
dier
by
at
most
1.
We
will
present
many
examples
that
support
this
conjecture,
along
with
many
Borel
classes
with
the
same
property;
however,
we
will
show
that
this
result
does
not
hold
for
arbitrary
Borel
classes.
More
precisely,
for
each
positive
integer
d,
we
will
define
a
Borel
class
of
structures
such
that
the
Turing
ordinal
and
the
back-and-forth
ordinal
of
the
class
differ
by
at
least
d.