UPPSALA UNIVERSITET
Matematiska institutionen

Vårterminen 2002

Domänteori MN1 (Domain Theory)

Domain theory is a mathematical theory which is the foundation for denotational semantics of programming languages. It may also be viewed as a theory of computation, especially for "higher order" objects.

Literature and contents

[MTD] Stoltenberg-Hansen, V, Lindström, I and Griffor, E: Mathematical Theory of Domains. Cambridge University Press, 1994.

[ID] Palmgren, E: Interval analysis and domains - Supplementary notes for Domänteori MN1. Uppsala 2002.

Reference literature

[IA] Ramon E. Moore: Interval Analysis Prentice-Hall 1966.

[NDT] Viggo Stoltenberg-Hansen: Notes on Domain Theory. Marktoberdorf 2001.

[V] Steven Vickers: Topology via Logic. Cambridge University Press.

[J] Peter T. Johnstone: Stone spaces. Cambridge University Press 1983.

[K] Christer O. Kiselman: Digital Jordan Curve Theorems. U.U.D.M. Report 2000.

The content of the course is described in the study guide (in Swedish). Some main topics:

(Topological and category-theoretic notions necessary for the theory will be introduced.) Additional topics may include:

Links

Lectures

Schedule: Mondays 15.15-17 and Wednesdays 15.15-17 in room 2315 (unless otherwise indicated below) The course will be given in English.

Lecture diary:

  1. Fr. 8/2: Motivating examples: Interval arithmetic. Untyped lambda-calculus, self application, fixed point combinators. Recursive progams: the gcd example. Partial functions, information ordering. Functionals, monotone and continuous. [MTD: sections 0.1, 1.1, 12.1.] Question to ponder: do there exist non-continuous computable functionals?
  2. Må. 11/2: Kleene's recursion theorem. omega-complete partial orders. Montone and omega-continuous functions. Fixed point theorems. Examples. Interval numbers form a omega-complete partial order. Interval arithmetic. [MTD: section 1.2, IA: chapter 2 and 3.]
  3. On. 13/2: Interval arithmetic (cont.). Complete partial orders. Categories. Examples.
  4. Må. 18/2: The Cantor space. Flat domains. Products and coproducts in a category. Proofs without using elements. Products in CPO. Lattices: examples, completeness. [MTD: sections 0.3, 2.1, 2.2.]
  5. On. 20/2: Complete lattices, infinite distributive law and Heyting algebras. Boolean algebras. Classical and intuitionistic logic. Fuzzy sets.
  6. Må 25/2: Cartesian closed categories. Function spaces. CPO is cartesian closed. A Heyting algebra viewed as a cartesian closed category. [MTD: section 0.3, 2.3]. For further reading on Heyting algebras see [V], [J] or Troelstra and van Dalen, Constructivisim in Mathematics, vol. 2, North-Holland 1988.

    Recommended exercises, Set 1: [MTD]: 1.3.1, 1.3.2*, 1.3.5, 1.3.7, 1.3.10, 2.5.1*, 2.5.2, 2.5.8, 2.5.11, 2.5.17 (not mentioning elements). [IA]: Problem 2.3, 3.5. Handout on fuzzy sets: övning 2, 3, 11.

  7. Må 4/3: Continuous cpos, way-below relation, compact elements. [NDT]: section 2.3.1, [MTD]: section 3.1.
  8. Må 11/3: Interpolation in continuous domains. Bases for function spaces. [NDT]: section 2.3.3. Studied examples on page 54 - 57 of [MTD].
  9. On 13/3: Scott-Ershov domains. The representation theorem. [MTD]: section 3.2-3.3.
  10. Må 18/3: Solution of term equations. Compact elements of function spaces. Topological spaces. [MTD]: sections 3.3, 5.1-5.2.
  11. On 20/3: Alexandrov topology on partially ordered sets. Examples from digital geometry: Khalimsky line and plane. Finite topologies. The fixed point property problem. [MTD] section 5.1-5.2.
  12. Må 25/3: Scott topology. Closed sets. Kuratowski closure axioms. Interior operator. The open sets form a complete lattice

    Recommended exercises, Set 2: [MTD]: 3.5.1, 3.5.4, 3.5.5, 3.5.6, 3.5.7, 3.5.9*, 5.6.2, 5.6.3, 5.6.8. [ID]: exercises on page 11 and 12.

  13. On 10/4: Dismantable posets. Fixed point theorems of Baclawski and Björner. Does every real number really have a decimal expansion?
  14. Fr 12/4: Signed digit expansions of real numbers. Point-free topology. Frames. Formal spaces. Real line and Cantor space as a formal topology. Compact formal spaces.
  15. Må 15/4: Approximable mappings. Inductively generated covers.
  16. On 17/4: The functor Pt. Formal real numbers. Equivalence with constructive reals.
  17. Må 22/4: Möbius function for partial orders. Domain equations. Direct limits.
  18. On 24/4: Domain equations.

    Recommended exercises, Set 3: [MTD]: 4.7:1,2,8,12,14,15,23; 5.6:1,2; 6.5:13,16;

    Find signed (binary) digit expansions of 1/3, -37 and Pi. Show that e.g. 1 has infinitely many expansions.

    [ID]: Which partial ordered sets with 5 elements has the fixed point property? Show that covering compactness (Lemma 8.23) is valid if the alfabet "Sigma" is any finite, non-empty set. What can be said if the alfabet is infinite?

  19. Fr 3/5, 13.15-15, room 2315. Domain equations: a general fixed point theorem for continuous functors. Categofication (see John Baez paper From finite sets to Feynman diagrams. )
  20. Må 6/5. Continuous functors. Effective domains. Models of the lambda-calculus.
  21. Take-home exam: starting 9.00 Monday 13/5 and ending Friday 17/5 at 17.00.

Examination

The exam will be a take-home exam where some problems (>50%) are handed out already during the course. These will be a subset of "recommended exercises" (see above). The results are now announced on the notice board !!

Homepage

The homepage of the course http://www2.math.uu.se/~palmgren/dt/ will be updated regularly. (Which probably is this one if you are reading this on a computer screen.) I will try to keep a brief "diary" of the lectures (see above), and add references for further readings. Watch also for changes of schedules etc.

Lecturer

May 30, 2002, Erik Palmgren.