Computational Prospects Of Infinity Part Ii Presented Talks Chitat Chong

Computational Prospects Of Infinity Part Ii Presented Talks Chitat Chong
Computational Prospects Of Infinity Part Ii Presented Talks Chitat Chong
Computational Prospects Of Infinity Part Ii Presented Talks Chitat Chong

1. Computational Prospects Of Infinity Part Ii
Presented Talks Chitat Chong download
https://ebookbell.com/product/computational-prospects-of-
infinity-part-ii-presented-talks-chitat-chong-5251358
Explore and download more ebooks at ebookbell.com

2. Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Computational Prospects Of Infinity Part I Tutorials Chitat Chong
https://ebookbell.com/product/computational-prospects-of-infinity-
part-i-tutorials-chitat-chong-5251356
An Introduction To Scientific Computing Twelve Computational Projects
Solved With Matlab Ionut Danaila
https://ebookbell.com/product/an-introduction-to-scientific-computing-
twelve-computational-projects-solved-with-matlab-ionut-
danaila-50300156
An Introduction To Scientific Computing Fifteen Computational Projects
Solved With Matlab 2nd 2nd Edition Ionut Danaila
https://ebookbell.com/product/an-introduction-to-scientific-computing-
fifteen-computational-projects-solved-with-matlab-2nd-2nd-edition-
ionut-danaila-53596822
Tensorflow Machine Learning Projects Build 13 Realworld Projects With
Advanced Numerical Computations Using The Python Ecosystem Ankit Jain
Armando Fandango Amita Kapoor
https://ebookbell.com/product/tensorflow-machine-learning-projects-
build-13-realworld-projects-with-advanced-numerical-computations-
using-the-python-ecosystem-ankit-jain-armando-fandango-amita-
kapoor-51309824

3. Computational Intelligence And Data Analytics Proceedings Of Iccida
2022 1st Ed 2023 Rajkumar Buyya
https://ebookbell.com/product/computational-intelligence-and-data-
analytics-proceedings-of-iccida-2022-1st-ed-2023-rajkumar-
buyya-45333718
Computational Methods In Organometallic Catalysis From Elementary
Reactions To Mechanisms Yu Lan
https://ebookbell.com/product/computational-methods-in-organometallic-
catalysis-from-elementary-reactions-to-mechanisms-yu-lan-46084622
Computational Intelligence Based Solutions For Vision Systems Ansari
Bajaj
https://ebookbell.com/product/computational-intelligence-based-
solutions-for-vision-systems-ansari-bajaj-46094270
Computational Methods Using Matlab An Introduction For Physicists P K
Thiruvikraman
https://ebookbell.com/product/computational-methods-using-matlab-an-
introduction-for-physicists-p-k-thiruvikraman-46098316
Computational Semiotics Jeanguy Meunier
https://ebookbell.com/product/computational-semiotics-jeanguy-
meunier-46098550

6. Part II: Presented Talks
COMPUTATIONAL
PROSPECTS OF INFINITY

7. LECTURE NOTES SERIES
Institute for Mathematical Sciences, National University of Singapore
Series Editors:Louis H. Y. Chen and Ka Hin Leung
Institute for Mathematical Sciences
National University of Singapore
Published
Vol. 4An Introduction to Stein’s Method
edited by A. D. Barbour & Louis H. Y. Chen
Vol. 5Stein's Method and Applications
edited by A. D. Barbour & Louis H. Y. Chen
Vol. 6Computational Methods in Large Scale Simulation
edited by K.-Y. Lam & H.-P. Lee
Vol. 7Markov Chain Monte Carlo: Innovations and Applications
edited by W. S. Kendall, F. Liang & J.-S. Wang
Vol. 8Transition and Turbulence Control
edited by Mohamed Gad-el-Hak & Her Mann Tsai
Vol. 9Dynamics in Models of Coarsening, Coagulation, Condensation
and Quantization
edited by Weizhu Bao & Jian-Guo Liu
Vol. 10Gabor and Wavelet Frames
edited by Say Song Goh, Amos Ron & Zuowei Shen
Vol. 11Mathematics and Computation in Imaging Science and
Information Processing
edited by Say Song Goh, Amos Ron & Zuowei Shen
Vol. 12Harmonic Analysis, Group Representations, Automorphic Forms
and Invariant Theory — In Honor of Roger E. Howe
edited by Jian-Shu Li, Eng-Chye Tan, Nolan Wallach & Chen-Bo Zhu
Vol. 13Econometric Forecasting and High-Frequency Data Analysis
edited by Roberto S. Mariano & Yiu-Kuen Tse
Vol. 14Computational Prospects of Infinity — Part I: Tutorials
edited by Chitat Chong, Qi Feng, Theodore A Slaman, W Hugh Woodin
& Yue Yang
Vol. 15Computational Prospects of Infinity — Part II: Presented Talks
edited by Chitat Chong, Qi Feng, Theodore A Slaman, W Hugh Woodin
& Yue Yang
ISSN: 1793-0758
*For the complete list of titles in this series, please go to
http://www.worldscibooks.com/series/lnsimsnus_series.shtml
LaiFun - Comp Prospects - Vol-15.pmd 4/29/2008, 3:38 PM2

8. NEW JERSEY • LONDON • SINGAPORE • BEIJING • SHANGHAI • HONG KONG • TAIPEI • CHENNAI
World Scientific
Lecture Notes Series, Institute for Mathematical Sciences,
National University of Singapore Vol.
15
Editors
Part II: Presented Talks
Chitat Chong
National University of Singapore, Singapore
Qi Feng
Chinese Academy of Sciences, China & National University of Singapore, Singapore
Theodore A. Slaman, W. Hugh Woodin
University of California at Berkeley, USA
Yue Yang
National University of Singapore, Singapore
COMPUTATIONAL
PROSPECTS OF INFINITY

9. British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library.
For photocopying of material in this volume, please pay a copying fee through the Copyright
Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to
photocopy is not required from the publisher.
ISBN-13978-981-279-654-7
ISBN-10981-279-654-1
All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means,
electronic or mechanical, including photocopying, recording or any information storage and retrieval
system now known or to be invented, without written permission from the Publisher.
Copyright © 2008 by World Scientific Publishing Co. Pte. Ltd.
Published by
World Scientific Publishing Co. Pte. Ltd.
5 Toh Tuck Link, Singapore 596224
USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601
UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE
Printed in Singapore.
Lecture Notes Series, Institute for Mathematical Sciences,
National University of Singapore – Vol. 15
COMPUTATIONAL PROSPECTS OF INFINITY
Part II: Presented Talks
LaiFun - Comp Prospects - Vol-15.pmd 4/29/2008, 3:38 PM1

