The Logic and Computation Group is composed of faculty and graduate students from the Computer and Information Science, Mathematics, and Philosophy departments, and participates in the Institute for Research in the Cognitive Sciences. The Logic and Computation group runs a weekly seminar. The seminar is open to the public and all are welcome.
The seminar meets regularly during the school year on Mondays at 4:30 p.m. in room DRL 4C8 on the fourth (top) floor of the David Rittenhouse Laboratory (DRL), on the Southeast corner of 33-rd and Walnut Streets at the University of Pennsylvania. Directions may be found here. Any changes to this venue or schedule will be specifically noted.
The mean ergodic theorem is a central tool in the study of dynamical systems. On its face, the theorem gives no bounds for the quantities it asserts to exist; this is unfortunate, since the theorem is routinely in ergodic proofs of combinatorial statements. In this setting, it is often desirable to "unwind" these ergodic proofs to extract combinatorial bounds for the quantities involved. I describe how limited constructive information can be extracted from the mean ergodic theorem in a systematic way using Godel's Dialectica translation.
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 partial results regarding Vaught's conjecture was made by Michael Morley in the 1970 paper "The Number of Countable Models". In this paper Morley proved that every sentence of L_{omega_1,omega} has either countably many, continuum many or omega_1 many countable models. In the proof he showed that the countable models of such a sentence could be arranged in a natural way in what is now called a Vaught tree. He further showed that the number of models at any level of this tree is either countable or has size of the continuum. Hence, the only way that that Vaught's conjecture could fail is if there is a sentence of L_{omega_1,omega} whose Vaught tree has only countably many models at each level and has height omega_1.
In this series of talks we will present a method which (with a few assumptions) allows us to construct for each ordinal alpha a sentence of L_{omega_1,omega} whose Vaught tree has height approximately alpha and which has only countably many models at each level. As such these sentences can be viewed as approximations to a counterexample to Vaught's conjecture. This work is based on the main result of my PhD thesis.
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 partial results regarding Vaught's conjecture was made by Michael Morley in the 1970 paper "The Number of Countable Models". In this paper Morley proved that every sentence of L_{omega_1,omega} has either countably many, continuum many or omega_1 many countable models. In the proof he showed that the countable models of such a sentence could be arranged in a natural way in what is now called a Vaught tree. He further showed that the number of models at any level of this tree is either countable or has size of the continuum. Hence, the only way that that Vaught's conjecture could fail is if there is a sentence of L_{omega_1,omega} whose Vaught tree has only countably many models at each level and has height omega_1.
In this series of talks we will present a method which (with a few assumptions) allows us to construct for each ordinal alpha a sentence of L_{omega_1,omega} whose Vaught tree has height approximately alpha and which has only countably many models at each level. As such these sentences can be viewed as approximations to a counterexample to Vaught's conjecture. This work is based on the main result of my PhD thesis.
Many logics can be regarded as classes of reachability games between two players, whom we may call Adam and Eve: Eve claims that a given structure has a certain property, while Adam challenges that claim. We consider the problem of large games, i.e., games with long programs. In the real world, such programs are composed of smaller subprograms, with the result that we are ultimately presented with what looks like a small program, but with calls to subprograms, which in turn have calls to subsubprograms, and so on. We look at some examples and some theoretical issues.
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 partial results regarding Vaught's conjecture was made by Michael Morley in the 1970 paper "The Number of Countable Models". In this paper Morley proved that every sentence of L_{omega_1,omega} has either countably many, continuum many or omega_1 many countable models. In the proof he showed that the countable models of such a sentence could be arranged in a natural way in what is now called a Vaught tree. He further showed that the number of models at any level of this tree is either countable or has size of the continuum. Hence, the only way that that Vaught's conjecture could fail is if there is a sentence of L_{omega_1,omega} whose Vaught tree has only countably many models at each level and has height omega_1.
In this series of talks we will present a method which (with a few assumptions) allows us to construct for each ordinal alpha a sentence of L_{omega_1,omega} whose Vaught tree has height approximately alpha and which has only countably many models at each level. As such these sentences can be viewed as approximations to a counterexample to Vaught's conjecture. This work is based on the main result of my PhD thesis.
In 1985 Woodin showed that if there is a proper class of measurable Woodin cardinals and $V^{B_1}$ and $V^{B_2}$ are generic extensions of $V$ satisfying $CH$ then $V^{B_1}$ and $V^{B_2}$ agree on all $Sigma^2_1$-statements. In modern terms this can be reformulated by saying that under the above large cardinal assumption $ZFC+CH$ is $Omega$-complete for $Sigma^2_1$. Moreover, $CH$ is the unique $Sigma^2_1$-statement with this feature in the sense that any other $Sigma^2_1$-statement with this feature is $Omega$-equivalent to $CH$. It is natural to look for other strengthenings of $ZFC$ that enjoy a greater degree of $Omega$-completeness. For example, one can ask for recursively enumerable axioms $A$ such that relative to large cardinal axioms $ZFC+A$ is $Omega$-complete for all of third-order arithmetic. Going further, for each specifiable segment $V_lambda$ of the universe of sets (for example, one might take $lambda$ to be the least huge cardinal), one can ask for recursively enumerable axioms $A$ such that $ZFC+A$ is $Omega$-complete for the theory of $V_lambda$, relative to large cardinal axioms. If such theories exist, extend one another, and are unique in the sense that any other theory $A'$ with the same level of $Omega$-completeness as $A$ is actually $Omega$-equivalent to $A$, then this would make for a very strong case for new axioms that settle the theory of $V$ in $Omega$-logic. In this talk I will motivate the above scenario and sketch a proof that uniqueness must fail. This is joint work with Hugh Woodin. In particular, we show that if there is one such theory that $Omega$-implies $CH$ then there is another that $Omega$-implies $negCH$.
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 partial results regarding Vaught's conjecture was made by Michael Morley in the 1970 paper "The Number of Countable Models". In this paper Morley proved that every sentence of L_{omega_1,omega} has either countably many, continuum many or omega_1 many countable models. In the proof he showed that the countable models of such a sentence could be arranged in a natural way in what is now called a Vaught tree. He further showed that the number of models at any level of this tree is either countable or has size of the continuum. Hence, the only way that that Vaught's conjecture could fail is if there is a sentence of L_{omega_1,omega} whose Vaught tree has only countably many models at each level and has height omega_1.
In this series of talks we will present a method which (with a few assumptions) allows us to construct for each ordinal alpha a sentence of L_{omega_1,omega} whose Vaught tree has height approximately alpha and which has only countably many models at each level. As such these sentences can be viewed as approximations to a counterexample to Vaught's conjecture. This work is based on the main result of my PhD thesis.
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 partial results regarding Vaught's conjecture was made by Michael Morley in the 1970 paper "The Number of Countable Models". In this paper Morley proved that every sentence of L_{omega_1,omega} has either countably many, continuum many or omega_1 many countable models. In the proof he showed that the countable models of such a sentence could be arranged in a natural way in what is now called a Vaught tree. He further showed that the number of models at any level of this tree is either countable or has size of the continuum. Hence, the only way that that Vaught's conjecture could fail is if there is a sentence of L_{omega_1,omega} whose Vaught tree has only countably many models at each level and has height omega_1.
In this series of talks we will present a method which (with a few assumptions) allows us to construct for each ordinal alpha a sentence of L_{omega_1,omega} whose Vaught tree has height approximately alpha and which has only countably many models at each level. As such these sentences can be viewed as approximations to a counterexample to Vaught's conjecture. This work is based on the main result of my PhD thesis.
I will give a survey talk on the notion of modularity, a central theme leading the development of modern model theory. A model ( =structure) or its theory having a suitable independence notion (such as simple, rosy, or o-minimal) is said to be modular if any two closed sets are independent over their intersection, sharing the dimensional property as a module or a vector space. The natural questions on modularity are whether a concrete infinite module (field, resp.) can be recovered in some first-order manner from a modular (non-modular, resp.) structure. For stable theories, Zilber and Hrushovski made pioneering works to answer the questions, and those play crucial roles in supplying spectacular applications of model theory to number theory. A considerable part of the results are recently extended to the context of simple theories. For o-minimal theories, the questions are fully answered without a constraint by Peterzil and Starchenko in mid 1990s. Modularity also appears unexpectedly in algebraic geometry. For example, Faltings's solution to absolute Mordell-Lang says that the induced structure on the set of rational points of an elliptic curve is modular.
Equivalence in System F goes beyond beta-eta equivalence, due to parametric polymorphism. Syntactic logical relations and applicative bisimulations have been used as tools for reasoning about program equivalence in polymorphic languages. Nevertheless, even in the simplest case of pure System F, the connection between certain syntactic logical relations and program equivalence is not clear.
This talk is a call for discussion: We will focus on such questions; we will present alternative ways of stating them, and propose possible directions for answering them.
The calculus of relations has been introduced by Alfred Tarski, in an attempt to axiomatize the theory of binary relations, without dealing with individuals (the objects being related). It has also been called "relation algebras". Ten years ago, Doornbos, Backhouse and van der Woude [1997] showed that we can characterize the notion of a well-founded relation in a similar setting, so that we end up with the ability to reason by well-founded induction at this relatively high level of abstraction.
This setting is very well suited to the analysis of (semi)commutation properties (e.g., Newman's Lemma). In particular, we use it to obtain a new commutation property, which in turn can be used in order to obtain up-to techniques for bisimulation, the coinductive proof method commonly found in concurrency theory.
Bisimilarity has been discovered rather independently in Concurrency Theory [Milner, Park] and Set Theory [Azcel, Barwise]. In both cases, bisimilarity gives a way to equate objects with infinite behavior: infinite processes in the former, non well-founded sets in the latter. The overall intuition is that we move from a stratified, inductive equality, to a coinductive one (instead of considering a least fixpoint, we consider a greatest fixpoint). One of the advantages of this approach is that it naturally comes with a powerful coinduction principle, which gives an effective method for proving equalities.
In Concurrency Theory, standard techniques can be used in order to refine this proof method: "up-to techniques". I will illustrate the usefulness of such techniques on a concrete example. I will then define a theory of such up-to techniques, at a rather abstract level: we can just work in an arbitrary complete lattice, eventually enriched with a monoid structure.
Admissible set theory is, in a sense, the intersection of model theory, recursion theory, and set theory. From the set theory point of view they provide models of important fragments of ZFC. From the recursion theory point of view they provide a very strong generalization of the notion of finite. And from the model theory point of view they provide a way in which to see that L_{omega_1, omega} is a generalization of first order logic that preserves many of first order logics nice properties.
In this talk we will be focusing on the model theoretic aspects of admissible sets. Specifically we will introduce admissible sets and their connection to the logic L_{omega_1, omega}. We will then review the model existence theorem and use it to prove two of the most important results concerning L_{omega_1,omega}, the completeness theorem and Barwise compactness. These two results show that, when viewed through the lens of admissible sets, L_{omega_1,omega} is a good generalization of first order logic.
While most of the axioms of ZFC assert the existence of certain sets, the axiom of foundation is one of the few axioms which limit the type of sets which can exist. The axioms says (For all A not the emptyset) (there exists B in A) such that (For all C in A) C is not in B. In other words this axiom guarantees that all sets are "well-founded". While this axiom is incredibly useful for studying the properties of a universe of sets, from a naive set theoretic point of view it is not clear why ill-founded sets shouldn't be able exist. As such, one might hope that by allowing ill-founded sets we could better express the naive set theoretic idea that "all sets that can exist do". However, when we do this we find that we very quickly run into a problem. When we remove the axiom of foundation, the axiom of extensionality looses a lot of its power. The axiom of extensionality says that two sets are equal if and only if they contain the same elements. One of the most useful consequences of foundation and extensionality is that every set is uniquely determined by its structure. However, once we remove regularity this no longer holds. (To see this consider two sets x = { x } and y = { y }. These sets obviously have the same structure but are not necessarily the same.) Aczel's anti-foundation axiom is an attempt to handle ill-founded sets while still keeping the important property that a set is defined by its structure. In this talk we will introduce Aczel's axiom and discuss how it ensures that a set is determined by its structure as well as how Aczel's axiom relates to the axiom of extensionality.
While most of the axioms of ZFC assert the existence of certain sets, the axiom of foundation is one of the few axioms which limit the type of sets which can exist. The axioms says (For all A not the emptyset) (there exists B in A) such that (For all C in A) C is not in B. In other words this axiom guarantees that all sets are "well-founded". While this axiom is incredibly useful for studying the properties of a universe of sets, from a naive set theoretic point of view it is not clear why ill-founded sets shouldn't be able exist. As such, one might hope that by allowing ill-founded sets we could better express the naive set theoretic idea that "all sets that can exist do". However, when we do this we find that we very quickly run into a problem. When we remove the axiom of foundation, the axiom of extensionality looses a lot of its power. The axiom of extensionality says that two sets are equal if and only if they contain the same elements. One of the most useful consequences of foundation and extensionality is that every set is uniquely determined by its structure. However, once we remove regularity this no longer holds. (To see this consider two sets x = { x } and y = { y }. These sets obviously have the same structure but are not necessarily the same.) Aczel's anti-foundation axiom is an attempt to handle ill-founded sets while still keeping the important property that a set is defined by its structure. In this talk we will introduce Aczel's axiom and discuss how it ensures that a set is determined by its structure as well as how Aczel's axiom relates to the axiom of extensionality.
While most of the axioms of ZFC assert the existence of certain sets, the axiom of foundation is one of the few axioms which limit the type of sets which can exist. The axioms says (For all A not the emptyset) (there exists B in A) such that (For all C in A) C is not in B. In other words this axiom guarantees that all sets are "well-founded". While this axiom is incredibly useful for studying the properties of a universe of sets, from a naive set theoretic point of view it is not clear why ill-founded sets shouldn't be able exist. As such, one might hope that by allowing ill-founded sets we could better express the naive set theoretic idea that "all sets that can exist do". However, when we do this we find that we very quickly run into a problem. When we remove the axiom of foundation, the axiom of extensionality looses a lot of its power. The axiom of extensionality says that two sets are equal if and only if they contain the same elements. One of the most useful consequences of foundation and extensionality is that every set is uniquely determined by its structure. However, once we remove regularity this no longer holds. (To see this consider two sets x = { x } and y = { y }. These sets obviously have the same structure but are not necessarily the same.) Aczel's anti-foundation axiom is an attempt to handle ill-founded sets while still keeping the important property that a set is defined by its structure. In this talk we will introduce Aczel's axiom and discuss how it ensures that a set is determined by its structure as well as how Aczel's axiom relates to the axiom of extensionality.
We consider the question in the subtitle, and the closely related question "When is a semigroup embeddable in a group?". Although the latter question has a history going back 70 years, it appears that no-one has previously considered its categorical analogue. We show that the categorical viewpoint enables one to give simpler and more perspicuous proofs of the results of Mal'cev, Lambek, Bush and others, as well as strengthening them in some respects. The central ingredient in our proofs is a simple combinatorial structure which we call a quadrangle club, but the proofs also have a homotopy-theoretic flavour.