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.