Abstracts of Papers and Notes

# Abstracts of Papers and Notes

These documents are listed in reverse chronological order, that is with the latest at the top and the earliest at the bottom. Each is given a label consisting of a number together with either P (for Paper) or N (for Notes). Some of the Papers have already been published or I intend to submit them for publication. Others I will simply leave here, at least for the time being.

Where available, after each abstract there are links to various forms of each of that document. The directory contains all of the available documents,

(23P) The Ackermann functions are not optimal, but by how much?

Abstract: The Ackermann functions are examples of functions that are not primitive recursive but are clearly recursive in some sense. I show that these functions are far from being optimal examples of this phenomenon.

25 pages

Paper can be found at Ackermann.pdf

(22P) Fruitful and helpful ordinal functions

Abstract: This is a companion to (03P) A comparison of two systems or ordinal notations'. In it I set down some of the details that are missing from that paper. Some of the material is extracted from (04P).

19 pages

Preliminary version from FruitHelp.dvi. or FruitHelp.ps.gz or FruitHelp.pdf

(21P) Regularity, fitness, and the block structure of frames

Abstract: I study the point-free and point-sensitive aspects of regularity, fitness, and subfitness, and the difference between these notions, and the relationships with other separation properties. Several open problems are stated.

31 pages

Preliminary version from Fitness.dvi.

(20P) Examples of the Cantor-Bendixson process on the reals

Abstract: The Cantor-Bendixson rank of the reals is no bigger than $\Omega$, the first uncountable ordinal. In this note I construct for each countable ordinal a set of rational numbers that is closed in the reals and scattered with CB-rank the nominated ordinal.

9 pages

Full document from CB-examples.dvi or CB-examples.ps.gz or CB-examples.pdf.

(19P) A new' lambda-abstraction algorithm
(with M. Price)
A short 3 page account of an algorithm that seems to have been forgotten.

Preliminary version from Lambda-abstraction.dvi.

(18P) Topologically valued transition structures
(with M. Collinson)
being written.

(17P) A coverage construction of the reals and the irrationals

Abstract: There is a standard use of the coverage technique to construct the space of real numbers from the set of rationals (as a linearly ordered set). I modify that coverage to obtain a parallel construction of the irrationals. The only novelty with this second construction is that nobody seems to have done it before. However, we do get a bonus. Each coverage construction has a rank, a closure ordinal, which is an indication of the complexity of the constructed space. That of the reals is $\omega+1$, whereas that of the irrationals is $\Omega$ (the first uncountable ordinal).

This paper appeared in Annals of Pure and Applied Logic 145 (2007) 176-203.

The link is to a version in a larger page size with the typos corrected.

33 pages

Full document from Irrationals.pdf.

(16P) An ordinal indexed hierarchy of separation properties
(with R. Sexton).

Abstract: We show that the difference between $T_3$ to $T_2$ can be abstracted and repeated to produce an ordinal indexed sequence of new separation properties below $T_2$ and somewhat above $T_1$. The nature of these new properties is concerned with the behaviour of the compact saturated sets of the space, and is related to the properties the associated patch space and the Vietoris hyperspace. We indicate, by examples, that the hierarchy progresses through all the ordinals.

This paper appeared in Topology and its Applications 30 No 2 (2006) 586-625.

The link is to a version in a larger page size.

31 pages

Full document from SeparationProps.pdf.

(15P) The extended Cantor-Bendixson analysis of trees

Abstract: The standard CB-process can be set up in a point-free context, and lifted to the higher level assemblies to obtain a topological analogue of the Gabriel dimension of an abelian category. (This has been known some people for many years but, apparently, not others who should have taken more notice.) Exactly what this measures for a topological space is not at all clear, but it is concerned with the nature of the higher level assemblies of the topology. I examine what it does for the Alexandroff topology on a tree, and find that it gives a generalization of the Hausdorff analysis of linearly ordered sets. The seemingly severe restrictions on the space make it possible to carry out various calculations.
[This paper was originally written many years ago, but has been rewritten and shortened.]

26 pages

Full document from CB-analysis.dvi or CB-analysis.ps.gz or CB-analysis.pdf.

(14N) The Vietoris modifications of a frame

Abstract: There are many different point-sensitive V-modifications (hyperspaces) of a topological space $S$, the two most common being carried by the family $QS$ of compact saturated subsets of $S$ and the family $LS$ of compacts lenses of $S$. There is also a more recent and less well known point-free version. In its most general version this converts a frame into a second frame but can be used to convert a space $S$ into a space $VS$. These notes set down the basic properties as they relate to the construction of points. There is a generous selection of examples.

79 pages including 21 pages of examples and 2 pages of open questions

Full document from Vietoris.dvi or Vietoris.ps.gz or Vietoris.pdf.

(13N) The tensor product of commutative monoids

Abstract: One of our research students came across a cryptic remark concerning these gadgets and asked me to explain it to him. Since I didn't know the details and didn't know a reference to the details, I wrote this short set of notes.

12 pages

Full document from TPoCM.dvi or TPoCM.ps.gz or TPoCM.pdf.

(12N) The topos of actions on a monoid

Abstract: A topos is a certain kind of category with origins in algebraic geometry but now used for several other purposes. The category of presheaves on a category is a topos. In particular, the category of presheaves on a 1-object category (a monoid) is a topos. These notes give an algebraic account of such a topos.

