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 (
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.