Logic Computation Hierarchies Vasco Brattka Editor Hannes Diener Editor Dieter Spreen Editor

Logic Computation Hierarchies Vasco Brattka
Editor Hannes Diener Editor Dieter Spreen Editor
download
https://ebookbell.com/product/logic-computation-hierarchies-
vasco-brattka-editor-hannes-diener-editor-dieter-spreen-
editor-50990754
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Logic Computation Hierarchies Vasco Brattka Hannes Diener Dieter
Spreen
https://ebookbell.com/product/logic-computation-hierarchies-vasco-
brattka-hannes-diener-dieter-spreen-5424606
Logic Computation And Rigorous Methods Essays Dedicated To Egon Brger
On The Occasion Of His 75th Birthday Lecture Notes In Computer Science
12750 1st Ed 2021 Alexander Raschke Editor
https://ebookbell.com/product/logic-computation-and-rigorous-methods-
essays-dedicated-to-egon-brger-on-the-occasion-of-his-75th-birthday-
lecture-notes-in-computer-science-12750-1st-ed-2021-alexander-raschke-
editor-34004368
Logic Computation And Set Theory Published As Logic Induction And Sets
Thomas Forster
https://ebookbell.com/product/logic-computation-and-set-theory-
published-as-logic-induction-and-sets-thomas-forster-1214188
Logic Meaning And Computation Essays In Memory Of Alonzo Church 1st
Edition Peter Apostoli Auth
https://ebookbell.com/product/logic-meaning-and-computation-essays-in-
memory-of-alonzo-church-1st-edition-peter-apostoli-auth-2325958

Logic And Computation Rzvan Diaconescu
https://ebookbell.com/product/logic-and-computation-rzvan-
diaconescu-50112446
Logic And Computation Rzvan Diaconescu
https://ebookbell.com/product/logic-and-computation-rzvan-
diaconescu-50655768
Mathematical Logic And Computation Jeremy Avigad
https://ebookbell.com/product/mathematical-logic-and-computation-
jeremy-avigad-45946756
Puzzles In Logic Languages And Computation The Red Book Radev
https://ebookbell.com/product/puzzles-in-logic-languages-and-
computation-the-red-book-radev-20009654
Proof Computation And Agency Logic At The Crossroads 1st Edition John
N Crossley Auth
https://ebookbell.com/product/proof-computation-and-agency-logic-at-
the-crossroads-1st-edition-john-n-crossley-auth-2148220

Logic, Computation, Hierarchies

Ontos Mathematical Logic
Edited by
Wolfram Pohlers, Thomas Scanlon,
Ernest Schimmerling, Ralf Schindler,
Helmut Schwichtenberg
Volume 4

Logic,
Computation,
Hierarchies
Edited by
Vasco Brattka, Hannes Diener, Dieter Spreen

ISBN 978-1-61451-783-2
e-ISBN 978-1-61451-804-4
ISSN 2198-2341
Library of Congress Cataloging-in-Publication Data
A CIP catalog record for this book has been applied for at the Library of Congress.
Bibliographic information published by the Deutsche Nationalbibliothek
The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie;
detailed bibliographic data are available on the Internet at http://dnb.dnb.de.
© 2014 Walter de Gruyter Inc., Boston/Berlin
Printing: CPI books GmbH, Leck
♾ Printed on acid-free paper
Printed in Germany
www.degruyter.com

Victor Selivanov, Würzburg, 2013¹
1Reproduced with permission of Ernestina Selivanova.

Preface
Computability and hierarchies are the leading themes of Victor Selivanov’s scien-
tifc work. As a student he got interested in mathematical logic mainly because
of being dissatisfed with the level of rigour in the mathematical analysis lectures
he followed. Today, he is regarded as a world-expert in hierarchy theory, with his
publications having been highly infuential. This volume is dedicated to Victor on
the occasion of his 60th birthday.
The idea for this Festschrift was born during a workshop in Novosibirsk in
honour of him and the splendid birthday party afterwards. We asked collaborators
and friends of his to contribute to a book that also should refect the width of his
scientifc interests. The result is a collection of 17 refereed articles written by 23
authors.
We would like to thank all that helped to produce this volume of high scien-
tifc standard. These are of course the authors, but also the referees. Their careful
reading of the manuscripts and critical remarks made a crucial contribution. Spe-
cial thanks go to Svetlana Selivanova for answering questions on bibliographical
data.
Cape Town, Christchurch, Munich, Pretoria, Siegen, Winter 2013/14
Vasco Brattka¹
Hannes Diener²
Dieter Spreen³
1Faculty of Computer Science, Universität der Bundeswehr, Munich, Germany, and Department
of Mathematics and Applied Mathematics, University of Cape Town, South Africa
2
Department of Mathematics, University of Siegen, Germany, and Department of Mathematics
and Statistics, University of Canterbury, Christchurch, New Zealand
3
Department of Mathematics, University of Siegen, Germany, and Department of Decision Sci-
ences, University of South Africa, Pretoria, South Africa

Contents
PrefacefVII
Dieter Spreen
The Life and Work of Victor L. Selivanovf1
Collins Amburo Agyingi, Paulus Haihambo, and Hans-Peter A. Künzi
Tight Extensions ofT
f-Quasi-Metric Spacesf9
Klaus Ambos-Spies
On the Strongly Bounded Turing Degrees of Simple Setsf23
Matthew de Brecht
Levels of Discontinuity, Limit-Computability, and Jump Operatorsf79
Jacques Duparc, Olivier Finkel, and Jean-Pierre Ressayre
The Wadge Hierarchy of Petri Netsω-Languagesf109
Willem L. Fouché
Diophantine Properties of Brownian Motion: Recursive Aspectsf139
Sy-David Friedman
The Completeness of Isomorphismf157
Peter Hertling, Victor Selivanov
Complexity Issues for Preorders on Finite Labeled Forestsf165
Anton Konovalov
Boolean Algebras of Regular Quasi-aperiodic Languagesf191
Eryk Kopczyński, Damian Niwiński
A Simple Indeterminate Infnite Gamef205
Luca Motto Ros, Philipp Schlicht
Lipschitz and Uniformly Continuous Reducibilities on Ultrametric Polish
Spacesf213

Xf Contents
Sergey Odintsov
On the Equivalence of Paraconsistent and Explosive Versions of Nelson
Logic259
Svetlana Selivanova
Computing Clebsch-Gordan Matrices with Applications in Elasticity
Theory273
Nikolay V. Shilov
An Approach to Design of Automata-Based Axiomatization for Propositional
Program and Temporal Logics (by Example of Linear Temporal Logic)297
Dieter Spreen
Partial Numberings and Precompleteness325
Dieter Spreen
An Isomorphism Theorem for Partial Numberings341
Ludwig Staiger
Two theorems on the Hausdorf measure of regularω-languages383
Anton V. Zhukov
Some Notes on the Universality of Three-Orders on Finite Labeled
Posets393
Index411

Dieter Spreen
The Life and Work of Victor L. Selivanov
ff
Dieter Spreen:
Department of Mathematics, University of Siegen, Germany, and Department of
Decision Sciences, University of South Africa, Pretoria, South Africa
Victor L. Selivanov was born on the 25th of August, 1952, in Oktyabr’sky, a small
industrial city in the Republic of Bashkortostan (Russian Federation), near the
border with Tatarstan. He was the fourth (and youngest) child in his family. His
parents Lev N. Selivanov and Lidya G. Selivanova both worked as mathematics
teachers at a college in Oktyabr’sky.
He graduated with honours from Kazan State University (1974) and became
a postgraduate student of M.M. Arslanov and R.G. Bukharayev in Kazan. In 1979
he was awarded a Ph.D. in Mathematics from Novosibirsk University. The title of
the thesis was “On computable numberings”. Victor defended his habilitation the-
sis “Hierarchical classifcation of arithmetical sets and index sets” at the Institute
of Mathematics of the Siberian Devision of the Russian Academy of Sciences in
Novosibirsk in 1989.
After spending a few years (1978–82) as Assistant Professor, frst at Ulyanovsk
Polytechnic Institute and then at Kazan Institute of Chemical Technology, he
moved to Novosibirsk State Pedagogical University, where he was Senior Lecturer
(1982–86), Docent (1986–90), Professor (1990–91) and Head of the Chair of In-
formatics and Discrete Mathematics (1991–2009). In 1993 he was appointed Full
Professor. Since 2009 he is Chief Research Fellow at the A.P. Ershov Institute of
Informatics Systems of the Siberian Devision of the Russian Academy of Sciences.
Selivanov’s research started in 1974 when he became a postgraduate student
at Kazan State University. It is devoted to Mathematical Logic, Computer Science,
and Didactics of Mathematics and Informatics. The main focus of his research is
computability, ranging from general computability theory to automata theory. In
the beginning his main contributions were in numbering theory. Later he shifted
to the study of hierarchies, which is still his central interest.
Numbering Theory
In his Ph.D. thesis he (i) proved that any nontrivial semilattice of computable num-
berings is not a lattice; (ii) constructed an example of a discrete, but not efectively
discrete family of total recursive functions having a unique (up to equivalence)

2f Dieter Spreen
computable numbering; (iii) constructed an example of a non-discrete family of
computably enumerable sets having a unique (up to equivalence) computable
numbering. The results answers well known questions on computable number-
ings [1; 2; 3; 4; 5]. Result (ii) was later applied in learning theory.
In addition, he proved several facts on degrees of unsolvability, among oth-
ers he classifed the possible versions oftt-reducibilities (a result that was in-
dependently obtained by Bulitko) and completely described the relationship be-
tween the Ershov hierarchy and the high-low hierarchy of degrees of unsolvability
[9; 16; 18; 25]. This was independently discovered by Jockusch and Shore.
Selivanov also developed a relativized version of the theory of precomplete
and complete numberings which led to priority-free proofs of several known re-
sults about the structure oftt-type degrees and aboutm-degrees of index sets in
such structures [17; 19; 26; 29].
In the beginning of the 1990s, Selivanov obtained general results on positively
numbered Boolean algebras, part of them jointly with Odintsov [21; 24]. The main
results are that this class of Boolean algebras always has a good computable num-
bering (an analog of the numbering of the computably enumerable sets) and that
there is a unique (up to efective isomorphism) universal positive Boolean alge-
bra (an analog of the creative sets). He also characterized many natural and im-
portant index sets of positive Boolean algebras. Later some of these results were
extended by him to the very general context of recursively axiomatizable quasiva-
rieties [29; 34]. This research has diferent applications, e.g. to the classifcation of
many natural index sets in the lattice of computably enumerable sets, in the semi-
lattice of computably enumerablem-degrees and in the Lindenbaum algebra of
propositions [21; 22; 24; 28; 29; 34].
Hierarchies in Computability Theory
As is well known, the Ershov diference hierarchy is closely related to the so called
m-jump operator. In his habilitation thesis Selivanov defned and investigated sev-
eral generalizations of this operator. It turned out that the generalized operators
are closely related to the theory of complete numberings developed by Mal’cev and
Ershov, and to the study of structures ofm-degrees of index sets of the computably
enumerable sets as well as the partial recursive functions. The results led to a sim-
plifcation and generalization of results by Hay about index sets [8; 11; 13; 15].
Selivanov, moreover, defned a refnement of the arithmetic hierarchy called
the fne hierarchy and proved that it contains many known hierarchies and has
some rather strong closure properties with respect to refnements. These results
informally mean that the fne hierarchy is in some sense the fnest possible. Later,

The Life and Work of Victor L. Selivanovf 3
using set-theoretic operations introduced by Wadge, he gave a set-theoretical de-
scription of the fne hierarchy. This yields the possibility of defning the hierarchy
in very diferent contexts, e.g. in the context of logic and descriptive set theory.
In the latter case, he could show that the fne hierarchy is, in an exact sense, the
fnite version of the Wadge hierarchy of Borel sets [13; 15; 20; 23; 24; 27; 28]. These
results are also part of his habilitation thesis.
He extended the fne hierarchy from the case of sets to the case ofk-partitions
[52]. With heavy use of Priestley duality he showed that the methods of alternating
trees and ofm-reducibilities developed earlier by Addison, by him, and by others
for concrete examples of fne hierarchies apply to a broad class of fne hierarchies.
Selivanov gave a complete description of analogs of the famous Rice-Shapiro
theorem for all levels of the arithmetic hierarchy (as well as of some of its refne-
ments). Another principal result is a complete description ofm-degrees of index
sets of the predicates which are frst-order defnable in the Lindenbaum algebra
of statements of nontrivial signature. Note that this classifcation needs all levels
of the fne hierarchy, i.e., it could not be achieved without the invention of the fne
hierarchy (see [6; 7; 8; 10; 11; 12; 14; 20; 22; 24]).
Hierarchies in Complexity Theory
In the context of structural complexity theory Selivanov defned and considered
analogs of the hierarchies mentioned above. He was able to extend the well-
known result of Kadin about the non-collapse of the Boolean hierarchy overNP
to a much richer hierarchy, called the plus-hierarchy [27; 31]. Further work in this
direction, essentially developed jointly with Glasser and Reitwiessner [51], led
to the solution of long-standing open problems such as a question by Blass and
Gurevich on the status of the shrinking property (also known as the reduction
property) for levels of the polynomial hierarchy.
Hierarchies in Language Theory
Selivanov also used the fne hierarchy to classify regularω-languages. It turned
out that the resulting classifcation coincides with the Wagner hierarchy. This re-
sult establishes a close relationship between descriptive set theory and the the-
ory of regularω-languages. It leads to rather diferent proofs of deep and com-
plicated results of Wagner [30]. This investigation seems to have been the frst
applications of modern descriptive set theory to the theory ofω-languages, a line
which was also developed by French mathematicians such as Perrin, Carton, Du-

4f Dieter Spreen
parc and Finkel. Recently, Selivanov classifed the Wadge degrees ofω-languages
of deterministic Turing machines [35]. In this way he answered a question raised
by Duparc.
In pursuing this research Selivanov developed a complete analog of the Wag-
ner hierarchy for the class of regular star-freeω-languages [42]. He also extended
the Wagner hierarchy from the case of sets to the case ofk-partitions which, for
k>
2, leads to a much more complicated but still tractable structure of degrees
[53; 56]. Jointly with Wagner, he comprehensively investigated complexity ques-
tions related to his hierarchy [41].
Further on, he proposed a new, logical approach to the well known problem
of the decidability of the dot-depth hierarchy and of some its refnements. In this
way, he obtained quite diferent and shorter proofs of important results, as well
as new results on analogs of the dot-depth problem. Some of these results were
obtained independently and by other methods by Glasser, Schmitz and Wagner.
Using some previous results on the so called leaf languages, he established a deep
connection of these automata-theoretic hierarchies with the complexity-theoretic
ones mentioned above [32; 33].
In joint work with Wagner [38] the above-mentioned results were applied to
defning and investigating a reducibility on star-free languages which fts perfectly
to the dot-depth hierarchy. Both established a close relationship of this reducibil-
ity with the leaf-language approach to complexity classes. This research was ex-
tended to quasi-periodic languages, which form another important class of regu-
lar languages. [47].
Hierarchies in Descriptive Set Theory
Selivanov picked up an old problem of Scott and developed a rather comprehen-
sive theory of Borel and diference hierarchies in so calledφ-spaces, which are
topological counterparts of algebraic directed-complete partial orderings, and a
theory of Wadge reducibility in such spaces. In a sense this theory parallels the
corresponding classical theory for Polish spaces. The theory has non-trivial appli-
cations to classicalω-ary Boolean operations of Kantorovich and Livenson and is
closely related to the theory of infnitary languages, i.e. languages that may con-
tain both, fnite and infnite words [36; 37; 39; 44]. The extension is very natural
and suggests new interesting ways of extending classical descriptive set theory.
Recently, the descriptive set theory forφ-spaces was extended by de Brecht,
Becher and Grigorief to some broader natural classes of spaces.
The theory was partially extended from the case of sets to the case ofk-par-
titions [40; 43; 44; 48]. Jointly with Motto Ros and Schlicht, Selivanov extended

The Life and Work of Victor L. Selivanovf 5
the classical Wadge theory to the broader class of quasi-Polish spaces [57], and
together with Schröder [58] he introduced and studied hierarchies of topological
spaces that include well known classes of spaces as the quasi-Polish spaces and
the Kleene-Kreisel continuous functionals.
New methods to study frst order defnability in countable structures were de-
veloped which apply to structures on words and labeled trees [45; 46; 49; 50; 54;
55]. As a consequence comprehensive defnability results for degree structures nat-
urally arising in topology and computable analysis were obtained, in particular,
for initial segments of the Wadge and Weihrauch degrees ofk-partitions. This pro-
vides frst steps in the development of degree theory for topological structures in
parallel to the classical degree theory for discrete structures.
Many of Selivanov’s mathematical ideas have been taken up and developed
further by other mathematicians. His results found their way into monographs
and textbooks in computability and formal language theory, as well as in hand-
books. In addition to his interest in the foundations of mathematics and computer
science Selivanov has developed a strong interest in didactics. Here, his main aim
was to create new and more efcient methods of teaching mathematics and in-
formatics to students of diferent specialties and diferent qualifcations. He pro-
duced methods for teaching basic skills of ofce software, and found ways of in-
troducing algorithmics to school children, and conveying fundamentals of visual
programming as well as elements of computer modeling in secondary and high
school.
Selivanov has supervised 9 Ph.D. theses and many master dissertations. He
is the author of about 100 publications as well as several textbooks and didactic
materials of diferent kind in Algebra, Logic, Informatics, and Didactics of Infor-
matics.
His work was honoured by a Humboldt Fellowship, Visiting Professorships
in Siegen and Paris, as well as two Mercator Professorships by the German Re-
search Foundation. He was awarded the honorary title “Merited Worker of the
High School” of the Russian Government in 1999 and the honorary title “Merited
Worker of Science and Technology of the Russian Federation” by the Ministry of
Science and Education of the Russian Federation in 2012.
Thanks to generous funding by the Austrian Science Fund, the German Aca-
demic Exchange Service, the German Research Foundation, the Russian Founda-
tion for Basic Research and, more recently, the European Union Selivanov was
an ever-welcome guest in Aachen, Cambridge, Darmstadt, Heidelberg, Munich,
Siegen, Swansea, Vienna, and Würzburg.

6f Dieter Spreen
Bibliography
[1]On numberings of families of total recursive functions. Algebra and Logic, 15, N 2 (1976),
128–141.
[2] Two theorems on computable numberings. Algebra and Logic, 15, N 4 (1976), 297–306.
[3]
On computability of some classes of numberings. Prob. Methods and Cybernetics, v.12-13,
Kazan University, Kazan,1976, 157–170 (Russian).
[4]
Numberings of canonically computable families of fnite sets. Sib. Math. J., 18, N 6 (1977),
1373–1381 (Russian, there is an English translation).
[5]
Some remarks on classes of recursively enumerable sets. Sib. Math. J., 19, N 1 (1978),
109–115.
[6]
On index sets of classes of numberings. Prob. Methods and Cybernetics, v.14, Kazan
University, Kazan,1978, 90–103 (Russian).
[7]
On index sets of computable classes of fnite sets. In: Algorithms and Automata, Kazan
University, Kazan,1978, 95–99 (Russian).
[8] On the structure of degrees of index sets. Algebra and Logic, 18, N 4 (1979), 286–299.
[9]
On a class of reducibilities in recursion theory. Prob. Methods and Cybernetics, v.14,
Kazan University, Kazan, v. 18 (1982), 83–101 (Russian).
[10]
On index sets in the Kleene-Mostowski hierarchy. Trans. Inst. Math., Novosibirsk, N 2
(1982), 135–158 (Russian).
[11]
On the structure of degrees of generalized index sets. Algebra and Logic, 21, N 4 (1982),
316–330.
[12]
Efective analogs ofA-,B-, andCs-sets with applications to index sets. Prob. Methods
and Cybernetics, v.14, Kazan University, Kazan, v. 19 (1983), 112–128 (Russian).
[13]
Hierarchies of hyperarithmetical sets and functions. Algebra and Logic, 22, N 6 (1983),
473—491.
[14] Index sets in the hyperarithmetical hierarchy. Sib. Math. J., N 3 (1984), 474–488.
[15] On a hierarchy of limiting computations. Sib. Math. J., 25, No 5 (1984), 798–806.
[16] On Ershov hierarchy. Sib. Math. J., 26, N 1 (1985), 105–116.
[17]
Index sets of factor-objects of the Post numbering. Algebra and Logic, 27, N 3 (1988),
215–224.
[18] Ershov hierarchy and Turing jump. Algebra and Logic, 27 N 4 (1988), 292–301.
[18]
On algorithmic complexity of algebraic systems. Math. Notes, 44, No 5–6 (1988) p.944–
950.
[19]
Applications of precomplete numberings to tt-type degrees and to index sets. Algebra
and Logic, 28, N 1 (1989), 51–56.
[20]
Fine hierarchies of arithmetical sets and defnable index sets. Trans. Inst. Math., Novosi-
birsk, 12 (1989), 165–185 (Russian).
[21]
Arithmetical hierarchy and ideals of numbered boolean algebras (jointly with S.P.
Odintsov). Sib. Math. J., 30, N 6 (1989), 140–149 (Russian, there is an English transla-
tion).
[22]
Index sets of classes of hyperhypersimple sets. Algebra and Logic, 29, N 2 (1990), 155–
168.
[23] A fne hierarchy of formulas. Algebra and Logic, 30, N 5 (1991), 368–378.
[24] Fine hierarchies and defnable index sets. Alg. and Logic, 30, N 6 (1991), 463–475.
[25] Jumps of some classes of sets. Math. Notes, 50, No 6 (1991), p.1299–1300.

