Past talks in the Mathematical Logic Seminar
Organizer: Rami Grossberg (Rami@cmu.edu)
M 4:30 - 6:00 PM
Wean 8427
April 26, 2002 (4:30PM at WeH 7500) SPEAKER: Andres Villaveces, Mathematics,
National University of Colombia at Bogota TITLE: What kind of interaction can you expect between Model Theory and
the rest of Mathematics? ABSTRACT: Model theory in the last years has started to provide results
in branchs of mathematics such as algebra, Banach Space theory and Compact
Manifolds.
In this talk, I will show why the interaction between Model Theory and
other parts of mathematics is very natural, and mention several examples
of these interactions. I plan to concentrate on the role of homogeneous
and universal mathematical structures.
April 22, 2002 SPEAKER: Mirna Dzamonja, Mathematics,
University of East Anglia TITLE: Axioms for universality ABSTRACT: In the first talk we discuss an axiom that
is a sufficent condition for an abstract elementary class
to consistently have $\lambda^{++}$ universal elements of size
$\lambda^+$ for a cardinal $\lambda$ that has the value of
$2^\lambda$ very large and satisfies $\lambda=\lambda^{<\lambda}$.
In the second talk we show how these axioms can be applied to a
class of Boolean algebras and a class of topological spaces
coming from functional analysis.
April 15, 2002 SPEAKER: No seminar.
April 8, 2002 SPEAKER: Kerry Ojakian, Mathematics,
CMU TITLE: A few tidbits about Bounded Arithmetic ABSTRACT: Bounded Arithmetic is a weak theory contained in Peano Arithmetic. I will
present some background material, and then talk about some stuff you can
and cannot prove in this theory and its subtheories. I'll probably talk
about some things I've worked on, like a Ramsey principle, and the
Tournament Principle. The first can be proved in Bounded Arithmetic, the
second, well ...
This talk should be accessible to "anyone," at least at an intuitive
level (that's my goal, no promises).
March 25, 2002 SPEAKER: Classifying simple unstable theories: Generalized
amalgamation properties, Part III
March 18, 2002 SPEAKER: Classifying simple unstable theories: Generalized
amalgamation properties, Part II
March 11, 2002 SPEAKER: Alexei Kolesnikov, Mathematics,
CMU TITLE: Classifying simple unstable theories: Generalized
amalgamation properties, Part I ABSTRACT:In a recent list of open problems in model theory, Shelah conjectured
the existence of a hierarchy of $\omega+1$ many subclasses of the class
of simple theories.
I will present my solution to Shelah's conjecture in this series of
talks.
I will introduce a family of properties that divide the class of all
simple theories into the following subclasses: $n$-simple theories for
$1\ge n <\omega$ and $\omega$-simple
theories. I then prove a characteristic property of $n$-simple theories.
The first lecture will be devoted almost entirely to the examples of
theories in each subclass. Only basic model theory will be used at this
stage.
March 4, 2002 No seminar.
February 25, 2002 SPEAKER: Grant Reaber, Mathematics, CMU TITLE: Large cardinals under AD, Part II
February 18, 2002 SPEAKER: Grant Reaber, Mathematics, CMU TITLE: Large cardinals under AD, Part I ABSTRACT:I will present some old consequences of the
Axiom of Determinacy. In the first part I will prove Solovay's
theorem that AD implies aleph_1 and aleph_2 are measurable
cardinals. In the second part I will prove a powerful result
known as Moschovakis's Coding Lemma, a consequence of which is
that the supremum of the ordinals onto which the set of real
numbers can be mapped is a relatively large cardinal.
February 11, 2002 SPEAKER: Steve Awodey, Philosophy, CMU TITLE: The groupoid model of intensional type theory, Part III
February 4, 2002 SPEAKER: Steve Awodey, Philosophy, CMU TITLE: The groupoid model of intensional type theory, Part II
January 28, 2002 SPEAKER: Steve Awodey, Philosophy, CMU TITLE: The groupoid model of intensional type theory, Part I ABSTRACT: Extensional equality in dependent type theory is easily modelled in locally
cartesian closed categories (LCCCs) ; in sheaves, for example, it's just
the usual "diagonal" embedding d : F --> F x F . The *intensional
identity* types (of Martin-Loef) are more subtle, however. Indeed, some
very basic questions about these remained open until the groupoid semantics
were developed a few years ago by Martin Hoffmann and Thomas Streicher.
In these talks, I'll review the intentional type theory and show why it
*cannot* be modelled in the usual way in an LCCC. I'll then give an
axiomatic description of the desired semantics, and show that the groupoid
model satisfies it. Along the way, I'll introduce the essential concept of
a *fibration,* and discuss some of the properties and applications of
these. Finally, I'll show how the Hoffmann-Streicher groupoid model can be
generalized to give "complete semantics" for intensional type theory.
These talks presume familiarity with only the most basic notions from type
theory and category theory.
October 15, 2001 SPEAKER: Ernest Schimmerling, CMU TITLE: Title: Some new large cardinals and what they are good for. ABSTRACT: During the last three years, several new large cardinal
properties have been isolated and found to be relevant to core model
theory. One that I have in mind falls between Woodin and Shelah, another
between Shelah and superstrong, and two more between superstrong and
supercompact. I'll give the definitions and explain how they came up.
October 8, 2001 SPEAKER: James Cummings, CMU TITLE: $\Omega$-logic ABSTRACT: A survey (without many proofs) of Woodin's recent work on
large cardinals, forcing and the Continuum Hypothesis.
October 1, 2001 No seminar today.
September 24, 2001 SPEAKER:Ulrich Kohlenbach,
University of Aarhus.
TITLE: Proof mining: a proof theoretic approach to numerical
analysis ABSTRACT: With the term `proof mining' we denote the activity
of transforming a prima facie non-constructive proof
into a new one from which certain computational information can be
read off which was not visible beforehand.
Already in the 50's Georg Kreisel realized that logical techniques
from proof theory -- originally developed for foundational
purposes -- can be put to use here. In recent years, a more
systematic proof theoretic approach to proof mining in numerical
analysis emerged yielding new quantitative (and even qualitative)
numerical results in approximation theory and fixed point theory
and providing a bridge between mathematical numerical analysis
and the area of computability (and complexity) in analysis which
has mainly been developed by logicians (and complexity theorists).
Although proof mining has been applied also to e.g. number theory and
combinatorics, the area of numerical (functional) analysis is of
particular interest since here non-effectivity is at the core of
many principles (like compactness arguments) which are used to ensure
convergence. In mathematical terms this non-computability often is
an obstacle to obtain a quantitative stability analysis and rates of
convergence.
We will give a survey and discuss two recent applications concerning:
- new uniform bounds for theorems of Ishikawa and Borwein-Reich-Shafrir
on the asymptotic regularity of non-expansive mappings yielding even
new qualitative results,
- fully explicit description of the rate of strong unicity for best
L_1-approximations of continuous functions by polynomials (joint work
with Paulo Oliva).
September 17, 2001 SPEAKER: James Cummings, CMU TITLE: "proofs of determinacy" ABSTRACT: A survey of the various known techniques for
proving infinite games are determined.
September 10, 2001 SPEAKER: James Cummings, CMU TITLE: Transversals (again) ABSTRACT:
This talk is a sequel of sorts to my two talks on
transversals from February. I will review (without proofs)
the material I covered in those talks, and then prove some
theorems of Shelah and Magidor about compactness properties
for transversals at successors of singular cardinals.
[A {\em transversal} of a set is a 1-1 choice function for that
set]
April 23, 2001 SPEAKER: Alexei Kolesnikov TITLE: Simple homogeneous models, Part 2
April 16, 2001 No seminar.
April 9, 2001 SPEAKER: Alexei Kolesnikov TITLE: Simple homogeneous models, Part 2
April 2, 2001 SPEAKER: Alexei Kolesnikov, CMU TITLE: Simple homogeneous models, Part 1 ABSTRACT:
One of the central notions in model theory is that of dependence. For simple
first order theories, the relation of forking has the properties one
would expect a dependence relation to have; moreover, it has been
proved that if a first order theory has a ``nice" dependence relation,
then it has to be simple and the dependence has to be forking.
Recently, Buechler and Lessmann defined and studied the forking relation in a
more general context of (non-first order) homogeneous structures. It is
believed that their proofs are ``optimal" not only for the homogeneous case,
but also for the first order theories.
I will attempt to make the talks as self-contained as possible.
March 26, 2001 Spring break, no seminar.
March 19, 2001 SPEAKER: Lubos Thoma, CMU TITLE: Amalgamation and Finite Models, Part 2
April 26, 2001 No seminar.
March 5, 2001 SPEAKER: Lubos Thoma, CMU TITLE: Amalgamation and Finite Models, Part 1 ABSTRACT:
Under which assumptions does a theory T have finite
models? The famous Cherlin-Harrington-Lachlan
theorem answers this question in the case of
\aleph_0-categorical \aleph_0-stable theories.
Let L^n (n<\omega) stand for a sublogic of the FO
logic in which each formula contains at most n distinct
variables. We will discuss a recent work by Baldwin
and Lessmann on the existence of finite models of
L^n-theories under several distinct amalgamation properties.
February 26, 2001 SPEAKER: Joel David Hamkins, CUNY/CMU TITLE: An elementary presentation of the Laver Preparation ABSTRACT:
Laver proved that any supercompact cardinal can be made
indestructible by a large class of forcing notions. In this talk I will give
an elementary account of this interesting result. A related version of it,
the Lottery Preparation, applies to many other large cardinals.
February 19, 2001 Due to the meeting in Rutgers there will be no
seminar.
February 12, 2001 SPEAKER: Jame Cummings, CMU TITLE: Transversals. Part 2
February 5, 2001 SPEAKER: Jame Cummings, CMU TITLE: Transversals. Part 1 ABSTRACT: A {\em transversal} of a set $X$ is a function
with domain $X$ such that $f$ is 1-1 and $f(x) \in X$ for
every $x \in X$. There are many easily stated problems
about transversals which require deep set-theoretic ideas
for their solution. I will discuss some of these problems.
The talks should be accessible to anyone who has taken
a beginning graduate course in set theory.
January 29, 2001 SPEAKER: Rami Grossberg, CMU TITLE: The continuum hypothesis is true for
automorphism groups. ABSTRACT: Let M be a countable structure and
denote by AUT(M) its group of automorphisms.
I will present a proof for David Kueker's theorem:
THEOREM. If AUT(M) is uncountable then the cardinality
of AUT(M) is the cardinality of the real numbers.
The proof will be presented in a self contained form, without any
prerequisits. Implicit in the proof is one of the most
basic ideas of infinitary logic that generalizes the
Cantor-Haussdorf back and forth construction.
December 11, 2000 SPEAKER: Rami Grossberg, CMU TITLE: The finite cover property and categoricity, Part 2
December 4, 2000 SPEAKER: Rami Grossberg, CMU TITLE: The finite cover property and categoricity, Part 1 ABSTRACT: I will discuss the finite cover property (fcp).
The fcp was introduced by Keisler in 1967 in his analysis
of when a first-order theory has a saturated
ultrapower. The negation of the fcp is the
statement that a strong finite version of the compactness theorem holds.
I will present some results of Baldwin, Shelah and myself that
connect the fcp with issues related to categoricity of
pseudo elementary classes (aka projective classes).
This is a step toward Shelah's program for developing a classification
theory
for PC-classes
This talk does not assume familiarity with the fcp or with PC-classes.
November 20, 2000 SPEAKER: Monica VanDieren, CMU TITLE: Categoricity and Stability in Abstract Elementary Classes,
Part 2
November 13, 2000 SPEAKER: Monica VanDieren, CMU TITLE: Categoricity and Stability in Abstract Elementary Classes, Part 1 ABSTRACT: One of the most influential conjectures in model theory was
Los' Conjecture, which generalizes Steinitz's Theorem about algebraically
closed fields.
Shelah in the mid-seventies conjectured that a categoricity theorem,
similar to Los' conjecture, should hold for the infinitiary logic,
$L_{\omega_1,\omega}$, and more generally for abstract
elementary classes (AEC). Moreover
he foresaw that work in this direction would lead to a stability theory
for non-first-order logics.
I will present the work of Shelah-Villaveces
towards a categoricity theorem in AEC under the assumption of no
maximal models and relate it to another paper by Shelah (Sh600).
I will present the proof
that under some mild set-theoretic assumptions, categoricity implies
density of amalgamation bases, which is
necessary to develop a theory of types.
In all the proofs of Los' Conjecture for first-order theories, saturated
models played a pivotal role. I will present some ideas from
Shelah-Villaveces that may lead to a good substitution for saturated
models in the AEC case.
Finally, I will present Shelah-Villaveces' result that categorcity implies
that there does not exist an $\omega$-chain of splitting
types. In first order logic, this is a consequence of superstability.
Proving this theorem under a superstability assumption would be a good
test question for an AEC stability theory.
This talk does not assume familiarity with Shelah's stability theory
and AEC.
November 6, 2000 SPEAKER: James Cummings, CMU TITLE: Woodin's $\Sigma^2_1$ absoluteness theorem ABSTRACT: Shoenfield's absoluteness theorem says that $\Sigma^1_2$
statements are absolute between inner models of ZFC. It is natural to
ask about statements that allow quantification over sets of reals.
Woodin proved that $\Sigma^2_1$ statements are absolute for set
forcing between models of "ZFC + CH + there are many large cardinals"
(A $\Sigma^2_1$ statement is one which allows one existential
quantification over sets of reals --- CH is a $\Sigma^2_1$ statement).
October 31, 2000 SPEAKER: Ernest Schimmerling, CMU TITLE: Core models ABSTRACT: Steel's monograph "The core model iterability problem" is the
foundation of the theory of K below one Woodin cardinal. Among the
theorems he proves is that if NS is saturated and there is a measurable
cardinal, then there is an inner model with a Woodin cardinal. This is a
partial converse to Shelah's theorem that if there is a Woodin cardinal,
then NS is saturated in a generic extension. I'll try to say something
meaningful about Steel's proof and core models in general.
October 16, 2000 SPEAKER: Rick Statman, CMU TITLE: The word problem for combinators, Part 3
October 9, 2000 SPEAKER: Rick Statman, CMU TITLE: The word problem for combinators, Part 2
October 2, 2000 SPEAKER: Rick Statman, CMU TITLE: The word problem for combinators, Part 1 ABSTRACT: In 1936 Alonzo Church observed that the "word problem" for
combinators is undecidable. He used his student Kleene's representation
of partial recursive functions as lambda terms. This illustrates very
well the point that "word problems" are good problems in the sense
that a soultion either way - decidable or undecidable - can give useful
information. In particular, this undecidability proof shows us how to
program arbitrary partial recursive functions as combinators.
I never thought that this result was the end of the story for
combinators. In particular, it leaves open the possibility that the
unsolvable problem can be approximated by solvable ones. It also
says nothing about word problems for interesting fragments i.e.
sets of combinators not combinatorially complete.
Perhaps the most famous subproblem is the problem for S terms.
Recently Waldmann has made significant progress on this problerm . Prior
we solved the word problem for the Lark, a relative of S. Similar solutions
can be given for the Owl (S*) and Turing's bird U . Familiar
decidable fragments include Girard's linear combinators and
various sorts of typed combinators. We shall survey known results and
interesting open problems.
September 25, 2000 SPEAKER: James Cummings, CMU TITLE: Reconstructing structures ABSTRACT: If M is an "internally approachable" structure
then $M \cap \aleph_\omega$ is determined by the function
whch maps $n$ to $\sup(M \cap \aleph_n)$ for $n < \omega$.
This fact (due to Shelah) has many interesting consequences,
for example in cardinal arithetic and in the study of
covering properties. I will discuss some of these
consequences.
September 11, 2000 SPEAKER: Joel Hamkins, CUNY and CMU TITLE: A simple maximality principle ABSTRACT: The Maximality Principle I propose, following an idea of
Christophe Chalons, asserts that any sentence that holds in some forcing
extension V^P and all subsequent extensions V^P*Q, holds already in V and
all forcing extensions of V. The principle is naturally expressed in the
modal logic context in which a sentence phi is possible when it holds in a
forcing extension and necessary when it holds in all forcing extensions.
Specifically, in this terminology the Maximality Principle asserts that
every possibly necessary sentence is necessary. That is, it is the scheme
(diamond box phi) implies (box phi). In this talk, I will prove the relative
consistency of the Maximality Principle and consider stronger forms of it.
One of these stronger forms, the Necessary Maximality Principle, has a
surprising degree of large cardinal strength.
The talk will be accessible to graduate students in logic.
May 1, 2000 SPEAKER: Lenore Blum, SCS CMU TITLE: Complexity and Real Computation ABSTRACT: I plan to give a series of lectures next
fall (in the logic seminar)
that will expand on aspects of my math colloquium talk this spring.
This seminar will be a warm-up. I will leisurely present the model,
basics of complexity theory and some transfer results.
April 24, 2000 SPEAKER: Rami Grossberg, CMU TITLE: What is abstract model theory? ABSTRACT: In 1969 Per Lindstrom published a theorem known as Lindstorm's first theorem: Let L be a logic containing first-order logic.
If the logic satisfies both the Lowenhiem-Skolem theorem and the compactness
theorem (for countable theories) then L is equivalent to first-order predicate
calculus.
In 1970 Harvey Friedman rediscovered Linsdstrom's result
and widely circulated two manuscripts presenting a proof
(which incidentally was identical to Lindstrom's).
This massive mailing of Friedman's manuscript attracted so
much attention to the result that a new branch of model theory was
born (Abstract model theory) where the objects of study are not models or
theories but model-theoretic properties of logics.
In this lecture I will present Lindstorm's result and will discuss
some deeper results e.g. the Makowsky-Shelah theorem.
April 17, 2000 SPEAKER: James Cummings, CMU TITLE: forcing axioms, reflection principles and all that, Part 3
April 10, 2000 SPEAKER: James Cummings, CMU TITLE: forcing axioms, reflection principles and all that, Part 2
April 3, 2000 SPEAKER: James Cummings, CMU TITLE: forcing axioms, reflection principles and all that, Part 1 ABSTRACT: Some important classes of forcing posets are the proper,
semi-proper and stationary-preserving posets. With each of these
classes of posets there is associated a natural forcing axiom,
giving us the axioms PFA, SPFA and MM.
I will give Shelah's proof that the axiom SPFA is equivalent to
the formally stronger axiom MM, and discuss some of the associated
combinatorics. I'll also discuss examples of forcing posets which
are stationary-preserving but not semi-proper.
March 27, 1999, spring break
March 20, 2000 SPEAKER: Alexei S. Kolesnikov, CMU TITLE: Simple theories, ACFA, and Generic Structures, part 4
March 13, 2000 SPEAKER: Alexei S. Kolesnikov, CMU TITLE: Simple theories, ACFA, and Generic Structures, part 3 ABSTRACT: For the remainder of the series, we will focus on
the generic structures
and in particular on Algebraically Closed Field with an Automorphism
(ACFA).
The first order theory of ACFA is a natural algebraic example of a simple
unstable theory. Whenever possible, the proofs of model-theoretic
properties will be presented in a more general context of generic
structures. The speaker will make an attempt not to sacrifice the
algebraic meaning of the results for the sake of generality.
March 6, 1999, mid semester break
February 28, 2000 SPEAKER: Alexei S. Kolesnikov, CMU TITLE: Simple theories, ACFA, and Generic Structures, part 2
February 21, 2000 SPEAKER: Alexei S. Kolesnikov, CMU TITLE: Simple theories, ACFA, and Generic Structures, part 1 ABSTRACT: ACFA stands for Algebraically Closed Field with an Automorphism, where the
automorphism must satisfy certain properties. It turns out that this
class of structures has a first order axiomatization, and the resulting
first order theory is simple and unstable.
On the other hand, ACFA is an example of a "generic structure." There are
several ways to say what a generic structure is; one of them uses the
model-theoretic forcing, a notion that somewhat resembles its
set-theoretic counterpart.
In their recent work, Zoe Chatzidakis and Anand Pillay discovered that one
can obtain simple theories by adding a generic predicate or automorphism
to stable theories. The resulting structures resemble either ACFA (when we
add an automorphism), or a random graph over a stable structure (the
underlying set comes from the stable structure, and the generic predicate
gives the coloring).
I plan to cover at least the following topics:
Independence Theorem for simple theories;
Basic facts about ACFA, and why it is simple and unstable;
Generic models, model-theoretic forcing;
Creating simple theories by adding a generic predicate or an
automorphism to a stable theory.
February 14, 2000 SPEAKER: Rami Grossberg, CMU TITLE: An introduction to forking, Part 2
February 7, 2000 SPEAKER: Rami Grossberg, CMU TITLE: An introduction to forking, Part 1 ABSTRACT:
In the early seventies Shelah introduced a notion to model theory that
generalizes simultaneously the notions of linear dependence in a vector
space and that of algebraic dependence in a field. This generalization is
called forking.
The theorems that for stable theories the forking relation is very nice
are among the most fundamental theorems of modern model theory. In 1996
Kim in his thesis managed to shake the foundations of the field by
discovering new and very short proofs to the nice properties of forking at
an even more general context than stable theories (the technical term is
simple theories). Recently Buechler and Lessmann discovered even shorter
and easier proofs.
In this lecture I will present the newest and the shortest proofs for the
basic properties of forking.
A purpose of this talk is to provide some of the necessary preliminaries to
talks to be given by Alexei Kolesnikov about ACFA.
The presentation will be very elementary.
January 31, 2000 SPEAKER: James Cummings, CMU TITLE: Saturated ideals versus CH, Part 2
January 24, 2000 SPEAKER: James Cummings, CMU TITLE: Saturated ideals versus CH, Part 1 ABSTRACT: Woodin proved that if the non-stationary ideal on
$\aleph_1$ is $\aleph_2$-saturated and there is a measurable
cardinal then the Continuum Hypothesis fails in a strong sense.
We will outline the proof and discuss the problem of removing
the measurable cardinal from the assumptions.
November 29, 1999 SPEAKER: Ernest Schimmerling, CMU TITLE: The extender algebra, Part 2
November 22, 1999 SPEAKER: Ernest Schimmerling, CMU TITLE: The extender algebra, Part 1 ABSTRACT: Hugh Woodin proved the following
remarkable theorem in the 1980's.
Suppose that $M$ is an iterable transitive class model of ZFC with
a Woodin cardinal. Let $x$ be any real. Then there is a
transitive class $N$ and an elementary embedding from $M$ to $N$
such that $x$ is generic over $N$.
More specifically, suppose that $$M \models \mbox{``$\delta$ is a
Woodin cardinal''}$$ Then there exists $\mathbb{Q} \subseteq
V^M_\delta$ such that $$M \models \mbox{``$\mathbb{Q}$ is
$\delta$-c.c. complete Boolean algebra''}$$ with the property that
for any real $x$, there is an iteration tree $\mathcal{T}$ on $M$
such that $x$ is $i^\mathcal{T}_{0.\infty} ( \mathbb{Q} )$-generic
over $M^\mathcal{T}_\infty$.
$\mathbb{Q}$ is known as the {\it extender algebra}.
This result is useful in Descriptive Set Theory. For example, the
extender algebra plays a role in Woodin's proof that $\Pi^1_2$
determinacy is equiconsistent with the existence of a Woodin
cardinal.
November 15, 1999 SPEAKER: Arthur Apter, CUNY - Baruch college. TITLE: Indestructibility and Level by Level Equivalence, Part 2
November 8, 1999 SPEAKER: Arthur Apter, CUNY - Baruch college. TITLE: Indestructibility and Level by Level Equivalence, Part 1 ABSTRACT: We show that if $\kappa$ is indestructibly supercompact and
$\lambda > \kappa$ is $2^\lambda$ supercompact, then
$\{\delta < \kappa :
\delta$ is $\delta^+$ strongly compact but $\delta$ isn't $\delta^+$
supercompact$\}$ is unbounded in $\kappa$. This means that level by level
equivalence between strong compactness and supercompactness and the
existence of an indestructibly supercompact cardinal are incompatible
if there are large enough cardinals in the universe. We then
discuss the compatibility of level by level equivalence between
strong compactness and supercompactness with the existence of an
indestructibly supercompact cardinal if the size of the universe
is restricted.
November 1, 1999 SPEAKER: James Cummings, CMU TITLE: Colouring and Ramsey problems for uncountable graphs , part 3. ABSTRACT: I will prove the consistency (due to Shelah) of the statement
that for every graph $X$ there is a graph $Y$ such that for
any 2-colouring of the edges of $Y$ there is a monochromatic
induced copy of $X$"
October 25, 1999
The seminar is canceled
due to conflict with Theorem proving seminar.
is canceled.
October 17, 1999 SPEAKER: James Cummings, CMU TITLE: Colouring and Ramsey problems for uncountable graphs , part 2. ABSTRACT: In the second lecture I will consider the following "partition
relation" for graphs: $Y \rightarrow^* (X)^2_\gamma$ iff for every
colouring of the edges of $Y$ in $\gamma$ colours there exists a
monochromatic copy of $X$ which is an induced subgraph of $Y$.
Surprisingly, the statement $\forall X \; \exists Y \; Y \rightarrow^*
(X)^2_2$
is independent of ZFC; we will outline the proof (which is due
to Hajnal, Komjath and Shelah).
October 11, 1999
Midsemester break no seminar.
October 4, 1999 SPEAKER: James Cummings, CMU TITLE: Colouring and Ramsey problems for uncountable graphs , part 1. ABSTRACT: A {\bf graph} is a pair $G= (V, E)$ where $E \subseteq
[V]^2$. The {\bf chromatic number} $\chi(G)$ of a graph is the
least $\lambda $ such that there exists $c: V \rightarrow \lambda$
with the property $\forall \{ a, b \} \in E \; c(a) \neq c(b)$.
A {\bf subgraph} of $(V, E)$ is a pair $G' = (V', E')$ where
$V' \subseteq V$ and $E' \subseteq E \cap [V']^2$; $G'$ is
{\bf induced (by $V'$)} when $E' = E \cap [V']^2$.
In the first lecture I will consider the problem: when must a graph
with uncountable chromatic number have a subgraph of size and
chromatic number $\aleph_1$? This problem is still open, I will
survey the known partial results. The problem is connected with
the existence of generic elementary embeddings.
September 26, 1999 SPEAKER: Rami Grossberg, CMU TITLE: On the number of non conjugate subgroups, part 2.
September 20, 1999 SPEAKER: Rami Grossberg, CMU TITLE: On the number of non conjugate subgroups, part 1. ABSTRACT: I will start a sequence of lectures
dedicated to proving the following Theorem of Saharon Shelah: Theorem (ZFC) Let G be a group and let
F be the family of pairwise non-conjugate subgroups of G.
If G is
of uncountable cardinality $\lambda$ then
the cardinality of F is at least $\lambda$.
The proof consists of a combination of ideas from
combinatorial set theory with basic group theory and model theory.
The proof is by cases (and increasingly more difficult).
The first lecture will be dedicated to the relatively simple
(and interesting) case when $\aleph_0<\lambda\leq 2^{\aleph_0}$.
The first lecture will be very
elementary and assume no more
than our advanced undergraduates know.
There will be a fluids seminar at 6:30.
September 13, 1999 SPEAKER: Paul Larson, Paris VII TITLE:
Chain conditions in maximal models (joint work with Stevo Todor\v{c}evi\'{c})
ABSTRACT:
Todor\v{c}evi\'{c} and Veli\v{c}kovi\'{c} showed that Martin's Axiom is
equivalent to the statement that every c.c.c. partition on finite subsets
of $\omega_1$ has an uncountable homogeneous set. They also formulated for
each integer $n$ the axiom $\mathcal{K}_{n}$, which says that every
uncountable c.c.c. poset contains an uncountable subset for which
every $n$-tuple has a lower bound. Though it is expected that the
$\mathcal{K}_{n}$'s are all different (and conjectured by
Todor\v{c}evi\'{c} and Veli\v{c}kovi\'{c} by that $\mathcal{K}_{2}$ does
not imply $\mathcal{K}_{3}$), none of the implications between them has
been shown to be one-way. We will discuss a $\mathbb{P}_{max}$ variation
whose extension sheds some light on the problem of separating
$\mathcal{K}_{2}$ from $\mathcal{K}_{3}$, and related variations for
similar problems.
April 26, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, Part 6 (last)
April 19, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, Part 5
April 12, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, Part 4
April 5, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, Part 3
March 29, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, Part 2
March 22, 1999
Spring break, no seminar
March 15, 1999
SPEAKER: Alexei Kolesnikov TITLE: There is more than one uncountable model, part 1
ABSTRACT: In the first order logic case, the statement appearing in the
title is just a simple observation. However, it is far from being trivial
in non first order logic. I will present the basics of what is known
as Shelah's "Classification theory for non elementary classes."
Among other results, I will present Shelah's proof to the
statement in the title for $L_{\omega_1,\omega}(Q)$. This answers to the
question asked by J. Baldwin: "Can a theory of $L(Q)$ have only one
uncountable model?" The talks will require minimal background and will be
self-contained except few facts that will be quoted without proofs.
February 15, 1999
SPEAKER: Lubos Thoma TITLE: Zero-one laws and finite models , Part 2
ABSTRACT:
In the lectures I will discuss several topics concerning
finite models and 0.1 laws for random structures.
After giving a general introduction, I will focus on first
order languages of certain structures (e.g. graphs) and
0.1 laws for them. In the second part I will present
an extension to 0.1 laws based on a joint work with J. Spencer
and its application to the characterization of limit probabilities
of the first order sentences of the random graph.
Depending on time left, I mention connections to computational
complexity.
February 8, 1999
SPEAKER: Lubos Thoma TITLE: Zero-one laws and finite models , Part 1
ABSTRACT:
In the lectures I will discuss several topics concerning
finite models and 0.1 laws for random structures.
After giving a general introduction, I will focus on first
order languages of certain structures (e.g. graphs) and
0.1 laws for them. In the second part I will present
an extension to 0.1 laws based on a joint work with J. Spencer
and its application to the characterization of limit probabilities
of the first order sentences of the random graph.
Depending on time left, I mention connections to computational
complexity.
February 1, 1999
SPEAKER: John Krueger TITLE: Properness and Preservation in the Theory of Forcing, Part
3
January 25, 1999
SPEAKER: John Krueger TITLE: Properness and Preservation in the Theory of Forcing, Part 2
January 11, 1999
SPEAKER: John Krueger TITLE: Properness and Preservation in the Theory of Forcing,
Part 1
ABSTRACT: In this lecture series we discuss several topics in
the advanced theory of forcing. There are certain properties of partial
orders which are desirable from the standpoint of forcing. The most
familiar of such properties are the countable chain condition, countable
closure, and a generalization of these two, properness. Under certain
conditions such properties are preserved when iterating forcing. In these
lectures we focus on properness, the preservation of properness in
countable support iterations, and other preservation results related to
the space $^\omega\omega$.
November 30, 1998
SPEAKER: James Cummings TITLE: Can you have an uncountable Ramsey theorem?
ABSTRACT: The infinite form of Ramsey's celebrated theorem states
that if the unordered n-tuples from an infinite set are coloured
in finitely many colours, then there is an infinite subset in which
every n-tuple gets the same colour. It is natural (at least to a
set theorist) to ask about generalisations to the uncountable:
after some partial results Todorcevic proved the following strong
"anti-Ramsey" theorem (here $\aleph_1$ is the least uncountable
cardinal)
THEOREM (Todorcevic): There is a colouring of pairs from $\aleph_1$
in $\aleph_1$ colours such that any uncountable subset contains pairs
of every colour.
I will give a simplified proof of this result due to Velleman,
and if time allows will discuss generalisations by Shelah to
higher cardinals.
November 23, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 8
November 16, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 7
November 9, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 6
November 2, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 5
October 19, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 3
October 26, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 4
October 12, 1998
SPEAKER:Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 2
October 5, 1998
SPEAKER: Monica VanDieren TITLE: Shelah's categoricity conjecture for $L_{\kappa,\omega}$ where
$\kappa$ is a compact cardinal is true., Part 1
ABSTRACT: In the 1970's Shelah made a conjecture, which
is the central conjecture in the field of
``classification theory for non elementary classes'':
CONJECTURE: If $\psi\in L_{\kappa^+,\omega}$ is categorical in some
$\lambda$ greater than $\beth_{(2^\kappa)^+}$, then it is categorical
in every $\mu\geq\beth_{(2^\kappa)^+}$.
There are many partial results on the conjecture.
Makkai and Shelah in 1989 published an
approximation of this conjecture when
$\kappa$ is a compact cardinal. In this series of talks I will
present thier approach.
While doing that, I
will present an
improvement of their result which captures Shelah's
conjecture in full for
$\kappa$ compact.
This solves one of his problems from [Sh666].
September 27, 1998
SPEAKER: John Krueger TITLE:The Partition Calculus and Some Applications to Topology, Part
2
September 21, 1998 No seminar.
September 14, 1998
SPEAKER: John Krueger TITLE:The Partition Calculus and Some Applications to Topology, Part 1 ABSTRACT:
In this lecture series I will present the rudiments of a field
of combinatorial set theory called the partition calculus. I will
introduce the notion of a partition tree, and use it to prove a variant
of the Erdos-Rado Theorem. I will then present several applications of
the partition calculus to general topology. In particular, I will
present a proof of a famous theorem by Arkhangel'skii that any first
countable compact Hausdorff space is no larger than the continuum.
HISTORY OF THIS SEMINAR: The seminar started around 1991 by Rami
Grossberg and since it meets regularly every Monday every semester (from
the third Monday of the semester).
PRE 9/98 SPEAKERS IN THIS SEMINAR:
Michael Albert,
Jeremy Avigad, Matt Bishop, James Cummings,
Doug Ensley, Martin Goldstern,
Rami Grossberg, Jose Iovino, Kitty Holland,
Menachem Kojman, Alexie Kolesnikov, Olivier Lessmann,
Nate Segerlind,
Rick Statman, Jay Stewart, Thilo Trap, Monica VanDieren,
Boban Velickovic, Roberto Virga,
HongWei Xi.