10. April11,2008 MasterReviewVol.9inx6in{(forLectureNoteSeries,IMS,NUS) contentsLNS-Vol15
CONTENTS
Foreword vii
Preface ix
GeneratingSetsfortheRecursivelyEnumerableTuringDegrees
KlausAmbos-Spies,SteenLemppandTheodoreA.Slaman 1
CodingintoH(!2),Together(orNot)withForcingAxioms.
ASurvey
DavidAspero 23
NonstandardMethodsinRamsey'sTheoremforPairs
ChiTatChong 47
PromptSimplicity,ArrayComputabilityandCupping
RodDowney,NoamGreenberg,JosephS.Millerand
RebeccaWeber 59
LownessforComputableMachines
RodDowney,NoamGreenberg,NenadMihailovicand
AndreNies 79
ASimplerShortExtendersForcing|Gap3
MotiGitik 87
LimitComputabilityandConstructiveMeasure
DenisR.HirschfeldtandSebastiaanA.Terwijn 131
TheStrengthofSomeCombinatorialPrinciplesRelatedto
Ramsey'sTheoremforPairs
DenisR.Hirschfeldt,CarlG.Jockusch,Jr.,
BjrnKjos-Hanssen,SteenLemppand
TheodoreA.Slaman 143
v

11. April11,2008 MasterReviewVol.9inx6in{(forLectureNoteSeries,IMS,NUS) contentsLNS-Vol15
vi Contents
AbsolutenessforUniversallyBaireSetsandtheUncountableII
IlijasFarah,RichardKetchersid,PaulLarsonand
MenachemMagidor 163
MonadicDenabilityofOrdinals
ItayNeeman 193
ACuppableNon-BoundingDegree
KengMengNg 207
EliminatingConcepts
AndreNies 225
ALowerConeinthewttDegreesofNon-Integral
EectiveDimension
AndreNiesandJanReimann 249
AMinimalrK-Degree
AlexanderRaichevandFrankStephan 261
DiamondsonP
MasahiroShioya 271
RigidityandBiinterpretabilityintheHyperdegrees
RichardA.Shore 299
SomeFundamentalIssuesConcerningDegreesofUnsolvability
StephenG.Simpson 313
WeakDeterminacyandIterationsofInductiveDenitions
MedYahyaOuldMedSalemandKazuyukiTanaka 333
AttVersionofthePosner-RobinsonTheorem
W.HughWoodin 355
CuppingComputablyEnumerableDegreesinthe
ErshovHierarchy
GuohuaWu 393

12. April10,2008 MasterReviewVol.9inx6in{(forLectureNoteSeries,IMS,NUS) foreword
FOREWORD
TheInstituteforMathematicalSciencesattheNationalUniversityof
Singaporewasestablishedon1July2000.Itsmissionistofostermathemat-
icalresearch,bothfundamentalandmultidisciplinary,particularlyresearch
thatlinksmathematicstootherdisciplines,tonurturethegrowthofmath-
ematicalexpertiseamongresearchscientists,totraintalentforresearchin
themathematicalsciences,andtoserveasaplatformforresearchinter-
actionbetweenthescienticcommunityinSingaporeandthewiderinter-
nationalcommunity.
TheInstituteorganizesthematicprogramswhichlastfromonemonth
tosixmonths.Thethemeorthemesofaprogramwillgenerallybeof
amultidisciplinarynature,chosenfromareasattheforefrontofcurrent
researchinthemathematicalsciencesandtheirapplications.
Generally,foreachprogramtherewillbetutoriallecturesfollowedby
workshopsatresearchlevel.Notesontheselecturesareusuallymadeavail-
abletotheparticipantsfortheirimmediatebenetduringtheprogram.The
mainobjectiveoftheInstitute'sLectureNotesSeriesistobringtheselec-
turestoawideraudience.Occasionally,theSeriesmayalsoincludethepro-
ceedingsofworkshopsandexpositorylecturesorganizedbytheInstitute.
TheWorldScienticPublishingCompanyhaskindlyagreedtopub-
lishtheLectureNotesSeries.ThisVolume,\ComputationalProspectsof
Innity,PartII:PresentedTalks",isthefteenthofthisSeries.Wehope
thatthroughtheregularpublicationoftheselecturenotestheInstitutewill
achieve,inpart,itsobjectiveofpromotingresearchinthemathematical
sciencesandtheirapplications.
January2008 LouisH.Y.Chen
KaHinLeung
SeriesEditors
vii

13. This page intentionally left blank This page intentionally left blank

14. April10,2008 MasterReviewVol.9inx6in{(forLectureNoteSeries,IMS,NUS) preface
PREFACE
TheWorkshoponComputationalProspectsofInnitywasheldattheIn-
stituteforMathematicalSciences,NationalUniversityofSingapore,from
20Juneto15August2005.
ThefocusintherstmonthoftheWorkshopwasonsettheory,with
twotutorialsrunninginparallel,byJohnSteel(\DerivedModelsAsso-
ciatedtoMice")andW.HughWoodin(\SuitableExtenderSequences").
Therewerealso21talksgivenduringthisperiod.Thesecondhalfofthe
Workshopwasdevotedtorecursiontheory,withtwotutorialsgivenrespec-
tivelybyRodDowney(\FiveLecturesonAlgorithmicRandomness")and
TedSlaman(\DenabilityoftheTuringJump").Inaddition,therewere
42talksdeliveredoverfourweeks.
ThisvolumeconstitutesPartIIoftheproceedingsoftheWorkshop.
Itcontainsrefereedarticles,bothcontributedandinvited,basedontalks
presentedattheWorkshop.Writtenversionsofthetutorialsarecollected
inPartIoftheproceedingswhichappearsasaseparatevolume.
Theworkshopprovidedaplatformforresearchersinthelogiccom-
munityfrommanypartsoftheworldtomeetinSingapore,todiscuss
mathematicsandtoexperienceacitythatisameetingpointofEastand
West.WethanktheDepartmentofMathematicsandtheInstitutefor
MathematicalSciencesattheNationalUniversityofSingaporefortheir
supportandhospitalityextendedtoallparticipants.
November2007 ChiTatChong
NationalUniversityofSingapore,Singapore
QiFeng
ChineseAcademyofSciences,Chinaand
NationalUniversityofSingapore,Singapore
TheodoreA.Slaman
UniversityofCaliforniaatBerkeley,USA
W.HughWoodin
UniversityofCaliforniaatBerkeley,USA
YueYang
NationalUniversityofSingapore,Singapore
Editors
ix

15. This page intentionally left blank This page intentionally left blank

16. GENERATING SETS FOR THE RECURSIVELY
ENUMERABLE TURING DEGREES
Klaus Ambos-Spies
Department of Mathematics and Computer Science
University of Heidelberg
D-69120 Heidelberg, Germany
E-mail: [email protected]
Steffen Lempp
∗
Department of Mathematics
University of Wisconsin–Madison
Madison, WI 53706-1388, USA
E-mail: [email protected]
Theodore A. Slaman
†
Department of Mathematics
University of California–Berkeley
Berkeley, CA 94720-3840, USA
E-mail: [email protected]
We give an example of a subset of the recursively enumerable Tur-
ing degrees which generates the recursively enumerable degrees using
meet and join but does not generate them using join alone.
1. Introduction
One of the recurrent themes in the area of the recursively enumerable
(r.e.) degrees has been the study of themeet operator. While, trivially,
the partial ordering of the r.e. degrees is an upper semi-lattice, i.e., the join
∗
Lempp was partially supported by NSF grant DMS-0140120 and a Mercator Guest
Professorship of the Deutsche Forschungsgemeinschaft.
†
Slaman was partially supported by the Alexander von Humboldt Foundation and by
National Science Foundation Grant DMS-9988644.
1

17. 2 K. Ambos-Spies, S. Lempp and T. A. Slaman
operator is total, the meet of two incomparable r.e. degrees may or may not
exist (Lachlan (1966), Yates (1966)). The asymmetry between joins and
meets is further illustrated by the fact that, by Sacks’ splitting theorem
(Sacks (1963)), every nonzero r.e. degree is join-reducible, i.e., is the join of
two lesser degrees, whereas there are both, meet-reducible (branching) and
meet-irreducible (nonbranching), incomplete r.e. degrees (Lachlan (1966)).
The existence of meets andthe failure of meets are densely distributed in
the partial ordering of the r.e. degrees. So Fejer (1983) showed that the non-
branching degrees are dense while Slaman (1991) showed that the branching
degrees are dense. Similarly, every interval of the r.e. degrees contains an
incomparable pair of degrees without meet (Ambos-Spies (1984)) and an
incomparable pair of degrees with meet (Slaman (1991)). That, actually,
the lack of meets is more common than the existence of meets has been
demonstrated by Ambos-Spies (1984) and, independently, by Harrington
(unpublished a,
there is an incomparable degreebsuch that the meet ofaandbdoes not
exist, but also that there is such a degreeasuch that, for any incomparable
degreeb, the meet ofaandbdoes not exist. More evidence, that the
failure of meets is more typical than their existence, was given by Jockusch
(1985) who showed that, given r.e. degreesa,bandcsuch thataandb
are incomparable andcis the meet ofaandb, none of these degrees is
e-generic.
Another way to look at the join and meet operators in the r.e. de-
grees is to studygenerating sets, i.e., sets of r.e. degrees which generate all
the recursively enumerable degrees under (finitely many applications of)
join and meet. The question now arises naturally whether both the join
operation and the meet operation areneeded here. As observed in Ambos-
Spies (1985), the above results on nonbranching degrees easily imply that
the join operation is indeed necessary, namely there is a subset of the re-
cursively enumerable degrees which generates all recursively enumerable
degrees using join and meet but not using meet alone. Ambos-Spies, how-
ever, left open the question of whether the meet operation is necessary (see
Ambos-Spies (1985), Problem 1). The above mentioned negative results
on meets by Fejer (1983), Ambos-Spies (1984) and Jockusch (1985) may
suggest a negative answer to this question. More evidence in this direction
has been obtained by Ambos-Spies (1985) who showed that any generating
set intersects any notrivial initialsegment of the r.e. degrees and, more
recently, by Ambos-Spies, Ding and Fejer (unpublished) who showed that
any generating set generates the high r.e. degrees using join alone. Despite

18. Generating Sets for the Recursively Enumerable Turing Degrees 3
this negative evidence, in this paper, we answer Ambos-Spies’ question af-
firmatively by the following
Theorem 1.1There exists a subsetGof the recursively enumerable Tur-
ing degrees which generates the recursively enumerable Turing degrees using
meet and join but does not generate them using join alone.
Proof.Our theorem follows by our technical result, Theorem 2.1, be-
low, using a nonconstructive definition of the setG. Fix the recur-
sively enumerable degreeafrom Theorem 2.1. Let{x
n}n∈ωbe a (non-
effective) enumeration of all recursively enumerable degrees≤a.We
now define a (noneffective) sequenceof recursively enumerable degrees
0=y
0≤y1≤y2≤ ···<aas follows: Sety 0=0.Giveny n<a,
check whethery
n∪xn=a.Ifnot,thensety n+1=yn∪xn. Otherwise, let
bbe the recursively enumerable degree given by Theorem 2.1 usingx=x
n
andy=y n,andsety n+1=yn∪b. Finally, we define
G={x|xΛ ≤aor∃n(x≤y
n)}.
By Theorem 2.1, the degreeais clearly not the join of any finite set of
degrees inG. On the other hand, fix any recursively enumerable degreex
and assumex/∈G.Thenx≤a,andsox=x
nfor somen∈ω.Since
x/∈G,wehavexΛ ≤y
n+1and sox∪y=afory=y n.Fixb,c,d,ande
as in Theorem 2.1. Thenx=b∪(d∩e)whereallofb,d,andeare inG
sinceb≤y
n+1andd,eΛ ≤a. ff
2. The technical theorem and some intuition for its proof
Starting with this section, we will prove the technical theorem needed to
establish Theorem 1.1:
Theorem 2.1There is a nonrecursive, recursively enumerable setAsuch
that for every pair of recursively enumerable setsXandY,ifXandYare
recursive inAandAis recursive inXYthen one of the following conditions
holds.
1.Ais recursive inY.
2. There are recursively enumerable setsB,C,D,andEsuch that
(a)XhasthesameTuringdegreeasBC,

19. 4 K. Ambos-Spies, S. Lempp and T. A. Slaman
(b)DandEare not recursive inAand the degree ofCis the infi-
mum of the degrees ofDCandEC,and
(c)Ais not recursive inBY.
2.1.Requirements and simple strategies
We disassemble the statement of Theorem 2.1 into requirements as follows.
First,Amust be nonrecursive and so we must satisfy all the requirements
ΘΛ =A, where Θ is a recursive function.
Second, for eachX,Y,Λ
a,x,Λa,y,andΛxy,a, we associate the principal
equations Λ
a,x(A)=X,Λ a,y(A)=Y,andΛ xy,a(XY)=A. We can satisfy
our requirement onX,Y,Λ
a,x,Λa,y,andΛxy,ain any of several ways. If
the principal equations are not valid then our requirement is satisfied.
Anticipating that the principal equations actually are valid, we enumer-
ate the setsB,C,D,andEand recursive functionals Γ
x,b,Γx,c,andΓbc,x.
We ensure that Γ
x,b(X)=B,Γ x,c(X)=C,andΓ bc,x(BC)=X.Now,our
requirement is satisfied in one of two ways.
For every recursive functional Θ
by,ifΘby(BY)=Athen there is a ∆ y,a,
which we enumerate during our construction, such that ∆
y,a(Y)=A.If
there is a ∆
y,asuch that ∆y,a(Y)=A, then again our requirement is
satisfied.
Otherwise, we ensure that every instance of the following family of re-
quirements is satisfied.
1. For all Θ
a,Θa(A)Λ =Dand Θ a(A)Λ =E.
2. For all Ψ
cdand Ψce,ifΨcd(CD)=Ψ ce(CE) then there is a Ξcsuch
that Ξ
c(C)=Ψ cd(CD)=Ψ ce(CE).
2.2.Strategies
2.2.1.MakingΘΛ =A:σ
0(Θ)
We ensure that ΘΛ =Aby choosing a numbern, keepingnout ofAuntil
seeing Θ(n) = 0, and then enumeratingnintoA.Thisstrategyσ
0is one
of the standard methods to satisfy requirements of this form.
2.2.2.Measuring whether the equations hold:σ
1(X, Y,Λ a,x,Λa,y,Λxy,a)
Now, we consider the more complicated requirements. Suppose thatX,Y,
Λ
a,x,Λa,y,andΛxy,aare given.

20. Generating Sets for the Recursively Enumerable Turing Degrees 5
Our strategyσ 1(X, Y,Λ a,x,Λa,y,Λxy,a) approximates if the principal
equations hold forX,Y,Λ
a,x,Λa,y,andΛxy,a. We will abbreviate byσ 1the
strategyσ
1(X, Y,Λ a,x,Λa,y,Λxy,a) and use similar conventions throughout
this section. Essentially,σ
1measures expansionary stages in the approxi-
mation to these equalities. For technical reasons, explained below,σ
1waits
for something more than simple expansion. In the following,a
1anda 2are
variables of the strategy which enumerates pairs (a
1,a2) into a list of pairs
of witnesses.
1. Ifa
1is undefined and it is possible to do so, choose a value fora 1that
is larger thanλ
a,x(A, x)[s] for everyxpreviously mentioned in the
construction during aσ
1-expansionary stage. Letx 1be the smallest
numberxsuch thatλ
a,x(A, x)[s] is greater thana 1. Suspend the
enumeration of any functionals associated withB,C,DorE.(We
may assume that we have not enumerated any computations fromBC
ofXat arguments greater than or equal tox
1.)
Wait until the first stagessuch that (Λ
xy,a(XY)Θa 1+1 =
AΘa
1+1)[s], and (Λ a,x(A)=X)[s]and(Λ a,y(A)=Y)[s]onall
numbers less than or equal to the maximum ofλ
xy,a(XY)[s]Θa 1+1.
At this stage, we leta
2equal the supremum of (λ a,x(A)=X)[s]and
(λ
a,y(A)=Y)[s] on all numbers less than or equal to the maximum
ofλ
xy,a(XY)[s]Θa 1+ 1. We enumerate the pair (a 1,a2) into our list
and let the strategies of lower priority resume the enumeration of any
functionals associated withB,C,DorE.(The(a
1,a2) notation will
be convenient below.) Go to Step 2.
2. At the next stage whenσ
1is active, we say thata 1is undefined, and
go to Step 1.
Consider the possibilities. The strategyσ
1could reach a limit in Step 1.
In this case, one of the principal equations fails and the requirement is
satisfied.
Ifσ
1does not reach a limit in Step 1 then it enumerates infinitely many
stable pairs and has no othereffect on the construction.
For the remainder of this section, we assume thatσ
1does not reach a
finite limit and that all subsequent strategies act during the stages when
σ
1enumerates a new pair. We call such stagesσ 1-expansionary.

21. 6 K. Ambos-Spies, S. Lempp and T. A. Slaman
2.2.3.Computations betweenB, C,andX:σ 2(X, Y,Λ a,x,Λa,y,Λxy,a)
Our strategyσ
2builds functionals Γx,band Γx,cand ensures that if the
principal equations are valid then for eachnthere are infinitely manyssuch
that (Γ
x,b(X, n)=B(n))[s]and(Γ x,c(X, n)=C(n))[s]. This, combined
with our preservingA,B,andC, will be sufficient to conclude thatBand
Care recursive inX.
We ensure their correctness by imposing the constraint on all lower
priority strategiesτthat if Γ
x,b(X, n)[s]orΓ x,c(X, n)[s] is defined while
τacts thenτcannot enumeratenintoBorC, respectively, during that
stage.
Similarly, we ensure thatXis recursive inBCby enumerating a func-
tional Γ
bc,xand ensuring that if the principal equalities hold then for alln,
Γ
bc,x(BC,n)=X(n) during infinitely many stages of the construction.
We have complete freedom to define the uses of these functionals, but
the construction does not require a subtle decision. Duringσ
1-expansionary
stages, we enumerate newcomputations into Γ
bc,x.IfnentersXduring
stagesand Γ
bc,x(BC,n)=0[s] then we must enumerate a number less
than or equal toγ
bc,x(BC,n)[s]intoeitherBorC. Wesettheusesofthese
functions to be larger than any number previously used in the construction.
In the case of maintaining Γ
bc=X, we also have the freedom to decide
which ofBandCto change when recording a change inX.Thechoice
made is irrelevant toσ
2. In our construction, we will leave the decision to
the highest priority strategy for which it is relevant. See the discussion of
the strategies of typeσ
6.
2.2.4.MakingCthe infimum ofCDandCE:
σ
3(X, Y,Λ a,x,Λa,y,Λxy,a,Ψcd,Ψce)
We will use the branching strategies from Fejer (1982) and attempt to
make the degree ofCequal to the infimum of the degrees ofCDand
CE. Suppose that Ψ
cdand Ψceare given and letσ 3denote our branching
strategy associated with this pair. Then,σ
3enumerates a functional Ξc.
Say thatsisσ
3-expansionaryif and only if the least numbernsuch that
(Ψ
cd(CD,n)Λ =Ψ ce(CE,n))[s] is larger than at any earlier stage.
First, during stages,ifthereisannsuch that Ξ
c(C, n)[s] is defined
and a strategy of priority less than or equal to that ofσ
3enumerates
numbers intoC,D,orEso that neither (Ψ
cd(CD,n)=Ξ c(C, n))[s]nor
(Ψ
ce(CE,n)=Ξ c(C, n))[s], thenσ 3must enumerate a number less than or

22. Generating Sets for the Recursively Enumerable Turing Degrees 7
equal toξ c(C, n)[s]intoC. (We will have to argue that this enumeration
is compatible withC’s being recursive relative toX.)
Second, ifsisσ
3-expansionary then for the leastnsuch thatξ c(C, n)is
not defined, we choose a value forξ
c(C, n)[s] which is larger than any num-
ber previously mentioned in the construction and enumerate a computation
into Ξ
csetting Ξc(C[s],n)=Ψ cd(CD[s],n)withuseξ c(C, n)[s].
If Ψ
cd(CD)=Ψ ce(CE) then there will be infinitely manyσ 3-
expansionary stages. Since we will be preserving computations fromCD
andCE, the converse will also be true. So, if Ψ
cd(CD)Λ =Ψ ce(CE), thenσ 3
will act finitely often. Otherwise, it produces a functional ΞcfromCwhich
is defined infinitely often to agree with the common value of Ψ
cd(CD)and
Ψ
ce(CE). Again, since we are preserving the sets that we construct, this
will be sufficient to ensure that Ξ
c(C) is equal to this common value.
We will assume that there are infinitely manyσ
3-expansionary stages
and describe the appropriate strategies to follow. These strategies act only
duringσ
3-expansionary stages.
Instability inCand compatibility betweenσ
2andσ 3.The strate-
giesσ
3introduce an instability to the initial segments ofC. Namely, sup-
pose that a strategyτenumerates a numbercintoC. Then,centers
bothCDandCEand could change the common value of Ψ
cd(CD,c1)and
Ψ
ce(CE,c1). In response,τenumeratesξ c(C, c1)intoC, possibly changing
Cat a number less thanc, and the effect can propagate. We call the set of
numbers that enterCin this way the cascade initiated byc.
When combined with the strategy to ensure thatCis recursive inX,
the branching strategies make it difficult to enumerate any number at all
intoC.IfΓ
x,c(X, m) is defined then we cannot enumerate anycintoC
unless we can be sure that the instability inCwill not propagate to the
point of requiring thatmenterC. We will use some of the ideas of Slaman
(1991) to work within this constraint.
Definition 2.2Anumbercisσ
3-stable at stagesif for allm,if
ξ
c(C, m)[s]<cthen eitherψ cd(CD,m)<corψ ce(CE,m)<c.
We note that ifcisσ
3-stable at stagesthen any cascade initiated by
a number greater than or equal tocduring stagesdoes not include any
number less thanc. To prove this claim, consider the recursive propagation
of a cascade initiated by a number greater than or equal toc,andletm
be the first number less thancto appear in the cascade. Earlier in the

23. 8 K. Ambos-Spies, S. Lempp and T. A. Slaman
propagation of the cascade,Cwould have to change below the minimum
ofψ
cd(CD,m)[s]andψ ce(CE,m)[s]. By the stability ofc, this minimum
is less thancand we have contradictedm’s being first.
Thus, ifcis stable and Γ
x,c(X, c)[s] is not defined, then we can enumer-
atecintoCand respect bothσ
2andσ 3. We will design all the strategies to
follow so that they enumerate only stable numbers intoC. Of course, there
is no such constraint onB,sinceBis not constructed to be branching.
2.2.5.MakingΘ
a(A)Λ =DandΘ a(A)Λ =E:σ 4(X, Y,Λ a,x,Λa,y,Λxy,a,Θa)
andσ
5(X, Y,Λ a,x,Λa,y,Λxy,a,Θa)
We use a variation,σ
4, on the basic Friedberg strategy to ensure that
Θ
a(A)Λ =D.(Thestrategyσ 5forEis similar.) We choosenlarger than
any number previously mentioned in the construction and constrainnfrom
enteringD. We wait for a stagessuch that (Θ
a(A, n)=0)[s]. By our
assumption,swill beσ
1andσ 3-expansionary.
Then, we enumeratenintoDand constrain any number less thans
from entering any set under construction other thanD.Wenotethat
these actions are consistent. Since we did not enumerate anything intoA
andA’s computation ofXexists on a longer interval than ever before,X
cannot change at any numbermsuch that Γ
bc,x(BC,m)[s] is defined. So,
σ
2will not require any change inBorC.Sincesisσ 3-expansionary, both
Ψ
cd(CD)[s]andΨ ce(CE)[s] were defined (before we changedD), agreed on
a longer interval than ever before, and agreed with Ξ
c(C)[s]whereΞ c(C)[s]
was defined. Since we did not changeE,Ψ
ce(CE)[s] is still equal to Ξc(C)[s]
where the latter is defined andσ
3does not require any change inC.
2.2.6.IfΘ
by(BY)=Athen∆ y,a(Y)=A:σ 6(X, Y,Λ a,x,Λa,y,Λxy,a,Θby)
Now we come to the crux of the proof of Theorem 2.1. Our strategyσ
6
must either diagonalize Θby(BY) againstA,oritmustdeterminethatAis
recursive inY.SinceYis an arbitrary set belowA, both cases are possible.
In the context of the construction,σ
6can assume that every stage isσ 1-
andσ
2-expansionary. Now, this implies that if we enumerate a numbera
intoAduring stages, there is a later stagetduring whichArecomputesX
andYand eitherX[s]Λ =X[t]orY[s]Λ =Y[t]andtheleastmat which the
inequality occurs is less thanλ
xy,a(XY,a)[s]. In other words, if we change
Athen one ofXorYmust change in order to correct Λ
xy,a(XY).
To establish Θ
by(BY)Λ =A, at least once we would have to changeA
without having to changeBand withoutY’s having changed. This could

24. Generating Sets for the Recursively Enumerable Turing Degrees 9
happen, since the change inAcould be recorded inXand we could record
the change inX(for the sake ofσ
3)inC. If, on the other hand, this
diagonalization is not possible then we must conclude thatAis recursive
inY. The conclusion is not unreasonable since every change inAresults
in a change inY. But, if even one change inAresults in a change inX,
then we must be able to record that change inC.
We have reached the technical problem to be solved to prove the theo-
rem. For everyA-change allowed byσ
6, if it results in a change inX,then
we must be able to record that change inXand inC.Nowrememberthat
we are only able to enumerate numbers intoCwhich areσ
3-stable during
their stage of enumeration. So we must ensure that changes inXcan be
recorded inCby the enumeration of such numbers. This is the purpose in
our strategyσ
6.
Configurations.Consider a possible stage-ssituation as depicted in
Figure 1. In this picture, we illustrate a numbera
1whichweintendto
enumerate intoA;x
1is the least numberxsuch thata 1is less than
λ
a,x(A, x)[s] and hence the least number which might enterXwhena 1
entersA;x 2is equal toλ xy,a(XY,a1)[s]anda 1’s enteringAwould cause
a change inXYbelowx
2;a2is the supremum ofλ a,x(A, x2)[s]and
λ
a,y(A, x2)[s], so our preservingAon numbers less thana 2will preserve
the relationship betweena
1,x1,andx 2;cisγ bc,x(BC,x1)[s] and so enu-
meratingcintoCwould correct the computation ofXfromBCon every
argument at whichXmight change; we intend thatcbeσ
3-stable at stage
sand so, for anym,ifξ
c(m)islessthancthen one ofψ cd(CD,m)[s]or
ψ
ce(CE,m)[s]isalsolessthanc; finally,x 3isγx,c(X, c), the use ofX’s
computation ofCat argumentc. Note that we can preserve the relation-
ships between these numbers by preservingAup toa
2,andB,C,D,andE
up toc. (We can keepx
3abovex 2by enumerating our functions so that
the uses of new computations are at least as great as the uses of earlier
computations at the same argument.)
Suppose that, in this situation, we were to enumeratea
1intoAandY
did not change belowx
2to record that fact (for example, ifYΛ ≥A). Then
Xwould change belowx
2, allowing us to enumerate theσ 3-stable numberc
intoCand thereby correctBC’s computations for any change inXallowed
bya
1’s enteringA.
We say that the situation depicted in Figure 1 is aσ
1-configuration
fora
1. Anticipating that Θby(BY)=A, we must ensure that for all but a

25. 10 K. Ambos-Spies, S. Lempp and T. A. Slaman
A X Y C B D E
ff
ff
ff
ff
ffff Θ
ff
ff
ff
ff
ffff Θ
Λ
Λ
Λ
Λ
ΛΛ Γ
ff
ff
ff
ff
ff
ff
ff
ff Θ
∆
∆
∆
∆
∆
∆
∆
∆
∆
∆
∆
∆ Ψ
a1
a2
x1
x2
x3
c
ξ
c(m)
ψ
ce(m)
Λ
a,x
Λa,x
Λxy,a Γbc,x
Γx,c
Figure 1: Configuration fora 1.
recursive set of numbersa,ifaentersAthen it does so in the role ofa
1
with a configuration as above.
Generating configurations. Though configurations seem artificial at
first, they are very common. In fact, a new configuration can be produced
during everyσ
1-expansionary stage.
Note that, by the constraint imposed byσ
3, at the beginning of every
staget, for everym,ifΞ
c(C, m)[t] is defined then one of Ψ cd(CD,n)[t]and
Ψ
ce(CE,n)[t] is also defined with the same value.
Now consider aσ
1-expansionary stages.Letcbe the least strict upper
bound on the range ofξ
c(C)[s]. By the observation above,cisσ 3-stable.
Sincesisσ
1-expansionary,σ 1enumerated a pair (a 1,a2) related as in Fig-
ure 1. Further, by the choice ofa
1anda 2,a1is greater thanλ a,x(A, x)[s]for
everyxsuch that Γ
bc,x(BC,x) has ever been defined. Consequently, there
is no computation in Γ
bc,x[s] which applies to the argumentx 1. Then, we
can useσ
2to enumerate computations into Γx,b,Γx,c,andΓbc,xso that
γ
bc,x(BC,x1)>c,andγ x,c(X, c)>λ xy,a(X, a1). In Figure 1,λ xy,a(X, a1)

26. Generating Sets for the Recursively Enumerable Turing Degrees 11
would bex 2andγ x,c(X, c)wouldbex 3. In short, at the beginning of each
stages,thewholeofξ
c[s] is stable and at aσ 2-expansionary stage, we can
use the pair (a
1,a2)enumeratedbyσ 1and enumerate new computations
into our functionals to extendξ
c[s] to a configuration fora 1.
Restricting to configured numbers. We satisfy the requirement
Θ
by(BY)=A=⇒∆ y,a(Y)=A
as follows.
1. Ifais undefined and we are not preserving an inequality between
Θ
by(BY)andA, then choose a value forasuch thatais larger than
any value previously chosen and such that there is a configuration
fora.Werestrainafrom enteringAand preserve the configura-
tion forauntil we find a stagessuch that (Θ
by(BY,a)=0)[s]and
that Λ
a,y(A)[s]isequaltoY[s] on all numbers less than or equal to
θ
by(BY,a)[s]. At stages,wegotoStep2.
2. Leta
0be the largest number that we have previously enumerated as
allowed to enterAwith a certified configuration(or 0 if there is no
such number). For each numbernbetweena
0anda,ifnΛ ∈A[s]then
we restrainnfrom ever enteringA.Weenumerateainto the set of
numbers still allowed to enterAand we say that the current configura-
tion foratogether with the current computation (Θ
by(BY,a)=0)[s]
is the certified configuration associated withaduring stages.
For all strategiesτof lower priority, require that ifτenumeratesa
intoAduring stagetthen the certified configuration associated with
aduring stagesmust also exist during staget. That is, the initial
segments of the sets involved in the configuration foraand the com-
putation fromBYmust not have changed. Further, if during the
nextσ
1-expansionary stageuit happens thatYΘθ by(BY)[t]isequal
toYΘθ
by(BY)[u] (i.e.,Ydid not change) then the change inXis
recorded inCand we preserve the inequality Θ
by(BY,a)Λ =A(a)by
preserving the appropriate initial segments of the sets under construc-
tion.
We say thatais now undefined and go to Step 1.
Clearly, if for every Θ
bywe can conclude that Θby(BY)Λ =Athen we
have satisfied our requirement. Further, each of the strategies will act at
most finitely often and cause little trouble to the rest of the construction.

27. 12 K. Ambos-Spies, S. Lempp and T. A. Slaman
Suppose this is not the case and consider the effects of the above strategy
σ
6when Θby(BY)=A. Assume that the strategy is never injured (or be
willing to accept finitely many exceptions). Thenσ
6enumerates an infinite
increasing sequence of numbersaas still being allowed to enterA.Call
this sequence theσ
6-stream of numbers. For each numbern,ifnis not
an element of theσ
6-stream thennis an element ofAif and only ifnis
enumerated intoAbefore any number greater thannis enumerated into
theσ
6-stream. Thus, the restriction ofAto the numbers not in theσ 6-
stream is recursive. Now, consider a numberawhich is enumerated into
theσ
6-stream, say at stages a.
By the action ofσ
6, for every numberain theσ 6-stream, ifaenters
Aduring a stagesgreater than or equal to the one during whichawas
enumerated in the sequence, thenthe configuration existent whenawas
enumerated into the stream byσ
6is still available during stages.Since
Θ
by(BY)=Aand there are infinitely manyσ 1-expansionary stages, it
must be the case that during the interval from stagetto the nextσ
1-
expansionary stage aftert,Ychanged belowλ
xy,a(XY,a)[s]. Thus, ifais
an element of theσ
6-stream and is enumeratedinto the stream at stage
s,thenaentersAno later than the first stageuafter stagessuch that
Y[u]Θλ
xy,a(XY,a)[s]=YΘλ xy,a(XY,a)[s]. It follows thatAis recursive
relative toY.
2.2.7.One sequence (X, Y,Λ
a,x,Λa,y,Λxy,a)
If we were to work only with one sequence (X, Y,Λ
a,x,Λa,y,Λxy,a)orequiv-
alently have only one strategy of typeσ
1, then our construction would be
particularly simple. We would start with the strategies of typeσ
1andσ 2
and follow them with the strategies of typeσ 3,σ4,σ5,andσ 6(as well as
nonrecursivenessstrategiesσ
0). In the simplest case, one of these strategies
could have a finite outcome and we could conclude that our requirement
is satisfied. In the simplest case, theσ
1-strategy could have a finite out-
come and we could conclude that our requirement is satisfied. If not, then
either each of theσ
6-strategies would have a finite outcome and we would
have satisfied all the necessary requirements Θ
by(BY)Λ =A, or one of our
strategies would have an infinite outcome and we would conclude that our
requirement is satisfied by virtue ofA’s being recursive relative toY.
In this last case, how can we conclude thatAis not recursive? The
σ
6-strategy that generates an infinite stream associates with these num-
bers an infinite stream of certified configurations. The strategy to ensure

28. Generating Sets for the Recursively Enumerable Turing Degrees 13
ΘΛ =Achooses a numbera, preserves its configuration and preserves its
certification by preservingBand preserving enough ofAto ensure thatY
cannot change on any relevant number. If at a later stagetit happens that
Θ(a)[t] = 0 then the diagonalization strategy enumeratesaintoA.
3. The global construction
In the previous section, we analyzed the combinations of the strategies
associated with a single sequence (X, Y,Λ
a,x,Λa,y,Λxy,a). We now combine
the strategies for all possible such sequences and thereby present a proof of
Theorem 2.1.
3.1.Interactions betweenσ-strategies
In fact, there is very little interactionbetween the strategies associated with
different sequences. For the most part,their constraints apply to different
B’s,C’s,D’s, andE’s and so are mutually compatible. The only set that
they have in common isAand the only constraints that they put uponA
are the finite ones associated with successful diagonalization and the infinite
one constraining the enumeration of new elements ofAto the conditions
of aσ
6-stream.
Consider a strategyτconstrained to work within an infiniteσ
6-stream.
The new constraint onτis that at staget,τcan enumerate elementainto
Aif and only ifawas enumerated into theσ
6-stream at a stages<tand
the configuration associated withaduring the stagesstill exists during
staget.
Ifτis associated with aσ
0-strategy ensuring ΘΛ =Athen whenτchooses
its number with which to diagonalize,τchooses that numberafrom the
σ
6-stream. Whileτis waiting for Θ(a)=0,τpreserves enough ofAto
preserve theσ
6-configuration associated witha.IfΘ(a) is seen to be equal
to 0 thenτcan enumerateaintoAconsistently with the constraint ofσ
6.
By inspection of the strategies, this is the only way by which numbers
enterAand so we need not make many internal changes within our families
of strategies.
3.2.The tree of strategies
We fix recursive enumerations (Θ
i
:i∈ω) of all recursive functionals
relative to the empty set, ((X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
):i∈ω) of all sequences

29. 14 K. Ambos-Spies, S. Lempp and T. A. Slaman
as described inσ 1, and, for eachi,(Ψ
i,j
:j∈ω), (Θ
i,j
a
:j∈ω), and
(Θ
i,j
by
:j∈ω) of all recursive functionals with one set argument. Of course,
the enumerations (Ψ
i,j
:j∈ω), (Θ
i,j
a
:j∈ω), and (Θ
i,j
by
:j∈ω) need not
depend oni, but the notation will be convenient below. Let ((i, j):i, j∈ω)
be a recursive ordering ofω×ωof order typeω. We will assume that for
allj,iis less than or equal to the position of (i, j)inthisordering.
We define a treeTof sequences of pairs of strategies and outcomes using
recursion. We will also order the immediate extensions of each node from
left to right. Ordering by first difference, we have a left to right ordering
for all incompatible sequences inT. As usual, shorter nodes or nodes to
the left will be assigned higher priority than those below or to the right.
Forη∈T, we will speak of the extensions ofηas being belowηinT.We
start with the empty sequence as an element ofT.
Suppose thatη=((τ
k,ok):k<)isanelementofT.
Definition 3.1Supposek< andτ
kis of the formσ 1(X
i
,Y
i
,Λ
i
a,x
,
Λ
i
a,y
,Λ
i
xy,a
). Then
1.τ
kisin effect atηif and only ifo kis Π2,and
2.τ
kisunresolved atηif and only if for allj,
(σ
6(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
by
),Π2)Λ ∈η.
Definition 3.2Supposek< andτ
kis of the formσ 6(X, Y,Λ a,x,Λa,y,
Λ
xy,a,Θby). Then,τ kisin effect atηif and only ifo kis Π2.
Strategies belowηinTare based on the assumption that there will be
infinitely many expansionary stages for theσ
1-andσ 6-strategies in effect
atη.Ifτ
kis unresolved atηthen no strategy inηhas determined thatA
is recursive relative toY.
Leti
maxbe the largestisuch that there is ak<such thatτ kis equal
toσ
1(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
). (If there is no suchi,leti max=−1.)
Case 1.If there is a pair (i
∗
,j
∗
)amongthefirsti maxmany such pairs
such that
A.σ
1(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x
,Λ
i
∗
a,y
,Λ
i
∗
xy,a
) is in effect atη, unresolved atη,and
B. one ofσ
2(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x
,Λ
i
∗
a,y
,Λ
i
∗
xy,a
),
σ
3(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x
,Λ
i
∗
a,y
,Λ
i
∗
xy,a
,Ψ
i
∗
,j
∗
),

30. Generating Sets for the Recursively Enumerable Turing Degrees 15
σ4(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x
,Λ
i
∗
a,y
,Λ
i
∗
xy,a
,Θ
i
∗
,j
∗
a
),
σ
5(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x
,Λ
i
∗
a,y
,Λ
i
∗
xy,a
,Θ
i
∗
,j
∗
a
),
orσ
6(X
i
∗
,Y
i
∗
,Λ
i
∗
a,x,Λ
i
∗
a,y,Λ
i
∗
xy,a,Θ
i
∗
,j
∗
by
) does not appear in (the first
coordinate of an element of)η,
then let (i, j) be the least such (i
∗
,j
∗
). We determine the immediate suc-
cessor ofηinTby the first of the following conditions which applies.
1. Ifσ
2(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
) does not appear inηthen
η
Θ
(σ2(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
),Π1)∈T.
2. Ifσ
3(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Ψ
i,j
) does not appear inηthen
η
Θ
(σ3(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Ψ
i,j
),Σ2)∈T,
η
Θ
(σ3(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Ψ
i,j
),Π2)∈T,
and the Σ
2-extension ofηis to the right of the Π 2-extension.
3. Ifσ
4(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
) does not appear inηthen
η
Θ
(σ4(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
),Σ1)∈T,
η
Θ
(σ4(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
),Π1)∈T,
and the Π
1-extension ofηis to the right of the Σ 1-extension.
4. Ifσ
5(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
) does not appear inηthen
η
Θ
(σ5(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
),Σ1)∈T,
η
Θ
(σ5(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
a
),Π1)∈T,
and the Π
1-extension ofηis to the right of the Σ 1-extension.
5. Ifσ
6(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
by
) does not appear inηthen
η
Θ
(σ6(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
by
),Σ2)∈T,
η
Θ
(σ6(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θ
i,j
by
),Π2)∈T,
and the Σ
2-extension ofηis to the right of the Π 2-extension.

31. 16 K. Ambos-Spies, S. Lempp and T. A. Slaman
Case 2.If there is no such pair (i, j)asabovethenweseti=i max+1
and determine the immediate successor ofηinTas follows.
1. Ifσ
0(Θ
i
) does not appear inηthen
η
Θ
(σ0(Θ
i
),Σ1)∈T,
η
Θ
(σ0(Θ
i
),Π1)∈T,
and the Σ
1-extension ofηis to the left of the Π 1-extension.
2. Otherwise,
η
Θ
(σ1(X, Y,Λ a,x,Λa,y,Λxy,a),Σ2)∈T,
η
Θ
(σ1(X, Y,Λ a,x,Λa,y,Λxy,a),Π2)∈T,
and the Σ
2-extension ofηis to the right of the Π 2-extension.
3.2.1.η-configurations
Notice that ifη∈Tthen there is a unique strategyσsuch thatσappears
as the first component in the last element of the immediate successors ofη.
Definition 3.3Suppose thatηis an element ofT.
1. Let
{σ
1(X
ij
,Y
ij
,Λ
ij
a,x
,Λ
ij
a,y
,Λ
ij
xy,a
):j< 1}
be the sequence ofσ
1-strategiesσin effect atη.Thenan η-
configuration fora
1is a finite initial segmentAand the sets asso-
ciated with these strategies such that for eachj<
1,thereisa
σ
1(X
ij
,Y
ij
,Λ
ij
a,x,Λ
ij
a,y,Λ
ij
xy,a)-configuration fora 1within this initial
segment.
2. We say that anη-configuration iscertifiedif in addition to the above,
for everyσ
6-strategyτ kwhich is in effect atη, the computation setting
Θ
by(BY,a) = 0 has not changed since the stage during whichτ k
enumerated the configuration foraas certified.
For example, ifηhas only oneσ
1-strategyσ 1(X, Y,Λ a,x,Λa,y,Λxy,a)
with a Π
2-outcome, then anη-configuration fora 1is the same as a
σ
1(X, Y,Λ a,x,Λa,y,Λxy,a)-configuration fora 1, as described in Figure 1.
Withnsuch strategies, anη-configuration is described byncopies of Fig-
ure 1, one for each strategy and involving the sets associated with that
strategy, sharing a common value fora
1.

32. Generating Sets for the Recursively Enumerable Turing Degrees 17
Thei jth component of anη-configuration fora 1is the initial segment
ofA,B
ij
,C
ij
,D
ij
,andE
ij
which makes up theσ 1(X
ij
,Y
ij
,Λ
ij
a,x,Λ
ij
a,y,
Λ
ij
xy,a)-configuration fora 1.
3.3.The construction
We organize our construction by stagess,wheresis greater than or equal
to 1. Each stagesis divided into at mostsmany substagest,wheretis
also greater than or equal to 1. We proceed as follows during stages.
Letη[s,0] equal the empty sequence.
Givenη[s, t−1] withtless than or equal tos,letσbe the strategy which
appears in the first component of the immediate successors ofη[s, t−1].
We may assume thatσhas been assigned a numbera
1and anη[s, t−1]-
configuration fora
1during an earlier stage and that no component of that
configuration has changed since the stage during which it was assigned.
(Otherwise, a strategy simply ends the stage since by its hypothesis, it
will eventually be assigned such a numbera
1by aσ 2-orσ 5-strategy as
described below.)
We follow the instructions ofσ, which depend on its type as described
below. At the end of its action, eitherσends stagesand we go to stage
s+1witht=0orσdetermines a value forη[s, t]. In the second case, ift
is less thansthen we continue with substaget+ 1 of stages.
We adapt the pure strategies described in the previous section to work
within the full construction as follows.
3.3.1.Adding anA-diagonalization strategyσ
0
Suppose thatσis a diagonalization strategyσ 0(Θ
i
) to ensure that Θ
i
Λ =A.
If Θ
i
(a1)[s] is not equal to 0 then we restrain any number from en-
tering any set involved in ourη-configuration fora
1.Weletη[s, t]be
η[s, t−1]
Θ
(σ,Π 1).
If Θ
i
(a1)[s]isequalto0and a 1is not an element ofA[s], then we
enumeratea
1intoAand end stages.
If Θ
i
(a1)[s] is equal to 0 and we have already enumerateda 1intoA,
then we letη[s, t]beη[s, t−1]
Θ
(σ,Σ 1).
3.3.2.Adding aσ
1(X, Y,Λ a,x,Λa,y,Λxy,a)
Suppose thatσisσ
1(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
). We alter the pureσ 1-
strategy (described in the previous section) in the following way.

33. 18 K. Ambos-Spies, S. Lempp and T. A. Slaman
First, we measureσ-expansions in terms of stages whenη[s, t−1] is
active in the construction. Second, while waiting for aσ-expansionary
stage, we preserve theη[s, t−1]-configuration fora
1.
Ifsis notσ-expansionary in the above sense then letη[s, t]be
η[s, t−1]
Θ
(σ,Σ 2).
Otherwise, we enumerate the pair (a
1,a2) as in the pureσ 1-strategy, we
letη[s, t]beη[s, t−1]
Θ
(σ,Π 2), and we cancel all strategies on nodes to the
right ofη[s, t].
3.3.3.Adding aσ
2(X, Y,Λ a,x,Λa,y,Λxy,a)
Suppose thatσisσ
2(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
). By the definition ofTand
the previous paragraph, we may assume that the last strategy mentioned
inη[s, t−1] is of the formσ
1(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
)andthatsis expan-
sionary for that strategy (i.e., the sequenceη[s, t−1] ends with the pair
(σ
1(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
),Π2)).
We letη[s, t]beη[s, t−1]
Θ
(σ,Π 1), and we alter the pureσ 2-strategy in
the following way.
First, we may need to changeBCto record a change inX. If during
the previous stages
Λ
during whichσ 2acted, some strategy associated with
an extension ofηenumerated a numberaintoA,thenletµbe the node
inTassociated with that strategy. There are two cases to consider. In
the first case, there is no strategyσ
6(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
,Θby)aboveµ
withB
i
=BandC
i
=Cwhich certifieda. In this case, we record the
change inXby changingBaccordingly. Otherwise, ifYdid not change
belowλ
i
xy,a
(a) between stages
Λ
and the current stage, thenXmust have
changed there. This allows us to record all changes inXby enumeratingc
intoC,wherecis the number depicted in Figure 1, and we do so without
changingB.
Next, let (a
1,a2) be the pair just enumerated byσ 1(X
i
,Y
i
,Λ
i
a,x
,
Λ
i
a,y
,Λ
i
xy,a
). We extend the definitions of the functionals Γx,b,Γx,c,and
Γ
bc,xso that we have aσ 1(X
i
,Y
i
,Λ
i
a,x
,Λ
i
a,y
,Λ
i
xy,a
)-configuration fora 1
and thus anη[s, t]-configuration fora 1.Ifthereisaµsuch thatη[s, t]⊆µ,
µwas active during a previous stage, the set of strategies in effect atµis
equal to the set of strategies in effect atη[s, t], andµdoes not currently
have anη[s, t]-configuration assigned to it, then we assign the configura-
tion fora
1to the leftmost and shortest suchµ(that is, the one of highest
priority). We cancel all strategies to the right ofµand end stages.

34. Generating Sets for the Recursively Enumerable Turing Degrees 19
3.3.4.Adding aσ 3(X, Y,Λ a,x,Λa,y,Λxy,a,Ψcd,Ψce)
Our only alteration to the pureσ
3-strategy is to make it measure ex-
pansionary stages taking into account only those stages during which it
is active. Forσ=σ
3(X, Y,Λ a,x,Λa,y,Λxy,a,Ψcd,Ψce)weletη[s, t]be
η[s, t−1]
Θ
(σ,Π 2)ifsisσ-expansionary andη[s, t−1]
Θ
(σ,Σ 2)otherwise.
3.3.5.Adding aσ
4(X, Y,Λ a,x,Λa,y,Λxy,a,Θa)or a
σ
5(X, Y,Λ a,x,Λa,y,Λxy,a,Θa)
We use the pureσ
4-andσ 5-strategies without change. For aσ 4-strategyσ,
we letη[s, t]beη[s, t−1]
Θ
(σ,Σ 1) if the diagonalization witnessnhas been
enumerated intoDandη[s, t−1]
Θ
(σ,Σ 2)otherwise.(Foraσ 5-strategyσ,
Dis replaced byE.)
3.3.6.Adding aσ
6(X, Y,Λ a,x,Λa,y,Λxy,a,Θby)
We do not alter the first phase of the pureσ
6-strategy. We start with a
numberafor which we have a certifiedη[s, t−1]-configuration. We restrain
afrom enteringAand preserve its configuration. We wait for a stages
such that (Θ
by(BY,a)=0)[s]. If the currentsis not such a stage then, for
σ=σ
6(X, Y,Λ a,x,Λa,y,Λxy,a,Θby)weset
η[s, t]=η[s, t−1]
Θ
(σ,Σ 2).
Otherwise, we set
η[s, t]=η[s, t−1]
Θ
(σ,Π 2).
If there is anasuch that we wait forever for anssuch that
(Θ
by(BY,a)=0)[s], then Θ byΛ =Aand the requirement is satisfied. Other-
wise, according to the pureσ
6-strategy, we should restrict the enumeration
of numbers intoAto those which appear in the stream it generates.
We must describe how the numbers in that stream are distributed to
the strategies associated with nodes extendingη[s, t]=η[s, t−1]
Θ
(σ,Π 2).
For this, we make the same alteration which we made for theσ
2-strategies.
We can assume thatσhas been assigned a certifiedη[s, t−1]-
configuration for a numbera
1.When σfinds a computation setting
Θ
by(BY,a1)=0andforwhichthereisareΛ a,y(A) computations agree-
ing withYbelowθ
by(BY,a1), then we say that these computations certify
theη[s, t−1]-configuration fora
1with respect toσ.Thus,a 1now has a
certifiedη[s, t]-configuration.

35. 20 K. Ambos-Spies, S. Lempp and T. A. Slaman
If there is aµsuch thatη[s, t]⊆µ,µwas active during a previous stage,
the set of strategies in effect atµis equal to the set of strategies in effect
atη,andµdoes not currently have anη[s, t]-configuration assigned to it,
then we assign the configuration fora
1to the leftmost and shortest suchµ
(that is, the one of highest priority). We cancel all strategiesη
Λ
to the right
ofµand end stages. If there is no suchµthen we cancel all strategies to
the right ofη[s, t].
3.4.Analyzing the construction
Letη
∞
be the path throughTsuch that
1. for infinitely stagessand infinitely many substagest,η[s, t] is a sub-
sequence ofη
∞
,and
2. for at most finitely many stagessand substagest,η[s, t]istotheleft
ofη
∞
.
Following convention, we say thatη
∞
is the true path of the construction.
Lemma 3.4The true pathη
∞
is an infinite path inT.
Proof.Suppose thatηis a finite initial segment ofη
∞
. We will argue that
there is a proper extension ofηwhich is also contained inη
∞
.
Note thatTis a finite branching tree. Consequently, if there are in-
finitely manysduring whichηacts and does not end the stage, then there
is a leftmost proper extension which acts infinitely often and the claim is
proven.
There are four cases in whichηperemptorily ends a stage during which
it acts. Firstlyηmight end with a strategy which ends the stage since it
is not assigned a number, which can happen at most finitely often in a row
by the strategy’s assumption on outcomes of strategies above it. Next,η
might end with a strategy for making ΘΛ =A, in which case this strategy
can end the stage at most once without being initialized. Otherwise, either
ηends with aσ
2-strategy, or it ends with aσ 6-strategy, and, in both cases,
ηallocates anη-certified configuration to a strategy below it. But, ifµis
eligible to be assigned a configuration byηthenµmust have been active
during an earlier stage of the construction. Ifηwere to end all but finitely
many of the stages during which it finds a new certifiedη-configuration,
then there can only be finitely many suchµ’s. Eventually, every suchµwill
have a certifiedη-configuration assigned to it. But then the next time that

36. Generating Sets for the Recursively Enumerable Turing Degrees 21
ηfinds a new certifiedη-configuration it will not end the stage and some
proper extension ofηwill be active.
Lemma 3.5For each finiteη⊂η
∞
, the following conditions hold.
1. We cancelηduring the last stages
ηduring which there is atsuch
thatη[s
η,t]is to the left ofη.
2. We letηact infinitely often.
3. During every stage greater than or equal tos
η, we respect all of the
constraints imposed byηduring any earlier stage.
Proof.Routine. ff
Lemma 3.6Our construction satisfies all of the requirements of Sec-
tion 2.1.
Proof.This follows as in the analysis of the individual strategies in Sec-
tion 2.2. ff
Theorem 2.1 follows directly from Lemma 3.6.
References
Ambos-Spies, K. (1984). On pairs of recursively enumerable degrees.Trans.
Amer. Math. Soc. 283(2), 507–531. MR MR737882 (85d:03083).
Ambos-Spies, K. (1985). Generators of the recursively enumerable degrees. In
Recursion theory week (Oberwolfach, 1984), Volume 1141 ofLecture Notes in
Math., pp. 1–28. Berlin: Springer. MR 87i:03081.
Fejer, P. A. (1982). Branching degrees above low degrees.Trans. Amer. Math.
Soc. 273(1), 157–180. MR 84a:03044.
Fejer, P. A. (1983). The density of the nonbranching degrees.Ann. Pure Appl.
Logic 24(2), 113–130. MR MR713296 (85g:03062).
Jockusch, Jr., C. G. (1985). Genericity for recursively enumerable sets. InRecur-
sion theory week (Oberwolfach, 1984), Volume 1141 ofLecture Notes in Math.,
pp. 203–232. Berlin: Springer. MR MR820782 (87f:03117).
Lachlan, A. H. (1966 bounds for pairs of recursively enumerable degrees.
Proc. London Math. Soc. (3) 16, 537–569. MR MR0204282 (34 #4126).
Sacks, G. E. (1963).Degrees of unsolvability. Princeton, N.J.: Princeton Univer-
sity Press. MR MR0186554 (32 #4013).

37. 22 K. Ambos-Spies, S. Lempp and T. A. Slaman
Slaman, T. A. (1991). The density of infima in the recursively enumerable de-
grees.Ann. Pure Appl. Logic 52(1-2), 155–179. International Symposium on
Mathematical Logic and its Applications (Nagoya, 1988). MR 92e:03061.
Yates, C. E. M. (1966). A minimal pair of recursively enumerable degrees.J.
Symbolic Logic 31, 159–168. MR MR0205851 (34 #5677).

38. CODING INTOH(!2),TOGETHER (ORNOT)WITH
FORCINGAXIOMS.ASURVEY
DavidAspero
InstitucioCatalanadeRecercaiEstudisAvancats(ICREA)
and
DepartamentdeLogica,HistoriaiFilosoadelaCiencia
UniversitatdeBarcelona
BaldiriReixac,s/n,08028Barcelona,Spain
E-mail:[email protected]
URL:http://www.icrea.es/pag.asp?id=David.Aspero
Thispaperismainlyasurveyofrecentresultsconcerningthepossi-
bilityofbuildingforcingextensionsinwhichthereisasimpledeni-
tion,overthestructurehH(!2);2iandwithoutparameters,ofapre-
scribedmemberofH(!2)orofawell-orderofH(!2).Someofthese
resultsareinconjunctionwithstrongforcingaxiomslikePFA
++
or
MM,somearenot.Ialsoobserve(Corollary4.4)thattheexistence
ofcertainobjectsofsize@1followsoutrightfromtheexistenceof
largecardinals.Thisobservationismotivatedbyan(unsuccessful)
attempttoextendaPFA
++
resulttoonementioningMM
++
.
1.Mainstartingquestionsandsomepiecesofnotation
Theworkpresentedheredealsmostlywiththeproblemofndingoptimal
denitionsofwell-ordersoftherealsandotherobjects.Moreprecisely,it
addressesthefollowingtwoquestions.
1
Question1:SupposeAisasubsetof!1.Supposewearegiventhetask
ofgoingovertoaniceset-forcingextension
2
inwhichAadmitsasimple
denition(x),withoutparameters,overthestructurehH(!2);2iorover
1
Asquotedfrom[As2].
2
So,ifniceistobeinterpretedaspreservingstationarysubsetsof!1intheground
modelandAisastationaryandco-stationarysubsetof!1,thenAwillremainstationary
andco-stationaryintheextension.
23

39. 24 D.Aspero
somenatural(denable)extensionofthisstructure,likehH(!2);2;NS!1i.
Whatisthelowestdegreeoflogicalcomplexitythatcanbeattributedtoa
denition(x)forwhichwecanperformtheabovetask?
Question2:Whatisthelowestdegreeoflogicalcomplexityofformu-
lasforwhichthereisaformula(x;y)(againwithoutparameters)with
thatcomplexityandwiththepropertythatwecangoovertoaset-forcing
extensioninwhichthesetofrealnumbersadmitsawell{orderdenedby
(x;y)(againoverthestructurehH(!2);2ioroversomenaturalextension
ofit)?
Forsomebackgroundontheseproblemsthereaderisreferredto[As2].
Logicalcomplexity{forformulasofalanguageextendingthelanguageof
settheory{willbemeasuredinthispaperbythefamiliarLevyhierarchy
S
n<!
fn;ng.Recallthataformulais0(equivalently,0)ifallofits
quantiersarerestricted
3
andthat,forn>0,aformulaisn(respectively,
n)ifitisoftheform(9x)'foran1formula'(respectively,ifitis
oftheform(8x)'foran1formula').Notethat,inanymodelM
ofZFwithoutthePowerSetAxiom,ifPisadenableclassinMand
'(x0;:::xk)isaformulainthelanguageofthestructurehM;2;Pi,then
thereissomeformula (x0;:::xk)2
S
n<!
fn;ng(inthesamelanguage)
suchthat,inhM;2;Pi,'(x0;:::xk)islogicallyequivalentto (x0;:::xk).
4
Inotherwords,theLevyhierarchyprovidesaclassication,uptological
equivalence,ofallformulasoverstructureshM;2;Piasabove.Also,note
that,foreveryn<!,everyformulainn[nislogicallyequivalenttoa
formulainn+1\n+1.
Throughoutthispaper,H(!2)denotesthesetofallsetswhosetransitive
closurehassizeatmost@1,andNS!1denotesthenonstationaryidealon
!1.Givenaregularcardinal,cf()istheclassofallordinalsofconality
.LwilldenotetherstorderlanguageofthestructurehH(!2);2;NS!1i.
GivenasetXofordinals,ot(X)willdenotetheordertypeofX.Recall
thatapartialorderPisproperifforeveryregularcardinal>jTC(P)j,
everycountableN4H()containingPandeveryp2P\Nthereissome
q2Pextendingpsuchthatqis(N;P){generic,i.e.suchthatqP2

N
whenever2NisaP{nameforanordinal.Also,Pissemiproperincase
forevery,Nandpasabovethereisaconditionqextendingpsuchthat
3
Inotherwords,ifallitsquantiersoccurinasubformulaoftheform(8x)(x2y!')
or(9x)(x2y^').
4
Thatis,hM;2;Pij=(8x0;:::xk)('(x0;:::xk)$ (x0;:::xk)).

40. CodingintoH(!2),Together(orNot)withForcingAxioms 25
qis(N;P){semigeneric,i.e.suchthatqP2

Nforeveryname2N
foranordinalin!
V
1
.Everyproperpartialorderissemiproperand,ifP
issemiproper,theneverystationarysubsetof!1remainsstationaryafter
forcingwithP.
L(R)isthe{minimaltransitiveinnermodelofZFcontainingallre-
alsandallordinals.SomeargumentsinSection4,andintheproofsof
Theorems2.8and2.9inSection2,involvePmaxforcing.Pmaxisaposet
belongingtoL(R)anddenableinL(R)(withoutparameters).Ifx
y
exists
foreveryrealx,
5
thenPmaxisahomogeneousforcingandis{closed(in
VandinL(R)).Inparticular,forcingwithitoverL(R)doesnotaddnew
reals.ThestandardreferenceforPmaxforcingis[W].
Itwillbeconvenienttoxanotionofincompatibility,forpairsoffor-
mulas,whichisabsolutewithrespecttosucientlyarbitrarymodelsof
settheory.WewillsaythattwoL{formulas0(x)and1(x)areZFC{
provablyincompatibleifZFCprovesthatforeveryuncountableregular
cardinalandeveryx2H(
+
),hH(
+
);2;NSij=:(0(x)^1(x)).
Also,foranL{formulaintwofreevariables(x;y),wewillsaythat(x;y)
isZFC{provablyantisymmetricifZFCprovesthatforeveryuncountable
regularcardinalandeveryx,y2H(
+
),x6 =y,hH(
+
);2;NSij=
:((x;y)^(y;x)).
6
Acknowledgment.Manyoftheresultsinthispaperwerepresentedin
twotalksthatIgaveinSingaporeinJuly2005.Thesetalkswerepart
oftheIMSworkshop\ComputationalProspectsofInnity".Ithankthe
membersoftheOrganizingCommitteeforinvitingme.
2.Resultsnotmentioningforcingaxioms
Thefollowingtheoremsareprovedin[As4].
Theorem2.1([As4])Thereare3L{formulas0(x)and1(x)and3
L{formulas 0(x)and 1(x)withthefollowingtwoproperties.
(1)(0(x);1(x))and( 0(x); 1(x))aretwopairsofZFC{provablyin-
compatibleformulasoverthestructurehH(!2);2;NS!1i.
5
Whichfollowsfromalllargecardinalassumptionsusedintheargumentsalludedto
here.
6
ThenotionsofprovablyincompatiblepairsofformulasoverhH(!2);2;NS!1
iand
ofprovablyincompatibleformulasinthelanguageofsettheory(overhH(!2);2i)areof
coursedenedinthenaturalway.Andthesamegoesforthecorrespondingnotionsof
provablyantisymmetricformulas.

41. 26 D.Aspero
(2)GivenanyA!1thereisaproperposetforcingthat
(a)Aisdened,overhH(!2);2;NS!1i,by0(x)andby 0(x),and
(b)!1nAisdened,overhH(!2);2;NS!1i,by1(x)andby 1(x).
Theorem2.2([As4])Thereisa3L{formula(x;y)anda3L{
formula (x;y)withthefollowingtwoproperties.
(1)(x;y)and (x;y)areZFC{provablyantisymmetricformulasover
thestructurehH(!2);2;NS!1i.
(2)Ifthereisaninaccessiblecardinal,thenthereisaproperposetP
forcingtheexistenceofawell{orderofH(!2)ofordertype!2
suchthatisdened,overhH(!2);2;NS!1i,bothby(x;y)andby
(x;y).
Infact,Theorem2.1canbeeasilyderived
7
fromthefollowingresult.
Theorem2.3([As4])Thereisa2L{formula(x)suchthatforevery
uncountableregularcardinalandeveryAthereisaposetPwiththe
followingproperties.
(1)Pis{distributive,
8
proper,andpreserves.Also,if2

=
+
when-
everisaninnitecardinalwith
+
<,thenPpreservesallsta-
tionarysubsetsof.Finally,if2
<
=and2

=
+
,thenPhas
the
+
{chaincondition.
(2)Pforces
A=f<:hH(
+
);2;NSij=()g
Similarly,Theorem2.2isaconsequenceofthefollowingresult,also
provedin[As4],bytaking=!1.
Theorem2.4([As4])Thereisa3L{formula(x;y)anda3L{
formula (x;y)satisfying(1)and(2)below.
7
Bytaking=!1andbytaking0(x)and 0(x)tobe(x)and1(x)and 1(x)
tobe:(x).
8
Recallthataforcingnotionis{distributiveifandonlyifitdoesnotaddnew
sequencesofordinalsoflengthlessthan.

42. CodingintoH(!2),Together(orNot)withForcingAxioms 27
(1)(x;y)and (x;y)areZFC{provablyantisymmetricformulas.
(2)GivenanyuncountableregularcardinalthereisaposetPwiththe
followingproperties.
(a)Ppreserves!1and,if>!1,thenitsatises(1)fromTheo-
rem2.3.
(b)Pforcesthat
f(x;y)2H(
+
)H(
+
):hH(
+
);2;NSij=(x;y)g
isequalto
f(x;y)2H(
+
)H(
+
):hH(
+
);2;NSij= (x;y)g
andisawell{orderofH(
+
)ofordertype
+
.
NotethatnoneofTheorems2.3and2.4canholdfor=!:By[Mar-St],
ProjectiveDeterminacyholdsifthereareinnitelymanyWoodincardinals.
Inparticular,underthislargecardinalassumptiontherecanbenowell{
orderoftherealsdenableoverhH(!1);2i(evenallowingparameters).
Anditcanbeseenthatif<aresuchthatisalimitofinnitelymany
Woodincardinalsandisameasurablecardinal,thengivenanyposetP
ofsizelessthan,anyP{genericlterGoverVandanyrealr2V[G]nV,
risnotdenableoverhH(!1)
V[G]
;2ibyanyformulawitharealnumber
inVasparameter.
9
Givenaregularcardinal!1,theproofsofTheorems2.3and2.4
involvethemanipulation,byforcing,ofcertainweakclub{guessingprop-
ertiesforclub{sequencesdenedonstationarysubsetsof,insuchaway
thatthe2theoryofhH(
+
);2;NSiwithordinalsinasparameters
codesanyprescribedsubsetof.
Givenanordinal,Lim()denotesthesetofnonzerolimitordinalsin
.Aclub{sequencewillbeasequenceoftheform =h:2Lim()i
{forsomeordinal{suchthateachisasubsetof.ThesetSof
2Lim()suchthatisaclubofiscalledthedomainof.Itwill
alsobedenotedbydom().WemaysaythatisdenedonS.Ifisa
club{sequenceandissuchthatsup(dom())=,thenwemaysaythat
isaclub{sequenceon.Ifisanordinalsuchthattheordertypeof
9
ThisfollowsfromaresultofWoodintotheeectthatthetheoryofL(R)withreal
numbersasparameterscannotbechangedbyforcingwithPwheneverPisaposetwith
jPj<and<areasabove(see[L],Theorem3.1.12foraproof).

43. 28 D.Aspero
isforeach2dom( ),thenwesaythattheheightofis.ht()will
denotetheheightof(ifitexists).Asin[A-Sh](forladdersystems,that
is,forclub{sequencesofheight!),ifisaclub{sequenceand2dom(),
thenwilldenote()(andsimilarlywithotherGreekletters).Wewill
saythatisacoherentclub{sequenceifthereisaclub{sequencewith
dom()dom()anddom()=dom(),
10
andsuchthatis
coherentintheusualsense,thatis,suchthatforevery2dom()and
everylimitpointof,2dom()and\=.
Theconceptsinthisparagrapharedenedin[A-Sh]forladdersys-
tems.
11
Letbeaclub{sequenceonanordinalofuncountableconality.
WesaythatisguessingincaseforeveryclubCthereissome
2C\dom()suchthatnCisboundedin.Furthermore,wesay
thatisstronglyguessingifforeveryclubCthereisaclubD
suchthatnCisboundedinforevery2D\dom().
12
isavoid-
ableifthereisaclubCsuchthat\Cisboundedinforeach
2dom()\C.Giventwoclub{sequencesandonthesameordi-
nal,ofuncountableconality,isdisjointfromif\=;for
every2dom()\dom().Givenastronglyguessingclub{sequence
onanordinalandasetXincludingdom(),issaidtobemaxi-
malforXincaseeveryladdersystemdenedonXanddisjointfromis
avoidable.
TheproofsofTheorems2.3and2.4makeuseofacertainweakclub{
guessingpropertyforclub{sequences,
13
whichisbestdenedafterintro-
ducingthefollowingstrongversionofintersectionoftwosetsofordinals:
Giventwosetsofordinals,XandY,X\

Yisdenedasthesetof2X\Y
suchthatisnotalimitpointofX.Now,givenaclub{sequenceonan
ordinalofuncountableconality,wewillsaythatistype-guessingin
caseforeveryclubCthereissome2C\dom()withot(\

C)
ashighaspossible,thatis,withot(\

C)=ot().Wewillsaythat
isstronglytype-guessingincaseforeveryclubCthereisaclubD
suchthatot(\

C)=ot()forevery2D\dom().
Also,forasetXofordinalsandanordinal,theCantor{Bendixson
rankofwithrespecttoX,rnkX(),isdenedbyspecifyingthat
rnkX()=0ifandonlyifisnotalimitpointofX,thatrnkX()1
10
Where,givenaclub{sequenceandasetX,therestrictionoftoX,tobedenoted
byX,isthatclub{sequencewhichisequaltoonXandis;elsewhere.
11
TheywilloccurinDenition2.3.
12
Notethatastronglyguessingclub{sequenceisguessingifandonlyifitsdomainis
stationary.
13
Denedin[As4].

44. CodingintoH(!2),Together(orNot)withForcingAxioms 29
ifandonlyifisalimitpointofXand,foreachordinal1,that
rnkX()>ifandonlyifisalimitordinalandthereisasequence
()
<ot()convergingtosuchthatrnkX()forevery.
14
Anordi-
nalwillbesaidtobeperfectifrnk()=.
15
Notethatrnk()for
everyordinalandthat,givenanyuncountableregularcardinal,theset
ofperfectordinalsbelowisaclub.
Denition2.1([As4])Givenanuncountableregularcardinal,A=
f

:<g(for1)isanalmostspeciablesetofclub{sequences
on(asscson,forshort)ifandonlyif
(a)thereisaone{to{onesequenceh:<iofperfectordinalsbelow
suchthat,foreach,hascountableconalityand

isacoherent
club{sequenceonofheight,
(b)hdom(

):<iisasequenceofpairwisedisjointstationarysets,
(c)each

isstronglytype-guessing,and
(d)givenanycoherentclub{sequenceonwithstationarydomain,if
hasheightofcountableconalityand6 =ht(

)forevery<,
thenisnotstronglytype-guessing.
Lemma2.5givesajusticationfortheuseofthephrase`almostspeci-
able'inDenition2.1.Itimpliesthatfht(

):<0g=fht(

):<
1gholdswheneverf

:<0gandf

:<1garetwoasscs'son
thesame.
Lemma2.5([As4])SupposeA=f

:<gisanalmostspeciable
setofclub{sequencesonanuncountableregularcardinal.Then,fht(

):
<gisequaltothesetofperfectordinals<ofcountableconality
andsuchthatthereisastronglytype-guessingcoherentclub{sequenceon
ofheightandwithstationarydomain.
Theabovelemmafollowsimmediatelyfromthedenitionofasscs.The-
orem2.3isanimmediateconsequenceofLemma2.5andofthefollowing
result.
14
Thus,forexample,rnkX()=1ifandonlyifisalimitpointofordinalsinXbut
notalimitpointoflimitpointsofX.
15
Thus,withthisdenition,therstperfectordinalis0,thesecondis0=
supf!;!
!
;!
(!
!
)
;!
(!
(!
!
)
)
;:::g,etc.

45. 30 D.Aspero
Theorem2.6([As4])Let!1bearegularcardinal,letAbeasubset
ofandlet()<bethestrictlyincreasingenumerationofallperfect
ordinalslessthanwithcf()=!.ThenthereisaposetPsatisfy-
ingthenicenesspropertiesin(1)fromTheorem2.3andforcingthatthere
isanasscsf

:<ot(A)gonsuchthatA=f<:(9<
ot(A))(ht(

)=)g.
Theorem2.3followsthensince,foranygivenregular!1andany
A,theposetgivenbytheabovetheoremforcesthatAistheset
of<withthepropertythatthereisacoherentstronglytype-guessing
club{sequencewithstationarydomainincludedinandofheight(where
()<isasintheabovetheorem).
16
Thestrategyforbuildingtheposet
PinTheorem2.6isquiteasonewouldexpect:Pisthelimitofaforcing
iterationoflength
+
builtwithsupportsofsizelessthan.Wemay
assumethat2
<
=and2

=
+
holdinthegroundmodel.Intherst
stepoftheiterationoneadds,byinitialsegments,asetAofcoherentclub{
sequenceswiththerelevantheights.Thenonekills,alongtheiteration,all
possibleobstaclestoAbeinganasscs.Infact,itsucestoforce,forall
clubsCarisingduringtheiteration,withthenaturalposetforshooting
aclubDsuchthatot(\

C)=ot()forall2D\dom()(for
all2A).Thisisenoughtoensurethat(d)fromDenition2.1holds
forA.Thebulkoftheproofisofcoursethevericationthatthisposet
Phasthedesiredproperties.Also,severalofthetechnicalitiesinvolvesin
thecoding|forexampletherestrictiontoperfectordinalsofcountable
conalityortheconsiderationoftheoperation\

|aretherepreciselyto
make(d)hold.
TheproofofTheorem2.4involvesacertainprinciplewhichprovidesa
simplewayofencodingmembersofH(
+
)(forsome)byordinalsin
+
,
quiteinthespiritoftheprinciple AC(forH(!2))from[W].
Denition2.2([As4])Letbeanuncountableregularcardinal,letFbe
afunctionfromintoP(),andletS=hSi:i<ibeasequenceof
pairwisedisjointstationarysubsetsof.
F;S
AC
isthenthestatementthat
thereisanenumerationhB:<
+
iofallsubsetsofsuchthat,
foreach,thereisaclubE[]
<
withthepropertythatforeveryX2E
andeveryi<,
16
Notingthatthispropertycanindeedbeexpressedbya2L{formulaoverthe
structurehH(
+
);2;NSi.

46. CodingintoH(!2),Together(orNot)withForcingAxioms 31
(a)ot(X)2F(X\)ifX\2Siandi2B,and
(b)ot(X)=2F(X\)ifX\2Siandi=2B.
Itiseasytoseethatthereisa1formula(x;y;z)withtheproperty
thatif,FandSaresuchthat
(1)isanuncountableregularcardinal,F:!P()isafunctionand
Sisa{sequenceofpairwisedisjointstationarysubsetsof,and
(2)
F;S
AC
holds,
thenF;S:=fhx;yi2H(
+
)H(
+
):hH(
+
);2ij=(x;y;hF;Si)gisa
well{orderofH(
+
)ofordertype
+
.Moreover,thisformulacanbetaken
sothatZFCprovesthatthereareno,FandSasin(1)forwhichthereare
anydistinctx,y2H(
+
)withH(
+
)j=(x;y;hF;Si)^(y;x;hF;Si).
Thefollowingresultisprovedin[As4].
Theorem2.7Let!1isaregularcardinal,andsuppose2
<
=and
2

=
+
hold.Thenthereisa{distributiveposetPaddingafunction
F:![]
<
anda{sequenceSofpairwisedisjointstationarysubsets
ofsuchthat
F;S
AC
holds.Furthermore,Phasthe
+
{chaincondition
and,if2

=
+
wheneverisaninnitecardinalwith
+
<,thenP
preservesallstationarysubsetsof.
When>!1,Theorem2.4isprovedbycombiningtheforcingcon-
structionforprovingtheaboveresultwiththeoneforprovingTheorem
2.6withrespecttoasubsetofcodingtheparameter(F;S)forwhichwe
force
F;S
AC:Wemayassumethat2
<
=and2

=
+
holdintheground
model.Westartbyadding,byforcingwithinitialsegments,afunction
F:![]
<
anda{sequenceSofmutuallydisjointstationarysubsets
of.Thenwebuildaforcingiterationoflength
+
withsupportsofsize
lessthaninwhichwesimultaneouslyperformthetasksof
(1)forcing
F;S
AC
(asintheproofofTheorem2.7),and
(2)addingasuitableasscson(asintheproofofTheorem2.6)coding
axedsubsetofthatencodes(insome1way)thepair(F;S).
Thedesiredforcingisthenthelimitofthisiteration.Now,theL{
formula(x;y)witnessingTheorem2.4canbetakentoexpressthefol-
lowingpropertyP0(x;y):\ThereisamaximalsetTofperfectordinals

47. 32 D.Aspero
<ofcountableconalitywiththepropertythatthereisacoher-
entstronglytype-guessingclub{sequencewithstationarydomainandwith
heightsuchthatTencodesapair(F;S)withFafunctionfrominto
P()andSa{sequenceofmutuallydisjointstationarysubsetsof,and
xF;Sy
17
".
P0(x;y)canalsobeexpressed,inaslightlymoreconvolutedway,by
sayingthatthereisasetTsuchthat
(a)forevery2T,isaperfectordinalinofcountableconalityand
thereisacoherentclub{sequence ofheight,withdom()and
dom()=2NS,andsuchthatforeveryclubC,f2dom():
ot(\

C)6 =g2NS,
(b)forevery2\cf(!),2Torelseforeverycoherentclub{sequence
ofheight,eitherdom()isnotastationarysubsetoforthere
isaclubC!1suchthatf2dom():ot(\

C)6 =g=2NS,
andsuchthat
(c)Tencodesapair(F;S)withFafunctionfromintoP()andSa
{sequenceofmutuallydisjointstationarysubsetsof,andxF;Sy.
Clearly,(a)and(b)are,respectively,a2propertyofToverthestruc-
turehH(
+
);2;NSianda2propertyofT,alsooverhH(
+
);2;NSi.
And,sinceF;SisasdescribedrightafterDenition2.2,(c)isa1prop-
erty,overhH(
+
);2i,aboutT,xandy.Thus,P0(x;y),beingexpressible
overhH(
+
);2;NSias(9T)[a(T)^b(T)^c(T;x;y)],witha(u)a2
L{formula,b(u)a2L{formula,and(u;v;w)a1formulainthelan-
guageofsettheory,canbewrittenasa3L{formulaoverhH(
+
);2;NSi.
Asto (x;y),itcanbetakentoexpresstheproperty{letuscallit
P1(x;y){thateverymaximalsetTofordinals<withtheproperty
statedinthedescriptionof(x;y)encodesapair(F;S)asbefore,and
xF;Sy.LetuscallQ(T)thepropertyofTexpressedbytheconjunction
of(a)and(b)intheabovedescription.P1(x;y)canbewrittenas
(8T)[Q(T)!(Tencodesapair(F;S)andxF;Sy)]:
Q(T)isa3propertyofToverhH(
+
);2;NSi,andtheexpressionto
therightoftheimplicationsignisa1propertyofT,xandy.Itfollows
thenthatP1(x;y)canbewrittenasa3formulaoverhH(
+
);2;NSi.
17
WhereF;SisasintheparagraphrightafterDenition2.2.

48. CodingintoH(!2),Together(orNot)withForcingAxioms 33
Theideabehindtheproofwhen=!1isthesame.Theproofinthis
casecombinestheforcingiterationforTheorem2.6withacertainiteration
ofproperposets,duetoMoore[Mo](seethenextsection),whichcodes
subsetsof!1byordinalsusingsomexedparameterp.Nowweforcethis
codingwhileatthesametimemakingpdenable.Intheextension,the
inaccessiblecardinalbecomes!2.
OnenalwordontheproofsofTheorems2.6and2.4:Theydonot
dependonanygeneralforcingiterationlemmas.Instead,theyrelyon
directconstructionsdependingquitecloselyontheactualdenitionofthe
iteration.ByaforcingiterationlemmahereImeanastatementtypically
assertingthatifhP:iisanyforcingiterationbuiltwithsomexed
kindofsupports,basedonasequenceh
_
Q:<iofnamesforposets,
18
andeach
_
Qisforced,byP,tohaveacertainpropertyP,thenPalsohas
propertyP.Itiswell{known
19
thatfairlygeneraliterationlemmascanbe
obtainedforcountablesupportiterations(orforsomereasonablevariation
ofthistypeofiterations).Ontheotherhand,thereareseriousobstacles
toprovingsimilargenerallemmasforiterationsbuiltusinguncountable
supports,whicharepreciselythekindofiterationsoneistypicallyfaced
withwhenforcingsomestatementaboutsubsetsof,forsome>!2,
whileatthesametimepreserving!1and!2.
ItturnsoutthatTheorems2.1and2.2areoptimalasstatedfromthe
pointofviewoftheLevyhierarchy.Morespecically,byappealingmainly
toresultsofWoodinonecanprovethat,inthepresenceofsuciently
stronglargecardinals,
20
3cannotbereplacedby2inthestatementof
eitherTheorem2.1orTheorem2.2.Infact,onecannotproveaversion
ofeitherTheorem2.1orTheorem2.2inwhich3(equivalently,3)is
replacedby2.Theorems2.8and2.9presentmorepreciseformulationsof
thisclaim.
Theorem2.8([As2])Givenanystationaryandco-stationaryA!1,if
AD,theAxiomofDeterminacy,holdsinL(R)(AD
L(R)
)andifthereisa
Woodincardinalbelowameasurablecardinal,thenthereisnopair0(x),
1(x)ofnecessarilyincompatible2formulasoverhH(!2);2;NS!1;rir2R
suchthatAisdened,overhH(!2);2;NS!1;rir2R,by0(x)and!1nAis
dened,overhH(!2);2;NS!1;rir2R,by1(x).
18
Thatis,forallwith+1,P+1isthesetof+1{sequencespsuchthat
p2Pandsuchthatpp()2_Q.
19
Seeforexample[Sh].
20
ForexampleaproperclassofWoodincardinals.

49. 34 D.Aspero
Theorem2.9([As2])AssumeAD
L(R)
andsupposethereisaWoodincar-
dinalwithameasurablecardinalabove.Thenthereisnonecessarilyan-
tisymmetric2formula(x;y)overthestructurehH(!2);2;NS!1;rir2R
suchthat(x;y)denes,overhH(!2);2;NS!1;rir2R,awell{orderofR.
InTheorem2.8above,twoformulas0(x)and1(x)inthelanguage
ofthestructurehH(!2);2;NS!1;ri{whererisarealnumber{aresaid
tobenecessarilyincompatibleif,foreverygenericextensionMofL(R)
satisfyingZFC,
hH(!2);2;NS!1;ri
M
j=:(0(x)^1(x))
foreveryx2H(!2)
M
.Also,inTheorem2.9,aformula(x;y)inthe
languageofthestructurehH(!2);2;NS!1;ri{where,again,risareal
number{isnecessarilyantisymmetricincaseforeverygenericextension
MofL(R)satisfyingZFC,
hH(!2);2;NS!1;ri
M
j=(:9x;y)(x6 =y^(x;y)^(y;x))
Theorems2.8and2.9areeasilyprovedusingthetheoryofPmaxforcing
byargumentsverymuchcontainedintheproofofObservation4.3inSection
4.
21
FromTheorem2.8itfollowsthatifthereisaproperclassofWoodin
cardinalsandAisastationaryandco-stationarysubsetof!1,thenthereis
nopair(0(x);1(x))ofZFC{provablyincompatible2L{formulasfor
whichthereisaposetPsuchthatPpreservesthestationarityofboth
Aand!1nAandsuchthatPforcesthatAand!1nAaredenedover
hH(!2);2;NS!1iby,respectively,0(x)and1(x).
22
Likewise,Theorem
2.9impliesthat,underthesamelargecardinalassumption,thereisnoposet
forcingtheexistenceofawell{orderofH(!2)denableoverthestructure
hH(!2);2;NS!1ibyaZFC{provablyantisymmetric2L{formula.
OnemayaskwhetheritispossibletodropthepredicateNS!1inthe
statementofeitherTheorem2.1or2.2.Concerningthisquestion,thereisa
versionoftheabovetheoremswithhH(!2);2ireplacingthemoreexpressive
hH(!2);2;NS!1i.Thecodingtechniquesemployedintheproofofthese
theoremsarequitedierentfromtheonesusedintheproofsofTheorems
2.6and2.4.TheseresultsuseZFC+\Thereisaninaccessiblelimitof
21
Usingthefactthat,underAD
L(R)
,Pmaxishomogeneousand{closedandusing,
respectively,thefactthatADprohibitstheexistenceofstationaryandco-stationary
subsetsof!1,andthefactthatADprohibitstheexistenceofwell{ordersofR.
22
Since,byaresultofWoodin,AD
L(R)
followsfromtheexistenceofinnitelymany
Woodincardinalswithameasurablecardinalabovethem.

50. CodingintoH(!2),Together(orNot)withForcingAxioms 35
measurablecardinals"asbasetheory,ratherthanjustZFC(+thereisan
inaccessiblecardinal).
Recallthat,if<!2isanordinaland:!1!isasurjection,
thefunctiong:!1!!1denedbylettingg()=ot(\)foreachis
calledacanonicalfunctionfor.Thisnameisjustiedbythefactthat
anytwofunctionsthusobtained(forthesame)coincideonaclubof!1.
Byacanonicalfunctionwillbemeantacanonicalfunctionforsomeordinal
below!2.GivenS!1andtwofunctionsf,g:S!!1,wewillsay
thatgdominatesfonSmod.aclub(equivalently,fisdominatedbygon
Smod.aclub)ifthereisaclubC!1suchthatf()<g()forevery
2S\C.
Thefollowingnotionisdenedin[As5].
Denition2.3([As5])Givenanordinal,1!1,hS;hSi:i<
i;f; iisasimpledecodingobjectif
(a)fSi:i<g[fS;!1n(S[
S
i<
Si)gisacollectionofpairwisedisjoint
stationarysubsetsof!1,
(b)everyfunctionfromSinto!1isdominatedonSmod.aclubbysome
canonicalfunction,
(c)fisafunctionfrom!1n(S[
S
i<
Si)into!1dominatingeverycanon-
icalfunctionon!1n(S[
S
i<
Si)mod.aclub,
(d)isaladdersystemdenedon
S
i<
Siwhichisstronglyguessing
andmaximalfor!1,and\
S
i<
Si=;forevery2
S
i<
Si,and
(e)thereisasequencehri:i<isuchthatforeveryi<andevery
2Si,riisthesetofk<!forwhichthereareinnitelymany
n<!suchthatf(n);(n+k+1)gSandf(n+j):1j
kg\S=;.
IfhS;hSi:i<i;f;iisasimpledecodingobject,thenwelet
code(S;hSi:i<i;f;)=fri:i<g,wherehri:i<iwitnesses(e)
forhS;hSi:i<i;f;i.WewillsaythathS;hSi:i<i;f;iencodes
fri:i<g.
Lemma2.10showsthatsimpledecodingobjectsareuniqueinaquite
strongsense.

51. 36 D.Aspero
Lemma2.10([As5])SupposehS
0
;hS
0
i
:i<0i;f0;
0
iandhS
1
;hS
1
i
:
i<1i;f1;
1
iaresimpledecodingobjects.ThenthereareclubsDCof
!1suchthat
(i)S
0
\C=S
1
\Cand
S
i<0
S
0
i
\C=
S
i<1
S
1
i
\C,
(ii)forevery2D,both
0


1

and
0

nCarenite.
Inparticular,code(S
0
;hS
0
i
:i<0i;f0;
0
)=code(S
1
;hS
1
i
:i<
1i;f1;
1
).
Thefollowingtheoremisprovedin[As5].
Theorem2.11([As5])Supposeisaninaccessiblelimitofmeasurable
cardinals.Letbeanordinal,1!1,andlethri:i<ibea
sequenceofsetsofintegers.ThereisasemiproperposetPVforcing
thatthereisasimpledecodingobjecthS;hSi:i<i;f;isuchthatcode
(S;hSi:i<i;f;)=fri:i<g.
TherstofthefollowingtworesultsisacorollaryofTheorem2.11,
andthesecondfollowsfromcombiningtheforcingconstructionforproving
Theorem2.11with,forexample,theoneforprovingTheorem2.7.
23
Theorem2.12([As5])Thereare3formulas0(x)and1(x)inthe
languageofsettheorysuchthat
(1)(0(x);1(x))areZFC{provablyincompatibleformulasoverthe
structurehH(!2);2i,and
(2)givenanyA!1,ifthereisaninaccessiblelimitofmeasurable
cardinals,thenthereisasemiproperposetPVforcingthatAand
!1nAaredenedoverhH(!2);2iby,respectively,0(x)and1(x).
Theorem2.13([As5])Thereisa3formula(x;y)inthelanguageof
settheorysuchthat
(1)(x;y)isaZFC{provablyantisymmetricformulaoverhH(!2);2i,
and
(2)ifthereisaninaccessiblelimitofmeasurablecardinals,thenthere
isasemiproperposetPVforcingthat(x;y)denes,over
hH(!2);2i,awell{orderofH(!2)ofordertype!2.
23
VerymuchasintheproofofTheorem2.4.

52. CodingintoH(!2),Together(orNot)withForcingAxioms 37
ForTheorem2.12,eachformula(x)(for2f0;1g)willbea3
formulasexpressingthepropertyP(x),whereP0(x)andP1(x)aredened
by,respectively,\xisacountableordinalandthereisarealrencodingx
(insome1way),togetherwithasimpledecodingobjectencodingaset
ofrealstowhichrbelongs"and\xisacountableordinalandthereisa
simpledecodingobjectencodingasetofrealsXsuchthatr=2Xwhenever
risarealencodingx(inthesamewayasbefore)".
Itiseasytoseethatbothpropertiescanbeexpressedby3formulas
overhH(!2);2i:ForP0(x),since\x2!1"and\rencodesx"are1
propertiesoftherelevantobjects,thevericationwillbenishedoncewe
seethat
(9S;(Si)i<;f; )Q(S;(Si)i<;f;;r)
canbewrittenasa3sentenceoverhH(!2);2iwithrasparameter,where
Q(S;(Si)i<;f;;r)expressesthat(S;(Si)i<;f;)isasimpledecoding
objectandthatr2code(S;(Si)i<;f;).ButQ(S;(Si)i<;f;;r)canbe
expressedbysayingthat(a){(d)fromDenition2.3holdfortherelevant
parameters,andthatr2code(S;(Si)i<;f;).Since!1is2denable
overhH(!2);2i,(a)fromDenition2.3isa2propertyofSand(Si)i<
(overhH(!2);2i).(b)fromDenition2.3isclearlya2propertyofS,
and(c)isalsoa2property(off,Sand(Si)i<).(d)isexpressedby
sayingthatisaladdersystemwithdom()=
S
i<
Si,thatforevery
clubC!1thereisaclubD!1suchthatnCisboundedin
forevery2D\dom(),andthatforeveryladdersystemdisjoint
fromthereisaclubC!1suchthat\Cisniteforevery2
C\dom();hence,itcanbewrittenasa2formulaoverhH(!2);2i.
Finally,\r2code(S;(Si)i<;f;)"canbeexpressedbysayingthatthere
issomei<suchthatr=fk<!:(9
1
n<!)(f(n);(n+k+1)g
S^f(n+j):1jkg\S=;)gforevery2Si,andsoitisa
0propertyofr,Sand(Si)i<.ItfollowsthatP0(x)canbewrittenasa
3formulaoverhH(!2);2i.ThevericationforP1(x)isalongthesame
lines.
Theformula(x;y)witnessingTheorem2.13canbetakentosaythat
thereisasimpledecodingobjectencodingasetofrealsXsuchthatX
encodes(insomesimplestandardway)apair(F;S)asinDenition2.2
(for=!2)andxF;Sy,fortherelationF;SdescribedafterDenition
2.2.Itiseasytosee,byananalysisasbefore,thatthereisindeeda3
formulaexpressingtheabovepropertyofxandyoverhH(!2);2i.

53. 38 D.Aspero
Question2.1IsitpossibletoproveversionsofeitherTheorem2.12or
2.13with3replacing3?
3.Resultsmentioningstrongforcingaxioms
Theforcingconstructionspresentedintheprevioussectionareexible
enoughtoaccommodateposetswiththecountablechaincondition.Thus,
allmodelsbuilttherecanbetakentobemodelsofMA!1.However,it
isnotpossibletomodifythoseconstructionssoastoproducemodelsof,
forexample,BPFA.
24
Infact,thetechniquespresentedthereforcoding
axedsubsetof!1areincompatiblewithBPFA.Thereasonforthisis
thatBPFAimpliesthateveryclub{sequenceisavoidable.
25
PFA
++
isthefollowingstrongformofPFA:
GivenanyproperposetP,anysequencehDi:i<!1iofdensesubsets
of!1andanysequencehi:i<!1iofP{namesforstationarysubsets
of!1thereisalterGPsuchthat,foreachi<!1,G\Di6 =;and
f<!1:(9p2G)(pP2i)gisastationarysubsetof!1.
Therstmainresultinthissectionisthefollowing.
Theorem3.1([As3])SupposeisasupercompactcardinalandAisa
subsetof!1.ThenthereisasemiproperposetPVsuchthat
(1)PforcesPFA
++
,
(2)PforcesthatAisdenable,overthestructurehH(!2);2;NS!1i,by
a5formulawithoutparameters,and
(3)Pforcestheexistenceofawell{orderofH(!2)denable,overthe
structurehH(!2);2;NS!1i,bya5formulawithoutparameters.
Thistimetheproofsinvolvethemanipulationofcertainguessing
propertiesoffunctionsF:S!P(!1)
26
withrespecttocanonical
functions.
24
BPFAistheassertionthathH(!2);2iisa1{elementarysubstructureofthestruc-
turehH(!2);2iascomputedinanyforcingextensionviaaproperposet.BPFAisa
trivialconsequenceoftheProperForcingaxiom(PFA).
25
Onecaneasilyverifythatthestandardposetforintroducing,byinitialconditions,
aclubavoidingaxedclub{sequencedenedonasubsetof!1andwhoseheightexists
isalwaysproper.
26
WhereS!1andwhere,forevery2S,ot(F())isinsomeprescribedinterval
ofcountableordinals.

54. CodingintoH(!2),Together(orNot)withForcingAxioms 39
Denition3.1([As3])LetSbeastationarysubsetof!1.GivenI!1,
ShasguessingdensityIifforeverystationaryS

S,
(a)thereisafunctionF:S

!P(!1)suchthatot(F())2Iforall
2S

andsuchthatf2S

:g()2F()gisstationaryforevery
<!2andeverycanonicalfunctiongfor,and
(b)givenanyfunctionF
0
:S

!P(!1),ifot(F
0
())<min(I)forall
2S

,thenthereisanordinal<!2suchthatf2S

:g()2
F
0
()gisnonstationaryforeverycanonicalfunctiongfor.
NotethateverystationaryS!1hasdensity!1andthatthereisno
suchthingastheuniqueguessingdensityofS:ifShasguessingdensityI0
andI1!1issuchthatmin(I1)min(I0)andsup(I0)sup(I1),thenS
alsohasguessingdensityI1.Also,itiseasytoseethatforeverystationary
S!1,theassumptionthat}(S

)
27
holdsforeverystationaryS

S
impliesthatShasguessingdensityf1g.Finally,BMM
28
impliesthatno
stationarysubsetof!1hasguessingdensityboundedin!1.
Thefollowingtheoremisprovedin[As3].
Theorem3.2([As3])Supposeisaninaccessiblecardinalwhichisalimit
ofmeasurablecardinals.LethSi:i<!1ibeasequenceofpairwisedisjoint
stationarysubsetsof!1andlethi:i<!1ibeasequenceofnonzero
countableordinals.
ThenthereisasemiproperposetPVforcing,foreveryi<!1,that
Sihasguessingdensitytheinterval[i;!
i!
)
29
ifi>1andthatSihas
guessingdensityf1gifi=1.
TheproofofTheorem3.2involvesananalysisofiterationsofmodelsof
settheoryrelativetosequencesof(possiblydierent)measurablecardinals.
ItusesageneralizationofatheoremofKunen([Ku])sayingthatforevery
ordinalthereareonlynitelymanymeasurablecardinalsforwhich
thereisanormalmeasureUonsuchthatisnotaxedpointbythe
elementaryembedding,oftheuniverse,derivedfromU.
27
NamelythestatementthatthereisasequencehX:2S

iwithXforall
andf2S

:X\=XgstationaryforeachX!1.
28
NamelythestatementthatthestructurehH(!2);2iisa1{elementarysubstructure
ofhH(!2);2i
V
P
foreverypartialorderPpreservingstationarysubsetsof!1.
29

!
i
denotesordinalexponentiation.

55. Random documents with unrelated
content Scribd suggests to you:

56. Silleen lohdutteli Juhana Eljasta, ja serkukset tunsivat toisensa.
Juhana häpesi, kun oli syyttä suotta ottanut närkästyäkseen
huolestuneelle serkulleen, jota hänen juuri oli velvollisuus auttaa
koronkiskojien kynsiin joutumasta, ja Eljas häpesi, että oli
hetkeäkään luullut Juhanan häneen todella suuttuneen.
Ja Juhanan ehdotuksen mukaan asiat järjestettiin siten, että Eljas
jo ensi viikolla pääsi lähtemään Helsingistä. Huononlaista oli
Juhanankin taloudellinen toimeentulo, ja kun hän nyt vielä serkkunsa
eduksi sitoutui kaikenlaisiin asioihin, kävi se yhä enemmän
huolestuttavaksi. Ja Eljasta pitivät jo useimmat huonon jäljelle
joutuneena, menneenä miehenä, haaksirikkoutuneena, joka jo
ennen pitkää kai jossakin maan nurkassa tulisi alituisissa puutteissa
ja huolissa elää kitkuttamaan surkeata elämätä, niinkuin monet muut
hukkaan joutuneet nerot. Kun se kerta noin oli lähtenyt vierimään,
niin ei se ennen pysähtyisi, kuin mies ryysyissä kulkisi ryyppylanttia
kerjäämässä. Sitä oli nähty ennenkin, oireet olivat samat. Semmoista
ajatteli jo vähin Juhanakin, mutta toivoi kumminkin, ja oli iloinen,
kun sai serkkunsa ajoissa pois.
Hyvillä mielin hän siis samana päivänä, jona oli saattanut Eljaan
asemalle, meni tätinsä nimipäiville. Harvemmin oli hän viime aikoina
siellä käynyt. Sen teatteri-illan jälkeen oli kulunut kuukausi, niin ettei
hän ollut näyttäytynytkään, — Juliata näet ei tahtonut tavata, — ja
Julia oli pysynyt saman verran aikaa poissa. Mutta sitten eräänä
pyhänä tulivat he kumpainenkin ja sopertelivat rouvalle kumpikin
erikseen saman syyn, että näet olivat sattuneet olemaan muualla.
Mutta sen jälkeen kävivät he arkkitehdissä niinkuin ainakin, tapasivat
toisensa, puhelivatkin joskus ja olivat niinkuin ennenkin. Mutta tyttöä
ei Juhana sen koommin kotiin saattanut — ei! Arkkitehdissä olivat
tavallistakin ystävällisempiä; kyselivät Eljaasta ja hänen aikeistaan ja

57. tuli sitten puhe Juhanankin toiveista ja tulevaisuudesta. Arkkitehti
kehoitti Juhanata toimeliaammin leipäpaikkaa hankkimaan, kehoitti
häntä puuhaamaan sitä varten suoranaisemmin ja innokkaammin,
käymään asianomaisten, vaikuttavien henkilöiden luona
kumartelemassa. Käski empimättä vain hakea virkoja, joita saattoi
hakea, jos kohta ei olisikaan toivoa niitä saada, sillä siitä on aina
etua, kun yritteleekin ja tekeytyy huomatuksi.
— Mutta kun on niin paljon muita, soperteli vastaan Juhana.
— Paljon on, mutta ei auta. Jos sinä siellä ylimääräisenä istut
äänetönnä ja unhotettuna, niin saat kai semmoisena pysyä
kymmenen vuotta, eikä kukaan tule sinulle sittenkään paikkaa
tarjoamaan. Onko sinulla ketään tuttavia ylempäin virkamiesten
joukossa?
— Ei ketään. Ketäpä minulla olisi?
— Se on vahinko, mutta ei se sentään tee mitään. Käyt vain
esittämässä itsesi, pyytämässä puoltosanaa. Niitä on aina toisinaan
auki joitakin sijaispaikkoja ja pikkuvirkoja, mitättömiä tosin. Mutta
kun semmoisenkin kerran onnistuisit saamaan, niin se olisi jo suuri
askel eteenpäin, — niin, sillä olisi jo melkein kaikki voitettu, mitä nyt
voi toivoa. Kun kerran on portailla, niin kyllä sitten aina sisälle
pääsee. Sinulla kai ei nykyjään ole mitään tuloja?
— Ei muuta kuin mitä vähän syrjätöistä, kirjoituksista.
— Niistä on vain haittaa, heitä ne jo ajoissa. Vakinainen paikka, jos
pienikin aluksi, se olisi toista. Ja sellaisia nyt tavallisesti saapi, kun
oikein koettaa, eihän se mikä mahdottomuus ole. Ja silloin olisi

58. asemasi vakaisempi, silloin voisit jo omaa kotiakin ruveta
ajattelemaan.
Kun arkkitehti mainitsi oman kodin, käänsi Juhana
tahtomattaankin katseensa Julian puoleen, joka, vaikka istui syrjässä
käsityönsä ääressä, kuitenkin heidän puhettaan kuunteli, ja myöskin
samassa nosti silmänsä ylös, niin että heidän katseensa osuivat
vastakkain. Ja ne katseet käsittivät toisensa, vaikka eivät
silmänräpäystäkään vastakkain olleet. Välähti tuokion vain, mutta
tulta ja toivoa! — Juhana soimasi itseään tyhmyri-pöllöksi, kun ei
ennen ollut tehnyt kaikkea mahdollista saadakseen asemansa
vakaisemmaksi. Nyt hän päätti koettaa kaikkia keinoja, kaikkia
kiertoteitä, voidakseen tulevaisuudessa, niin läheisessä kuin suinkin,
perustaa oman kodin. Vielä oli aikaa. Hän päätti lähteä
kumarruksille, kamreeri Hallmanille ensiksi, hänhän oli ainoa, joka oli
vähääkään tuttu.
Tuo päätös häntä innostutti, eikä hän voinut olla sitä Julialle
kertomatta, kun he taas vierekkäin sattuivat istumaan. Ja tyttökin
kehoitti hymyillen häntä toimimaan, — sillä tukalatahan se kai on
elää pitemmän aikaa noin epävarmalla kannalla. Mutta silmiin ei
uskaltanut katsoa, ne olisivat puhuneet paljon enemmän, — liiaksi.
Kun siis arkkitehti vielä hyvästellessä neuvoi häntä kaikkialla
katsomaan eteensä ja sanoi, että maailmassa pitää rientää ja
reistailla maailman mukaan, niin oli Juhana ihan samaa mieltä —
vaikka tuo kumartelemisaate häntä tosin vähän tympäisi. Jo
huomispäivänä aikoi hän harjata hännystakkinsa ja opettelipa jo
ruotsiksi puheen, minkä kamreerille sanoisi. —
Mutta tekemättä ne jäivät kumminkin Juhanalta sillä kertaa aiotut
kumarrukset. Muutamia päiviä myöhemmin makasi hän näet

59. klinikassa, houri kuumeessa.
Taudin teitä, niitä ei osaa arvata. Kaupungissa oli lavantauti
liikkeellä ja pieni vilustuminenko kylmässä huoneessa sille lie
valmistanut sijaa vai mikä. Aamulla Juhana tunsi pahoinvointia,
iltapäivällä pani jo pitkälleen ja parin päivän perästä tuli lähtö
klinikkaan.
Siellä makasi Juhana kauan ja huonona. Ja kun viimein tauti
hellitti ja hän alkoi toipua, olivat sittenkin surkeanlaiset hänen
päivänsä. Maata piti siellä toisten kituvaisten seurassa, hoitokin oli
kehnonlaista ja epäystävällistä, harvoin uskalsi joku toveri tulla häntä
tapaamaan. Täti kävi pari kertaa, sittenkuin vihdoin sai tiedon hänen
sairastumisestaan.
Mutta Juhana oli niinkin tyytyväinen ilottomaan potilaana
olemiseen. Sillä joka sunnuntaiaamu tuotiin tuolille hänen vuoteensa
ääreen vihkonen tuoreita, kauniita, tuoksuvia kukkia, ja Juhana tiesi,
mistä ne tulivat. Juhana tiesi, kuka se häntäkin muisteli, ja ajatteli,
että moni on häntäkin onnettomampi. Ohi ne menevät vielä nämä
kovat päivät, ja iloisemmat koittavat. Ja kun hän siksi oli toipunut,
että jo pääsi kävelemään, tuli Julia itse kerran tädin seurassa kukkia
tuomaan. Silloin kohosi hieno puna kalvakalle poskelle ja likeltä
piteli, ettei kyynel kimaltanut silmän nurkassa; tauti oli näet miehen
pehmentänyt.
Kotoaan toi hänelle täti taas pitkät kirjeet. Niissä pyydettiin häntä
tulemaan kotiin voimistumaan niin pian kuin jaksaisi. Eljas, joka
siellä oli voittanut kaikkien suosion, kuului lähtevän pian takaisin
Helsinkiin papiksi lukemaan.

60. — Takaisin … papiksi… Juhana luki sen kolmeen kertaan. Hyvin se
häntä ihmetytti, kun sitä ei tarkemmin selitetty. Juhanan vanhemmat
olivat vanhoillisia ihmisiä, ankaran uskonnollisia, jyrkkiä
puhdaskirkollisilta mielipiteiltään, oikein »vanhan testamentin
ihmisiä», kuten Eljaan oli ollut tapa sanoa. Kaikki uudet ilmiöt, eivät
ainoastaan liikkeet ja aatteet, joista he tuskin olivat kuulleet
puhuttavankaan, vaan myös kaikenlaiset keksinnöt, ajanmukaiset
parannukset ja muutokset olivat heistä maailmanlopun enteitä.
Juhanaa oli hyvin epäilyttänyt lähettää serkkuaan kaikkine
vapaamielisine aatteineen tuohon ahdasmieliseen, joskin
ystävälliseen kotiin. Hän oli pelännyt, että kun niin vastakkaiset
ainekset jysähtäisivät yhteen, niin hyvä sopu pian pilautuisi, ja oli
katsonut tarpeelliseksi oikein kirjeessä pyytää vanhuksia olemaan
pitkämielisiä. Ja nyt sai hän tietää, että Eljas oli siellä kaikkien
suosiossa ja tulee pian Helsinkiin papiksi lukemaan. Kummallinen
käänne!
Eljas itse ei koko talvena ollut kirjoittanut kellekään, ei Juhanalle
eikä muille. Huhuna vain kerrottiin, että hän olisi puuttunut
kotipuolessaan vallitseviin uskonnollisiin rientoihin, kerrottiin, että
hän olisi liittynyt hihhulilaisuuteen, ruvennut tuon laajalle levinneen
lahkolaisuuden varsinaiseksi pääapostoliksi. Tuota nyt eivät toverit
Helsingissä uskoneet, he nauroivat koko sille huhulle. Ja toiselta
puolen kuuluikin, että hän juuri oli esiintynyt mainitun
lahkolaisuuden ankarana vastustajana, saarnannut kirkossa ja
seuroissa sitä vastaan ja innokkailla ja hartailla puheillaan
saavuttanut suurta kansansuosiota.
Tuollaisia suupuheita niitä oli kulkenut, tietysti löyhiä huhuja, joihin
ei paljon voinut luottaa, kun Eljaalta itseltään ei mitään kuulunut.
Mutta jotakin peräähän niissä nyt kai täytyi olla, ja tovereista

61. arvelivat muutamat Eljaan pahanlaisesti ilveilleen, toiset hänen
joutuneen mielenvikaan.
Mutta eräänä iltana, kun jonkin kokouksen jälkeen ylioppilastalon
kapakan puolella istui joitakuita ukkosia juttelemassa tuutingin
ääressä, sattui joku taas mainitsemaan Eljaan nimen.
— Nyt minä tiedän sen varmasti, on niissä puheissa sittenkin
perää, huudahti muudan, katkaisten entisen keskustelun.
— Ettäkö hän olisi hihhuliksi ruvennut?
— Ei, muuten vain yhtynyt siihen kirkolliseen herännäisyyteen,
joka niillä paikoin nykyjään on hyvin valtava ja johon hänen
setänsäkin kuuluu, — ruvennut uskovaiseksi.
— Liekö jo körtitkin laittanut. Ja mistä sinä nyt sen niin varmasti
tiedät?
— Minä sain kirjeen velimieheltäni, joka siellä oli käynyt. Eljas
kuuluu siellä seuroissa kulkeneen ja seuroja pitäneen, saarnanneen,
puhuneen, lukeneen ja veisanneen. Sanalla sanoen: tehnyt
parannuksen ja parantanut muita.
— Loruja! Eljas, joka aina oli niin vapaamielinen ja järkevä.
— Eihän se mikään mahdottomuus ole, puolusti joukossa muudan.
— Eljas oli hyvin tunteellinen ja vaikutuksille herkkä, hän koetti ja
rientoili jos jonnekin päin, yhdestä tuumasta nakkautui toiseen, —
miksei siis uskonnonkin helmoihin, jolla on niin suuri vaikutus
ihmisiin?

62. — Ja kun hän vielä viime aikoina oli joutunut ahtaalle ja maailma
kaikilta puolin tuntui sulkeutuvan hänelle, kun hän jo alkoi kyllästyä
jokapäiväisiin, joutaviin riitoihin, niin onpa luonnollistakin, että hän
siihen tuli turvautuneeksi. Kenties hän, niinkuin moni muu, näki
turhuudeksi kaikki nämä maailman riennot ja haki rauhan satamaan.
— Näin puhuja oli teologi.
— Minä olen Tuomas, jos niinkuin jatketaan puhetta vertauksissa.
Minä en usko koko herännäisjuttua. Mikä se nyt miehen parissa
kuukaudessa olisi kääntänyt!
— Saatpahan nähdä, kun hän itse tulee tänne jonkin ajan perästä.
— Tänne? Mitä varten?
— Papiksi lukemaan tietysti.
— Papiksi! Ja millä rahoilla? Aikooko hän maksaa velkansakin, ja
sitten vielä lukea täällä papiksi? Mistä Eljaalle ne rahat?
— Sitä en tiedä, tulevan vain kuuluu.
Mutta joukosta eräs napsautti sormiaan ja päästi naurun:
— Nyt se peijoonin poika on hoksannut viimeisen hätäkeinon. Eli
ei juuri hoksannut, sillä johan sitä on ennenkin käytetty.
— Ettäkö olisi heittäytynyt?
— Heittäynyt uskonnolliseksi tietysti, pitänyt saarnoja ja veisannut
sionia, veitikka. Poikennut tositeologisille poluille. Siten puijannut
herännäisyydellään ukkoloilta rahoja, — siellä on ukkoja semmoisia
kyllin, jotka mieluiselle papinkisällille kaivelevat setelejä arkun

63. pohjalta, kunhan mies itkettää heidän eukkojaan! — Sitä keinoa on
ennenkin käytetty.
— Liekö käytetty, mutta Eljas ei semmoisiin keinoihin kajoa. Hän
on puhdasluonteinen, tervesydäminen mies, eikä ryhdy mihinkään
vastoin vakaumustaan. Kevyt on hän kyllä, mutta petosta ja valetta
hän vähimmässäkin inhoaa, saatikka sitten tunteen arimmissa
asioissa.
— Hätä kun käskee, niin la-la-la — hiiteen vakaumukset. —
Minkätähden sitten papiksi, ja mistä ne rahat?
— Ehkäpä on saanut rahat sieltä maalta ja ehkä rupeaa papiksi,
mutta miks'ei vakaumuksesta?
— Ei Eljas mikään tyhmä mies ole koskaan ollut. Henki raiska on
kallis ja papin pala lihava — vakaumusta kylliksi! Eivätkä ne sen
kauniimpia ole monen muunkaan vaikuttimet. — Hän puhui
teologille.
— Kaikiksi se tosin ei näyttäisi kumma olevan, mutta Eljas oli aina,
vaikka vapaamielinen, kumminkin suora luonteeltaan, — jota ei
monestakaan muusta voisi sanoa.
Keskustelu oli livahtanut arkaluontoisille paikoille, ja sentähden
ryhtyi eräs vanhempi jäsen sovittelemaan.
— Älkäähän riidelkö. Pääasia nyt on, että Eljas on saanut rahoja ja
rupeaa papiksi. Syyt ja vaikuttimet olkoot hänen asianaan. —
Puhutaanpa jo muistakin. —
Vaikea sitä olikin syrjäisen arvostella, oliko Eljas pyörähtänyt
elämän uudelle polulle halusta vaiko pakosta. Kenties sovittelemalla

64. kumpaisetkin vaikuttimet mahtuisivat samaan päätökseen, ei
kokonaisuudessaan, mutta osaksi, noin vähän muodostelemalla. Ei
enemmän toinen kuin toinenkaan, mutta kumpainenkin saattoi siihen
vaikuttaa.
Eikä Eljaskaan ruvennut lähempiin selvityksiin, kun hän huhtikuun
viime päivinä saapui Helsinkiin ja kirjoitutti itsensä jumaluusopilliseen
tiedekuntaan, — ei ruvennut selvittämään Juhanallekaan, vaikka hän
tälle muuten oli hyvin ystävällinen ja kiitollinen. Eikä tämä taas
kysynytkään. Juhana oli vasta päässyt sairashuoneelta pois, oli
voimaton vielä ja työhön kykenemätön. Eljas koetti auttaa ja
huvittaa häntä kaikin keinoin, teki hänen seurassaan kävelymatkoja,
istui illoin hänen luonaan juttelemassa, avittelipa kirjoitustoimissakin,
kun Juhana vähitellen rupesi virastossa käymään. Ja Juhanan raha-
asiat, jotka taudin aikana olivat ihan häiriölle joutuneet, järjesti nyt
Eljas vuorostaan. Sillä rahoja hänellä oli; vaikka kaikki entiset
pikkuvelkansa maksoi pois, niin riitti vielä Juhanatakin autella. Mutta
rahalähteitäänkään ei Eljas sen tarkemmin kertonut.
— Kävithän sinä kaupungissa omaisiasi katsomassa sieltä maalta,
kysyi kerran Juhana.
— Ei tullut käyntiä. Ei tuo himottanut mennä äitimuorin näkyviin,
ennenkuin vähän ovat puhdistuneet entiset jäljet.
— Etkö sinä sieltä sitten käynyt lainaasi ottamassa?
— Enhän minä sieltä mitä lainaa ole ottanut.
— Vai sieltä maaltako sinä kaikki sait?

65. — Sieltä, setäkin auttoi. — Voih, kun pääsisi pois tästä pahasta
pesästä — pois, pois maalle! Täällä pelkään, että alan taas tuntea
erään, jota en koskaan enää tahdo tuntea, entisen itseni.
Juhana ymmärsi jo, ettei Eljas halunnut raha-asioistaan puhella,
ymmärsi sen, vaikkei hän muuten serkkuaan enää täysin
ymmärtänyt eikä tuntenut.
Ja muuttunut se olikin Eljas kokonaan miehekseen: luonne ja
käytös oli ihan toinen. Siitä Eljaasta, joka vastuksissakin kantoi
päätään rohkeasti pystyssä, siitä innokkaasta Eljaasta, joka aina oli
valmis väittelemään hetkisenkin harrastuksensa puolesta, siitä
avomielisestä Eljaasta, joka pienimpiäkään aikeitaan, tuumiaan,
tunteitaan ei voinut olla heti toiselle kertomatta, siitä, joka
aatteittensa ja rientojensa palveluksessa aina oli tulena ja
leimauksena, — siitä Eljaasta ei ollut merkkiäkään jäljellä. Allapäin ja
vakavana asteli hän nyt, milloin ihmisten seurassa esiintyi, ja jokin
surunvoittoinen leima näytti lepäävän hänen kasvoillaan. Hänen
puheensa oli hiljaista, väsynyttä, hänen luonteensa umpinaista,
suljettua. Vanhoja tovereitaan hän ei suorastaan juuri vältellyt, vaan
ei hakenutkaan. Toverit paremminkin hakivat häntä, ja niinä päivinä
ne juuri sattuivat olemaan Antin kandidaattipidot. Tapa on näet
vanha ja kaunis, että sen, joka on jonkin julkisen tutkinnon
suorittanut, täytyy tämän johdosta juoda itse ja juottaa muita. Ja
kyllähän sitä silloin mielellään ryypätäänkin hyvien tovereiden
seurassa, kun on takanapäin kaikki tenttituskat, jännitykset,
kuristukset ja vavistukset, kun vihdoin saapi heittää inhottavaksi
käyneen frakin kaappiin tomuttumaan, saapi ruveta unhottamaan
niitä kiusallisia pikkuasioita, joita on pitkät ajat päähänsä ahtamalla
ahtanut. Niille määrin se oli nyt Antti päässyt, ja hänen kekkereihinsä
piti saada Eljaskin mukaan vaikka väkisin, — kaikki luokkatoverithan

66. toki koulun ajoilta piti olla koossa. Eljas empi ensin, vaan lupasi
sitten kumminkin tulla Hellaaseen.
Muut olivat jo koolla, kun Eljas saapui. Jo ulkona hän kuuli »hip»-
ja »hurraa»-ääniä. Anttia, päivän sankaria, hurrattiin, nostettiin,
viskottiin kattoa kohden, — sen tiesi Eljas, ja ennen olisi hän ollut
siinä ensimmäinen mies. Mutta nyt hän ei kiirehtinyt. Ja kun hän
porstuassa kuuli tutun laulunpätkän:
    Eikä ne surut paljon paina
    Tällä kymmenellä,
niin hän jo vakavasti tuumasi palata: mitä hän tuossa joukossa
teki? Meni kumminkin sisälle.
— Kas Eljas! — Yleinen oli riemastus. — Yksi konjakkari jo ovella,
muutoin et tähän seuraan pääse. Ka siinä!
Pitihän se nielaista. Mutta syrjäpuoleen vetäysi Eljas heti
hiljaisuudessa.
Pitkä pöytä oli taaskin asetettu keskelle Hellaan salia, ja sen
ympärillä istui miehiä pariinkymmentä juoden, puhellen, laulaen ja
rähisten, ihan niinkuin silloin, jolloin Eljas ensi kertaa siinä
huoneessa oli. Samoin kuin silloin komennettiin kapakkatyttöä ja
kisailtiin hänen kanssaan, samoin kuin silloin pidettiin puheita,
kilistettiin ja huudettiin »eläköön».
Kaikki oli vanhoillaan, Eljas vain ei. Ensi miesnä hän nyt ei johtanut
keskusteluja, ei ehdottanut lauluja, ei noussut lasiaan kilistellen
pitämään puheita, joihin toverit niin usein jo olivat tottuneet
mielistymään. Miettiväisenä istui hän siinä pöydän alapäässä jutellen

67. kahdenkesken, jos ken tuli hänen pakinoilleen, ja maisteli lasistaan
tuskin nimeksi. — Lassin kanssa puheli hän kauan, toisten laulellessa
ja kaskutessa. Sillä Lassi oli aluksi myöskin vakavatuulisena, vähän
niinkuin lannistettuna. Vasta oli kihlat purettu. Antin välityksellä se oli
tehty kaikessa sovussa ja hiljaisuudessa molemminpuolisella
suostumuksella, sillä he olivat vihdoinkin kumpainenkin tulleet
ajatelleeksi, ettei niillä kihloilla ollut mitään merkitystä, kun naimista
ei kumminkaan voinut ajatella, varsinkin koska Lassin jo oli täytynyt
ruveta velkautumaan, kun isäukko kävi tiukaksi. Ei se Lassi sitä
sentään juuri surrut, mutta vähän oli noin toverien keskuudessa
häpeissään, kun nämä eivät malttaneet olla pientä pilaa
laskettelematta.
Niistä he puhelivat, ja tuli sitten puhe Eljaastakin, vaikka tämä itse
koetti sitä vältellä.
— Aiotko tulla syksyksi Helsinkiin, kysyi Lassi.
— Luultavasti en.
— Olisithan jo syksyllä saanut kandidaattisi sinäkin, ja sitten voinut
kääntyä teoloogiksi. Miksi noin äkkiä pyörähdit?
— Siitä ei ollut tietoa minun kandidaatistani. Ja mitäpä minä sillä?
Joutava koristus.
— Hyvähän se olisi ollut olemassa. Nyt lukea poruutat teologiaa?
— Niin. Hankin täällä nyt kirjat ja menen kohta taas takaisin
kotipuoleen lukemaan. Helsingissä aion olla vain sen verran kuin on
välttämätöntä.
— Joko niin olet Helsinkiin kyllästynyt?

68. — Olen jo saanut siitä tarpeekseni, olen leikkinyt kylliksi.
Joku siinä sillävälin piti leikillistä puhetta. Sille taputettiin käsiä,
naurettiin ja huudettiin »eläköön». — Ja Antti oli hyvä isäntä.
— Soo! Kolmas lasi pojat! — Eikö Lassi juokaan; entä Eljas. Kippis!
Pankaa pohjaan ja tehkää uutta. Vielä yksi ehditään siemata ennen
iltasta.
Iltasen jälkeen olivat taas kahvin ja liköörin ja yhteisten laulujen
mieluisat hetket käsissä. Silloin Eljas hiljaa ja huomaamatta vetäysi
pois. Sivumennen hän nykäisi Lassia, joka myös oli aikaisin luvannut
lähteä, mutta tämä oli nyt vasta päässyt makuun, oli juuri
lystimmillään ja poislähdön tuumat olivat hävinneet. Eljas läksi siis
yksin tiehensä Hellaasta: hänen paikkansa ei ollut enää siellä,
iloisissa seuroissa, niistä oli hän jo erillään. Hän oli reuhtoillut ja
tempoillut aikansa, nyt olivat todet edessä, työalat toisilla vainioilla.
— Niitä hän mietti kävellessään tuota tietä Hellaasta kaupunkiin, jota
hän niin usein ennen oli kävellyt, eikä hän voinut olla muistelematta,
mitä hän milloinkin oli aikonut, millä mielellä ollut ennen kulkiessaan
näitä polkuja. Ne olivat menneitä aikoja! Nyt hän käveli Hellaasta
viimeistä kertaa.

69. — Eljas!
Ajatuksistaan hän havahtui, kun äkkiä kuuli nimeään mainittavan,
ja kääntyessään taapäin katsomaan tunsikin hän huutajan, Annin,
entisen Hellaan Annin. Olisihan Eljas voinut jatkaa matkaansa tytöstä
välittämättä — pakkoko niitä on tuntea kaikkia, jotka kadulla
huutelevat, — mutta hänessä heräsi äkkiä halu puhutella Annia,
tiedustella, kysellä hänen nykyistä elämistään, menneitä
kohtaloltaan. Kuihtuneilta näyttivät illan hämärässä ennen niin sirot
kasvot, arka oli katse, puku huoleton, huonohko. Kiusallista oli
Eljaasta viipyäkin. Mutta hän tahtoikin kiusata itseään, sillä kenties
oli juuri hänkin tavallaan kiirehtinyt tuon tytön turmiota. Tuota naista
oli hän kerta säälinyt, oli häntä rakastanut, lämpöisestikin, oli
tahtonut korjata hänet hylyksi joutumasta, — niin, oli häntä
ajatuksissaan ja unelmissaan jo omanaan lempinyt. Se oli siihen
aikaan, kun hän itsestään luuli voivansa jotakin, uskoi tahdon
voimaan ihmisessä. Hän ansaitsi kurituksensa. Hän päätti nyt
samalta naiselta kuulla, kuinka tämä oli vajonnut vajoamistaan,
laskeunut ihmisarvossa myötään maailman ja omissa silmissään,
kuulla, että tämä ei enää surrutkaan elämänsä haaskiota,
halunnutkaan pois mieronsa tieltä. Sen verran oli hän omasta
voimastaan toimittanut! — Ja semmoista hän saikin kuulla
kylliksensä. Nykyjään oli tyttö myyjättärenä syrjäisessä,
pahamaineisessa olutkapakassa, ja jonkin ajan kuluttua luultavasti
vielä syrjäisemmässä — niinhän se meni, ja yhden teki!
Katkeroilta tuntuivat Eljaasta nuo kertomukset, vaikka hän ne kyllä
jo saattoi ennestään arvata. Ja hän mietti, olisiko tuota ollut mikään
mahdollisuus pelastaa siihen aikaan, kuin hän sitä haaveksi. Mutta
hän tuli siihen päätökseen, että ei olisi ollut. Tyttö oli silloin jo

70. määrätty ihmiskunnan hylyksi; se oli jo laki, jota ei voinut muuttaa.
Ihmisen pyrinnöt siinä olivat turhuutta.
— Ja etkö nyt halua mitään parempaa, etkö toivokaan pois tuosta
kapakkamaailman viheliäisyydestäsi, kysyi vielä Eljas, vaikka tyttö jo
siihen kerran oli vastannut.
— En. Muistatko ehkä, kun kaksi vuotta sitten viimeistä kertaa
tavattiin, että minä silloin sanoin: kun ihminen vähitellen
hyytymistään hyytyy, niin hän ei enää koskaan sula? Ymmärsitkö
silloin, mitä tarkoitin?
— Niin, ymmärsin.
— Silloin olit sinäkin sattumalta vähän jäähdytetty jostakin
tuumastasi. Olet kai siitä jo lämminnyt?
— Lämminnyt ja jäähtynyt moneen kertaan.
— Tiesinhän sen. Ja mikä sinusta sitten on oikeastaan tullut?
— Ei mikään — vielä.
— Ja mikä sinusta sitten tehdään?
Eljas vitkasteli pikkuisen aikaa, vastasi sitten vakavasti, melkeinpä
juhlallisesti:
— Pappi.
— Pa-pappi! No niin, miks'ei? Puhumaan kyllä olet ovela ja mieliä
sulattamaan ja sydämiä valloittamaan. Ja taidatpa olla taitava
teeskentelemäänkin ja valehtelemaan.

71. — Älä ivaile vakavista asioista.
— Ohoo! Ja mistä se pappi tulee tähän aikaan vuorokautta?
— Minä kävelen Hellaasta.
— Vai Hellaasta, tutusta paikasta. Vieläkö siellä pappinakin
kuljetaan? Ja vieläkö siellä on kaikki entisellään? Vieläkö siellä
seisotaan tiskin luona puhuttelemassa kapakkatyttöä, josta nyt kai
aiotaan tehdä papin rouva. Vieläkö siellä eteisessä puristetaan
lämpöistä kättä ja vannotaan että: ei suukkoakaan — ha-ha-ha-ha!
— Kuule…
— Ei. Tästä kääntyy minun tieni syrjäpoluilleni, olutputkaani,
tännepäin ei papin sovi kääntyä; tänne laskeudutaan. Hyvästi!
Puhellessaan olivat he yösydännä verkalleen kävelleet kaupungin
halki siihen torinkolkkaan, josta Robertinkatu lähtee ohjaamaan
kaupungin laiteille. Siinä se Anni hyvästit sanoi ja lähti viiltämään
alaspäin hämäränlaista katua ja katosi ensi nurkasta vasemmalle.
Eljas seisoi siinä hetken ja asteli hänkin sitten päinvastaiseen
suuntaan, nousi Korkeavuorenkatua, jossa hänellä oli asunto.
Ja yksin kävellessään hän mietti tuota kohtausta.
Oli se Anni häntä pilkannut ja soimaillutkin, mutta ne soimaukset
eivät häneen sattuneet, ne sinkoilivat ohi, kalahtivat jotakin
tuntematonta vastaan, jonka Eljas oli entisyyteensä haudannut. Sillä
hän oli itse pettynyt; se oli ollut erehdystä, unelmaa kaikki, mitä hän
oli luullut ja luottanut saavansa toimeen — omin voimin. Se oli ollut
turhuutta, valetta. Hän oli hapuillut kuin sokea, yritellyt ja kierrellyt
kaikilla suunnilla, juossut joukon matkassa ja vasten joukkoa, — aina

72. muka vakuutettuna asiansa oikeudesta. Ja aina se oli ollut turhuutta,
valetta! Nyt oli hän vasta oikealle polulle päässyt, nyt oli hän löytänyt
sen vaikutusalan, jota oli hakenut, nyt oli hän vasta vakuutettu.
Vai oliko hän todella nytkään oikein vakuutettu! — pieni epäilys
pisti semmoisena kiilana varmuuden väliin. Oliko se hänen oikea
vaikutusalansa? Oliko se hänen kutsumuksensa? Eiköhän nytkin ollut
teeskentelemistä, valetta seassa; eikö hän nyt valehdellut
itselleenkin? Eiköhän ehkä kaikki hänen nykyinen vakaumuksensa
ollutkin petosta?
— Ei, tuumi Eljas päättäväisesti, kääntyen sisään kotiportistaan. —
Ei, nyt minä vasta tunnen sen, että olen löytänyt tieni ja työni; minä
olen siitä vakuutettu, minä tunnen sen!
Ja noustessaan ylös portaita hän vielä puoliääneen toistelihe: minä
olen siitä vakuutettu, ikäänkuin joku olisi tahtonut väittää vastaan.
Mutta yksin hän oli, ei kukaan voinut väittää vastaan, — ellei
hienoinen, moittiva ääni hänen omassa povessaan.

73. IX.
Kaksi vuotta oli »vierähtänyt iankaikkisuuden mereen» — syksyyn
asti kolmatta.
Eljaasta oli keväällä tehty pappi, ja apulaisena hän nyt oli
kotiseudullaan. Häntä sanottiin hyväksi papiksi, ja useinpa heltyivät
itkuun sydämet hänen saarnatessaan ja puhuessaan. Sillä hyvät
olivat hänen luonnonlahjansa, hänen puheensa oli selvää ja äänensä
helisevä, kaunis. — Ja häntä sanottiin myös oikeaksi papiksi: vakava
oli ryhti ja varmaa vakaumusta todisti koko hänen levollinen, harras,
tyyni olentonsa, ja lämpöisestä sydämestä tuntuivat hänen sanansa
lähtevän.
Ja niin hän vakuutti usein itselleenkin, että siellä syrjässä, poissa
maailman metelistä, oli hän nyt löytänyt oikean paikkansa, voittanut
epäilyksensä ja houreensa, voittanut itsensä.
Ja hän oli jo kihloissa. Sehän on niin luonnollista kulkua tuo, että
apulainen maalla naipi rovastin tyttären, ja sitä luonnollisempaa vielä
Eljaan suhteen, kun hän jo lapsuudestaan oli morsiamensa tuttava ja
jo ennen poikana maalla ollessaan oli häntä väliin hentukseen

74. kutsunut, — nimikoksi tosin vain, sillä ainahan se pitää joku henttu
olla, jos ei muu niin nimikko.
Kaikki oli nyt niin luonnollista ja selvää. Rauha ja onni näytti
vihdoinkin saaneen varman asuntopaikan Eljaan ennen
rauhattomassa mielessä. — Joulun alla ne häät oli pidettävä.
Syksy se näet taaskin oli, kolakka, harmaja syksy, jolloin pakkanen
jo on iskenyt roudan maahan, kelmentänyt luonnon ja riitoittanut
rannat, jolloin alaston maa peitteekseen odottaa puhdasta, talvista
lunta ja hallava taivas odottaa kirkasta, talvista tähtikoristettaan.
Sunnuntaipäivä oli jo ikäpuolelleen kulunut. Eljas oli saarnannut
aamupuolella, syönyt päivällisensä ja lepäili nyt hiukan lämpöisessä
huoneessaan, loikoili suloisesti sohvallaan silmäillen ulos syksyiseen
luontoon.
Elämä tuntui Eljaasta nyt niin levolliselta, niin varmalta. Oli
hänelläkin ollut tuommoinen kiihkoaikansa, jolloin hän katsoi elämätä
ainaiseksi taisteluksi, jolloin hän koko innollaan oli heittäytynyt sen
taisteluun, oli tahtonut siihen vaikuttavana ottaa osaa, taistella ja
voittaa, edistää yhteishyvää, niittää kunniaa. Silloin oli hän
sydämensä pohjasta halveksinut semmoista syrjään vetäytymistä,
mokomata pakolaisasemata, joka hänestä nyt jo oli käynyt niin
suloiseksi. — Nuoruuden unelmia! — Se aika oli ohi. Mutta hän olikin
jo koulut käynyt, oppinut näkemään nuo taistelut kaikki turhuudeksi
ja valheeksi. Hän oli voittanut itsensä. —
Postin tulo nostatti Eljaan levoltaan. Harvoin sitä muutenkin tulee
postia maalle, syrjään valtateiltä, ja kelirikko sitä oli sitä nyt vielä
viivyttänytkin, joten se oli mieluisa vieras päivällislepoakin
häiritsemään. — Sanomalehtiä tuli koko tukku, päivälehtiä ja
uskonnollisia aikakauskirjoja; ne pantiin syrjään, viikon varaksi.

75. Kuulutukset, kirjeet ja paperit pastorin kansliaan tuomiokapitulista ja
maaherralta joutivat myös jäädä avaamatta myöhäisempään;
Yksityisten kirjeitten kimppuun ensiksi käytiin.
Ja Eljaallekin oli kirje. Harvoin niitä tuli, sillä hän ei ollut
kirjeenvaihdossa paljon kenenkään kanssa. Hän oli katkaissut entiset
houreitten aikuiset tuttavuutensa eikä paljon rakentanut uusia.
Kukapa siis olisi kirjoittanut? Tämä kirje oli Juhanalta; Eljas oli
hänelle lähettänyt ilmoituksen kihloihinmenostaan, ja onnitellakseen
kai se nyt Juhana niin pian vastasi. — Niinpähän olikin. Eljas luki:
Helsingissä lokakuun 16 p:nä 18—.
Rakas serkkuni.
Kiitosta monta kirjeestäsi ja kihlakortista. Arvasin
semmoisen kyllä tulevan, vaikka en vielä tiennyt odottaa.
Mutta mitäpä siinä onkaan vitkastelemista, kun kerran on
tilaisuus naimispuuhiin ryhtyä. Onnea siis, paljon onnea
toivon sinulle täydestä, sulasta sydämestäni! Vaalisi
onnistumista en ensinkään epäile, sillä vaikkakaan en
Selmaasi tunne, — en ole nähnyt sittenkuin
kymmenvuotiasna, — niin on kai molemminpuolinen
taipumuksenne kyllin takeena onnenne kestäväisyydestä.
Sano siis Selmallesikin minun onnentoivotukseni. Jospa
voisin, niin mielellänihän tulisin hääjuhlaanne, samalla
kotonakin taas kerran käydäkseni, mutta pelkäänpä, että en
täältä pääse irtautumaan.
Tänne olen näet pikeytynyt pääkaupunkiin, ja samaa
jatkutusta on elämiseni kuin jo vuosia sitten. Aamupäivät

76. virastossa, illat ulkona missä milloinkin, aina sen mukaan kuin
massi lupaa. Onhan se minulla nyt jo muka viran
nimellinenkin, ja hyvähän se on sekin, vaikka ei sillä vielä
kauas potkita noin taloudelliselta kannalta minun oloissani.
Sillä siitä minulla on monet vaikeudet ollut, huolet ja harmit,
kun olen tullut kirjoittaneeksi nimeni muitten papereihin.
Mutta eihän siitä saa nurkua, kun olen itsekin taas apua
tarvinnut. Huonompi se on Lassin laita, joka on tullut
kirjoittaneeksi muitten nimiä omiin papereihinsa. Nyt on mies
kesästä asti kateessa, Amerikkaan lie mennyt.
Kysyt, enkö minäkin jo kohta lähetä korttia, jossa olisi
omani ja Julian nimi. Yllämainituista rahallisista syistä jo
huomaat minulle tuiki mahdottomaksi omaa kotia ajatella. Ja
sitäpaitsi ne unelmani, joista sinäkin tiesit, ovat jo häipyneet.
Kivulloinen oli Julia jo koko menneen talvea, kesällä sai hän
kovan rintataudin, ja lääkärit selvittävät, että keuhkot ovat
lopussa. Nyt he ovat lähettäneet hänet maalle, jonkun
sukulaisen luo muka virkoamaan, mutta itse asiassa, niinkuin
kaikki sen tietävät — kuolemaan. Sinä ehkä arvelet niinkuin
moni muukin, että eipä tuossa köyhässä, laihassa
kirjurinmamsellissa ollut paljon kadottamistakaan; eihän siinä
ollut, mutta minusta se tuntuu usein raskaammalta kuin voit
luullakaan. —
Uutisiapa en tiedä paljon mitä kertoisin, tärkeimmät
tapahtumat näet sanomalehdistä. — Äskenhän oli taas, kuten
tiedät, N.S:n vuosijuhla Hellaassa vanhaan tapaan, ja minä
olin siellä nytkin, kuten edellisinä vuosina. Samanlaista
hurakkaa siellä oli kuin ennen vanhaan, jolloin me nuorina
ensikertalaisina siellä innostuimme; useimmat vanhat vain

77. 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