Theory Seminar

Abstract

We show that there have been common ideas concerning important properties of formulas which were independently developed in the research on query languages and in some basic mathematical theories, like set theory and formal number theory: finiteness versus limitation of size, effectiveness versus safety, domain-independence versus absoluteness. We provide common generalizations in each case, and show that they are useful for both disciplines. In the database case they provide obvious improvements of usual syntactically characterized classes of reasonable queries. Apart from significantly enlarging those classes, they provide a firm theoretical basis for using in queries relations that are not completely given, but only partially accessible through links (like in the world wide web). In formal number theory our concepts lead to a new, simple characterization of the class of primitive recursive formulas. In set theory we show that the various comprehension axioms of ZF can be replaced by a single comprehension principle, which only allows the use of the syntactically defined class of "safe" formulas. This leads to the conclusion that the comprehension axioms of ZF are nothing more than an extrapolation of properties of finite sets.

John Longley
Tuesday 7 September 1999 An error occured whilst processing this directive