Logical Approaches to Computational Barriers

From Constructibility and Absoluteness to Computability and Domain Independence

Speaker:
| Arnon Avron |

Godel's main contribution to set theory is his proof that GCH is consistent with ZFC (assuming that ZF is consistent). For this proof he has introduced the important ideas of constructibility of sets, and of absoluteness of formulas. In this paper we show how these two ideas of Godel naturally lead to a simple unified framework for dealing with computability of functions and relations, domain independence of queries in relational databases, and predicative set theory.

websites: Arnold Beckmann | 2006-04-29 |