I will show that some notions used in traditional mathematical fields like topology or algebra cannot be split into finer subnotions. In other words, all of the representatives of these notions have the same properties. This has some impact on the methodology of mathematics.
This talk is a contribution to the foundational study of corecursion, a version of recursion in which there is no 'base case'. The problem is to formulate existence results which are general and natural, and perhaps ones which show the similarities and differences with recursion. The first work in this area is Aczel's "Special Final Coalgebra Theorem", and other contributions include Turi's reformulation of Aczel's work, and an approach that Jon Barwise and I worked out using set theory with urelements. In this talk, I'll develop an approach that I think improves on all of the previous ones. If I have time I'll discuss a result which is slightly tangential to the main topic of the talk but of related interest: the equational properties of recursion and corecursion coincide.
Christensen found a natural extension of the notion of being of Lebesgue measure zero in finite dimensional Euclidean spaces (or Haar measure zero on locally compact groups) to infinite dimensional Banach spaces and more generally to non-locally compact Polish group. (This is non-obvious unlike, say, extending the notion of meagerness.) This notion, called Haar null, found many applications in functional analysis; for example in extending Rademacher's theorem on differentiability of Lipschitz functions.
The talk will be concerned with a circle of problems, initiated by Christensen, which have to do with comparing properties of the family of Haar null sets on non-locally compact groups with the properties of the family of Haar measure zero sets on locally compact groups. I will do a short survey and present, among other things, a theorem showing that on non-locally compact abelian Polish groups the family of Haar null sets "reduces" (in a precise sense related to the Rudin-Keisler reduction between filters on $\omega$) the family of non-dominating subsets of the Baire space. As immediate consequences we will obtain known results due to Christensen, Dougherty, and myself concerning Haar nullness of compact sets and the failure of the countable chain condition. Moreover, we will get an answer to a question of Kechris by deducing from this theorem that descriptive set theoretic complexity of the family of closed Haar null sets on a Polish abelian group determines whether or not the group is locally compact.
We present a general methodology for reasoning about functional programs, which uses as axioms only the properties most intrinsic to the data type in hand, and treats programs as auxiliary axioms. Its advantages include expressive flexibility, minimal axiomatics, dispensing with coding for reasoning about partial functions, data genericity, and a clear conceptual framework for machine-independent characterizations of a wide spectrum of computational complexity classes.
In Chapters 9-11 of The Logical Basis of Metaphysics, Michael Dummett claims to formulate a proof-theoretic method for providing justifications of logical laws of inference. According to this method, a law is justified if any deduction of a certain standard type for the premises of the law can be transformed into a deduction of the standard type for the conclusion of the law. The laws justified by this method, Dummett claims, are just the laws of intuitionistic logic.
An analysis of Dummett's method is presented that makes its scope transparent. This uncovers counterexamples: clearly incorrect laws that are "justified" according to the method. A simple modification avoids such counterexamples, but is at odds with the philosophical underpinnings of Dummett's enterprise. Even with the modification, some non-intuitionistic laws are "justified." The discrepancy reveals some fundamental difficulties in Dummett's view of the nature of logic and its relation to meaning.
A finitely representable relation over the reals is a relation defined by a FO-formula over the reals with addition and multiplication. Such a relation is alternatively known as a semi-algebraic set. Semi-algebraic sets suffice to represent most geometric information encountered in computer applications (for example spatial databases).
A query is a function that maps semi-algebraic sets to semi-algebraic sets. For example, the mapping that returns the convex hulls of semi-algebraic sets is a query.
A query language is a syntactic entity wherein certain classes of queries can be expressed.
In this talk, I will talk about the model theory of certain FO-based query languages, where the models are finitely representable relations. In addition, I will discuss how this developing theory has applications in geometric information bases.
It will be shown that an appropriate axiom of determinacy plus some large cardinal axioms inspired by Ockham's principle of economy of concepts and Leibniz identity principle imply
2^aleph(n) = aleph(n + 1),
for finite n's and also for some infinite n's.
A positive first-order formula is bounded if the sequence of its stages converges to the least fixed-point of the formula within a constant number of steps independent of the input structure. In other words, a formula is bounded if the depth of the recursion generated by the formula is finite and independent of the structure on which the formula is iterated. The boundedness problem for a fragment of first-order logic asks: given a positive formula in that fragment, is it bounded?
Our aim in this talk is to present a comprehensive overview of structural and algorithmic aspects of the boundedness problem for various fragments of first-order logic. Specifically, we first review earlier results by other researchers that delineate the boundary between decidability and undecidability of the boundedness problem for existential first-order formulas. After this, we present recent work, carried out jointly with Martin Otto, on the boundedness problem for two-variable first-order logic. As a general rule, two-variable first-order logic is well behaved; in particular, it has a decicable satisfiability problem. In contrast, our main result asserts that the boundedness problem for two-variable first-order logic is undecidable, even when restricted to certain rather limited classes of two-variable formulas. We conclude by discussing an application of this result to circumscription, one of the main formalisms for nonmonotonic reasoning.
I propose a new method of semantic analysis for intuitionistic logic in terms of intuitionistic state-descriptions. I consider a possibility of contradictory state-descriptions and show that such state-descriptions may be of use in defining a negation operator of an intuitionistic type. On this basis I develop a general Kripke-style semantic construction for Curry collection of systems for various kinds of constructive negation.
The modern reconsideration of computation is based on the distinction between polynomial time and slower algorithms. Quantum computers appear to confer a substantial speed up over Turing machines. It is natural to ask if computational models based on string theory will go still further. Topological quantum field theory (TQFT) is an obvious instance. We answer in the negative that unitary TQFT can be efficiently simulated by quantum computers. In this talk, we will start with the definition of quantum Turing machines and define the class BQP. We will discuss the simulation result, and a topological approach to quantum computation.