38 pages

Full document from Rsets.dvi or Rsets.ps.gz or Rsets.pdf.

(11N) The coverage technique for enriched posets.

Abstract: The coverage technique is used to convert a poset (perhaps with some extra structure) into a complete poset of a certain kind, usually a frame or quantale. These notes describe the basics of the method with a decent selection of examples. Especially written for the hard of hearing.

84 pages including 40 pages of examples
More information on one of these examples is given in (17P).

Full document from Coverage.dvi or Coverage.ps.gz or Coverage.pdf.

(10N) Forms of recursion and induction

Abstract: A brief introduction to subrecursive hierarchies and related topics, but not intended as a detailed account. The notes deal with such topics as the various kinds of recursions (over the natural numbers), the primitive recursive functions and the way these are stratified, the complexities beyond primitive recursion as can be generated by jump operators.
[These notes were written originally as part of a lecture course, but not used. They are, therefore, little more than a first draft. I may have an opportunity some time in the future to re-work them.]

60 pages + 17 pages of solutions

Full document from FormsRec.dvi or FormsRec.ps.gz or FormsRec.pdf.

(09N) While loops and programs

Abstract: A short introduction to the denotational semantics of While loops. These are little more than a first draft.

29 pages + 6 pages + 8 pages of solutions

Full document from While.dvi or While.ps.gz or While.pdf.

(08N) Domains for recursion

Abstract: A short introduction to domains from various forms of recursion over the natural numbers.

19 pages + 14 pages of solutions

Full document from Domains.dvi or Domains.ps.gz or Domains.pdf.

(07P) Tiering as a recursion technique

Abstract: I survey the syntactic technique of tiering which can be used to restrict the power of a recursion scheme. I show how various results can be obtained entirely proof theoretically without the use of a model of computation. The essence of the method is to move between explicit numerals and simulated (Church) numerals.

To appear Bulletin of Symbolic Logic.

Preliminary version from Tiering.ps.gz [This version may not be exactly the same as the journal version. Eventually there will also be a longer account of this material as a set of notes.]

(06N) The point-free approach to sheafification

Abstract: Let $\Omega$ be an arbitrary frame, and consider the category $\mathsf{Psh}(\Omega)$ of presheaves on $\Omega$ and the and the category $\mathsf{Set}(\Omega)$ of $\Omega$-sets. There are various other associated categories and functors between them. I describe these with emphasis on the functor which separates a presheaf and the functor that sheafifies a presheaf.

49 pages + 13 pages of solutions

Full document from Omegasets.dvi or Omegasets.ps.gz or Omegasets.pdf.

Eventually the following three items will be absorbed into a longer account of the whole material, see [***]

(05P) An applied $\lambda$-calculus for iteration templates

Abstract: Let $\lambdaH$ be the term calculus of Howard's system of constructive ordinals. I use this to name iteration gadgets (generalized ordinal notations). I isolate a family of higher order ordinal functions which give a partial semantics of $\lambdaH$. I indicate how $\lambdaH$ provides an intrinsic measure of each ordinal below the Howard ordinal.

30 pages

Full document from Applied-l-calc.dvi or Applied-l-calc.ps.gz.

(04P) Derivatives for ordinal functions and the Sch\"utte brackets

Abstract: I develop the notion of a derivative, an operator which converts a normal function into a (faster) normal function. I show how these can be constructed using higher order fixed point extractors, and I develop some evaluation techniques. As an illustrations I show how the Sch\"utte brackets produce a large family of derivatives.

30 pages

Full document from Derivatives.dvi or Derivatives.ps.gz.

(03P) A comparison of two systems of ordinal notations

Abstract: I show how the Bachmann method of generating countable ordinals using uncountable ordinals can be replaced by the use of higher order fixed point extractors available in the term calculus of Howard's system of constructive ordinals. This leads to a notion of the intrinsic complexity of a notated ordinal analogous to the intrinsic complexity of a numeric function described in G\"odel's $T$.
[This web version may contain material that is not in the journal version.]

Archive for Math. Logic 43 (2004) 65--63.

Full document from Comparison.dvi or Comparison.ps.gz.

(02P) Point-sensitive and point-free patch constructions
(with R. A. Sexton)

Abstract: Using the category of frames we consider various generalizations of the patch space of a topological spaces. Some of these are old and some are new constructions. We consider how these variants interact and under what circumstances they agree.

35 pages -->

Full document from Patch.dvi or Patch.ps.gz or Patch.pdf.

(01P) Monoid based semantics for linear formulas
(with W. P. R. Mitchell)

Abstract: Each Girard quantale (i.e. commutative quantale with a selected dualizing element) provides a support for a semantics for linear propositional formulas (but not for linear derivations). Several constructions of Girard quantales are known. We give two more constructions, one using an arbitrary partially ordered monoid and one using a partially ordered group (both commutative). In both cases the semantics can be controlled be a relation between pairs of elements of the support and formulas. This gives us a neat way of handling duality.

Journal of Symbolic Logic, 66 (2001) 1597--1619 [in corrupted form]; 67 (2002) 505--527 [in uncorrupted form]

Full document from MonSem.dvi or MonSem.ps.gz.

Harold Simmons