The Life and Work of Victor L. Selivanovf 7
[26]Precomplete numberings and functions without fxed points. Math. Notes,Math. Notes,
51, No 1 (1992), p.95–99.
[27]
Fine hierarchies and Boolean terms. The Journal of Symbolic Logic, 60, N 1 (1995), 289–
317.
[28]
Fine hierarchy and defnability in the Lindenbaum algebra. In: Logic: from foundations to
applications, Proceedings of the Logic Colloquium-93 in Keele. Oxford, 1996, 425–452.
[29]
On recursively enumerable structures. Annals of pure and applied logic, 78 (1996), 243–
258.
[30] Fine hierarchy of regular omega-languages. Theor. Computer Science, 191 (1998), 37–59.
[31] Refning the polynomial hierarchy. Algebra and Logic, 38 (1999), N 4, 248–258.
[32]
Relating automata-theoretic hierarchies to complexity-theoretic hierarchies.Theoret.
Informatics Appl., 36 (2002), 29–42.
[33]
On decidability of classes of hierarchies of regular aperiodic languages.Algebra and
Logic,41, N 5 (2002), 337–348.
[34]
Positive structures. In:Computability and Models, Perspectives East and West, S. Barry
Cooper and Sergei S. Goncharov, eds., Kluwer Academic / Plenum Publishers, New York,
2003, 321–350.
[35]
Wadge degrees ofω-languages of deterministic Turing machines.Theoretical Informatics
and Applications, 37 (2003), 67–83.
[36] Diference hierarchy inφ-spaces.Algebra and Logic, 43, N 4 (2004), 238–248.
[37] Hierarchies inφ-spaces and applications.Math. Logic Quarterly, 51, N 1 (2005), 45–61.
[38]
A reducibility for the dot-depth hierarchy (jointly with K.W. Wagner).Theoretical Computer
Science, 345, N 2-3 (2005), 448–472.
[39]
Towards a descriptive set theory for domain-like structures.Theoretical Computer Sci-
ence, 365 (2006), 258–282.
[40]
The quotient algebra of labeled forests modulo h-equivalence.Algebra and Logic,46,N2
(2007), 120–133.
[41]
Complexity of topological properties of regularω-languages (jointly with K.W. Wagner).
Fundamenta Informaticae, 83(1-2): 197–217 (2008).
[42]
Fine hierarchy of regular aperiodicω-languages.International Journal of Foundations of
Computer Science, 19, No 3 (2008) 649–675.
[43]
Wadge reducibility and infnite computations.Mathematics in Computer Science,2
(2008), 5–36 doi: 10.1007/ s11786-008-0042-x
[44]
On the diference hierarchy in countably basedT0-spaces. Electronic Notes in Theoretical
Computer Science, V. 221 (2008), 257-269, doi: 10.1016/ j.entcs. 2008.12.022.
[45]
Defnability in theh-quasiorder of labeled forests (jointly with O.V. Kudinov and A.V.
Zhukov). Annals of Pure and Applied Logic, 159(3): 318–332 (2009). doi: 10.1016/ j.apal.
2008.09.026.
[46]
Undecidability in Some Structures Related to Computation Theory. Journal of Logic and
Computation, 19, No 1 (2009), 177–197; doi: 10.1093/ logcom/exn023
[47]
Hierarchies and reducibilities on regular languages related to modulo counting.RAIRO
Theoretical Informatics and Applications, 41 (2009), 95–132. DOI: 10.1051/ ita:2007063
[48]
On the Wadge reducibility of k-partitions. Journal of Logic and Algebraic Programming, 79,
No 1, 2010, 92–102. PII: S1567-8326(09)00024-1 DOI: 10.1016/ j.jlap.2009. 02.008
[49]
Defnability of closure operations in the h-quasiorder of labeled forests (jointly with Oleg
Kudinov and Anton Zhukov). Algebra and Logic, 49, No 2 (2010), 181–194.

8f Dieter Spreen
[50]
Defnability in the subword order (jointly with O.V. Kudinov and L.V. Yartseva). Siberian
Mathematical Journal, 51, No 3 (2010), 575–583.
[51]
The Shrinking Property for NP and coNP (jointly with C. Glasser and C. Reitwiessner).
Theoretical Computer Science 412 (2011), 853-864.
[52]
Fine hierarchies via Piestley duality. Annals of Pure and Applied Logic, 163 (2012) 1075-
1107, doi:10.1016/j.apal.2011.12.029
[53]
Complexity of aperiodicity for topological properties of regularω-languages (jointly with
K.W. Wagner). Conf. Computability in Europe-2008Lecture Notes in Computer Science, v.
5028. Berlin: Springer, 2008, 533–543.
[54] A Gandy theorem for abstract structures and applications to frst-order defnability (jointly
with O.V. Kudinov). Proc. Of CiE-2009 (K. Ambos-Spies, B. Löwe and W. Merkle, eds.),
Lecture Notes in Computer Science, v. 5635. Berlin: Springer, 2009, 290–299.
[55]
Undecidability in Weihrauch degrees (jointly with O. Kudinov and A. Zhukov). Proc. of
CiE-2010 (F. Ferreira, B. Löwe, E. Mayordomo and L.M. Gomes, eds.), Lecture Notes in
Computer Science, v. 6158. Berlin: Springer, 2010, 256–265.
[56]
A fne nierarchy ofω-regulark-partitions. B. Löwe et.al. (Eds.): CiE 2011, LNCS 6735, pp.
260–269. Springer, Heidelberg (2011).
[57]
Wadge-like reducibilities on arbitrary quasi-Polish spaces (jointly with L. Motto Ros and P.
Schlicht). Accepted by Mathematical Structures in Computer Science, arXiv:1204.5338 v1
[mathLO] 24 Apr 2012.
[58]
Some hierarchies ofQCB0-spaces (jointly with M. Schröder). Mathematical Structures in
Computer Science, to appear.

Collins Amburo Agyingi, Paulus Haihambo, and
Hans-Peter A. Künzi
Tight Extensions ofT 0-Quasi-Metric Spaces¹
Abstract:Dress introduced and studied the concept of the tight span of a metric
space. It is known that Dress’s theory is equivalent to the theory of the injective
hull of a metric space independently discussed by Isbell some years earlier. In
a paper by Kemajou et al. it was shown that Isbell’s approach can be modifed
to work similarly forT
0-quasi-metric spaces and nonexpansive maps. Continuing
that work we show in the present paper that large parts of the theory developed
by Dress do not use the symmetry of the metric and - when appropriately modifed
- hold essentially unchanged forT
0-quasi-metric spaces.
Keywords:hyperconvexity;T
0-quasi-metric space; injective hull;q-hyperconvex,
tight extension, tight span
Mathematics Subject Classifcation 2010:AMS (2010) Subject Classifcations:
54D35; 54E15; 54E35; 54E55; 54E50
ff
Collins Amburo Agyingi, Paulus Haihambo, Hans-Peter A. Künzi:
Department of Mathematics
and Applied Mathematics, University of Cape Town, South Africa
fIntroduction
In [7] Isbell showed that every metric spaceXhas an injective hullT X,which is
compact ifXis compact. Let us also recall that a metric space is called hypercon-
vex (see e.g. [9, p. 78]) if and only if it is injective in the category of metric spaces
and nonexpansive maps. Dress [4] later gave an independent, but equivalent ap-
proach to Isbell’s theory that is based on the concept of a tight extension.
In analogy to Isbell’s theory Kemajou et al. [8] proved that eachT
0-quasi-
metric spaceXhas aq-hyperconvex hullQ
X,which is joincompact ifXis join-
compact. They called aT
0-quasi-metric spaceq-hyperconvex if and only if it is in-
jective in the category ofT
0-quasi-metric spaces and nonexpansive maps. In this
paper we intend to generalize results due to Dress [4] on tight extensions of met-
1The authors would like to thank the National Research Foundation of South Africa for partial
fnancial support. This research was also supported by a Marie Curie International Research Staf
Exchange Scheme Fellowship within the 7th European Community Framework Programme.

10− C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
ric spaces to the category ofT 0-quasi-metric spaces and nonexpansive maps. In
particular we show that large parts of the theory of tight extensions do not use the
symmetry of the metric and under appropriate modifcations still hold essentially
unchanged forT
0-quasi-metrics. The results of the present paper will be applied
in further investigations of the authors about endpoints inT
0-quasi-metric spaces
[2]. Hence it was necessary to develop the discussed theory below carefully in de-
tail, although it sometimes closely follows the classical metric theory.
−Preliminaries
This section recalls the most important defnitions that we shall use in the follow-
ing.
Defnition 1.LetXbe a set andd
:X×X→[0,∞)be a function mapping into
the set
[0,∞)of the nonnegative reals. Thendis aquasi-pseudometriconXif
(a)d
(x,x)=0wheneverx ∈X,and
(b)d
(x,z)≤d(x,y)+d(y,z)wheneverx,y,z ∈X.
We shall say that
(X,d)is aT 0-quasi-metric spaceprovided thatdalso satisfes
the following condition: For eachx,y
∈X,d(x,y)=0= d(y,x)implies that
x
=y.
Letdbe a quasi-pseudometric on a setX.Thend
−1
:X×X→[0,∞)defned by
d
−1
(x,y)=d(y,x)wheneverx,y ∈Xis also a quasi-pseudometric, called the
conjugate quasi-pseudometricofd.Note that ifdis aT
0-quasi-metric onX,then
d
s
= max{ d,d
−1
}=d∨d
−1
is a metric onX.
Let
(X,d)be a quasi-pseudometric space. For eachx ∈Xand−> 0,B
d(x,−)=
{
y∈X:d(x,y)<−}denotes theopen−-ball atx.The collection of all “open” balls
yields a base for a topologyτ
(d).It is called thetopology induced bydonX.
A mapf
:(X,d)→( Y,e)between quasi-pseudometric spaces is callediso-
metricprovided thatd
(x,y)=e(f(x),f(y))wheneverx,y ∈X.Note that each
isometric map with aT
0-quasi-metric domain is a one-to-one map.
A mapf
:(X,d)→(Y,e)between quasi-pseudometric spaces is callednon-
expansiveprovided thate
(f(x),f(y))≤d(x,y)wheneverx,y ∈X.
Given two nonnegative real numbersaandbwe shall writea
˙−bformax{a−
b,0},which in a more lattice-theoretic terminology we shall also denote by(a−
b)∨0.Note thatu (x,y)=x˙−ywithx,y ∈[0,∞)defnes the standardT 0-quasi-
metric on
[0,∞).

