Previous seminars at: http://home.gwu.edu/~harizanv/index.html#GW_Logic_Seminar_
4:00–5:00 p.m.
Speaker: Nate
Ackerman,
http://www.math.upenn.edu/~nate/
Place: Monroe Hall (
Title: Vaught's Conjecture and Vaught Trees: Part II
Speaker: Nate
Ackerman,
http://www.math.upenn.edu/~nate/
Place: Monroe Hall (
Title: Vaught's Conjecture and Vaught Trees: Part I
Abstract: In 1961 Robert Vaught published a ground breaking
paper on countable model theory entitled Denumerable Models of Complete
Theories. In this paper he set out many
of the fundamental results concerning countable model theory. At the end of this paper he made a conjecture that every
countable first order theory in every model of set theory had
either countably or continuum many countable models.
This conjecture is what is now called Vaught’s Conjecture and is one of the oldest open problems in model theory.
One of the most significant steps towards
resolving this conjecture is a result of
Morley’s which says: For every countable first order
theory one of three possibilities occurs. (1) T has a perfect kernel of countable models. (2) T
has countably many models. (3) T has w1 many
models.
In this talk we will prove this by
showing that if T does not have a perfect kernel of countable models then we
can arrange these models in a hierarchy of complexity called the Vaught tree.
Further we will show that each level of the Vaught tree has either a perfect
kernel of models or is countable.
If we have time we will also show that
the statement T satisfies Vaught’s Conjecture is absolute between
models of set theory.
Speaker: Joseph S. Miller,
http://www.math.uconn.edu/~josephmiller/
Place: Monroe Hall (
Title: Extracting information is hard
Abstract: Can
randomness – or more technically, “information” – be effectively extracted from
a semi-random source? A special case of this question was answered by von
Neumann in 1951. He described a simple method for extracting an unbiased random
sequence from the flips of a biased coin. A more general form of the question
was asked by Reimann and Terwijn
in the context of algorithmic randomness, so we will start with an introduction
to Kolmogorov complexity, effective Hausdorff dimension, and Martin-Löf
randomness. Kolmogorov complexity measures the
information content of a finite binary string. Informally, the complexity of a
string is defined to be the length of the shortest program that generates it. A
closely related notion, effective (Hausdorff)
dimension, measures the information density of infinite binary sequences. We
can now formulate the question in terms of effective dimension: is there a
sequence that has effective Hausdorff dimension 1/2 –
in other words, a half-random sequence – that does not compute a sequence of
higher effective dimension? As it turns out, such sequences exist. We will
discuss this and related results.
Speaker: Andrei Morozov, Sobolev Institute of Mathematics and
http://www.math.nsc.ru/~asm256/
Place: Monroe Hall (
Title:
Countable structures Σ-definable over classical continuous number
fields
Abstract:
We give a complete characterization of countable
structures that are Σ-definable over classical number systems, such as
reals, complex numbers, and quaternions. Some of the work that will be
presented is with M. Korovina.
Speaker: Jennifer Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Monroe Hall (
Title: Computability
and Buttsworth's group, Part II
Speaker: Jennifer Chubb, GWU
http://home.gwu.edu/%7Ejchubb/
Place: Monroe Hall (
Title: Computability
and Buttsworth's group
Place: Monroe Hall (
Speaker: Russell Miller,
http://qcpages.qc.cuny.edu/~rmiller
Title: Locally
computable structures
Abstract:
Computable model theory has always restricted
itself to the study of countable structures. The natural numbers form the
standard domain and range for partial computable functions, due to the
finiteness of the programs and computations in the Turing model. In this talk
we continue to use this standard model of computation, but in such a way as to
allow consideration of uncountable structures. We no longer aspire to describe
a structure S globally. Instead, we content ourselves with a local description: a
list of the finitely-generated substructures of S, up to isomorphism. Initially
we require that these substructures should be computable, and that the list of
them be given effectively. If this can be done, then S is said to be locally
computable. (Such an S must have only countably many finitely-generated
substructures, up to isomorphism.) Then we consider more sophisticated
effective descriptions of S, by naming embeddings among the
substructures which reflect the inclusions in S. We will prove several
theorems about locally computable structures, but since the notion of local
computability is extremely new, much of this talk will be devoted to
definitions and examples.
OTHER LOGIC TALKS
Monroe
Hall (
Speaker: Karen Lange,
Title: The relative strength of the
Atomic and Homogeneous Model Theorems
Abstract: Reverse mathematics and
computable model theory both attempt to measure the strength of classical
mathematical principles, the former from a proof-theoretic perspective and the
latter from a computable one. I will present computability results on the
Homogeneous Model Theorem (HMT), an existence theorem for general model-theoretic
structures found throughout mathematics. I will discuss how these results
provide insight into the reverse mathematical strength of HMT. In
particular, I will discuss how HMT compares with the Atomic Model Theorem
studied by Hirschfeldt, Shore, and Slaman.
Monroe
Hall (
Speaker: Sara Quinn,
Title: A tour of computable
structure theory
Abstract: Computable structure theory is a branch of mathematical
logic in which the algorithmic complexity of algebraic structures is
examined. In other words, we determine how complicated it is to answer
certain questions about algebraic structures, such as: “Are these two
structures isomorphic?” There is a hierarchy we use to rank the
complexity of these questions. In this talk I will give all of the
necessary definitions, and then describe the kinds of questions that we ask in
computable structure theory.