5:00–6:00 p.m.

Speaker: Hunter Monroe,
International Monetary Fund

Place: Monroe Hall (

Title:** ***Speedup for Natural Problems*

Abstract:** **Informally, a language *L* has speedup if, for any Turing machine for *L*, there exists one that is better. Blum showed that there are
computable languages that have almost-everywhere speedup. These languages were
unnatural in that they were constructed for the sole purpose of having such
speedup. We identify an intuitive condition which, like several others in the
literature, implies that accepting any *coNP*-complete
language has an infinitely-often (i.o.) superpolynomial speedup. We also
exhibit a natural problem which unconditionally has a weaker type of i.o.
speedup based upon whether the full input is read. Neither speedup pertains to
the worst case.

3:30–5:00 p.m.

(jointly with the Philosophy
Department; Contact: Michele Friend michele@gwu.edu)

Speaker: Andrea Pedeferri, *Università degli Studi**
*di *Milano,
Italy*

Place: Phillips Hall (^{nd} Street

Title:** ***Why Do We Call Second Order Logic *“*Logic*”

Abstract:** **Second order logic has been always considered
as problematic by modern logicians: the lack of completeness and the subsequent
lack of a sound deductive system seem to rule out second order from the realm
of “pure” logic. However, second order logic provides, with its expressive
power, the possibility to give categorical characterizations of infinite
structures. Accordingly, on the one hand we do not call second order a proper
logic due to its being “uncontrollable”. On the other hand, we consider the
Löwenheim-Skolem Theorem as a corner stone of the “controllable” first order,
although it states the incapability of a theory to “control” its models.

I think limitative theorems of first order are only *desiderata*. It has been shown in many
ways how to deal with second order. I think it is time to move on to a more
general level. In the light of these results on second order logic it is
possible to start a discussion on which notions and rules are needed to make
formalized languages “really” logic. Of course we need a sound deductive
system; is it possible to find a way to control deduction in a second order
framework to make it sound “enough”?

5:00–6:00 p.m.

Speaker: Russell Miller, CYNY,

http://qcpages.qc.cuny.edu/~rmiller/

Place: Monroe Hall (

Title:** ***BSS
Machines: Computability Without Search Procedures*

5:00–6:00 p.m.

Speaker: Valentina Harizanov, GWU

Place: Monroe Hall (

Title:** ***Computable Categoricity of Equivalence Structures*

Abstract:** **We
investigate algorithmic properties of computable equivalence structures, their
equivalence classes, and their characters. A computable structure *A* is computably categorical if for every
computable isomorphic copy *B* of *A*, there is a computable isomorphism
from *A* onto *B*. We establish that a computable equivalence structure *A* is computably categorical if and only
if *A* has only finitely many finite
equivalence classes, or *A* has only
finitely many infinite classes, bounded character, and at most one finite *k* such that there are infinitely many
classes of size *k*. We show that all computably
categorical equivalence structures are relatively computably categorical. This
is joint work with W. Calvert, D. Cenzer, and A. Morozov.

Previous seminars at: http://home.gwu.edu/~harizanv/index.html#GW_Logic_Seminar_

5:15–6:15
p.m.

Speaker:
Kai Maeda

Place:
Monroe Hall (

Title:** ***Ordered Groups, Conradian Groups, and
Spaces of Orders*

Speaker: Nate Ackerman,

http://www.math.upenn.edu/~nate/

Place: Monroe Hall (

Title:** ***Trees, Sheaves and Definition by Recursion*

Abstract:** **We
will show there is a topological space for which presheaves are the same thing
as trees. We will further show that there is a sheaf on this topological space
which has an important relationship with Baire space.

We will then use these connections to show how a
definition by transfinite recursion can be thought of as an operation on
sheaves, and how the well-definedness of such a definition can be through of as
a property of the sheaf we are working on.

This will then allow us to define a second order tree
as a sheaf on a tree and to expand our notion of definition by recursion to all
well-founded second order trees (even those which are ill-founded as normal
trees). We will then mention how these techniques can be used to prove a variant
of the Suslin-Kleene Separation theorem.

Speaker: Ali Enayat,

http://academic2.american.edu/~enayat/

Place: Monroe Hall (

Speaker: Ali Enayat,

http://academic2.american.edu/~enayat/

Place: Monroe Hall (

Abstract:** **`For the purposes of this
talk, a “finite set theory” is any axiomatic system of set theory that includes
the axiom “every set is finite.” For
example, the theory ZF_fin obtained from Zermelo-Fraenkel set theory by
replacing the axiom of infinity with its negation is a finite set theory. In this talk we shall give an overview of old
and new results about finite set theory, including Ackermann’s classical
interpretation of ZF_fin in Peano Arithmetic, and recent joint work with
Jim Schmerl and Albert Visser on the metamathematics of finite set theory. In particular, I plan to explain why, contrary
to a widely held misconception, Peano arithmetic and ZF_fin are not
bi-interpretable.`

Speaker: Joe Mourad,

Place: Monroe Hall (

Title: *Some descriptive set theory for recursion theorists** *

*Part
IV: How to build a real*

Speaker: Joe Mourad,

Place: Monroe Hall (

Title: *Some descriptive set theory for recursion theorists** *

*Part
III**: **Calculating
the size of the fixed point*

Speaker: Joe Mourad,

Place: Monroe Hall (

Title: *Some descriptive set theory for recursion theorists** *

*Part
II**: **The
passage to ultra effective descriptive set theory*

Speaker: Joe Mourad,

Place: Monroe Hall (

Title: *Some descriptive set theory for recursion theorists** *

*Part
I: The passage to ultra effective
descriptive set theory*

Along the way we will look at
some classical results such as Suslin’s characterization of Borel sets as analytic
sets with analytic complements and ideas such as are found in Shoenfield’s
Absoluteness Theorem. The emphasis will be on getting a feel for what are the
most critical ideas in such results.

Speaker: Russell
Miller, CYNY,

http://qcpages.qc.cuny.edu/~rmiller/

Place: Monroe Hall (

Title: *Degrees of categoricity of algebraic fields*

Abstract: Let
F be a computable field: a countable
field in which the addition and multiplication are given by computable
functions. We investigate the Turing
degrees d such that F is **d**-computably categorical, meaning that d is
able to compute isomorphisms between F and any other computable field
isomorphic to F. We prove that algebraic
fields can fail to be **0**'-computably categorical, but that there is a
degree **d**, low relative to **0**', such that every algebraic field is **d**-computably
categorical. We also prove analogous
results, one jump lower, for computable fields with splitting algorithms.

Speaker: Joe Mourad,

Place: Monroe Hall (

Title: *Some descriptive set theory for recursion theorists:
Introduction*

Abstract:
In this first talk of what will probably be a
series of talks I will mostly motivate an approach to descriptive set theory
that focuses on understanding Sigma^1_2 sentences from a constructive point of
view. This talk will be followed up by introducing some joint work that I have
done with Mark Lance of the Georgetown University Philosophy Department.

We will also review some classical results along the way as well as make
connections to classical recursion theory and proof theory. As far as possible,
the material will be presented so as to be understandable to beginning graduate
students and advanced undergraduates.

Speaker: Jennifer Chubb, GWU

http://home.gwu.edu/%7Ejchubb/

Place: Monroe Hall (

Title: *Algorithmic properties
of relations on computable structures*

Abstract: We consider algorithmic
properties of additional relations definable on computable structures. For example, for a computable linear ordering
we may consider the successor relation, which does not have to be computable. I will discuss some general results in the
literature, and present some examples from my recent collaborative projects. We will see that for a large class of linear
orderings, the Turing degree spectrum of the successor relation is closed
upward in the computably enumerable degrees. Then, we will use algorithmic information
theory to analyze the strong degree spectra of certain initial segments of computable
linear orderings and compare them to the Turing degree spectra of these
segments.