UPPSALA UNIVERSITET Matematiska institutionen | Vårterminen 2002 |

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.

[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:

- Fixed points
- Notions of domains: cpos, Scott-Ershov domains
- Domain constructions
- Domain equations
- Point-free topology

- interval analysis,
- fuzzy sets,
- combinatorics of partial orders
- connections to digital geometry.

- Computation and appoximation
- Topology, Domain Theory and Theoretical Computer Science, by M. Mislove.

- 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? - 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. Categories. Examples.
- 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 [MTD].
- 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 decimal expansion? - 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 constructive reals.
- 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.

- Erik Palmgren. Office: room 2137, phone 471 32 85.

May 30, 2002, Erik Palmgren.