LOGIC SEMINAR
FALL 2006
Friday, December 15, 2006
1:002:00 p.m.
Speaker: Ali Enayat, American University
http://academic2.american.edu/~enayat/
Place: Old
Main (1922 F Street), Room 104
Title: The Scott
set problem and related conundrums
Abstract: Scott
sets arise in various parts of logic, e.g., in
the model theory of nonstandard models of arithmetic and set theory, in
computability theory, and in reverse mathematics. A major unsolved
problem
regarding Scott sets asks whether every Scott set can be realized as
the
standard system of a nonstandard model of arithmetic. In this talk, I
will
discuss recent progress on this and related problems.
Thursday, December 7, 2006
4:005:00 p.m.
Speaker: Eric Ufferman, GWU
Place: Old
Main (1922 F Street), Room 104
Title: Applications of delta-0-2 permitting,
II
Abstract:
The computability theoretic technique of
delta-0-2 permitting has recently been used to obtain powerful new
results in
computable model theory.
Friday, November 17, 2006
2:303:30 p.m.
Speaker: Hosam M. Mahmoud,
Department of Statistics, GWU
http://home.gwu.edu/~hosam/
Place: 1957
E Street,
Room 111
Title: Phase changes in subtree
varieties in random trees
Abstract: The
occurrence of patterns in random objects is an important area of modern
research. The prime example is the
interest one may have in the number of occurrences of words of a
certain length
in that text. Applications abound in
linguistics where one wishes to analyze grammatical frequencies,
or in genetics where one tries to identify genes in strands of DNA. The equivalent and equally important view in
random trees is tofind patterns (which are
trees of a
certain size or a certain shape) in a given tree generated randomly. We
look at
the number of subtrees of a certain size
on the
fringe of random recursive trees, which have applications in
epidemiology,
philology, etc., and in random binary search trees, which have
applications in
computer science.
We consider the variety
of subtrees of various sizes and shape slying
on the fringe of a recursive tree. For
the number of subtrees of a given size k=k(n)
in a random recursive tree of size n, three cases are
identified: the subcritical, when k(n)/sqrt(n)
tends to zero, the critical, when k(n) is of the exact order sqrt(n), and the supercritical,
when k(n)/sqrt(n) tends to
infinity. We show by analytic methods
convergence in
distribution to 0 in the supercritical case and to normality (of a
normalized
version of the size) in the subcritical
case. We show that the size in the
critical case when
k/sqrt(n) approaches a limit
converges in
distribution to a Poisson random variable, and in the case k/sqrt(n) does
not
approach a finite nonzero limit, the size oscillates and does not
converge in
distribution to any random variable. This
provides an understanding of the complete spectrum of phases and the
gradual
change from the subcritical to the
supercritical
phase. We utilize the same battery of
methods to derive similar results for binary search trees. Connections
are made
to Riccati equations, Polya
urns and contraction in metric spaces of distributions and fixed-point
equations for distribution functions.
This work is based on
papers
joint with Chun Su, and Qunqiang Feng,
University of Science and
Technology of China, and Alois Panholzer,
Technical University, Vienna, Austria.
The lecture will be
accessible to
all math, statistics, and computer science graduate students.
Friday, November 3, 2006
2:303:30 p.m.
Speaker: Hosam M. Mahmoud,
Department of Statistics, GWU
http://home.gwu.edu/~hosam/
Place: 1957
E Street,
Room 111
Title: The Polya
process
and applications
Abstract: We
investigate the Polya process, which
underlies an urn
of white and blue balls growing in real time. A
partial differential equation governs the
evolution of the process. Some special
cases are amenable to exact and asymptotic solution: they include the
(forward
or backward) diagonal processes, and the Ehrenfest
process.
Applications of standard
(discrete) urns and their analogue when embedded in real time include
several
classes of random trees that have applications in computer science
(design and
analysis of algorithms), epidemiology and philology. We
shall present some of these applications.
The lecture will be
accessible to
all math and statistics graduate students.
Thursday, October 26, 2006
4:005:00 p.m.
Speaker: Valentina
Harizanov, GWU
Place: Old
Main (1922 F Street), Room 104
Title: Coding into nilpotent
groups
Abstract: We will
show how Malcevs coding of rings into
Heisenberg
3x3 matrices, which form a 2-step nilpotent group, can be used to
obtain
interesting new results in computable model theory.
Thursday, October 19, 2006
4:305:30 p.m.
Speaker: Eric Ufferman, GWU
Place: Old
Main (1922 F Street), Room 104
Title: Applications of
delta-0-2 permitting
Abstract: The
computability theoretic technique of delta-0-2 permitting has recently
been
used to obtain powerful new results in computable model theory. We will
present
some of these applications.
Thursday, October 12, 2006
4:005:00 p.m.
Speaker: Eric Ufferman, GWU
Place: 1957
E Street,
Room 308
Title: Permitting, Part II
Abstract: In this
talk I will focus on delta-0-2 permitting, a sophisticated technique
for
constructing a set computable in a given limit computable (i.e.,
delta-0-2)
set.
Friday, October 6, 2006
2:303:30 p.m.
Speaker: Eric Ufferman, GWU
Place: Old
Main (1922 F Street), Room 104
Title: Permitting
Abstract: Permitting
is a familiar technique for constructing sets computable in any given
computably enumerable Turing degree. In
this talk, I will give an example of how permitting works, and then
discuss
delta-0-2 permitting, an analogous, but much more complicated technique
for
constructing sets computable in an arbitrary delta-0-2 Turing degree.
Thursday, September 28, 2006
4:005:00 p.m.
Speaker: Jennifer
Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Old
Main (1922 F Street), Room 104
Title: Computable Vaughtian
model theory
Abstract:
I will present some
recent
results about the computable content of prime, saturated, and
homogeneous models
of decidable theories in the spirit of Vaught, combined with
computability
theoretic methods in the spirit of Turing.
Friday, September 22, 2006
2:303:30 p.m.
Speaker: Jennifer
Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Old
Main (1922 F Street), Room 104
Title: Continuous
model theory
Abstract:
I will present
a brief introduction to the recently developed logic of model theory
for metric
structures, which combines semantic constructs from analysis with the
syntax of
standard first order model theory, and thus serves as common ground for
analysts and model theorists. The notion
of definable sets and predicates is fundamental to standard first order
model
theory. Continuous model theory has at
its core a generalized notion of a predicate as a continuous bounded
map into
the real numbers, or even more generally, some topological space. In this model theory, the notion of equality
is replaced by a metric, and the structures are metric structures. This talk will be accessible to all math
graduate students.
Friday, September 15, 2006
2:303:30 p.m.
Speaker: Jennifer
Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: 1957
E Street,
Room 111
Title: Uncertain
reasoning
Abstract:
Mathematical reasoning
is done on categorical
(definitely true) statements, and our formal logic reflects this fact. However, everyday we are confronted with
information that may be uncertain, vague, or even contradictory. To what extent can we reason and draw
conclusions based on information like this?
Humans do just that all the time and make decisions based on
those
conclusions, but can we formalize this process?
In this talk I will give an introduction to predicate uncertain
reasoning. Everybody welcome, from all departments, including
undergraduates.