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,
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.
[IA] Ramon E. Moore: Interval Analysis Prentice-Hall 1966.
[NDT] Viggo Stoltenberg-Hansen: Notes on Domain Theory.
[V] Steven Vickers: Topology via Logic. Cambridge
[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:
- Fixed points
- Notions of domains: cpos, Scott-Ershov domains
- Domain constructions
- Domain equations
- Point-free topology
- interval analysis,
- fuzzy sets,
- combinatorics of partial
- connections to
Schedule: Mondays 15.15-17 and Wednesdays 15.15-17 in room 2315
(unless otherwise indicated below)
The course will be given in English.
- Fr. 8/2: Motivating examples: Interval arithmetic.
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
- 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.]
- On. 13/2: Interval arithmetic (cont.). Complete partial orders.
- 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.]
- On. 20/2: Complete lattices, infinite distributive law
and Heyting algebras. Boolean algebras. Classical and intuitionistic
logic. Fuzzy sets.
- 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.
- Må 4/3: Continuous cpos, way-below relation, compact elements.
[NDT]: section 2.3.1, [MTD]: section 3.1.
- Må 11/3: Interpolation in continuous domains. Bases for
function spaces. [NDT]: section 2.3.3. Studied examples on page 54 - 57 of
- On 13/3: Scott-Ershov domains. The
representation theorem. [MTD]: section 3.2-3.3.
- Må 18/3: Solution of term equations. Compact elements of function
spaces. Topological spaces. [MTD]: sections 3.3, 5.1-5.2.
- 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.
- 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.
- On 10/4: Dismantable posets. Fixed point theorems of
Baclawski and Björner. Does every real number really have a
- 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.
- Må 15/4: Approximable mappings. Inductively generated covers.
- On 17/4: The functor Pt. Formal real numbers. Equivalence with
- Må 22/4: Möbius function for partial orders.
Domain equations. Direct limits.
- 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?
- 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. )
- Må 6/5. Continuous functors. Effective domains.
Models of the lambda-calculus.
- Take-home exam: starting 9.00 Monday 13/5 and
ending Friday 17/5 at 17.00.
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 !!
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
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.
May 30, 2002,