Tight Extensions ofT 0-Quasi-Metric Spaces( 11
For further basic concepts used from the theory of asymmetric topology we re-
fer the reader to [5] and [10]. Some recent work about quasi-pseudometric spaces
can be found in [1; 3; 11; 12; 14]. In the preprint [3] de Brecht for instance investi-
gates connections between the theory ofT
0-quasi-metric spaces and Victor Seliv-
anov’s work in descriptive set theory (see e.g. [15]).
(q-hyperconvex hulls ofT (-quasi-metric spaces
Next we recall some results mainly from [8] belonging to the theory of theq-
hyperconvex hull of aT
0-quasi-metric space.
Let
(X,d)be aT 0-quasi-metric space. We shall say that a function pairf =
(
f1,f2)on(X,d)wheref i:X→[0,∞)(i=1,2)isampleprovided thatd (x,y)≤
f2(x)+f1(y)wheneverx,y ∈X.
LetP
Xdenote the set of all ample function pairs on(X,d).(In such situations
we may also writeP
(X,d)in cases wheredis not obvious.) For eachf,g ∈PXwe
setD
(f,g)=sup
x∈X
(f1(x)˙−g1(x))∨sup
x∈X
(g2(x)˙−f2(x)).ThenDis an extended²
T
0-quasi-metric onP X.
We shall call a function pairfminimalon
(X,d)(among the ample function
pairs on
(X,d)) if it is ample and whenevergis ample on (X,d)and for eachx ∈X
we haveg
1(x)≤f1(x)andg 2(x)≤f2(x),³theng =f.It is well known that Zorn’s
Lemma implies that below each ample function pair there is a minimal ample
pair (for a more constructive and global approach, essentially due to Dress [4], see
Proposition 2 below). ByQ
Xwe shall denote the set of all minimal ample pairs on
(X,d)equipped with the restriction ofDtoQ X×QX,which we shall also denote by
D.Recall thatDis indeed a (real-valued)T
0-quasi-metric onQ X×QX[8, Remark
6].
Furthermoref
∈PXbelongs toQ Xif and only iff 1(x) = sup{ d(y,x)˙−f2(y):
y∈X}andf 2(x)=sup{ d(x,y)˙−f1(y):y∈X}wheneverx ∈X(see [11, Remark
2]).
It is known (see [8, Lemma 3]) thatf
∈QXimplies thatf 1(x)−f1(y)≤d(y,x)
andf 2(x)−f2(y)≤d(x,y)wheneverx,y ∈X:
2If we replace in the defnition of a quasi-pseudometric[0,∞) by[0,∞] we obtain the defni-
tion of anextendedquasi-pseudometric. Of course, the triangle inequality for extended quasi-
pseudometrics is interpreted in the self-explanatory way.
3For any function pairsfandgsatisfying this relation we shall writeg≤f.

12f C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
Indeed (compare [13, remark before Proposition 3.1]) givenx ∈Xwe have that
f
2(x)−d(x,x
f
) = sup{ d(x,y)˙−f1(y):y∈X}−d(x,x
f
)≤sup{ d(x
f
,y)˙−f1(y):
y∈X}=f2(x
f
).The inequality forf 1is verifed similarly.
Moreover
sup
x∈X
(f1(x)˙−g1(x)) = sup
x∈X
(g2(x)˙−f2(x))wheneverf,g ∈QX
(compare [8, Lemma 7]).
For eachx
∈Xwe can defne the minimal function pair
f
x(y)=(d(x,y),d(y,x))
(whenevery ∈X) on(X,d).The mapjdefned byx p˙fxwheneverx ∈Xdefnes
an isometric embedding of
(X,d)into(QX,D)(see [8, Lemma 1]).
We recall that
(QX,D)is calledtheq-hyperconvex hull of (X,d).AT 0-quasi-
metric spaceXis said to beq-hyperconvexiff
∈QXimplies that there is anx ∈X
such thatf
=fx(compare [8, Corollary 4]). For an intrinsic characterization of
q-hyperconvexity see [8, Defnition 2].
We also note thatD
(f,fx)=f1(x)andD (fx,f)=f2(x)wheneverx ∈Xand
f
∈QX[8, Lemma 8].
fTf-quasi-metric tight extensions
In this section we generalize some crucial results about tight extensions of metric
spaces from [4] to our quasi-metric setting.
Proposition 2.(compare [4, Section 1.9]) Let
(X,d)be aT 0-quasi-metric space.
There exists a retraction mapp
:PX→QX,i.e., a map that satisfes the conditions
(a)D
(p(f),p(g))≤D(f,g)wheneverf,g ∈PX.
(b)p
(f)≤fwheneverf ∈PX.
(In particularp
(f)=fwheneverf ∈QX,since eachfinQ Xis minimal, and
thuspindeed is a retraction.)
Proof.Given a pairf
∈PX,we setf
∗
1
(y)=sup{ d(x
f
,y)˙−f2(x
f
):x
f
∈X}whenever
y
∈Xandf
∗
2
(x)=sup{ d(x,y
f
)˙−f1(y
f
):y
f
∈X}wheneverx ∈X.
Claim 1:f
∗
≤f.
Note that for anyx,y
f
∈X,we haved (x,y
f
)≤f2(x)+f1(y
f
)and thusd (x,y
f
)−
f1(y
f
)≤f2(x).Thereforef
∗
2
(x) = sup{ d(x,y
f
)˙−f1(y
f
):y
f
∈X}≤f2(x).In a
similar manner, we can show thatf
∗
1
(y)≤f1(y)whenevery ∈X.Thusf
∗
≤f.
Claim 2:d
(x,y)≤f
∗
2
(x)+f1(y)andd (x,y)≤f2(x)+f
∗
1
(y)wheneverx,y ∈X.
Letx,y
∈X.We see thatsup{d(x,y
f
)˙−f1(y
f
):y
f
∈X}+f1(y)≥d(x,y)−
f1(y)+f1(y)=d(x,y).Similarly we haved (x,y)≤f2(x) + sup{ d(x
f
,y)˙−f2(x
f
):

Tight Extensions ofT 0-Quasi-Metric Spacesτ 13
x
τ
∈X}.Therefore we getd (x,y)≤f
∗
2
(x)+f1(y)andd (x,y)≤f2(x)+f
∗
1
(y)
wheneverx,y ∈X.
Defneq
:PX→PXbyf∞→q(f)=(
1
2
(f1+f
∗
1
),
12
(f2+f
∗
2
))wheneverf ∈PX.
Claim 3:q
(f)is indeed ample andq (f)≤f.
In fact
(q(f))2(x)+(q(f))1(y)=
1
2
(f1(y)+f
∗
1
(y))+
12
(f2(x)+f
∗
2
(x)) =
12
(f1(y)+
f
∗
2
(x)) +
12
(f
∗
1
(y)+f2(x))≥
12
d(x,y)+
1
2
d(x,y)=d(x,y)wheneverx,y ∈X.
This shows thatq
(f)is ample. Obviouslyq (f)≤f,sincef
∗
≤f.
Claim 4: We have thatD
(q(f),q(g))≤D(f,g)wheneverf,g ∈PX:
Letf,g ∈PXandx ∈X.Then
f
∗
1
(x)=sup{ d(y,x)˙−f2(y):y∈X}≤
sup{
d(y,x)˙−g2(y)+g2(y)˙−f2(y):y∈X}≤
sup{
d(y,x)˙−g2(y):y∈X}+ sup{ g2(y)˙−f2(y):y∈X}≤g
∗
1
(x)+D(f,g).
Therefore
sup
x∈X
((q(f))1(x)˙−(q(g))1(x))≤
1
2
sup
x∈X
(f1(x)˙−g1(x)) +
1
2
sup
x∈X
(f
∗
1
(x)˙−g
∗
1
(x))
≤
1
2
D(f,g)+
1
2
D(f,g)=D(f,g).
Similarly we can show that
sup
x∈X
((q(g))2(x)˙−(q(f))2(x))≤ D(f,g)whenever
f,g
∈PX.ThusD (q(f),q(g))≤D(f,g)wheneverf,g ∈PX.
In the rest of the proof, givenf
∈PX,we obtain a minimal ample function
pair belowfas the pointwise limit of the sequence
(q
n
(f))n∈Nwhereq
n
is then
th
-
iteration ofq
:
Fixf∈PX.Obviously forn ∈Nthen-iterationq
n
ofqyields a monotonically
decreasing sequence
(q
n
(f))that is bounded below by the0-pair.
Hence the mapp
(f) := limn→∞q
n
(f)exists, where we take the pointwise
limit pair with respect to the usual topologyτ
(u
s
)on[0,∞).
Note that obviously for eachn
∈N,q
n
(f)belongs toP Xandq
n
satisfes the
conditions (a) and (b), too.
Thereforep
(f)∈PXandpalso satisfes condition (b).
For eachn
∈N,f,g ∈PXandx ∈Xwe have
[(q
n
(f))1(x)˙−(q
n
(g))1(x)]∨[(q
n
(g))2(x)˙−(q
n
(f))2(x)]≤D(f,g);
thusD (p(f),p(g))≤D(f,g)andpsatisfes condition (a), too.
We fnally show thatp
(f)∈QXwheneverf ∈PX.
Letf
∈PX.For alln ∈Nwe havep (f)≤q
n
(f)and hencep (f)
∗
≥q
n
(f)
∗
by
defnition of the
∗-operation.

14P C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
So0≤p(f)−p(f)
∗
≤q
n
(f)−q
n
(f)
∗
= 2(q
n
(f)−q
n+1
(f))(compare [13,
proof of Proposition 3.1]), sinceq
n+1
(f)=
q
n
(f)+q
n
(f)
∗
2
.In particular this yields
thatp
(f)=p(f)
∗
.But thenh :=p(f)is minimal among the ample function pairs:
Indeed letg
≤h,that isg 1≤h1andg 2≤h2,and letgbe an ample function
pair. Then for eachx
∈X,
h
2(x)=sup
y∈X
(d(x,y)˙−h1(y))≤sup
y∈X
(d(x,y)˙−g1(y))≤g2(x)
by ampleness ofg.Sog 2=h2.Similarlyg 1=h1and therefore the pairhis
minimal ample.
Remark 1.We next note that Proposition 2 can also be proved by Zorn’s Lemma
(compare [4, Section 1.9]).
Proof.We only sketch the idea of this proof. LetPbe the set of all mapspfromP
X
toPXsatisfying the following two conditions (1)p (f)≤fand (2)D (p(f),p(g))≤
D(f,g)wheneverf,g ∈PX.
Defne a partial order
=onPas follows:
p
=qif [p (f)≤q(f)andD (p(f),p(g))≤D(q(f),q(g))]wheneverf,g ∈PX.
LetKbe a nonempty chain in
(P,=).Defne a mapt :PX→PXby
t
(f)(x) := ( inf
k∈K
(k(f))1(x),inf
k∈K
(k(f))2(x))
wheneverx ∈X,where the infma are taken pointwise in[0,∞).
One verifes thattis a lower bound ofKin
(P,=).By Zorn’s LemmaPhas a
minimal element, saym.
Let us now see thatm
(f)∈QXwheneverf ∈PX.We need the following
lemma that is of independent interest.
Lemma 3.(compare [4, Section 1.3]) Let
(X,d)be aT 0-quasi-metric space and let
f
∈PX.For eachx ∈Xset(px(f))1(z)=f1(z)ifz∈X\{x}and
(px(f))1(x) = sup{ d(y,x)˙−f2(y):y∈X}
and(px(f))2(z)=f2(z)ifz∈X\{x}and
(px(f))2(x)=sup{ d(x,y)˙−f1(y):y∈X}.
Then for eachx
∈X,px∈P.
Proof.We leave the details of the proof of the lemma to the reader.
We now fnish the proof of Remark 1. For eachx ∈Xwe obviously have thatp x◦
m∈Pandp x◦m=m.Hence by minimality ofm,p x◦m=mwheneverx ∈X.

Tight Extensions ofT 0-Quasi-Metric SpacesΨ 15
It follows that for eachx
∈X,px(m(f)) =m(f)wheneverf ∈PX. Thus by the
defnition of the elements ofQ
Xwe conclude thatm (f)∈QXwheneverf ∈PXby
[11, Remark 2].
Remark 2.(The general quasi-metric “segmentI
ab”.) LetX = [0,1].Choose
a,b
∈[0,∞)such thata +b2=0.Setd
ab(x,y)=(x−y)aifx>yand
d
ab(x,y)=(y−x)bify ≥x.Then([0,1],d
ab)is aT 0-quasi-metric space, as it is
readily checked, by considering the various cases for the underlying asymmetric
normn
abonRdefned byn
ab(x)=xaifx> 0andn
ab(x)=−xbifx ≤0.
Remark 3.(compare [4, Section 1.10]) Using somep(as in Proposition 2) we can
defne for anyf
∈QXa mapΨ : [0,1]×QX→QXas follows:(t,g):+pt(g)=
p(tf+ (1− t)g)fromp 0,the identity onQ X,top 1,the constant mapQ X→{f}⊆
QX.Here we used the fact thattf + (1− t)g∈PX.
Note that moreover, for anys,t
∈[0,1]witht ≤sone hasD (ps(g),pt(g)) =
D(p(sf+ (1− s)g),p(tf+ (1− t)g))≤D(sf+ (1− s)g,tf+ (1− t)g) = sup
x∈X
((s−
t)f1(x)˙−(s−t)g1(x))∨sup
x∈X
((s−t)g2(x)˙−(s−t)f2(x))=(s−t)D(f,g).
Furthermore
D
(f,g)≤D(f,ps(g)) +D(ps(g),pt(g)) +D(pt(g),g)=
D(p1(g),ps(g)) +D(ps(g),pt(g)) +D(pt(g),p0(g)) =
(1−
s)D(f,g)+D(ps(g),pt(g)) +tD(f,g).
Therefore
D
(ps(g),pt(g))≥(s−t)D(f,g)
and thus
D
(ps(g),pt(g))=(s−t)D(f,g)
wheneverg ∈QXand0≤t≤s≤1.
If
0≤s≤t≤1andg ∈QX, then a similar computation yields
D
(ps(g),pt(g)) =D
−1
(pt(g),ps(g))=(t−s)D
−1
(f,g)=(t−s)D(g,f).
Seta
=D(f,g)andb =D(g,f).Then the map([0,1],d
ab)→(QX,D)defned
bys
:+ps(g)yields an isometric map connectinggtof.
We next show that if we equip the unit interval
[0,1]of the reals with its stan-
dard topologyτ
(u
s
)(where, as usual,u
s
also denotes the restriction of the metric
u
s
to[0,1])andQ Xwith the topologyτ (D),then the mapΨis continuous, that is,
Ψ
: [0,1]×QX→QXis a homotopy andQ Xis contractible in the classical sense.
Indeed suppose that the sequence
(sn)n∈Nconverges tosin ([0,1],τ(u
s
))and
the sequence
(gn)n∈Nconverges togin (QX,τ(D)), that isD (g,gn)→0 ifn→∞.

160 C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
Then for eachn ∈N, by the triangle inequality we have that
D
(ps(g),psn(gn))≤D(ps(g),psn(g)) +D(psn(g),psn(gn)).
Therefore for eachn
∈Nwe see that
D
(ps(g),psn(g))=(s−sn)D(f,g)
ifs≥snand
D
(ps(g),psn(g))=(sn−s)D(g,f)
ifsn≥s,according to the calculations completed above.
Moreover for eachn
∈N, we get that
D
(psn(g),psn(gn)) = (1− sn)D(g,gn)
by defnition ofD.
By our assumptions we conclude that
D
(ps(g),psn(g))→0
and
D
(psn(g),psn(gn))→0
ifn→∞.ThereforeD (ps(g),psn(gn))→0 ifn→∞,and henceΨis indeed
continuous.
Proposition 4.(compare [4, Section 1.11]) Let
(Y,d)be aT 0-quasi-metric space
and letXbe a (nonempty) subspace of
(Y,d).Then there exists an isometric em-
beddingτ
:QX→QYsuch thatτ (f)|X=fwheneverf ∈QX.
Proof.Letx
0∈Xbe fxed and choose a retractionp :PY→QYsatisfying the
conditions (a) and (b) of Proposition 2. Furthermore lets
:QX→PYbe defned
ass
(f)=f
0
wheref
0
1
(y)=f1(y)whenevery ∈X,andf
0
1
(y)=f1(x0)+d(x0,y)
whenevery ∈Y\X.Similarlyf
0
2
(y)=f2(y)whenevery ∈X,andf 2(y)=d(y,x0)+
f2(x0)whenevery ∈Y\X.
We prove thatf
0
∈PYby considering four cases:
Supposex
∈Xandy ∈X;thenf
0
2
(x)+f
0
1
(y)=f2(x)+f1(y)≥d(x,y).
Suppose thatx
∈Y\Xandy ∈Y\X;thenf
0
2
(x)+f
0
1
(y)=d(x,x0)+f2(x0)+
f1(x0)+d(x0,y)≥d(x,x0)+d(x0,y)≥d(x,y).
Suppose thatx
∈Xandy ∈Y\X;thenf
0
2
(x)+f1(y)=f2(x)+f1(x0)+
d(x0,y)≥d(x,x0)+d(x0,y)≥d(x,y).
Suppose thatx
∈Y\Xandy ∈X;thenf
0
2
(x)+f
0
1
(y)=d(x,x0)+f2(x0)+
f1(y)≥d(x,x0)+d(x0,y)≥d(x,y).Thusf
0
∈PY.

Tight Extensions ofT 0-Quasi-Metric Spacesτ 17
Defneτ
=p◦s:QX→QY.Note thatτ (f)|X=p(f
τ
)|X=fwheneverf ∈QX,
sincep
(f
τ
)≤f
τ
,thereforep (f
τ
)|X≤f
τ
|X=f,andfis minimal onX.
Furthermore for anyf,g
∈QX,
D
(f,g)=D(τ(f)|X,τ(g)|X)≤ D(τ(f),τ(g)) =
D(p(f
τ
),p(g
τ
))≤ D(f
τ
,g
τ
)=D(f,g)
where the last equality follows from the defnition off
τ
andg
τ
.
Defnition 5.(compare [8, Remark 7]) LetXbe a subspace of aT 0-quasi-metric
space
(Y,d).ThenYis called atight extensionofXif for any quasi-pseudometric
eonYthat satisfese
≤dand agrees withdonX ×Xwe have thate =d.
In [8, Remark 7] it was shown that for anyT
0-quasi-metric space(X,d)we have
that the isometric embeddingj
:X→QXistight, that is,Q Xis a tight extension
ofj
(X).
Remark 4.(see [4, Section 1.12]) For anyT
0-quasi-metric tight extensionY 1ofX,
anyT
0-quasi-metric extension(Y2,d)ofXand any nonexpansive mapψ :Y1→
Y2satisfyingψ (x)=xwheneverx ∈X,ψis necessarily an isometric map.
Proof.Otherwise the quasi-pseudometricρ
:Y1×Y1→[0,∞)defned by
(x,y)→ρ(x,y)=d(ψ(x),ψ(y))would contradict the tightness of the extension
Y
1ofX.
Proposition 6.(compare [4, Section 1.13]) Let (Y,d)be aT 0-quasi-metric tight
extension ofX.Then the restriction map defned byf
→f|Xwheneverf ∈QYis a
bijective isometric mapQ
Y→QX.
Proof.Choose a retractionp
:PX→QXsatisfying the conditions (a) and (b) of
Proposition 2 and letψ
:QY→QX:f→p(f|X)denote the composition ofpwith
the restriction map. Thenψis a nonexpansive map andQ
YandQ XareT 0-quasi-
metric extensions ofX. According to Remark 4ψmust be an isometric map, since
Q
Yis a tight extension ofX,becauseQ Yis a tight extension ofYandYis a tight
extension ofX.
By Proposition 4 there is an isometric embeddingτ
:QX→QYsatisfying
τ
(f)|X=ffor allf ∈QX.Then we haveψ (τ(f)) =p(τ(f)|X)=p(f)=ffor
allf
∈QXand thusψis necessarily surjective. But a surjective isometric map
on aT
0-quasi-metric domain is necessarily bijective. Soτ :QX→QYhas to be
the map inverse toψand thus for anyf
∈QYwe necessarily have the formula
f
|X=τ(ψ(f))|X=ψ(f)∈QX,that is, the restriction mapQ Y→PX:f→f|Xmaps

181 C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
QYalready ontoQ X,without having to be composed with the retraction mapp.
Hence we see that for anyT
0-quasi-metric tight extensionYofXthe restriction
mapQ
Y→QX:f21f|Xyields a bijective isometric map betweenQ YandQ X.Proposition 7.(compare [6, Theorem 2]) LetXbe a subspace of theT 0-quasi-
metric space
(Y,d).Then the following three conditions are equivalent:
(a)Yis a tight extension ofX.
(b)d
(y1,y2)=sup{( d(x1,x2)−d(x1,y1)−d(y2,x2))∨0: x1,x2∈X}
whenevery 1,y2∈Y.
(c)f
y|X(x)=(d(y,x),d(x,y))withx ∈Xis minimal onXwhenevery ∈Yand
the mapΦ
:(Y,d)→(QX,D):y21fy|Xis an isometric embedding.
Proof.(a)
→(b): LetYbe aT 0-quasi-metric tight extension ofX.By Proposition
6 the mapQ
Y→QXdefned byf 21f|Xdefnes a bijective isometric map between
Q
YandQ X.Hence the extensionYofX, as a subspace ofQ Y,fulfls condition (b)
of Proposition 7, since the extensionQ
XofXsatisfes it by [8, Remark 7].
(b)
→(c): For anyx 1,x2∈Xandy 1∈Ywe have that
d
(x1,x2)≤d(x1,y1)+d(y1,x2).
Therefore for anyx
1,x2∈Xandy 1,y2∈Ywe see that
d
(x1,x2)−d(x1,y1)−d(y2,x2)≤d(y1,x2)−d(y2,x2).
Consequently for anyy
1,y2∈Ywe have by (b) that
d
(y1,y2)=sup{( d(x1,x2)−d(x1,y1)−d(y2,x2))∨0: x1,x2∈X}≤
sup{(
d(y1,x2)˙−d(y2,x2)) :x2∈X}≤d(y1,y2).
Similarly
d
(x1,x2)≤d(x1,y2)+d(y2,x2)
wheneverx 1,x2∈Xandy 2∈Y.
It follows that for eachx
1,x2∈Xandy 1,y2∈Ywe have that
d
(x1,x2)−d(y2,x2)−d(x1,y1)≤d(x1,y2)−d(x1,y1).
Thus for anyy
1,y2∈Ywe see by (b) that
d
(y1,y2)≤sup{( d(x1,x2)−d(y2,x2)−d(x1,y1))∨0: x1,x2∈X}≤
sup{(
d(x1,y2)˙−d(x1,y1)) :x1∈X}≤d(y1,y2).
Hence we conclude thatd
(y1,y2)=D(fy1|X,fy2|X)whenevery 1,y2∈Y.

Tight Extensions ofT 0-Quasi-Metric Spacesϕ 19
As we have just shown, for anyy
1,y2∈Ywe have that
d
(y1,y2)=sup{( d(x1,y2)˙−d(x1,y1)) :x1∈X}
and
d
(y1,y2)=sup{( d(y1,x2)˙−d(y2,x2)) :x2∈X}.
Substitutingx
2∈Xfory 2andx 1∈Xfory 1, respectively, we obtain the two
equations
(fy1)1(x2)=d(y1,x2)=sup{( d(x1,x2)˙−d(x1,y1)) :x1∈X}
whenevery 1∈Yandx 2∈X,
and
(fy2)2(x1)=d(x1,y2)=sup{( d(x1,x2)˙−d(y2,x2)) :x2∈X}
whenevery 2∈Yandx 1∈X.
By [11, Remark 2] the restrictionf
y|Xis minimal onXwhenevery ∈Y.
(c)
→(a): Letq :Y×Y→[0,∞)be a quasi-pseudometric onYsuch thatq ≤d
andq
|X×X=d|X×X.
According to (c) and sincef
y|Xis minimal whenevery ∈Xwe haved (y1,y2)=
D(fy1|X,fy2|X) = sup
x∈X
(d(y1,x)˙−d(y2,x)) = sup
x∈X
(d(x,y2)˙−d(x,y1))when-
every
1,y2∈Yby [8, Lemma 7].
Then substituting
d
(x1,y2) = sup{( d(x1,x2)˙−d(y2,x2)) :x2∈X}
into the formula
d
(y1,y2)=sup{( d(x1,y2)˙−d(x1,y1)) :x1∈X},
we obtain
d
(y1,y2) = sup
x1∈X
sup
x2∈X
{(d(x1,x2)−d(x1,y1)−d(y2,x2))∨0}
≤sup
x1,x2∈X
{(q(x1,x2)−q(x1,y1)−q(y2,x2))∨0}≤ q(y1,y2)
whenevery 1,y2∈Yby our assumption. Consequentlyq =d.
Therefore condition (a) is satisfed.
Remark 5.(compare [4, Section 1.14]) Let (Y,d)be aT 0-quasi-metric ofX.Elabo-
rating further on Proposition 7 we see that there is only one isometric embedding
ϕ
:Y→QXsatisfyingϕ (x)=fxwheneverx ∈X,since for such an embedding

20C C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
ϕ:Y→QX,y∈Yandx ∈X,we have(fy)2|X(x)=d(x,y)=D(ϕ(x),ϕ(y)) =
D(fx,ϕ(y)) = (ϕ(y))2(x);therefore(fy)2|X=(ϕ(y))2. In a similar way, one can
show that
(fy)1|X=(ϕ(y))1whenevery ∈Y.
In particular we see that the tight extensionYofXcan be understood as a
subspace of the extensionQ
XofX.HenceQ Xis maximal among theT 0-quasi-
metric tight extensions ofX.
We fnally discuss an asymmetric version of a result due to Herrlich. To this end,
given a quasi-pseudometric space
(X,dX), for eachx ∈Xand(> 0,byC
dX
(x,()=
{
y∈X:dX(x,y)≤(}we denote the so-called closed ball of radius(atx.(Note
that it is closed with respect to the topologyτ
(d
−1
X
).)
InXwe say that the (double) familyC
=(C
dX
(xi,ri),C
d
−1
X
(yi,si))i∈Iof such
ballsmeets potentiallyprovided that there exists aT
0-quasi-metric extension
(Y,dY)of(X,dX)such that
C
i∈I
(C
dY
(xi,ri)∩C
d
−1
Y
(yi,si))1=∅ .
Proposition 8.(compare [6, Proposition]) IfC
=(C
dX
(xi,ri),C
d
−1
X
(xi,si))i∈Iis a
(double) family of balls in aT
0-quasi-metric space(X,d),then the following condi-
tions are equivalent:
(1)Cmeets potentially inX.
(2) For anyi,j
∈I,C
dX
(xi,ri)meets with anyC
d
−1
X
(xj,sj)potentially inX.
(3)d
X(xi,xj)≤ri+sjwheneveri,j ∈I.
(4) There exists a minimal (ample) function pairt
=(t1,t2)onXwitht 2(xi)≤
riandt 1(xi)≤siwheneveri ∈I.
Proof.
(1)→(2)→(3) are obvious.
(3)→(4) is obvious forI =∅.
Otherwise defne a function pairf
=(f1,f2)onY={xi:i∈I}by setting for
eachy
∈Y,f1(y) = inf{ si:xi=y}andf 2(y) = inf{ ri:xi=y}. Choosey 0∈Y.
Setg
1(x)=f1(x)ifx∈Y,andg 1(x)=f1(y0)+dX(y0,x)ifx∈X\Y.
Furthermore setg
2(x)=f2(x)ifx∈Y,andg 2(x)=dX(x,y0)+f2(y0)if
x
∈X\Y.
Theng
1(xi)≤siandg 2(xi)≤riwheneveri ∈I.Furthermored X(x,x
τ
)≤
g2(x)+g1(x
τ
)wheneverx ∈Xandx
τ
∈X.Thusg =(g1,g2)is an ample function
pair onXand by Zorn’s Lemma there is a minimal ample pairt
=(t1,t2)onX
such thatt
≤g.
(4)
→(1) :Lett=(t1,t2)be a minimal ample pair onXwitht 1(xi)≤siand
t
2(xi)≤riwheneveri ∈I.Ift =fxfor somex ∈X,thenx ∈
C
i∈I
(C
dX
(xi,ri)∩
C
d
−1
X
(xi,si)). Thus the familyCmeets inX.
Otherwise extendXto a spaceYby adding one pointy
0toXand by defn-
ing aT
0-quasi-metricd YonYextendingd Xand satisfyingd Y(x,y0)=t2(x)and

Tight Extensions ofT 0-Quasi-Metric Spacesě 21
d
Y(y0,x)=t1(x)wheneverx ∈X.One readily checks thatd Yis aT 0-quasi-metric
onY(compare [8, end of proof of Theorem 1]).
Theny
0∈
ě
i∈I
(C
dY
(xi,ri)∩C
d
−1
Y
(xi,si))and we are done.
The following example answers a question asked by one of the referees.
Remark 6.(see [8, Example 7]) LetXbe the set
{0,1}equipped with the discrete
metric. ThenQ
Xis isometric to the product set[0,1]×[0,1]of two copies of real unit
intervals
[0,1]equipped with theT 0-quasi-metricD ((α,β),(α
f
,β
f
)) =u(α,α
f
)∨
u(β,β
f
)whenever(α,β),(α
f
,β
f
)∈[0,1]×[0,1],whileT Xcan be identifed with
the subspace
{(α,1−α):α∈[0,1]}in this product, that is,T Xis isometric to the
unit interval
[0,1]of the reals equipped with the restriction of the metricu
s
.
Observe that, intuitively,Q
Xconsists of all the pointszdetermined by the
equations
1=D(f0,z)+D(z,f1)and1=D(f1,z)+D(z,f0).
We recall from [8, Proposition 5] that for any metric space
(X,m), there exists
a canonical isometric embedding ofT
XintoQ X.
Acknowledgement:We would like to thank an anonymous referee for his useful
comments.
Bibliography
[1]E. Colebunders, S. De Wachter and B. Lowen, Intrinsic approach spaces on domains,
Topology Appl.158: 2343–2355, 2011.
[2]
A. Collins Amburo, P. Haihambo and H.-P.A. Künzi, Endpoints inT0-quasi-metric spaces,
in preparation.
[3] M. de Brecht, Quasi-Polish spaces,Ann. Pure Appl. Logic164: 356–381, 2013.
[4]
A.W.M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension
of certain groups: a note on combinatorial properties of metric spaces,Adv. Math.53:
321–402, 1984.
[5] P. Fletcher and W.F. Lindgren, Quasi-uniform Spaces, Dekker, New York, 1982.
[6] H. Herrlich, Hyperconvex hulls of metric spaces,Topology Appl.44: 181–187, 1992.
[7]
J.R. Isbell, Six theorems about injective metric spaces,Comment. Math. Helv.39: 65–76,
1964.
[8]
E. Kemajou, H.-P.A. Künzi and O.O. Otafudu, The Isbell-hull of a di-space,Topology Appl.
159: 2463–2475, 2012.
[9]
M.A. Khamsi and W.A. Kirk, An Introduction to Metric Spaces and Fixed Point Theory, John
Wiley, New York, 2001.
[10]
H.-P.A. Künzi, An introduction to quasi-uniform spaces,Contemp. Math.486: 239–304,
2009.
[11]
H.-P.A. Künzi and M. Sanchis, The Katětov construction modifed for aT0-quasi-metric
space,Topology Appl.159: 711–720, 2012.

22ě C. A. Agyingi, P. Haihambo, and H.-P.A. Künzi
[12]
H.-P.A. Künzi and M. Sanchis, Addendum to “The Katětov construction modifed for a
T0-quasi-metric space”,Math. Struct. in Comp. Science(to appear).
[13]
U. Lang, Injective hulls of certain discrete metric spaces and groups, arXiv:1107.5971v2
[math.GR] 28 June 2012.
[14]
J. Marín, S. Romaguera and P. Tirado, Weakly contractive multivalued maps andw-
distances on complete quasi-metric spaces,Fixed Point Theory Appl.2011:2, 9pp, 2011.
[15]
V. Selivanov, On the diference hierarchy in countably basedT0-spaces,Electronic Notes
in Theoretical Computer Science221: 257–269, 2008.

Klaus Ambos-Spies
On the Strongly Bounded Turing Degrees of
Simple Sets¹
Abstract:We study ther-degrees of simple sets under the strongly bounded Tur-
ing reducibilitiesr
=cl (computable Lipschitz reducibility) andr =ibT (iden-
tity bounded Turing reducibility) which are defned in terms of Turing function-
als where the use function is bounded by the identity function up to an additive
constant and the identity function, respectively. We call a c.e.r-degreeasimple if
it contains a simple set and we callanonsimple otherwise. As we show, the ibT-
degree of a c.e. setAis simple if and only if the cl-degree ofAis simple, and there
are nonsimple c.e.r-degrees>f. Moreover, we analyze the distribution of the sim-
ple and nonsimpler-degrees in the partial ordering of the c.e.r-degrees. Among
the results we obtain are the following. (i) For any c.e.r-degreea>f, there are sim-
pler-degrees which are belowa, aboveaand incomparable witha. (ii) For any c.e.
r-degreea>f, there are nonzero nonsimple c.e.r-degrees which are belowaand
incomparable witha; and there is a nonsimple c.e.r-degree aboveaif and only if
ais not contained in the complete wtt-degree. (iii) There are infnite intervals of
c.e.r-degrees entirely consisting of nonsimple c.e.r-degrees respectively simpler-
degrees. (iv) Any c.e.r-degree is the join of two nonsimple c.e.r-degrees whereas
the class of the nonzero c.e.r-degrees is not generated by the simpler-degrees
under join though any simpler-degree is the join of two lesser simpler-degrees.
Moreover, neither the class of the nonsimple c.e.r-degrees nor the class of the
simpler-degrees generates the class of c.e.r-degrees under meet.
Keywords:Computable Lipschitz reducibility, identity bounded Turing reducibil-
ity, strong reducibilities, computably enumerable degrees, computably enumer-
able sets, simple sets, Post’s Program
Mathematics Subject Classifcation 2010:03D25, 03D30
ff
Klaus Ambos-Spies:
Department of Mathematics and Computer Science, University of Heidel-
berg, Germany
1This research was partially done whilst the author was a visiting fellow at the Isaac Newton
Institute for the Mathematical Sciences in the programme ‘Semantics&Syntax’ in the spring of
2012.

24f Klaus Ambos-Spies
fIntroduction
The notion of a simple set is among the most well known concepts in computabil-
ity theory. Simple sets were introduced in 1944 by Post in his seminal paper [15]
where he raised the question of whether there are more than two computably enu-
merable (c.e.) Turing degrees which became known as Post’s Problem. This pa-
per may be viewed as the origin of degree theory and specifcally of the theory
of the c.e. (Turing) degrees which became one of the most productive areas in
computability theory (see e.g. Odifreddi [14] and Soare [16]). Post’s approach to
solve Post’s Problem - now known as Post’s Program - was a structural one. He
tried to fnd a nonvacuous propertyPof c.e. sets such that any c.e. set with this
property is neither computable nor (Turing) complete. In order to get such a prop-
erty, Post looked at c.e. sets with “thin” (but infnite) complements. In particular,
Post called a c.e. setAsimpleif its complement is infnite but does not contain
any infnite c.e. set as a subset. He showed that simple sets exist and that they
are not complete under many-one reducibility (in fact under bounded truth-table
reducibility) but that they may be complete under truth-table reducibility. So, in
order to guarantee Turing incompleteness, Post suggested some refnements of
simplicity, namely hyper-simplicity and hyper-hyper-simplicity. As it turned out,
however, neither of these properties guarantees Turing-incompleteness and - in
a strict sense - Post’s Program fails. The solution of Post’s Problem was given by
Friedberg and Muchnik in 1956, by introducing the priority method. Though this
constructive approach proved to be very powerful and most of the results on the
structure of the c.e. degrees are proven by priority arguments, Post’s structural
approach and variations of Post’s Program still attracted researchers in the past.
So, by replacing thinness properties by other structural properties, several solu-
tions to Post’s Problem were given where, probably, the solution found by Harring-
ton and Soare [11] is the most satisfying one. Moreover, Post’s structural approach
proved to be very useful for the study of the c.e. degrees under the strong reducibil-
ities as many-one (m), bounded truth-table (btt) and truth-table (tt) reducibilities
(see e.g. Chapter III in Odifreddi [14]).
One may consider a generalization of Post’s Program in a diferent direction:
instead of replacing thinness properties by more general structural properties one
may look at degrees in general and not only at the complete degree. For this sake,
given a propertyPof c.e. sets implying noncomputability, let
P
ρ(degρ(A))⇔ there is a setPwith propertyPsuch thatP =ρA
be the corresponding degree property (for a given reducibility
≤ρ). Then, in or-
der to solve Post’s Problem forρ-reducibility, i.e., to show that there are at least

On the Strongly Bounded Turing Degrees of Simple Setsf 25
two nonzero c.e.ρ-degrees, it sufces to show that there are noncomputable
c.e. setsAandBsuch that theρ-degree ofAcontains a set with propertyP(i.e.,
P
ρ(degρ(A))holds) and theρ-degree ofBdoes not contain a c.e. set with property
P(i.e.,P
ρ(degρ(B))fails).
ThisGeneralized Post’s Programis more technical but also more powerful than
Post’s original program. Namely, the simple set propertySdoes not sufce to
solve Post’s Problem for tt-reducibility in the sense of Post’s Program (since, as
mentioned before, Post has shown that there are tt-complete simple sets), but
it sufces in the sense of Generalized Post’s Program since - by Post - there is
a simple setA(henceS
tt(degtt(A))holds) while - as shown by Jockusch [12] -
there is a noncomputable c.e. setBwhich is not tt-equivalent to any simple set
(henceS
tt(degtt(B))fails). But, even in the sense of Generalized Post’s Program,
simplicity fails to solve Post’s Problems for Turing reducibility, since Dekker has
shown in 1954 that any nonzero c.e. Turing degree contains a (hyper-)simple set.
The stronger propertyHHSof hyper-hyper-simplicity, however, solves the origi-
nal Post’s Problem for Turing reducibility in the sense of Generalized Post’s Pro-
gram since Martin has shown that a c.e. Turing degree contains an hh-simple set
if and only if the degree is high. So there are noncomputable c.e. setsAandB
such thatHHS
T(degT(A))holds whileHHS T(degT(B))fails. (For defnitions and
references see Chapter III in Odifreddi [14].)
The above described role played by simple sets in the study of the degrees of
c.e. sets led us to look at the degrees of simple sets under the strongly bounded
Turing reducibilities. These reducibilities -computable Lipschitz reducibility(cl-
reducibility for short) andidentity bounded Turing reducibility(ibT-reducibility
for short) are defned in terms of Turing functionals where the use function is
bounded by the identity function up to an additive constant and the identity
function, respectively. They were introduced only fairly recently by Downey,
Hirschfeldt and Laforte [8] and Soare [17], respectively. Computable Lipschitz
reducibility is of particular interest in the theory of algorithmic randomness since
it does not only capture relative computability but also measures the relative de-
gree of randomness in the sense of Kolmogorov complexity. We refer the reader
to the recent monograph of Downey and Hirschfeldt [9] and to Ambos-Spies et al.
[3] for more motivation and details.
The strongly bounded Turing reducibilities have some interesting structural
properties which distinguish them from the other computable reducibilities. So
there are no complete sets under these reducibilities (Downey, Hirschfeldt and
LaForte [8]); in fact, there are so-calledr-maximal pairs of c.e. sets, i.e., c.e. sets
AandBsuch that there is no c.e. setCsuch thatA
≤rCandB ≤rCforr =ibT,cl
(Barmpalias [5] and Fan and Lu [10]; see [3] for more on maximal pairs). (By the

26f Klaus Ambos-Spies
former, Post’s Program does not make sense in the context of these reducibilities,
but one may consider Generalized Post’s Program here.)
We start our investigation in the degrees of simple sets under the strongly
bounded Turing reducibilities by showing that a setAis ibT-equivalent to a sim-
ple set if and only if it is cl-equivalent to a simple set, and we show that there
are noncomputable c.e. sets which are notr-equivalent to any simple set (where
r
=ibT,cl throughout this paper).
We then analyze the distribution of the classesS
rand
Srof the c.e.r-degrees
containing respectively not containing simple sets in the partial ordering
(Rr,≤)
of the c.e.r-degrees. While the classS mof the simple many-one degrees is a proper
ideal in the partial ordering
(Rm,≤)of the c.e. m-degrees, it turns out that the class
S
rof the simpler-degrees is quite scattered in the partial ordering(Rr,≤). For in-
stance, for any nonzero c.e.r-degreea, there are simple and nonzero nonsimple
r-degrees belowa, there are simple and nonsimpler-degrees incomparable with
a, and - unlessais ther-degree of a wtt-complete set - there are simple and non-
simpler-degrees abovea. For wtt-completeAwe show thatdeg
r(A)is simple. So,
in contrast to the situation for the m-degrees where the class of the simple degrees is an ideal, here the simple degrees are not closed downwards and a simple degree can be found above any c.e. degree. Moreover, we show that there are infnite inter-
vals in
(Rr,≤)consisting only of simple degrees respectively nonsimple degrees
and we discuss the question whether the classesS
rand
Srare closed under join
and meet. Finally, we indicate that - in some sense - there are more nonsimple de- grees than simple degrees. Namely while the class
Srof the nonsimpler-degrees
generates the classR
rof all c.e.r-degrees under join (but not under meet), the
classS
rof the simpler-degrees generatesR rneither under join nor under meet.
The outline of the paper is as follows. In Sections 2 and 3 we introduce the facts
on the strongly bounded Turing reducibilities and simple sets, respectively, to be used in the following. Then, after proving the coincidence theorem for simple ibT- and cl-degrees (Section 4), we present our results on nonsimpler-degrees where
we start with the basic construction of a nonzero nonsimpler-degree (Section 5)
and then extend this construction in order to get the stronger positive results onSr
(Sections 6 and 7). We then turn to existence results for simple sets. First we show
that there are simple sets above and below any noncomputable c.e. set (Section 8). By refning these results we obtain more insight in the distribution of the simpler-
degrees among the c.e.r-degrees and can show that any noncomputable c.e. set is
equivalent to a simple set under linearly bounded Turing reducibility (Section 9).
We then show that wtt-complete sets have simpler-degrees (Section 10) and look
at splittings into simpler-degrees (Section 11). Finally, in Section 12, we pose some
open problems. There we also propose a further generalization of Post’s Program
which allows a solution of Post’s Problem for wtt-reducibility in terms of simple

On the Strongly Bounded Turing Degrees of Simple Sets= 27
sets. Whether the simple sets also give a solution of the original Post’s Problem
for Turing reducibility along these lines is left open.
=The strongly bounded Turing reducibilities
We start with some basic defnitions and notation on the reducibilities we con-
sider here. For more details see e.g. Ambos-Spies et al. [3] or Ambos-Spies [2].
Let
{Φe}
e≥0be a standard enumeration of the Turing functionals obtained by
goedelization of the oracle Turing machines, and letφ
ebe the use function² of
Φ
e. Then a setAis Turing reducible to a setB,A ≤TB, ifA =Φ
B
e
for somee ≥0.
For any functionf, we say thatAisf-bounded Turing reducibletoB(A
≤
f-TB) if
Ais Turing reducible toBvia a reduction where the use function is bounded byf,
i.e., if there is a numberesuch thatA
=Φ
B
e
andφ
B
e
(x)≤f(x)for allx ≥0. This
leads to the following reducibility notions.
1.Aisidentity-bounded-Turing (ibT-) reducibletoB(A
≤
ibTB) ifAisf-bounded
Turing reducible toBfor the identity functionf
(x)=x.
2.Aiscomputable Lipschitz (cl-) reducibletoB(A
≤
clB) if there is a numberk ≥
0
such thatAisf-bounded Turing reducible toBforf (x)=x+k. Moreover,
fork
≥0,Ais(i+k)bT-reducibletoB(A ≤
(i+k)bTB) ifAisf-bounded Turing
reducible toBforf
(x)=x+k. (SoAis ibT-reducible toBifAis (i+ 0)bT-
reducible toB, andAis cl-reducible toBifAis
(i+k)bT-reducible toBfor
somek
≥0.)
3.Aislinearly bounded Turing (lbT-) reducibletoB(A
≤
lbTB) ifAisf-bounded
Turing reducible toBfor a linearly bounded functionf, i.e., for a functionf
satisfyingf
(x)≤k0x+k1for some numbersk 0,k1≥0and all numbers
x
≥0.
4.Aisweak-truth-table (wtt-) reducibleorbounded-Turing (bT-) reducibletoB
(A
≤wttB) ifAisf-bounded Turing reducible toBfor some computable func-
tionf.
2Warning: Here we work with a slightly nonstandard defnition of the use. While most commonly
the use function givesstrictupper bounds on the oracle queries, here we consider nonstrict bounds.
I.e., we letφ
X
e
(x)↑ ifΦ
X
e
(x)is undefned and we letφ
X
e
(x)be the greatest oracle query in the
computation ofΦ
X
e
(x)ifΦ
X
e
(x)is defned (where we letφ
X
e
(x)=0if no queries are asked).

280 Klaus Ambos-Spies
In the following we refer to ibT and cl as thestrongly bounded Turing reducibilities.
Moreover we use the following convention.
Convention.Since we will obtain many results for both of the strongly bounded
reducibilities, ibT-reducibility and cl-reducibility, simultaneously, in order to sim-
plify notation,r-reducibility will stand for both ibT-reducibility and cl-reducibility in
the following. Similarly, if we simultaneously refer to ibT, cl and wtt then we shortly
writer
0
, and if we refer to ibT, cl, wtt and T then we writer
00
.ρwill stand for any
reducibility.
We call a Turing functionalΦ
eanf-bounded Turing functional ifφ
X
e
(x)≤f(x)
for all oracle setsXand inputsxsuch thatΦ
X
e
(x)is defned. ibT-, cl-, lbT- and wtt-
functionals are defned correspondingly. Note that, for any computable functionf,
A
≤
f-TBif and only if there is anf-bounded Turing functionalΦsuch thatA ≤TB
viaΦ, and similarly for ibT, cl, lbT and wtt. (Namely, ifA
≤
f-TBviaΦ ethenAis
f-T-reducible toBvia thef-bounded Turing functionalΨ
ewhereΨ
X
e
(x)=Φ
X
e
(x)
if in the latter computation no oracle query exceedsf (x)andΨ
X
e
(x)is undefned
otherwise.) Moreover, there are computable enumerations of the corresponding
functionals (where in case of the wtt-functionals we have to include the Turing
functionals bounded by partial computable functions). In the following we let
{
ˆΦe}
e≥0and{
˜Φe}
e≥0be computable enumerations of the ibT- and cl-functionals,
respectively, and let
ˆφeand˜φebe the corresponding use functions, where the cl-
functionals
˜
Φeare chosen so that˜φ
X
e
(x)≤x+eif
˜
Φ
X
e
(x)is defned. Finally we let
{φe}
e≥0and{We}
e≥0be standard enumerations of the unary partial computable
functions and c.e. sets, respectively, whereW
e=dom(φe). We use computable
approximations of the functionals and the corresponding use functions which are
denoted by an additional indexsgiving the stage of the approximation. So, for in-
stance,Φ
X
e,s
(x)is the result of computingΦ
X
e
(x)forssteps andφ
X
e,s
(x)is the corre-
sponding use. We assume that wheneverΦ
X
e,s
(x)is defned thene,x,φ
X
e,s
(x)<s.
This convention applies to ibT- and cl-functionals, partial computable functions
and c.e. sets correspondingly.
Theρ-degree of a setAis denoted bydeg
ρ(A), and(Rρ,≤)denotes the partial
ordering of the c.e.ρ-degrees, i.e., theρ-degrees of c.e. sets. Lower case boldface
letters denote c.e.ρ-degrees.0denotes theρ-degree of the computable sets, and
R
+
ρ=Rρ\{0}denotes the class of the c.e.ρ-degrees of noncomputable sets. For
c.e.ρ-degreesaandb,a
∨bdenotes the join (least upper bound) ofaandbin
R
ρ(if it exists) anda ∧bdenotes the meet (greatest lower bound) ofaandbin
R
ρ(if it exists). In the following all sets and degrees are computably enumerable
(unless explicitely stated otherwise).
Note that, for any setsAandB,
A
≤
ibTB⇒A≤
clB⇒A≤
lbTB⇒A≤wttB⇒A≤TB (1)

On the Strongly Bounded Turing Degrees of Simple Sets0 29
hence
deg
ibT(A)⊆deg
cl(A)⊆deg
lbT(A)⊆degwtt(A)⊆degT(A). (2)
The structures of the c.e. wtt- and T-degrees have been extensively studied in the
literature (see e.g. Soare [16]) while the strongly bounded Turing degrees have
been studied only more recently (see e.g. the recent monograph by Downey and
Hirschfeldt [9] or the recent papers [2] and [3]). While the partial orderings of
the c.e. wtt- and T-degrees are upper semi-lattices (but no lower semi-lattices)
with least and greatest elements (namely the degrees of the computable sets
and the complete sets, respectively), the partial orderings of the c.e. ibT- and cl-
degrees are neither upper semi-lattices nor lower semi-lattices (Downey and
Hirschfeldt [9]) and do not possess greatest - in fact no maximal - elements
(Downey, Hirschfeldt and LaForte [8], Barmpalias [5]). Also, while the partial
orderings of the c.e. wtt- and T-degrees are dense, the partial orderings of the c.e.
ibT- and cl-degrees are not dense (Barmpalias and Lewis [6], Day [7]).
It seems that the partial ordering of the c.e. lbT-degrees has not been studied
in the literature. One can easily show, however, that it shares the most basic prop-
erties with the partial ordering of the c.e. wtt-degrees: It is a dense and distributive
upper semi-lattice with least and greatest elements but not a lower semi-lattice.
We close with some simple but useful concepts and facts which will be applied
in the following quite frequently. They are taken from [2] and [3].
A(computable) shiftfis a strictly increasing (computable) functionf
:ω→
ω. A shiftfisnontrivialiff (x)>xfor some (hence for almost all)x, andfis
unboundedif, for any numberk, there is a numberxsuch thatf
(x)−x>k. For a
setAand a computable shiftf, thef-shiftofAis defned byA
f={f(x):x∈A}.
Lemma 1(Computable-Shift Lemma ([2], [3])). Letfbe a computable shift and let
Abe a noncomputable c.e. set.
(i)A
f=wttA.
(ii)A
f≤
ibTA. Moreover, iffis unbounded thenA ≤
clA
f(whenceA
f<
ibTAand
A
f<
clA).
(iii) Iffis unbounded then, for any c.e. setBsuch thatA
f∩B=∅andA ≤
clA
f∪B,
it holds thatA
≤
clB.
Lemma 2(Splitting Lemma (see e.g. [2], [3])). LetA
0,...,A n(n≥1) be pairwise
disjoint c.e. sets. Then, forr
00
∈{ibT,cl,wtt,T },
deg
r
00(A0∪∙∙∙∪Am)=deg
r
00(A0)∨∙∙∙∨deg
r
00(Am).
Finally, we will use the following simple fact on c.e. wtt-degrees.

30+ Klaus Ambos-Spies
Proposition 3.For any c.e. setAand any infnite computable setRthere is a c.e.
set
ˆ
Asuch thatA =wtt
ˆ
Aand
ˆ
A⊆R.
Proof.The computable functiongenumeratingRin increasing order is a com-
putable shift. So, sinceA
g⊆R, the claim follows from part (i) of the Computable-
Shift Lemma.
+Simple sets and simple degrees
Recall that a setAissimpleifAis c.e., co-infnite, andAintersects all infnite
c.e. sets (see Post [15]). A setAisimmuneifAis infnite and does not contain any
infnite c.e. subset. So a set is simple if it is c.e. and its complement is immune.
Moreover, since any infnite c.e. set contains an infnite computable set as a subset,
an infnite set is immune if and only if it does not contain any infnite computable
set.
Defnition 4.A c.e.ρ-degreeaissimpleifacontains a simple set, andaisnon-
simpleotherwise.
The classes of the simple and nonsimple c.e.ρ-degrees are denoted byS
ρand
Sρ,
respectively. Since, obviously, no computable set is simple, theρ-degree+of the
computable sets is nonsimple, i.e.,+
∈
Sρ. So, in order to avoid trivialities, in
the following we will usually consider the classS
+
ρ=Sρ\{+}of the nonzero
nonsimple c.e.ρ-degrees in place ofSρ.
Note that, for the reducibilities introduced in Section 2, there is nocompletely
simpledegree, i.e., no c.e. degree such thatallc.e. sets in the degree are simple.
By (2) it sufces to show this forρ
=ibT.
Proposition 5.For any c.e. setAthere is a c.e. setBsuch thatA
=
ibTBand
B
contains an infnite computable set. In particular, any c.e. ibT-degree contains a
nonsimple c.e. set.
Proof.FixA. IfAis computable, letB
=∅. IfAis noncomputable, hence infnite,
thenAcontains an infnite computable setR. Then, as one can easily check,B
=
A\Rhas the required properties.
The following are well known facts on simple sets to be used below. For the sake
of completeness we include the short proofs.

On the Strongly Bounded Turing Degrees of Simple Sets( 31
Proposition 6.LetAbe a simple set and letBbe an infnite c.e. set. ThenA
∩Bis
infnite.
Proof.For a contradiction assume thatA
∩Bis fnite. ThenB \(A∩B)is an infnite
c.e. set which does not intersectA. SoAis not simple.
Lemma 7(Simple Set Lemma). LetAbe a simple set, letBbe an infnite c.e. set,
and letkbe any number
≥0. There are infnitely many numbersx ≥ksuch that
x
∈Band the interval[x−k,x+k]is contained inA.
Proof.The proof is by induction onk. Fork
=0the claim is immediate by Propo-
sition 6. So fxk>
0and, by inductive hypothesis, assume that there are infnitely
many numbersx
∈Bsuch that the interval[x−(k−1),x+(k−1)]is contained
inA. Then, for
B
(k,0)={x−k:x∈B&[x−(k−1),x+(k−1)]⊆ A},
B
(k,0)is an infnite c.e. set. Hence, by Proposition 6,A ∩B
(k,0)is infnite. By defni-
tion ofB
(k,0)this implies that there are infnitely many numbersx ∈Bsuch that
the interval
[x−k,x+(k−1)]is contained inA. So, for
B
(k,1)={x+k:x∈B&[x−k,x+(k−1)]⊆ A},
B
(k,1)is an infnite c.e. set. Hence, by Proposition 6,A ∩B
(k,1)is infnite. But, by
choice ofB
(k,1), this implies that there are infnitely many numbersx ∈Bsuch
that
[x−k,x+k]is contained inA.
(Coincidence of the simple ibT- and cl-degrees
Before we establish the existence of nonsimple c.e.r-degreesa>(for the strongly
bounded Turing reducibilitiesr
=ibT,cl, we frst show that, for any c.e. setA,
deg
ibT(A)is simple if and only ifdeg
cl(A)is simple.
Theorem 8(Coincidence Theorem). For any c.e. setA,deg
ibT(A)is simple if and
only ifdeg
cl(A)is simple.
For the proof of the nontrivial implication we will use the following lemma. Lemma 9(Representation Lemma). LetAandBbe noncomputable c.e. sets such
thatA
≤
(i+k)bTBandB ≤
(i+k)bTA, and let{As}
s≥0and{Bs}
s≥0be computable
enumerations ofAandB, respectively. There are one-to-one computable functions

320 Klaus Ambos-Spies
aandbsuch that, for
ˆ
A=range(a)and
ˆ
B=range(b)and fors ≥0, the following
hold.
ˆ
A⊆A&
ˆB⊆B (3)
ˆ
A=
ibTA&
ˆB=
ibTB (4)
a
(s)∈A\As&b(s)∈B\Bs (5)
|b(s)−a(s)|≤k (6)
Lemma 9 is a symmetric version of a similar representation lemma in [2] where it is
shown that any
(i+k)bT-reduction between c.e. sets is witnessed by ak-permitting
argument. Since the proofs are quite similar we only sketch the proof and refer to
[2] for more details.
Proof (sketch)..Fix
(i+k)bT-functionalsΦandΨsuch thatB =Φ
A
andA =Ψ
B
.
Defne thelength (of agreement) functionlby
l
(s) = max{ x≤s:∀y<x(Bs(y)=Φ
As
s(y)&As(y)=Ψ
Bs
s(y))}.
Then
lims→ωl(s)=ωwhence there are infnitely manyexpansionary stagess, i.e.,
stagesssuch thatl
(t)<l(s)for allt<s. Call an expansionary stagescriticalif
there is a numberx<l
(s)such thatx ∈A\As, and say that criticalness ofs
is witnessed by a staget>sifA
s0l(s):=At0l(s). Note that criticalness of
any critical stagesis witnessed by somet>s, and, for any witnesst, all stages
t
1
≥tare witnesses too. Moreover, by noncomputability ofA, there are infnitely
many critical expansionary stages. So, since the set of all pairs
(s,t)such thats
is critical and criticalness ofsis witnessed bytis computable, we can defne a
computable ascending sequence of expansionary stagess
0<s1<s2<...such
thats
nis critical ands n+1witnesses criticalness ofs n.
Now let
a
(n)=μx(x∈Asn+1\Asn)andb (n)=μx(x∈Bsn+1\Bsn).
Note that, by choice of the stagess
nands n+1,a(n)exists anda (n)<l(sn)<
l
(sn+1). So
A
sn(a(n)) =Ψ
Bsn
sn
(a(n))=0andA sn+1(a(n)) =Ψ
Bs
n
+1
sn+1
(a(n))=1.
SinceΨis an
(i+k)bT-functional it follows that
B
sn0a(n)+k+1:= Bsn+10a(n)+k+1.

On the Strongly Bounded Turing Degrees of Simple Sets≥ 33
Sob
(n)exists too andb (n)≤a(n)+k. Moreover, the dual inequalitya (n)≤
b(n)+kfollows forb (n)<l(sn)by a symmetric argument and is forb (n)≥l(sn)
obvious.
The above observations easily imply that the functionsaandbare well de-
fned, computable and one-to-one, and that the conditions (3) - (6) are satisfed.Proof of Theorem 8.By (2) it sufces to show that, for any c.e. setAsuch that
deg
cl(A)is simple,deg
ibT(A)is simple too. So fx c.e. setsAandBsuch that
A
=
clBandBis simple. It sufces to give a simple setCsuch thatA =
ibTC.
ByA
=
clBwe may fxk ≥0such thatA ≤
(i+k)bTB≤
(i+k)bTA. So, given
any computable enumerations
{As}
s≥0and{Bs}
s≥0ofAandB, respectively, by
the Representation Lemma we may fx computable one-to-one functionsaandb
such that, for
ˆ
A=range(a)and
ˆ
B=range(b), (3) to (6) hold.
ThenCis given by the following computable enumeration.
s
=0
.C0={a(0)}.
s>
0
.Cs=Cs−1∪{a(s)}∪{x:a(s)<x&[x−k,x+k]⊆Bs}.
For a proof ofC
=
ibTA, by (4) it sufces to show thatC =
ibT
ˆ
A. The latter is done
by showing that, fors>
0,
a
(s)=µx(x∈Cs\Cs−1). (7)
Note that, bya
(s)=µx(x∈
ˆAs\
ˆAs−1)for
ˆ
As={a(0),...,a (s)}, this implies
thatC
≤
ibT
ˆ
Aand
ˆ
A≤
ibTCby permitting. Now, for a proof of (7), observe that,
by defnition ofC,a
(s)∈Csand no new number<a (s)entersCat stages. So
it sufces to show that, fors>
0,a(s)/∈Cs−1. For a contradiction, picks> 0
minimal such thata (s)∈Cs−1and fxt<sminimal such thata (s)∈Ct. Then,
by defnition ofC
t,a(s)is an element of the third part ofC t, hence[a(s)−k,a(s)+
k]⊆Bt. It follows with (6) thatb (s)∈Bt. But, byt<s, this contradicts (5).
Finally, for a proof thatCis simple, note that, byC
=
ibTAand by noncom-
putability ofA,Cis noncomputable hence co-infnite. So, given an infnite c.e. set
V, it sufces to show thatC
∩V=∅. In order to do so, note that by the Simple Set
Lemma there are infnitely many numbersx
∈Vsuch that the interval[x−k,x+k]
is contained in the simple setB. So, given any computable enumeration {Vs}
s≥0
ofVwe can efectively enumerate numbersx 0<x1<x2<...and corresponding
stagess
0<s1<s2<...such thatx n∈Vsnand[xn−k,xn+k]⊆Bsn. By non-
computability of
ˆ
Athis implies that there are somesandnsuch thats>s nand
a
(s)<xn. So, by defnition ofC s,xn∈CshenceC ∩V=∅.

340 Klaus Ambos-Spies
0A nonzero nonsimple cl-degree
We now show that, forr =ibT,cl, there is a nonsimple c.e.r-degreea>0. By the
Coincidence Theorem, it sufces to show this forr
=ibT.
Theorem 10.There is a noncomputable c.e. setAsuch thatdeg
ibT(A)is not simple.
Proof.By a fnite-injury argument we enumerate a noncomputable c.e. setA
which is not ibT-equivalent to any simple set. As usual, we letA
sdenote the fnite
part ofAenumerated by the end of stages(A
0=∅).
In order to makeAnoncomputable it sufces to meet the requirements
22e:A+=φe(e≥0)
and, in order to ensure thatAis not ibT-equivalent to any simple set, it sufces to
meet the requirements
22e+1:[A=
ˆΦ
We
0
e1
&We0=
ˆΦ
A
e
2
]⇒We0is not simple
fore
=]e0,e1,e2310.
Before we give the formal construction of the setA, we describe the strategies
for meeting the requirements
2n. Fix uniformly computable infnite and pairwise
disjoint setsR
n(n≥0), sayR n=ω
[n]
=4]n,x3:x≥0}, and reserveR nfor the
strategy for meeting requirement
2n.
The strategy for meeting a noncomputability requirement
22eis standard. We
wait for a stages>
2esuch that there is a numberx ∈R2esatisfyingφ e,s(x)=0.
Then, for the least such stagesand the least corresponding numberx,xis put
intoAat stages
+1thereby ensuringA (x)+=φe(x). Note that if there are no such
stagesand numberxthenφ
e(x)+=0for allx ∈R2e, and no number fromR 2eis
put intoA. So
22eis met in this case too.
The strategy for meeting a nonsimplicity requirement
22e+1(e=]e0,e1,e23)
is a diagonalization strategy aiming at destroying the premise of the requirement.
The strategy will fail to achieve this goal only ifR
2e+1∩We0is fnite hence (by
Proposition 6)W
e0is not simple. So requirement22e+1is met no matter whether
or not the strategy becomes active. The strategy is as follows.
Wait for a stages>
2e+1such that for some numberx ∈R2e+1the following
hold.
(S
1)x∈We0,s
(S2)x/∈As
(S3)As(x)=
ˆΦ
We
0
,s
e1,s(x)
(S4)We0,s0x=
ˆΦ
As
e2,s0x

On the Strongly Bounded Turing Degrees of Simple Setsf 35
Then enumeratexintoAat stages
+1and restrain all lesser numbers fromA
thereby guaranteeing thatAfx
=Asfx.
To show that this action guarantees that the premise of requirement
f2e+1
fails, frst assume that
ˆ
Φ
We
0
,s
e1,s(x)=
ˆΦ
We
0
e1
(x). Then, by (S2) and (S3),
A
(x)=As+1(x)f=As(x)=
ˆΦ
We
0
,s
e1,s(x)=
ˆΦ
We
0
e1
(x),
henceA
f=
ˆΦ
We
0
e1
. On the other hand, if
ˆ
Φ
We
0
,s
e1,s(x)f=
ˆΦ
We
0
e1
(x)(where, by (S3),
ˆ
Φ
We
0
,s
e1,s(x)↓) then - since
ˆ
Φe1is an ibT-functional and since, by (S1),xhas entered
W
e0by stagesalready - a numberx
f
<xhas to enterW e0after stages, while, by
the restraint imposed onAat stages
+1, no number<xentersAafter stages. It
follows with (S
4) that
W
e0(x
f
)f=We0,s(x
f
)=
ˆΦ
As
e2,s(x
f
)=
ˆΦ
A
e
2
(x
f
),
henceW
e0f=
ˆΦ
A
e
2
. So in either case the premise off2e+1is not correct.
For a proof that the above strategy guarantees that requirement
f2e+1is met,
w.l.o.g. assume that the premise of
f2e+1holds and the strategy for meetingf2e+1
does not become active, henceR 2e+1∩A=∅. Then, for anyx ∈R2e+1, the condi-
tions (S
2), (S3) and (S4) hold for all sufciently large stagess. So, for anyx ∈R2e+1,
condition (S
1) must fail at all sufciently large stagess, hencex/ ∈We0. It follows
thatW
e0∩R2e+1=∅, henceW e0is not simple. So requirementf2e+1is met.
Note that the above strategies are fnitary. (More precisely, the
f2e-strategy is
positive and acts at most once while the
f2e+1-strategy is positive and negative
and acts at most once unless its restraint is injured.) So the strategies can be eas-
ily combined in a standard fnite injury fashion in the actual construction ofAas
follows where we attach the restraint functionr
(n,s)to requirementfndenoting
the restraint imposed by
fnat the end of stages. Since the noncomputability re-
quirements are purely positive,r
(2e,s)=0fore,s ≥0; andr (2e+1,0)=0for
e
≥0.
Stages
+1.
Requirementf2erequires attentionat stages +1ifs+1>2e,
A
s∩R2e=∅, and there is a numberx ∈R2esuch thatx> max{r(n
f
):n
f
<2e}
andφ e,s(x)=0; and, for the least suchx(if any), f2erequires attention via
x. Requirement
f2e+1(e=ae0,e1,e2x)requires attentionat stages +1if
s
+1>2e+1,r(2e+1,s)=0and there is a numberx ∈R2e+1such that
(S
1), (S2), (S3), (S4), and
(S
5)x> max{r(n
f
,s):n
f
<2e+1}
hold; and, for the least suchx(if any), f2e+1requires attention viax.

360 Klaus Ambos-Spies
Fixnminimal such that0nrequires attention and say that0nbecomesactive
at stages
+1. (If no requirement requires attention letr (n,s+ 1) =r(n,s)for
alln
≥0and proceed to stages +2.) Letn =2e+i,i≤1.
Ifn
=2eand02erequires attention viaxthen enumeratexintoAand let
r
(n
0
,s+ 1) =r(n
0
,s)forn
0
<2eandr (n
0
,s+ 1) = 0forn
0
≥2e.
Ifn
=2e+1and02e+1requires attention viaxthen enumeratexintoA
and letr
(n
0
,s+ 1) =r(n
0
,s)forn
0
<2e+1,r(2e+1,s+ 1) =x+1, and
r
(n
0
,s+ 1) = 0forn
0
>2e+1.
To show that the construction is correct, it sufces to show that all requirements
0nrequire attention at most fnitely often and are met. The proof is by induction
onn. So fxnand the uniquee
≥0andi ≤1such thatn =2e+i. By inductive
hypothesis, there is a stages
0>nsuch that no requirement0
n
0withn
0
<nre-
quires attention after stages
0. So, in particular,r (n
0
,s)=r(n
0
,s0)forn
0
<nand
s
≥s0, and we may fxx 0∈Rnminimal such thatr (n
0
,s)<x0forn
0
<nand
s
≥s0. Moreover,0nbecomes active whenever it requires attention after stages 0.
Now frst assume thatn
=2e. Then02ebecomes active at most once since
if
02ebecomes active at staget +1then a numberx ∈R2eis put intoAat stage
t
+1whence the clauseA s∩R2e=∅in the defnition of02erequiring attention
at stages
+1fails for alls>t. So 02erequires attention at most once after stage
s
0.
It remains to show that
02eis met. For a contradiction assume that02eis not
met. Then, obviously,
02enever becomes active, henceA ∩R2e=∅. Moreover,
since
02eis not met,A (x)=φe(x)=0for allx ∈R2e. It follows that, for all
sufciently larges,
02erequires attention viax 0at stages +1. But this contradicts
the fact that
02erequires attention only fnitely often.
Finally assume thatn
=2e+1. If02e+1becomes active at a stages +1>s0
thenr (2e+1,t)=r(2e+1,s+ 1)>0for allt>s, hence 02e+1does not require
attention after stages
+1. So02e+1requires attention at most once after stages 0.
It remains to show that
02e+1is met. Since02e+1requires attention only
fnitely often, we may fxx
1≥x0minimal such that there is nox ∈R2e+1∩A
withx
≥x1. Now, for a contradiction, assume that02e+1is not met, i.e., that the
premise of
02e+1holds andW e0is simple. Note that, by the observations on the
02e+1-strategy preceding the construction, the premise of02e+1fails if there is
a stages
+1at which02e+1becomes active provided that02e+1is not injured
later. So, by assumption and by choice ofs
0,r(2e+1,s)=0fors≥s0and02e+1
does not require attention after stages 0. But the latter can be refuted as follows.
It sufces to show that there is a numberx>x
0inR2e+1and a stages ≥s0such
that (S
1)-(S4) hold. By simplicity ofW e0, fxx ∈We0∩(R2e+1∩{x:x≥x1})and

On the Strongly Bounded Turing Degrees of Simple Sets( 37
s
1≥s0such thatx ∈We0,s1. Then (S1) and (S2) hold at all stagess ≥s1; and (S3)
and (S
4) hold at all sufciently large stagessby the assumption that the premise
of
:2e+1is satisfed.
By the Coincidence Theorem, Theorem 10 immediately carries over to cl-re-
ducibility.
Corollary 11.There is a noncomputable c.e. setAsuch thatdeg
cl(A)is not simple.
For an extension of Corollary 11, which we will prove in the next section, we have
to use a direct argument for constructing a nonsimple cl-degree and cannot refer
to the Coincidence Theorem. So, in the remainder of this section, we show how the
proof of Theorem 10 can be adjusted in order to obtain a direct proof of Corollary
11.
Direct proof of Corollary 11.In order to makedeg
cl(A)nonsimple we have to re-
place the nonsimplicity requirements
:2e+1in the proof of Theorem 10 by the
stronger requirements
:2e+1:[A=
˜Φ
We
0
e1
&We0=
˜Φ
A
e
2
]⇒We0is not simple
(fore
==e0,e1,e2˜(0) where the ibT-functionals are replaced by cl-functionals
(while the noncomputability requirements
:2eare unchanged). Here we assume
that the coding function is chosen so thate
0,e1,e2&=e0,e1,e2˜. So, by choice
of the enumeration of the cl-functionals, the use of the cl-functionals
˜
Φ
We
0
e1
(x)and
˜
Φ
A
e
2
(x)is bounded byx +e.
The strategy for meeting the thus modifed nonsimplicity requirements for cl-
functionals is somewhat more involved than the previously described strategy for
meeting the original requirements for ibT-functionals.
Fix the computable partition ofωinto fnite intervalsI
n=[yn,yn+1)(y0=0)
where, fore,m
≥0, the intervalI
(2e,m)has length1while the intervalI
(2e+1,m)
has length2e+1, i.e.,y
(2e+1,m)+1=y
(2e+1,m)+2e+1, and letx
(2e+1,m)=
y
(2e+1,m)+ebe themiddle elementof the intervalI
(2e+1,m). Then the uniformly
computable infnite and pairwise disjoint setsR
nreserved for the requirements
:n,n≥0, are defned byR n=
(
m≥0
I
(n,m).
The revised strategy for meeting
:2e+1is as follows. Wait for a stages> 2e+1
such that for somem ≥0the following hold.
(S
[
1
)I
(2e+1,m)⊆We0,s
(S
[
2
)x
(2e+1,m)/∈As
(S
[
3
)As(x
(2e+1,m))=
˜Φ
We
0
,s
e1,s(x
(2e+1,m))
(S
[
4
)We0,s(y
(2e+1,m)=
˜Φ
As
e2,s(y
(2e+1,m)

380 Klaus Ambos-Spies
Then, for the least suchsand for the least correspondingm, putx
02e+1,m1into
A
s+1and restrain all numbers<x
02e+1,m1fromA.
To show that this action guarantees that the premise of requirement
02e+1
fails, frst assume that
˜
Φ
We
0
,s
e1,s(x
02e+1,m1)=
˜Φ
We
0
e1
(x
02e+1,m1). Then, by (S
2
2
) and
(S
2
3
),
A
(x
02e+1,m1)1=As(x
02e+1,m1)=
˜Φ
We
0
,s
e1,s(x
02e+1,m1)=
˜Φ
We
0
e1
(x
02e+1,m1),
henceA
1=
˜Φ
We
0
e1
. So, for the remainder of the argument, we may assume that
˜
Φ
We
0
,s
e1,s(x
02e+1,m1)1=
˜Φ
We
0
e1
(x
02e+1,m1)where, by (S
2
3
),
˜
Φ
We
0
,s
e1,s(x
02e+1,m1)↓. Then
there must be a numberz
∈We0\We0,ssuch that
z
≤˜φ
We
0
,s
e1,s(x
02e+1,m1)≤x
02e+1,m1+e<y
02e+1,m1+1.
In fact, by (S
2
1
),z<y
02e+1,m1. So, by (S
2
4
),We0(z)1=We0,s(z)=
˜Φ
As
e2,s(z)↓. But,
since
˜φ
As
e2,s(z)≤z+e<y
02e+1,m1+e=x
02e+1,m1,
it follows withA0x
02e+1,m1=As0x
02e+1,m1that
˜
Φ
A
e
2
(z)=
˜Φ
As
e2,s(z). SoW e0(z)1=
˜
Φ
A
e
2
(z), henceW e01=
˜Φ
A
e
2
.
For a proof that the above strategy guarantees that requirement
02e+1is met,
w.l.o.g. assume that the premise of
02e+1holds and the strategy for meeting02e+1
does not become active, henceR 2e+1∩A=∅. Then, for anym ≥0, the conditions
(S
2
2
), (S
2
3
) and (S
2
4
) hold for all sufciently large stagess. So, for anym ≥0, con-
dition (S
2
1
) must fail at all sufciently large stagess, henceI
02e+1,m1(mWe0, i.e.,
|I
02e+1,m1∩We0|<2e+1. (In the actual construction, due to the fnite injuries
we can only argue that this is true for all sufciently largem.) Now fxkmaximal
such that
|I
02e+1,m1∩We0|=kfor infnitely manym, fxm 0minimal such that
|I
02e+1,m1∩We0|≤kfor allm>m 0, and efectively enumerate numbersm pand
stagess
p(p≥1) such thatm 0<m1<m2<m3<...and |I
02e+1,mp1∩We0,sp|=k.
Then, for
z
p=μz(z∈I
02e+1,mp1\We0,sp),
z
p/∈We0. SoW e0does not intersect the infnite computable set{zp:p≥1}hence
is not simple. So
02e+1is met.
In the actual construction ofAit sufces to adjust the defnition of
02e+1re-
quiring attention and the action in case that
02e+1becomes active as follows. Now
requirement
02e+1(e=e0,e1,e2)requires attentionat stages +1ifs+1>2e+1,
r
(2e+1,s)=0and there is a numberm ≥0such that (S
2
1
), (S
2
2
), (S
2
3
), (S
2
4
), and
(S
2
5
)x
02e+1,m1>max{r(n
2
,s):n
2
<2e+1}
hold; and, for the least suchm(if any), 02e+1requires attention viam. If 02e+1
becomes active at stages +1and02e+1requires attention viamthenx
02e+1,m1is

On the Strongly Bounded Turing Degrees of Simple Sets0 39
enumerated intoAat stages
+1and the restraint of02e+1is set tor (2e+1,s+1) =
x
02e+1,m1+1.
The correctness of the construction is established as in the proof of Theorem
10 using the above observations on the strategy for the modifed nonsimplicity
requirements.
0An interval of nonsimple degrees
The proof of the existence of nonzero nonsimple c.e.r-degrees (r =ibT,cl) can be
easily extended to show that there are nontrivial - in fact infnite - intervals of c.e.
r-degrees containing only nonsimpler-degrees.
Theorem 12.There are c.e. setsAandBsuch that
A
≤
ibTB, (8)
B
21TA, (9)
and
∀Cc.e.[A≤
clC≤
clB⇒Cis not simple] (10)
hold.
Proof.The proof is obtained by some rather straightforward modifcations of the
direct proof of Corollary 11 outlined at the end of the preceding section. So we only
give the basic ideas and leave the details to the reader.
By a fnite-injury argument, we construct c.e. setsAandBwith the required
properties, and we letA
sandB sdenote the fnite parts ofAandB, respectively,
enumerated by the end of stages(A
0=B0=∅).
In order to satisfy (9) and (10) it sufces to meet the requirements
02e:B2=Φ
A
e
(fore ≥0) and
02e+1:[A=
˜Φ
We
0
e1
&We0=
˜Φ
B
e
2
]⇒We0is not simple
(fore
=]e0,e1,e2:,e≥0), respectively.
As in the direct proof of Corollary 11, fx the computable partition ofωinto
the fnite intervalsI
n=[yn,yn+1)(y0=0) where intervalI
02e,m1has length1and
intervalI
02e+1,m1has length2e+1, letx
02e+1,m1=y
02e+1,m1+e, and reserve

400 Klaus Ambos-Spies
the infnite computable setR n=
0
m≥0
I
∩n,m∅for requirement0n. Moreover, let
R
even=
0
e≥0
R2eandR
odd=
0
e≥0
R2e+1.
Then (8) is guaranteed by ensuring
A
∩Ieven=∅& A∩I
odd=B∩I
odd. (11)
The strategy for meeting requirement
02eis the standard Friedberg-Muchnik strat-
egy. We pick the least unused numberxfrom the reserved intervalsI
∩2e,m∅,m≥0,
which is not restrained by any higher priority requirement and wait for a stages
such thatΦ
As
e,s(x)=0(and such that no higher priority requirement wants to act).
Then, at stages
+1, we putxintoBand restrain all numbers ≤φ
As
e,s(x)fromA.
Note that this strategy is fnitary (i.e., if injured only fnitely often, then
02eacts
only fnitely often and the restraintr
(2e,s)imposed by02eis bounded).
The strategy for meeting requirement
02e+1is essentially the strategy for
meeting the corresponding requirement in the direct proof of Corollary 11. Since
the role played byAthere is now split betweenAandB, however, clause (S
≥
4
) has
to be replaced here by
(S
≥≥
4
)W e0,s0x
∩2e+1,m∅=
˜Φ
Bs
e2,s0x
∩2e+1,m∅
while clauses (S
≥
1
)-(S
≥
3
) remain unchanged.
So now the positive part is played byAwhile the negative part is played byB.
Accordingly, if the strategy acts at stages
+1viam, nowx
∩2e+1,m∅is put intoAand
all numbers<x
∩2e+1,m∅are restrained fromB. In order to satisfy (11), however, we
have to treatAandBequally onI
odd. So, actually, we putx
∩2e+1,m∅intoAandB
and we restrain the numbers<x
∩2e+1,m∅fromAandB. Note that this modifcation
does not interfere with the basic strategy, and we can argue as before that the
strategy succeeds.
Theorem 12 immediately implies that, forr =ibT,cl, there are c.e.r-degreesaand
bsuch thata<band the interval
[a,b]={c∈Rr:a≤c≤b}contains only
nonsimpler-degrees, i.e.,
[a,b]⊆
Sr. In fact, by the following observation we may
argue that the interval
[a,b]is infnite.
Lemma 13.(a) LetD,E,Fbe c.e. sets such thatD
≤wttE≤wttFandD ≤rF
(r
=ibT,cl). There is a c.e. set
ˆ
Esuch thatD ≤
ibT
ˆ
E≤rFand
ˆ
E=wttE.
(b) LetDandFbe c.e. sets such thatD<
wttFandD< rF(r=ibT,cl). There is
a c.e. setEsuch thatD<
rE<rFandD< wttE<wttF.
Proof.(a) By Proposition 5, w.l.o.g. we may assume that there is an infnite com-
putable setRsuch thatD
∩R=∅. Moreover, byE ≤wttFthere is a computable
shiftfsuch thatE
≤
f-TFhenceE
f≤
ibTF. So, for the computable shiftgenumer-
atingRin order, it follows with the Computable-Shift Lemma that
(E
f)g=wttE

Random documents with unrelated
content Scribd suggests to you:

and their abstemious temperament, but particularly their capability
of travelling without water, for many successive days, enable them to
perform such journeys as would destroy, probably, any other species
of quadruped. The caravans, or troops of merchants, that traverse,
in all directions, the deserts of Egypt and Arabia, are always
accompanied by camels, which are often more in number than the
men. These commercial travels are sometimes to the distance of 700
or 800 leagues, and are usually performed at the rate of ten or
twelve leagues a day, the camels being, every night, unloaded to
rest and feed. For the latter purpose, if better provender cannot be
had, they are contented with a small quantity of dates or a few
beans, together with the scattered and oftentimes bitter herbage
which the desert affords. The burden of each camel usually weighs
about half a ton; and, at the command of his conductor, he kneels
down for the greater convenience of being loaded. It is from this
practice that we account for those horny parts that are observable
on the bellies, knees, and limbs, even of the animals that are
exhibited in England. Camels are trained, from the earliest part of
their life, to the labours which they are afterwards to perform: and,
with this view, when but a few days old, their limbs are folded under
their body, and they are compelled to remain on the ground whilst
they are loaded with a weight, which is gradually increased as they
increase in strength. As soon as they have acquired sufficient
strength they are trained to the course, and their emulation is
excited by the example of horses or of other camels.
The pace of the camel is a high and swinging trot, which, to persons
unaccustomed to it, is at first disagreeable and apparently
dangerous, but is afterwards sufficiently pleasant and secure. The
Arabians, in general, ride on a saddle that is hollowed in the middle,
and has, at each bow, a piece of wood placed upright, or sometimes
horizontally, by which the rider keeps himself in the seat. A ring is
inserted into the nostrils of the camel, to which a cord is affixed; and
this serves as a bridle to guide and stop him, or to make him kneel
when the rider wishes to dismount. Mr. Bruce informs us that, in the

caravans of one of the Abyssinian tribes, the people sometimes ride
two together on each camel, and sit back to back.
The camels of Sahara are probably more fleet than any that are
known; and, on these animals, the Arabs, with their loins, breast,
and ears bound round, to prevent the injurious effects of percussion
from the quickness of motion, can cross that great desert in a few
days. With a goat's skin or a porous earthen pitcher filled with water,
a few dates, and some ground barley, the Arab travels from
Timbuctoo to Morocco, feeding his camel but once upon the road. In
one instance a camel was known to travel from Fort St. Joseph, on
the river Senegal, to the house of Messrs. Cabane and Depras at
Mogador, a distance of more than 1000 miles, in seven days.
It has been observed that the camel is the most completely and
most laboriously enslaved of all animals; the most completely,
because, in the other kinds of domestic animals, we find at least
some individuals in their natural state, and which have not yet been
subdued by man: but the whole species of the camel is enslaved;
and not any of them are now to be found in their primitive state of
independence and liberty. He is the most laboriously enslaved
because he has never been trained, but as a beast of burden whom
man has not harnessed nor taught to draw, but whose body is
considered a living carriage which may be loaded and oppressed.
The above are not the only uses of the camel. The hair or fleece of
these animals, which is renewed every year, and which regularly falls
off in the spring, is so soft that the finest parts of it may be
manufactured into stuffs of beautiful texture: and, in Europe, when
mixed with the fur of the beaver (69), it is sometimes made into
hats. The inhabitants in some parts of Sahara live in tents formed of
woven camel's hair; this forms a thick covering completely water-
proof. After the hair has been stripped off, the skin is converted into
leather.

In Arabia the milk of the camel is a most important article of
nutriment; and the flesh, though dry and hard, is not unpalatable,
particularly when young. By the inhabitants of Egypt camels' flesh is
so much esteemed, that, at Cairo and Alexandria, it was formerly
forbidden to be sold to Christians. In many parts of Africa the
tongues are salted and dried, both for use and exportation; and,
with the ancient Romans, the heels of camels were eaten as a great
delicacy.
77. The BACTRIAN, or TWO-BUNCHED CAMEL (Camelus
bactrianus), is known by having two bunches on its back; and by
being somewhat larger, and having shorter legs than the Arabian
species.
This animal is found in Usbec Tartary, the ancient Bactria: it is
likewise a native of Siberia, Thibet, and some parts of China.
The purposes to which the Bactrian camel are applied are the same
as those already described respecting the Arabian species (76).
These animals, however, are sufficiently hardy to sustain the climate
of the temperate parts of Siberia, and to be able, without injury, to
traverse even humid and marshy countries, which would soon prove
fatal to the Arabian camel.
78. The LLAMA, or GLAMA (Camelus glama), is a South
American species of camel, of small size, which has a
protuberance on the breast, and no bunch on the back.
The colour of the llama is white, grey, and russet, variously
disposed. Its height, to the top of the back, is somewhat more
than four feet, and to the head nearly six feet.

Without the aid of these animals, the Spaniards who inhabit the
mining districts of South America would labour under great
inconveniences for the transport of their merchandise and treasures:
since mountains that are altogether inaccessible to the horse, are
with facility traversed by the llama. This beast, though not so
patient, is nearly as abstemious as the camel. He proceeds, when
loaded, with a slow but sure pace, and performs journeys, in these
mountainous regions, more than 200 leagues in extent. Sometimes
he will travel four or five days successively without appearing
desirous of repose, and then he rests spontaneously, for twenty or
thirty hours, before he resumes his toil. Like the camel, these
animals kneel to be loaded; and they are directed in this, and in
most other of their motions, by their conductor's whistle. The value
of the best llamas is about eighteen ducats, and of the common
ones twelve or thirteen ducats each. The burdens they are able to
carry are from 150 to 200 pounds' weight: and the number of llamas
that are kept in actual employ is supposed to exceed 300,000.
Of the skin of the llama a hard kind of leather is made, which is
converted into harness, the soles of shoes, and to many other useful
purposes. But, as it is only tanned, and not curried, it is soon injured
by exposure to wet. The hair, or fleece, particularly of the wild
llamas, which is longer than that of the animals in a domesticated
state, is much in request for the manufacture of camlets and other
stuffs, some of which are of very beautiful texture, and also for the
making of hats. On this account the animals are frequently hunted in
the plains with dogs, or killed with guns; but such is their activity
amongst rocks, that, if they can once reach these, the hunters are
generally obliged to desist from any further pursuit. The flesh of the
llama is a wholesome and excellent food. Sometimes it is salted,
and, in this state, like our salt beef, is adopted as provision for ships
proceeding on long voyages. That, however, of the young llamas
four or five months old is preferred, and is considered as good as
veal. Many parts of these animals are adopted by the inhabitants of
South America as medicines.

79. The VICUNA (Camelus vicugna) is a small South American
species of camel, with woolly fleece, a flat and blunt nose, an
erect tail; and without any bunches.
This animal inhabits, in a wild state, and in extensive flocks, the
highest peaks of the Andes.
Unable to sustain burthens exceeding sixty or seventy pounds in
weight, the vicuna is seldom employed in the transport of
merchandise. It is chiefly in esteem on account of its fleece, which is
of a dead rose colour, and as soft and valuable as silk. This, in South
America, is spun and woven into gloves, stockings, quilts, carpets,
and innumerable other articles, which are sold at great prices, and
constitute an important branch of commerce.
In most of their habits these animals have a close alliance with the
llama, and their general figure is nearly the same. They are gentle
and inoffensive, and, though not tamed with quite so much facility,
are capable of great attachment towards those who have the care of
them. Amongst their native mountains they are so light and agile, in
all their motions, that it is not easy to come within reach of them,
except by stratagem; and, consequently, though dogs are sometimes
employed to hunt them, they are much more frequently killed by
snares or traps than in any other way.
In consequence of the great advantages which, in America, are
derived from the wool of the vicuna, the Spaniards were, some years
ago, induced to attempt the introduction of these animals into
Europe. Some of them were brought to Spain; but, from want of
proper attention to their natural habits, the experiment entirely
failed.

80. The MUSK (Moschus moschiferus, Fig. 27) is a small
quadruped, somewhat shaped like a deer, but without horns; it
has two projecting tusks curved downward, a short tail; and,
about the middle of the under part of the male, there is an oval
bag, about the size of a small egg.
This animal is seldom more than about two feet in height at the
shoulder, and is clad with long, upright, and thickset hair. Each
hair is waved, and of three different colours; the tip ferruginous,
the middle black, and the bottom dusky.
It inhabits the mountains of Thibet, Tonquin, and Siberia.
The drug called musk is a brown fatty substance, which appears
somewhat like clotted blood. It is contained in the bag or receptacle
under the belly, which has two small external orifices; through these,
when it is overcharged, the animal squeezes it out upon trees or
stones. The mode in which musk is collected for sale is to kill the
animals, cut off the bags, and tie them closely up to prevent it from
being spoiled by evaporation. In those countries where the animals
are most abundant they are pursued in the autumn and winter, and
generally with so much success that many thousands of bags are
annually collected. It is, however, presumed that, of those which are
sold, many are factitious, formed of other parts of the skin, and filled
with musk adulterated by mixture with other substances. Indeed, so
valuable is this drug, that it is seldom to be obtained in a pure state.
To increase its quantity blood is not unfrequently mixed with it; and,
to increase its weight, lead finely ground, and sometimes even little
bits of lead, are put into the bags. The natives of India are said to
have various methods of detecting this adulteration, by the taste and
the weight; but, principally, by a thread steeped in the juice of garlic,
which they draw through the bag with a needle; this, if it retain the
smell of garlic, is considered a decisive indication of the musk having
improper ingredients mixed with it. The purest musk is said to be

that which is brought from Patna, in the dominions of the Great
Mogul, where it is collected from various parts of the interior of the
country. It is imported into Europe in bags, each of which is about
the size of a pigeon's egg, well filled, and covered with short brown
hair.
Musk was formerly much used as a perfume. It is now chiefly in
repute as a medicine in spasmodic, convulsive, and other
complaints; and, when properly given, is thought a remedy of great
service. So powerful is the scent of this drug, that the smallest
particle of it will perfume a very considerable space; and, when the
bags are fresh, if one of them be opened in a close apartment, every
person present is obliged to cover his mouth and nose with several
folds of linen, to prevent suffocation.
In all the countries where these animals are found, their skins are in
great request as a strong and valuable leather; and, when tanned
and properly prepared, the Russians have a method of rendering this
nearly as soft and shining as silk. These skins are also sometimes
dressed as furs for winter clothing. The flesh of the musk is
frequently eaten; but that of the young ones only is tender and of
good flavour.
These animals, which are astonishingly light and active in all their
motions, and at the same time of inoffensive and timid habits and
disposition, are caught by snares placed near their feeding places;
are shot with arrows, and sometimes killed by cross-bows, so placed
that they discharge arrows, by the animals treading on a string
connected with the trigger.
81. The ELK, or MOOSE DEER (Cervus alces, Fig. 8), is the
largest species of deer that is known, and is distinguished from

all others by having broad and flattened horns with several
points, no brow-antlers, and a hairy protuberance on the throat.
In size these animals are frequently larger than a horse. Their
upper lip is square, very broad, deeply furrowed, and hangs over
the mouth. The hair of the male is black at the points, dusky in
the middle, and white at the roots; that of the female is of sandy
brown colour, except under the throat, belly, and flank, which
are whitish. The males only are horned.
The elk inhabits the forests of North America, of some parts of
Europe, and of Asia as far south as Japan.
Strong and powerful as these animals are, it has been found possible
to domesticate and train them to labour. Mr. Livingston, at a farm
near New York, made the experiment by breaking two elks to the
harness. After having been only twice bitted, though two years old,
they appeared equally docile with colts of the same age, applying
their whole strength to the draught, and proceeding in a steady
pace. The motion of these animals is a shambling kind of trot, but it
is very rapid, and, in drawing carriages, they are able to out-travel a
horse. They are also less delicate in their food than horses, are long-
lived, and more productive than any known beast of burden, having
annually from one to three young ones at a birth. Elks were formerly
used in Sweden for the drawing of sledges; but as they were
frequently employed in the escape of criminals from justice, the use
of them was prohibited under severe penalties.
The inhabitants of all countries where the elk is found esteem its
flesh a sweet and nutritious food, though the grain is coarser than
that of most other kinds of venison. The American Indians assert
that they can travel further, after having eaten of it, than of any
other animal food. After having been properly salted and dried, the
tongues are better than those of the ox; and the nose, when

cooked, is stated to eat like marrow, and to be one of the greatest
delicacies which are produced in Canada. Of the skins an excellent
buff leather is made, which is strong, light, and soft. This leather is
used by the Indians for tent-covers, snow-shoes, and the coverings
of canoes. The long hair of the elk is well adapted for the stuffing of
mattresses and saddles.
In Canada the hunting of the wild elk is a frequent but in general a
most laborious, pursuit, which chiefly occupies the attention of the
Indians during winter, when the whole surrounding country is
covered with snow.
In a wild state these animals browze the thick and lofty grasses of
the plains, and the leaves and tender branches of trees. During the
summer they frequent the banks of rivers and lakes; and in winter
they often traverse vast distances upon the frozen snow.
Notwithstanding the natural strength of their body, their disposition
is so mild and inoffensive, that, even when pursued and attacked,
they seldom attempt any resistance.
82. The REIN-DEER (Cervus tarandus, Fig. 28) is known by its
horns being long, bent back, slender, branched, and generally
broad at the extremities.
It is about four feet and half high at the shoulder, and is of
brown or greyish white colour above, and white on the under
parts of the body. Both the sexes are horned.
These animals inhabit several of the alpine districts of America,
and of the northern countries of Europe and Asia.
Useful and even indispensable as many of the domestic animals of
this country are to us, the rein-deer is infinitely more so to the

Laplander. For travelling, and the conveyance of heavy burdens in
sledges and carriages, he supplies the place of the horse; and such
is the speed with which he traverses the frozen snows of that dreary
region, that he is able, with ease, to perform a journey of near a
hundred miles in one day. To this labour the animals are trained from
the earliest period of their lives: and neither darkness nor storms
can essentially impede their progress. The usual mode of travelling is
in sledges, to which one or more of the animals are yoked. The
sledges are extremely light, somewhat shaped like a boat, having at
the back an upright board for the driver to lean against. Being
rounded and not flat underneath, much dexterity is requisite in the
balancing and management of them. The driver is tied in, and
protected by a cover which encloses all the lower parts of his body,
and shelters him from the inclemency of the weather. The rein-deer
is yoked by a collar, from which a trace is brought under the belly
between the legs, and fastened to the fore part of the sledge; and
the animal is guided by a cord or rein fastened to its horns, and tied
to a hoop held upon the driver's right thumb. He directs the course
of the deer by pulling the rein on the side he would have him go,
encouraging him at the same time with his voice. In general, the
Laplanders can travel with ease about thirty miles without stopping.
To persons unaccustomed to the habits of the Laplanders and their
animals, it will appear wonderful that they should be able to travel
during the winter, by night as well as by day, the earth presenting
one uniform surface of snow, and not a single vestige of human
industry and labour being discernible to direct their course; the
snow, at the same time, flying about in all directions, and almost
blinding them. Yet it is certain that they are under no difficulty in
finding the spot to which they are bound; and dangerous as these
journeys may seem, they rarely experience any accident. When
several persons are travelling in company, they fix bells to the
harness of the animals, that the whole may be kept together by
hearing when they cannot see each other, after the light of their
short day has failed them. To guide them in their course, the

Laplanders observe, in the day-time, the quarter whence the wind
blows, and, at night, they are directed by the position of the stars.
The missionary Leems, who resided ten years amongst the
Laplanders, remarks that, during the whole of that time, he did not
remember more than one fatal accident to have occurred from this
mode of travelling.
As the rein-deer supplies, to the Laplanders, the place of a horse for
conveyance and carriage, so it is an invaluable substitute for the cow
in affording them food. The females supply them with milk, each
yielding about as much as a common she-goat. This, though not so
thick as the milk of the cow, is said to be sweeter and more
nutritive: and produces them both butter and cheese. The mountain
Laplander subsists, through the whole winter, upon these, or upon
flesh of the rein-deer, slaughtering two or three every week,
according to the number of his family. The animals are killed by
stabbing them in the neck, and the wound is so dexterously inflicted
that no blood flows from it; but this is found in the inside, whence it
is carefully taken out, and prepared for use. The fat of the rein-deer
serves also for food.
Of the skin, after it has been properly prepared, the Laplanders
make garments, gloves, shoes, and caps, which cover them from
head to foot, and protect them against the cold. These skins also
serve as interior coverings for tents, as linings and coverings for
sledges, and as beds. They are more or less valuable, according to
the season in which the animals have been killed. If slain in the
spring, the hides are found to be perforated, in various parts, by a
species of insect which lays its eggs in them; but if the deer be killed
in winter the skin is free from these defects. The Laplander, however,
desirous of obtaining the same price for a defective skin as for a
perfect one, frequently attempts to defraud the purchaser by artfully
closing up the holes in such manner as to render them scarcely
visible.

The horns are converted into handles for different kinds of
instruments, and an excellent glue is made of them. The bones are
likewise of use; and the sinews or tendons of the legs, after having
been held before the fire and beaten with wooden hammers, are
divided into filaments as fine as hair, which answer all the purposes
of thread; and these filaments twisted together, serve for bowstrings
and cords of different kinds.
So numerous and important are the uses of the rein-deer in Lapland,
that there are few inhabitants of that country who do not possess
them; and some of the wealthiest Laplanders have herds consisting
of more than 1000 head. In the summer-time these feed on divers
plants which flourish during that season; but, in winter, they either
browze on the rein-deer liverwort (Lichen rangiferinus), which they
dig up from beneath the snow with their feet and horns; or on
another kind of liverwort, which hangs on the branches of fir-trees,
and which affords them sustenance when the snows are too deep or
too hard frozen to allow them to reach that.
Wild rein-deer live in the mountains and woods, and the hunting of
them is, in general, attended with excessive fatigue; as they are
endowed with astonishing muscular powers, and also possess a
nicety and acuteness of precaution which can scarcely be equalled.
Some idea may be formed of the difficulty of this pursuit, when it is
stated that a Laplander, in chase of one of these animals, has been
known to creep on his hands and knees through shrubs and moss,
for nearly five miles, before he could approach within gun-shot of his
prey. The various modes in which rein-deer are pursued, are too
numerous and too intricate to require a detail in this place. It may
be sufficient to say that they are assailed by dogs, traps, pitfalls,
snares, cross-bows, and fire-arms, in all the ways which the
inventive art of man can devise.

83. The STAG, or RED DEER (Cervus elaphus, Fig. 9), is a large
species of deer, generally of reddish brown colour on the upper
parts of the body, and white beneath; with large and much
branched horns, rounded through their whole length.
The males only are horned. The males is called stag, or hart, the
female hind, and the young one has the name of fawn.
Red deer are found in the mountainous parts of Scotland; in the
forest of Martindale, Cumberland; in the New Forest, Hampshire;
in the woods on the river Tamar, in Devonshire; and amongst
the mountains of Kerry in Ireland. On the Continent of Europe
and in several parts of Asia and North America, they are very
common.
The hunting of these animals was formerly considered one of the
most important occupations of the English nobility, and, during the
Saxton Heptarchy, it was the privileged pursuit of the sovereign and
his court. By the kings of the Norman line laws of the most
sanguinary description were enacted for the preservation of these
the royal game, it being then deemed less criminal to destroy an
individual of the human species than a beast of chase. Forests were
enlarged for the shelter of wild animals, and for the more ample
enjoyment of the diversion of hunting, at the expense of every
principle of justice and humanity. Happily for us, the scenes of
devastation which this pursuit occasioned have long ceased to exist;
and those vast tracts of country which were once dedicated to
hunting, are now, for the most part, applied to the advantages and
comfort of man.
As, therefore, the breed of red deer is now chiefly preserved in this
kingdom from motives of curiosity, rather than either an object of
amusement or utility, we are indebted almost wholly to foreign
countries for those parts of the stag which are important in a

commercial, economical, and medical view. The skins are
manufactured into an excellently soft, and somewhat yellow-
coloured leather, which is useful for numerous purposes. Many very
extraordinary medicinal virtues were formerly attributed to the horns
of the stag, and indeed to nearly all parts of its body: but the
experience of late years gives no countenance to them. The horns
are of nearly the same nature as bones, and the preparations of
them, by heat, are similar to those of solid animal substances in
general. Consequently the articles denominated spirit of hartshorn,
and salt of hartshorn, though formerly obtained only from the horns
of different species of deer, are now chiefly prepared from bones.
The former of these, which is a volatile alkali of very penetrating
nature, is an efficacious remedy in nervous complaints and fainting
fits; and salt of hartshorn has been successfully prescribed in fevers.
The scrapings or raspings of the horns, under the name of hartshorn
shavings, are variously employed in medicine. Boiled in water, the
horns of deer give out an emollient jelly which is said to be
remarkably nutritive. Burnt hartshorn is employed in medicine. The
horns of the stag are used by cutlers and other mechanics for the
handles of knives and for cutting instruments of different kinds. The
flesh of every species of deer has the name of venison; that of the
young red deer is very delicate eating, that of the female is by no
means bad, but that of the full-grown stag has a strong and
disagreeable flavour.
These animals generally live in herds that consist of females, with
their offspring, headed by one male, and they inhabit the wildest
and most unfrequented parts of forests, browzing on grass, and on
the leaves and buds of trees. They have a penetrating sight, and an
exquisite smell, and are always on guard against the approach of
danger. Their disposition, when unprovoked, is mild and peaceable;
but if attacked, they prove extremely formidable opponents. The
females produce their offspring (generally one each) about the end
of May, or the beginning of June.

84. The FALLOW DEER (Cervus dama, Fig. 10) is a considerably
smaller animal than the stag, generally of brownish bay colour
on the upper parts of the body and whitish beneath, with
branched horns, bent backward, compressed and broad at their
extremity.
The males only are horned. The male of the fallow deer is called
buck, the female doe, and the young one fawn.
Common as these animals are in parks throughout every part of
England, they are not found wild in this country. They, however,
inhabit various forests of the Continent; even as far as the south
of Persia.
There is no species of food in more general request by epicures and
bon-vivans than the venison of the fallow deer. This, when properly
dressed, is an excellent aliment, and easily assimilated to the human
fluids; but when half putrid, as is generally the case, it is considered
very detrimental to health. The best season for killing the bucks for
venison is from about the first of July to somewhat later than the
middle of September; and that for the does is from about the middle
of November to the middle of February.
The does produce one, sometimes two, and rarely three young ones
each, about the beginning of June; these, for the first year, are
called by the park-keepers fawns, if, during that time, they have no
horns; the second year, if the young one be a male, it is called a
pricket; in the third year, a sorel, and in the ensuing year, a sore;
when he attains his fifth year he has the name of buck, and is
accounted fit to be killed; but if he be suffered to live a year or two
longer, he will improve both in flesh and fatness. If the young one be
a female it is called during the first year, a fawn, during the second a
teg, and, after that, it takes its proper name of doe. Such does as
are intended to be killed in their season are either what have had no

fawns in the preceding summer, or have had these killed and taken
away.
The horns of fallow deer are used for all the same purposes as those
of the stag (83); and their hides, under the name of buck-skin and
doe-skin, have long been celebrated for their softness and pliability;
and the manufacturing of them into breeches and gloves affords
subsistence to a very numerous and industrious class of people.
Extensive herds of fallow deer associate together in large parks.
These animals are less savage than red deer, yet when offended
they often become ferocious. They feed on several kinds of
vegetables, and on the leaves, bark, and young branches of trees;
many of which, particularly hollies, are cut down, by park-keepers, in
the severe weather of winter, for their subsistence.
85. The ROE or ROE-BUCK (Cervus capreolus) is a small species
of deer, not more than two feet and half high at the shoulder, of
reddish brown colour, which has short erect horns, divided
towards their extremity into two or three points.
The males only have horns.
Small flocks of these animals are found wild in several of the
mountainous districts of Scotland, and also in the mountainous
woods of Germany, Switzerland, and other parts of the continent
of Europe, as well as in those of North America.
In some countries the venison of the roe is esteemed, during the
proper season, equal to that of any other species of deer. There is,
however, a great difference in it, according to the country in which
the animals have fed, and the different races or varieties of the
animals themselves. The flesh also of the bucks which have passed

their second year is said to be tough and not well flavoured, whilst
that of the does, though of much greater age, is tender. Those
animals that are fed in parks, plains, and valleys, are also greatly
inferior to such as have resided among mountains.
In America the skins of roes are an important object of commerce.
They are very light, and are capable, for some time, of resisting the
effects of moisture. Of these skins the American Indians make bags
or bottles, in which they are able to keep oil, honey, butter, and
other similar substances. They are also converted into clothing, and
are sometimes dressed as furs, but the hair soon falls off. The hair
itself is valuable for the stuffing of horse-collars and saddles, and it
has the advantage of not becoming knotty like that of the ox. The
horns are used in making handles for knives and for other purposes.
86. The CHAMOIS (Antilope rupicapra, Fig. 11) is a kind of
antelope about the size of a goat, with short, erect, round, and
smooth horns, which are hooked backward at the tips.
Its colour is dusky yellowish brown on the upper parts of the
body, with the cheeks, chin, throat, and belly, yellowish white.
The horns, which are common to both the sexes, are generally
about eight inches in length, but shorter in the female than the
male.
These animals inhabit many of the mountainous parts of Europe,
particularly the Alps and Pyrenees.
There are few pursuits more arduous and difficult than the hunting
of the chamois. Being wholly confined to rocky and mountainous
situations, dogs are nearly useless in it; and such are the sagacity
and acuteness of perception of these animals, that they take alarm
at the most distant approach of danger, and the stratagems which

are practised to come within gun-shot of them are almost
innumerable. They associate in flocks consisting of from four or five
to nearly a hundred in number; and, when alarmed, they are able to
spring, at a single leap, up rocks the perpendicular height of which is
more than twenty feet, and in this case, by a few bounds, they
throw themselves entirely out of the reach of their pursuers. If hard
pressed, they will sometimes turn upon the hunter and attack him
with fury; and instances have been related of men, thus attacked,
having been thrown down precipices and destroyed by them.
The chief objects of this pursuit are the flesh and the skin. The
former is, in general, a nutritious and wholesome food, and the
latter is useful in numerous ways. When dressed, it forms a soft,
warm, and pliable leather, which has the name of shammoy, and is
manufactured into breeches, vests, and gloves, that are very durable
and are much used by the labouring classes of people on the
Continent. Of late years, however, the art of tanning has been
brought to so much perfection, that excellent shammoy leather is
made from the skins of the goat, the sheep, and the deer. The horns
of the chamois are often cut into heads for canes, and the farriers of
the Continent sometimes sharpen and use them for the bleeding of
cattle. The blood of these animals is used medicinally, and, in
Switzerland, is a celebrated nostrum for the cure of pleurisy and
some other complaints.
87. The COMMON ANTELOPE (Antilope cervicapra, Fig. 12) is a
quadruped distinguished by having spiral, round, and expanded
horns, each marked with a great number of prominent rings;
and the body of a brown colour, clouded with whitish and dusky
shades and marks.
It is found in several parts of Africa and India.

One mode of hunting these and some other species of antelope is by
the hunting leopard and the ounce, but the most frequent mode of
killing them is with guns.
Their skins are sometimes dressed with the hair on, and sometimes
as leather; and the flesh constitutes an excellent kind of venison.
The horns are convertible to nearly all the same purposes as the
horns of the different kinds of deer; and they are also occasionally
used as weapons.
88. The COMMON GOAT (Capra ægagrus, Fig. 13) is
distinguished by having hollow, compressed, and rough horns,
which grow first upright, and then bend backward.
Both the male and female are horned.
These animals are found wild in many of the mountainous
countries of the European continent, of Africa, Persia, and India.
In many parts of Europe the goat is an animal essentially serviceable
to the necessities and the comforts of mankind; affording even
during its life, though fed on the most barren and uncultivated
grounds, an abundant supply of milk and cheese.
Goats' milk is not only considered to be thicker, but to have a richer
flavour than that of the cow; and, in some situations, especially on
ship-board, where the goat thrives better than any other animal, it is
peculiarly valuable. This creature eats readily every sort of refuse
vegetables, and is kept at little expense. In a medicinal view goat's
milk is an useful substitute for that of asses. It is of very peculiar
nature, as its oily and coagulate parts do not separate
spontaneously; they throw up no cream, and yield scarcely any
butter. But this milk affords a very large proportion of cheese.

Hence, in Switzerland, and other mountainous countries best
adapted to the pasturage of goats, cheese is the chief produce of
the dairies.
The flesh of the goat, when full grown, is rank, hard, and
indigestible; yet, in some countries, it is eaten both in a fresh and
salted state. That of the kid is peculiarly rich, and, by many persons,
is considered even preferable to lamb.
When properly tanned, the skin of the goat is manufactured into
gloves and other articles of dress. There is a way of preparing these
skins by maceration, so as to separate the surface or grain from the
coarse under parts, after which they are dyed of various colours for
different uses.
Morocco leather is chiefly made from the skins of goats, tanned and
dyed in a peculiar manner. The manufacture of this leather was
originally invented in the kingdom of Morocco, whence it has its
name. The colours that are chiefly communicated to it are red and
yellow, the former of which is produced by cochineal, and the latter
by a yellow kind of berries. Morocco leather is also dyed black,
green, and blue. Until within the last few years, the consumers of
this kind of leather in England have depended wholly on a foreign
supply: there are now, however, several manufactories of it in the
neighbourhood of London, from which the most beautiful moroccos
may be had at prices that have superseded the necessity of
importing it from abroad. For leather of inferior quality, and
particularly for such as is to receive a yellow colour, sheeps' skins are
often substituted. The reason why goats' skins have been principally
adopted for the manufacture of morocco is, that they take the dye
better, and that they are susceptible of richer and more beautiful
colours, than those of any other animals.

Goat-skins, as well as the skins of sheep, are sometimes made into
parchment. The skins of kids are thin and of beautiful texture; they
are consequently well adapted for ladies' gloves and shoes. On the
Continent they are made into stockings, bed-ticks, and sometimes
into hangings for beds, into sheets, and even into shirts.
Although the fleece of the goat is by no means so valuable as that of
the sheep, yet it has been found extremely useful. The long and
shaggy coated goat, which is bred in many parts of this country, has,
at the roots of the long hair, a fine and beautiful soft wool. The
latter, though scarcely known to our manufacturers, has long been
used in Russia for gloves, stockings, and other articles of dress,
which are highly valuable. About a pound of this wool, in an
unsorted state, was, some years ago, sent from Russia to be made
into shawls. As the quantity was too small to admit of being
manufactured into a web by itself, the chain was formed of silk, and
the woof of yarn made from the goat's wool. The fabric, when
completed, was compared with the finest Indian shawls; and,
notwithstanding the hardness of the silken part, it was decidedly
more soft and beautiful than any of these. Of the above-mentioned
small quantity of wool three full-sized shawls and one waistcoat
were made. Their colour was a dull white, with a delicate and
scarcely perceptible glance of red through it; and their texture was
so much admired, that Dr. Anderson, to whose care they were
consigned, states, that if a hundred of them had been offered for
sale, they would have produced at least twenty guineas each.
The long hair of goats, particularly that of the males, is used by
peruke-makers, for lawyers and judges' wigs. Previously to its being
used, it goes through several processes of preparation. The fine hair
of kids is sometimes employed in the manufacture of hats. Goat's
hair is occasionally made into a strong and coarse kind of cloth.

Of the horns of these animals the country people make handles for
tucks, and knives of different kinds. The fat or suet, which, in
general, is very abundant, may be made into candles, which, in
whiteness and quality, are greatly superior to those of the best
tallow of the sheep and ox.
Goats are active and mischievous animals, of hardy nature, which
delight in rocky and mountainous situations. They are sometimes
very injurious to young plantations, from their propensity to peel and
destroy the trees. The females usually have two, sometimes three,
and rarely four young ones at a birth; and, in our climates, the
duration of their life is said not often to exceed eleven or twelve
years.
89. The hair of the Angora goat is long, soft, and silky, and is one of
the most beautiful substances with which we are acquainted, for the
manufacture of shawls, and other fine stuffs; and these, which in
England have the name of camblets, are sometimes sold at very
high prices. It is supposed that, with attention, Angora goats might
be successfully and advantageously bred in Great Britain; particularly
in those parts where the country is mountainous, and where the
climate and food might not be far different from those of their native
country of Asia Minor.
90. The COMMON SHEEP (Ovis aries, Fig. 14) has, in general,
hollow, compressed, transversely wrinkled, and somewhat
crescent-shaped horns; but some of the varieties are entirely
destitute of these weapons.
The male is called ram, the female ewe, and the young one has
the name of lamb.

Sheep are found in nearly every country of the world.
The bodies of these animals, in temperate and cold climates, are
clad with a curled and closely matted kind of hair, which has the
peculiar appellation of wool. The distinguishing characteristic of wool
is that, when even the coarsest sort is manufactured into cloth, it
thickens in the milling, and forms a close texture, owing to the
peculiar roughness of its surface, and to its curly form; whereas the
finest possible hair, under the same operation, will neither thicken
nor form any texture whatever. It is by the manufacture of wool into
various kinds of clothing that many thousands of people, in different
countries of Europe, are entirely supported and fed. In temperate
countries the fleeces of sheep are shorn or cut off once, and in
others, where the climate is warmer, twice in the year, the animals
being previously well washed to cleanse the wool. The Shetland
sheep, and some others, have the fleece pulled, and not cut off.
When wool is intended to be manufactured into cloth of mixed
colours, it is dyed in the fleece before it is spun. When intended for
tapestry, it is dyed after it is spun; and when to be wrought into
cloth of uniform colour, it is not dyed until the cloth is made.
Much wool is used in the manufacture of hats. For this purpose it
goes through a process called felting, to unite or mat it into a firm
substance. Felt is either made of wool alone, or of a mixture of wool
with camel's or other hair.
The skins of sheep, after the processes called tanning and currying,
are manufactured into a thin and coarse but useful kind of leather,
which is much in request by saddlers, book-binders, and others.
These skins, by a different process, are converted into parchment,
which is used for writing deeds upon. Lambs' skins are made into
gloves.

Every part of the sheep is advantageous to mankind. The flesh,
under the denomination of mutton, supplies us with a wholesome
and palatable food, which is in greatest estimation when the animals
are at least three, and not more than six years old. That of lambs, in
the spring of the year, is also in considerable demand. House lamb is
so denominated from the animals being fattened within doors; but
this kind of food is neither so wholesome nor so nutritive as the
meat in a natural state. Suet is a solid kind of fat which is found in
various parts of the bodies (particularly about the kidneys and
intestines) of sheep, oxen, and other ruminating animals. It differs
materially from fat or grease, as the latter remains soft, and this
hardens in cooling. Suet is used for culinary and other purposes, and
very extensively in the making of candles. The milk of sheep is rich
and nourishing, and in great esteem among the peasantry of all
countries where these animals are bred. It produces an abundance
of butter, but this is so unpalatable as seldom to be eaten. Ewes'
milk yields a large proportion of strong and tough cheese. Of the
entrails of sheep are made the strings generally called cat-gut, which
are used for different kinds of musical instruments, and for the
coverings of whips. Handles of knives, and several other useful
articles, are made of the bones of sheep; the refuse parts of which
are coarsely ground to serve as manure. A very important advantage
is in another respect derived from these animals, by folding them
upon land on which corn is afterwards to be grown.
There are, in Great Britain, many different breeds of sheep, some of
which are very valuable.
91. Those called Leicester sheep are chiefly bred in that and the
adjacent counties, and are much esteemed for their property of
readily fattening. Their mutton, when in perfection, has a fineness of
grain and a superiority of flavour beyond that of almost every other
kind of sheep. These animals are capable of being rendered so fat,

that, in some instances they have measured more than six inches
deep in solid fat on the ribs. But, in this case, the mutton is scarcely
eatable.
92. A coarse wool, but so long as to measure from ten to more than
eighteen inches, is obtained from the breed called Lincolnshire sheep.
93. For united excellence of wool and mutton the South Down sheep
are in great demand. This breed, which particularly abounds on the
dry and chalky downs of Sussex and other southern parts of
England, has of late been dispersed over nearly the whole kingdom.
The animals are distinguishable by their grey or speckled face and
legs, and being destitute of horns.
94. From the Ryeland and or Herefordshire sheep is obtained a
peculiarly short, soft, and fine wool, which, if the filaments were of
equal thickness and quality throughout, would be as valuable as the
best wool that we import from Spain. The mutton of these sheep is
also fine-grained and of excellent flavour.
95. A breed of sheep, which is well known in Northumberland by the
name of Cheviot sheep, produces very admirable mutton and wool of
fine texture. Of the milk of these sheep great quantities of cheese
are made, which is sold at a low price. This, when three or four days
old, becomes very pungent, and is in considerable esteem for the
table.
96. The Shetland islands produce a kind of sheep so small as seldom
to exceed the weight of thirty or forty pounds. Their wool is
sufficiently soft to be adapted even to clothing of the most delicate

texture. A pair of stockings that were made of it were so fine as to
be sold for six guineas. The skins of these sheep with the fleece on
are capable of being converted into a fur of great value; and, when
the wool is stripped from them, they are, as leather, peculiarly
estimable for aprons, and are purchased by mechanics for this
purpose at double the price of other skins of the same size.
97. It is to the breed called Dorsetshire sheep that the London markets
are principally indebted for the house-lamb, which, at an early part
of the season, bears so high a price. After the lambs are produced
they are confined in small dark places, and never see the light,
except when brought out to be fed by the ewes; and, at the times
when thus brought out, their cabins are cleansed, and littered with
fresh straw, as a great part of their value depends upon the
cleanliness in which they are kept.
98. The mutton of the Heath sheep, a breed which is found in most of
the north-western parts of England, and even as far as the western
Highlands of Scotland, is accounted peculiarly excellent; and
immense numbers of these sheep are annually sold at the north
country fairs. The animals themselves are hardy and active, and well
adapted to subsist in healthy and mountainous districts.
99. MERINO SHEEP are a celebrated Spanish breed of sheep,
with small horns, white face and legs, small bones, a loose skin
hanging from the neck, the wool fine, the external part of the
fleece dark brown in consequence of the dust adhering to it, the
interior delicate white, and the skin of rosy hue.
The celebrity of this breed, for the production of a remarkably fine
wool, has been such, that all the highest priced cloths manufactured
in this country, until of late years, were made of Spanish wool. In

the year 1787 some of these sheep were first introduced into
England. And, although it was formerly a prevailing opinion that the
excellence of their fleece depended, in a great degree, upon the
temperature of the Spanish climate, it has been satisfactorily
ascertained that the fineness of Spanish wool is not in the slightest
degree impaired by breeding the sheep in this country. Even in
Hungary sheep of this kind have, for many years, been so
successfully reared, that much of the fine wool used in our clothing
countries has been imported from thence. The average weight of the
Merino fleece is about three pounds and half. It has lately been a
great object of attention in England to improve our own breeds,
particularly the Ryeland, by a mixture with merinos, and this cross
breed is stated to retain all the principal characteristics of the
Spanish race. The mutton of these sheep, for size and flavour, is
much in demand, and sells in the market at a higher price than that
of most other kinds of sheep.
100. The BROAD-TAILED SHEEP are a very remarkable kind of
sheep, distinguished by their tails being extremely large, and so
long as sometimes to drag upon the ground.
They are found in several parts of Persia, Syria, Egypt, and other
eastern countries.
The tails of these animals are almost wholly composed of a
substance resembling marrow, and sometimes they are equal in
weight to one-third of the whole carcase. To prevent them from
chafing against the ground, the shepherds not unfrequently put
boards, with small wheels, under them, attached to the hinder parts
of the animal. The substance of these tails is in great demand,
instead of butter, for culinary purposes; and it forms an ingredient in
several kinds of dishes. The fleece of the broad-tailed sheep is
peculiarly long and fine, and, in Thibet, is manufactured into shawls

and other articles of peculiarly delicate texture, which form a
considerable source of wealth to the inhabitants.
Of these, and of another kind of sheep called Tartarian or fat-
rumped sheep, the hinder parts of which are so excessively fat as
entirely to enclose the tail, there are great numbers bred in Tartary.
It is even stated that, on an average, 150,000 of them are annually
sold at the fairs of Orenburgh, and a much greater number in some
other places.
101. The COMMON OX (Bos taurus domesticus, Fig. 29) is
characterised by having rounded horns which curve outward,
and a loose skin or dewlap beneath the throat.
The male is called bull, the female cow, and the young one calf.
This animal, in a wild state, is the bison (Fig. 15) which is found
in the marshy forests of Poland and Lithuania.
It is almost impossible to enumerate all the benefits that mankind
derive from these admirable animals. In many countries nearly the
whole labour of agriculture is performed by oxen, and, after this
service is over, they are fatted and slaughtered for food. It is well
known in what estimation they were formerly held in Egypt; they
furnished even deities to the superstitious inhabitants of that
country. From their supplying the Gentoos with milk, butter, and
cheese, their favourite food, those people bear for them a veneration
so great that nothing on earth would induce them to slay one of
them.
In nearly all eastern countries oxen are employed in treading out
corn. By the Caffres of the Cape of Good Hope they are used as
beasts of draught and burden. When Mr. Barrow and his suite went

into the country of the Caffres, the king, who was at a distance from
his usual residence, was sent to; and he is stated to have arrived
riding upon an ox full gallop, attended by five or six of his people.
To the milk of the cow we are indebted for several important articles
of human subsistence. It is adapted to every state and age of the
body, but particularly to the feeding of infants after they have been
weaned. Skimmed milk, or that which remains after the cream has
been taken off, is employed, in considerable quantity, by wine and
spirit merchants, for clarifying or fining down turbid white wine,
arrack, and weak spirits.
Nearly all the cheese that is consumed in the British islands is made
of cow's milk. For this purpose the milk is curdled by mixture with a
substance called rennet, which is prepared from the inner membrane
of a calf's stomach; and the curd, thus formed, after being cleared
of the whey or watery part contained in the milk, is collected
together, pressed, and dried for use.
The richest of all the English kinds of cheese is that called Stilton
cheese. This, however, is not, as its name would import, made in the
town of Stilton, but in various parts of Huntingdonshire, and in
Leicestershire, Rutland, and Northamptonshire. Stilton cheese is
indebted, for its excellence, both to the rich pastures on which the
cows are fed, and to the peculiar process by which it is made. It is
not sufficiently mellowed for use until two years old, and is not in a
state to be eaten till it is decayed, blue, and moist. To hasten the
ripening of Stilton cheeses, it is not unusual to place them in
buckets, and to cover these with horse-dung. Cheshire is famous for
its cheese, which is generally much salter and more smart upon the
palate than any other English kind. In Wiltshire and Gloucestershire
much cheese of rich and excellent quality is made.

The neighbourhood of Chedder, in the county of Somerset, produces
a very admirable kind, which is little inferior in taste to Parmesan,
and is supposed to owe its peculiar quality to the cows feeding in
rich pastures, and particularly on the flote fescue grass (Festuca
fluitans), with which many of those pastures abound. Cottenham
cheese is a soft white cheese, for which we are chiefly indebted to a
small village of that name situated a few miles from Cambridge. In
the neighbourhood of Bath and York, and also in Lincolnshire, a rich
and excellent kind of cream cheese is made. In Scotland a species of
cheese is produced which has long been known and celebrated
under the name of Dunlop cheese, from a parish of that name in
Ayrshire, in the neighbourhood of which it is principally made.
Of foreign kinds of cheese the most celebrated is Parmesan. This is
made of ewes' milk, or of a mixture of ewes' or goats' milk with that
of the cow. We receive it from various parts of Italy, and also from
other countries, although the name would import it to be made
exclusively in the neighbourhood of Parma. In the district of Gruyere,
a small town in the canton of Friburg in Switzerland, a well-known
kind of cheese of large size is made, which goes by that name.
Gouda cheese is famous in Holland. The common Dutch cheeses are
of globular shape, and each three or four pounds in weight. They
are prepared in the same manner as Cheshire cheese, with the
exception that, instead of rennet, the Dutch use spirit of vitriol
(sulphuric acid). Hence this kind of cheese has a sharp and saline
taste, which is said to exempt it from the depredations of mites.
Green Swiss cheese has a strong and peculiar flavour derived from
the fragrant powder of melliot (Trifolium melilotus officinalis). This
cheese is, however, to many persons, very disagreeable.
When milk has been suffered to stand a few hours, a substance
called cream rises to the surface. This is skimmed off for several
uses, but principally for the purpose of being made into butter,
which is done by beating it in a vessel called a churn. In Cheshire it
is customary to churn the butter from the whole milk, without its

being skimmed, but this is contrary to the practice in most other
parts of England. The consumption of butter is so great that not less
than 50,000 tons' weight of it are stated to be annually used in
London only. That, which is principally in esteem there is produced in
Essex, and known by the name of Epping butter.
To make butter keep for a greater length of time than it would
otherwise do, it is salted and packed in small tubs or barrels; and, in
this state, it is a very considerable article of commerce. In the salting
and packing of butter many abuses are practised, to increase its bulk
and weight, against which there is an express act of parliament.
Lumps of good butter are sometimes laid, for a little depth, at the
top of a barrel, with butter of inferior quality beneath it. Sometimes
the butter is packed hollow; and sometimes the exterior part of the
butter is good whilst the whole interior is bad.
After the butter has been separated there remains in the churn a
kind of whey which is called butter-milk, and the quality of which
greatly depends on the manner of churning. Before it turns sour,
butter-milk is a favourite beverage in the families of some farmers. It
is also occasionally used as a wash for the face, being considered a
remedy against freckles; but it is principally applied for the feeding
of pigs.
The flesh of oxen constitutes the kind of food which we call beef.
This is usually eaten in a recent state, but is sometimes, particularly
in the northern parts of England, in Ireland, and Holland, salted in
the manner of bacon, and in this state, it is a considerable article of
trade. It affords a strong and invigorating nutriment, superior to any
that we are acquainted with. Beef-tea is a preparation commonly
made for invalids and convalescents, and consists of an infusion of
the lean parts of beef in boiling water. Veal, or the flesh of calves, is
an highly esteemed and delicate food.

Welcome to our website – the perfect destination for book lovers and
knowledge seekers. We believe that every book holds a new world,
offering opportunities for learning, discovery, and personal growth.
That’s why we are dedicated to bringing you a diverse collection of
books, ranging from classic literature and specialized publications to
self-development guides and children's books.
More than just a book-buying platform, we strive to be a bridge
connecting you with timeless cultural and intellectual values. With an
elegant, user-friendly interface and a smart search system, you can
quickly find the books that best suit your interests. Additionally,
our special promotions and home delivery services help you save time
and fully enjoy the joy of reading.
Join us on a journey of knowledge exploration, passion nurturing, and
personal growth every day!
ebookbell.com

Logic Computation Hierarchies Vasco Brattka Editor Hannes Diener Editor Dieter Spreen Editor

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Logic Computation Hierarchies Vasco Brattka Editor Hannes Diener Editor Dieter Spreen Editor

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 11

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Slide 80