Lectures In Logic And Set Theory Volume 1 Mathematical Logic 1st Edition George Tourlakis

Lectures In Logic And Set Theory Volume 1
Mathematical Logic 1st Edition George Tourlakis
download
https://ebookbell.com/product/lectures-in-logic-and-set-theory-
volume-1-mathematical-logic-1st-edition-george-tourlakis-47424902
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Lectures In Logic And Set Theory Volume 2 Set Theory 1st Edition
George Tourlakis
https://ebookbell.com/product/lectures-in-logic-and-set-theory-
volume-2-set-theory-1st-edition-george-tourlakis-47424900
Homogeneous Ordered Graphs Metrically Homogeneous Graphs And Beyond 2
Volume Hardback Set Lecture Notes In Logic New Gregory Cherlin
https://ebookbell.com/product/homogeneous-ordered-graphs-metrically-
homogeneous-graphs-and-beyond-2-volume-hardback-set-lecture-notes-in-
logic-new-gregory-cherlin-51157784
Concept And Judgment In Brentanos Logic Lectures Robin D Rollinger
https://ebookbell.com/product/concept-and-judgment-in-brentanos-logic-
lectures-robin-d-rollinger-56005454
Logic In Tehran Proceedings Of The Workshop And Conference On Logic
Algebra And Arithmetic Held October 1822 2003 Lecture Notes In Logic
26 Ali Enayat
https://ebookbell.com/product/logic-in-tehran-proceedings-of-the-
workshop-and-conference-on-logic-algebra-and-arithmetic-held-
october-1822-2003-lecture-notes-in-logic-26-ali-enayat-5546200

Constraints In Computational Logics Theory And Applications
International Summer School Ccl 99 Gifsuryvette France September 58
1999 Revised Lectures 1st Edition Jeanpierre Jouannaud
https://ebookbell.com/product/constraints-in-computational-logics-
theory-and-applications-international-summer-school-
ccl-99-gifsuryvette-france-september-58-1999-revised-lectures-1st-
edition-jeanpierre-jouannaud-4198638
Logic Computation And Rigorous Methods Essays Dedicated To Egon Brger
On The Occasion Of His 75th Birthday Lecture Notes In Computer Science
12750 1st Ed 2021 Alexander Raschke Editor
https://ebookbell.com/product/logic-computation-and-rigorous-methods-
essays-dedicated-to-egon-brger-on-the-occasion-of-his-75th-birthday-
lecture-notes-in-computer-science-12750-1st-ed-2021-alexander-raschke-
editor-34004368
The Notre Dame Lectures Lecture Notes In Logic 18 Peter Cholak
https://ebookbell.com/product/the-notre-dame-lectures-lecture-notes-
in-logic-18-peter-cholak-5546192
The Notre Dame Lectures Lecture Notes In Logic 18 Peter Cholak Editor
https://ebookbell.com/product/the-notre-dame-lectures-lecture-notes-
in-logic-18-peter-cholak-editor-11300600
Hegels Science Of Logic A Critical Rethinking In Thirty Lectures
Winfield
https://ebookbell.com/product/hegels-science-of-logic-a-critical-
rethinking-in-thirty-lectures-winfield-4948220

This page intentionally left blank

CAMBRIDGE STUDIES IN
ADVANCED MATHEMATICS
EDITORIAL BOARD
B. BOLLOBAS, W. FULTON, A. KATOK, F. KIRWAN,
P. SARNAK
Lectures in Logic and Set Theory Volume 1
This two-volume work bridges the gap between introductory expositions of
logic or set theory on one hand, and the research literature on the other. It can
be used as a text in an advanced undergraduate or beginning graduate course
in mathematics, computer science, or philosophy. The volumes are written in
a user-friendly conversational lecture style that makes them equally effective
for self-study or class use.
Volume 1 includesformal proof techniques,a section on applications of
compactness (including non-standard analysis), a generous dose of computa-
bility and its relation to the incompleteness phenomenon, and the ﬁrst presen-
tation of a complete proof of G¨odel’s second incompleteness theorem since
Hilbert and Bernay’sGrundlagen.

Already published
2 K. PetersenErgodic theory
3 P.T. JohnstoneStone spaces
5 J.-P. KahaneSome random series of functions, 2nd edition
7 J. Lambek & P.J. ScottIntroduction to higher-order categorical logic
8 H. MatsumuraCommutative ring theory
10 M. AschbacherFinite group theory, 2nd edition
11 J.L. AlperinLocal representation theory
12 P. KoosisThe logarithmic integral I
14 S.J. PattersonAn introduction to the theory of the Riemann zeta-function
15 H.J. BauesAlgebraic homotopy
16 V.S. VaradarajanIntroduction to harmonic analysis on semisimple Lie groups
17 W. Dicks & M. DunwoodyGroups acting on graphs
19 R. Fritsch& R. PiccininiCellular structures in topology
20 H. KlingenIntroductorylectures on Siegel modularforms
21 P.KoosisThe logarithmic integral II
22 M.J. CollinsRepresentations and characters of ﬁnite groups
24 H. KunitaStochastic ﬂows and stochastic differential equations
25 P. WojtaszczykBanach spaces for analysts
26 J.E. Gilbert & M.A.M. MurrayClifford algebras and Dirac operators in harmonic analysis
27 A. Frohlich & M.J. TaylorAlgebraic number theory
28 K. Goebel & W.A. KirkTopics in metric ﬁxed point theory
29 J.F. HumphreysReﬂection groups and Coxeter groups
30 D.J. BensonRepresentations and cohomology I
31 D.J. BensonRepresentations and cohomology II
32 C. Allday & V. PuppeCohomological methods in transformation groups
33 C. Soule et al.Lectures on Arakelov geometry
34 A. Ambrosetti & G. ProdiA primer of nonlinear analysis
35 J. Palis & F. TakensHyperbolicity, stability and chaos at homoclinic bifurcations
37 Y. MeyerWavelets and operators 1
38 C. Weibel,An introduction to homological algebra
39 W. Bruns & J. HerzogCohen-Macaulay rings
40 V. SnaithExplicit Brauer induction
41 G. LaumonCohomology of Drinfeld modular varieties I
42 E.B. DaviesSpectral theory and differential operators
43 J. Diestel, H. Jarchow, & A. TongeAbsolutely summing operators
44 P. MattilaGeometry of sets and measures in Euclidean spaces
45 R. PinskyPositive harmonic functions and diffusion
46 G. TenenbaumIntroduction to analytic and probabilistic number theory
47 C. PeskineAn algebraic introduction to complex projective geometry
48 Y. Meyer & R. CoifmanWavelets
49 R. StanleyEnumerative combinatorics I
50 I. PorteousClifford algebras and the classical groups
51 M. AudinSpinning tops
52 V. JurdjevicGeometric control theory
53 H. VolkleinGroups as Galois groups
54 J. Le PotierLectures on vector bundles
55 D. BumpAutomorphic forms and representations
56 G. LaumonCohomology of Drinfeld modular varieties II
57 D.M. Clark & B.A. DaveyNatural dualities for the working algebraist
58 J. McClearyA user’s guide to spectral sequences II
59 P. TaylorPractical foundations of mathematics
60 M.P. Brodmann & R.Y. SharpLocal cohomology
61 J.D. Dixon et al.Analytic pro-P groups
62 R. StanleyEnumerative combinatorics II
63 R.M. DudleyUniform central limit theorems
64 J. Jost & X. Li-JostCalculus of variations
65 A.J. Berrick & M.E. KeatingAn introduction to rings and modules
66 S. MorosawaHolomorphic dynamics
67 A.J. Berrick & M.E. KeatingCategories and modules with K-theory in view
68 K. SatoLevy processes and inﬁnitely divisible distributions
69 H. HidaModular forms and Galois cohomology
70 R. Iorio & V. IorioFourier analysis and partial differential equations
71 R. BleiAnalysis in integer and fractional dimensions
72 F. Borceaux & G. JanelidzeGalois theories
73 B. BollobasRandom graphs

LECTURES IN LOGIC
AND SET THEORY
Volume 1: Mathematical Logic
GEORGE TOURLAKIS
York University

  
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge  , United Kingdom
First published in print format
ISBN-13 978-0-521-75373-9 hardback
ISBN-13 978-0-511-06871-3 eBook (EBL)
© George Tourlakis 2003
2003
Information on this title: www.cambridge.org/9780521753739
This book is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
ISBN-10 0-511-06871-9 eBook (EBL)
ISBN-10 0-521-75373-2 hardback
Cambridge University Press has no responsibility for the persistence or accuracy of
s for external or third-party internet websites referred to in this book, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Published in the United States by Cambridge University Press, New York
www.cambridge.org

για την δεσπoινα, την µαρινα και τoν γιαννη

Contents
Preface pageix
IBasicLogic 1
I.1FirstOrderLanguages 5
I.2 A Digression into the Metatheory:
InformalInductionandRecursion 19
I.3AxiomsandRulesofInference 28
I.4BasicMetatheorems 42
I.5Semantics;Soundness,Completeness,Compactness 52
I.6Substructures,Diagrams,andApplications 75
I.7DeﬁnedSymbols 112
I.8ComputabilityandUncomputability 123
I.9 Arithmetic, Deﬁnability, Undeﬁnability,
andIncompletableness 155
I.10Exercises 191
IITheSecondIncompletenessTheorem 205
II.1PeanoArithmetic 206
II.2AFormalβ-Function 232
II.3FormalPrimitiveRecursion 248
II.4TheBoldfaceand 256
II.5Arithmetization 265
II.6DerivabilityConditions;FixedPoints 272
II.7Exercises 316
Bibliography 319
ListofSymbols 321
Index 323
vii

Preface
Both volumes in this series are about what mathematicians, especially logicians,
call the “foundations” (of mathematics) – that is, the tools of the axiomatic
method, an assessment of their effectiveness, and two major examples of ap-
plication ofthese tools, namely, in the development of number theory and set
theory.
There have been, in hindsight, two main reasons for writing this volume.
One was the existence of notes I wrotefor my lectures in mathematicallogic
and computability that had been accumulating over the span of several years
and badly needed sorting out. The other was the need to write a small section
on logic, “A Bit of Logic” as I originally called it, that would bootstrap my
volume on set theory
†
on which I had been labouring for a while. Well, one
thing led to another, and a 30 or so page section that I initially wrote for the
latter purpose grew to become a self-standing volume of some 300 pages. You
see, this material on logic is a good story and, as with all good stories, one does
get carried away wanting to tell more.
I decided to include what many people will consider, I should hope, as
being theabsolutely essential topics inproof, model, andrecursiontheory –
“absolutely essential” in the context of courses taught near the upper end of
undergraduate, and at the lower end of graduate curricula in mathematics, com-
puter science, or philosophy. But no more.
‡
This is the substance of Chapter I;
hence its title “Basic Logic”.
†
A chapter by that name now carries out these bootstrapping duties – the proverbial “Chapter 0”
(actually Chapter I) of volume 2.
‡
These topics include the foundation and development of non-standard analysis up to the ex-
treme value theorem, elementary equivalence, diagrams, and L¨owenheim-Skolem theorems, and
G¨odel’s ﬁrst incompleteness theorem (along with Rosser’s sharpening).
ix

x Preface
But then it occurred to me to also say something about one of the most
remarkable theorems of logic – arguablythemost remarkable – about the lim-
itations of formalized theories: G¨odel’s second incompleteness theorem. Now,
like most reasonable people, I never doubted that this theorem is true, but, as the
devil is in the details, I decided to learn its proof – right from Peano’s axioms.
What better way to do this than writing down the proof, gory details and all?
This is what Chapter II is about.
†
As a side effect, the chapter includes many theorems and techniques of one
of the two most important – from the point of view of foundations – “applied”
logics (formalized theories), namely, Peano arithmetic (the other one, set theory,
taking all of volume 2).
I have hinted above that this (and the second) volume are aimed at a fairly
advanced reader: The level of exposition is designed to ﬁt a spectrum of math-
ematical sophistication from third year undergraduate to junior graduate level
(each group will ﬁnd here its favourite sections that serve its interests and level
of preparation – and should not hesitate to judiciously omit topics).
There are no speciﬁc prerequisites beyond some immersionin the“proof
culture”, as this is attainable through junior level courses in calculus, linear al-
gebra, or discrete mathematics. However, some familiarity with concepts from
elementary na¨ıve set theory such as ﬁniteness, inﬁnity, countability, and un-
countability will be an asset.
‡
A word on approach.I have tried to make these lectures user-friendly, and thus
accessible to readers who do not have the beneﬁt of an instructor’s guidance.
Devices to that end include anticipation of questions, frequent promptings for
the reader to rethink an issue that might be misunderstood if glossed over
(“Pauses”), and the marking of important passages, by
, as well as those that
can be skipped at ﬁrst reading, by.
Moreover, I give (mostly)verydetailed proofs, as I know from experience
that omitting details normally annoys students.
†
It is strongly conjectured here that this is the only complete proof in print other than the one
that was given in Hilbert and Bernays (1968). It is fair to clarify that I use the term “complete
proof” with a strong assumption in mind: That the axiom system we start with isjustPeano
arithmetic. Proofs based on a stronger – thus technically more convenient – system, namely,
primitive recursive arithmetic, have already appeared in print (Diller (1976), Smory´nski (1985)).
The difﬁculty with using Peano arithmetic as the starting point is that the only primitive recursive
functions initially available are the successor, identity, plus, and times. An awful amount of work
is needed – a preliminary “coding trick” – to prove that all the rest of the primitive recursive
functions “exist”. By then are we already midway in Chapter II, and only then are we ready to
build G¨odel numbers of terms, formulas, and proofs and to prove the theorem.
‡
I have included a short paragraph nicknamed “a crash course on countable sets” (Section I.5,
p. 62), which certainly helps. But having seen these topics before helps even more.

Preface xi
The ﬁrst chapter has a lot of exercises (the second having proportionally
fewer). Many of these have hints, but none are marked as “hard” vs. “just about
right”, a subjective distinction I prefer to avoid. In this connection here is some
good advice I received when I was a graduate student at the University of
Toronto: “Attempt all the problems. Those you can do, don’t do. Do the ones
you cannot”.
What to read.Consistently with the advice above, I suggest that you read this
volume from cover to cover – including footnotes! – skipping only what you
already know. Now, in a class environment this advice may be impossible to
take, due to scope and time constraints. An undergraduate (one semester) course
in logic at the third year level will probablycover Sections I.1–I.5, making light
of Section I.2, and will introduce the student to the elements of computability
along with a hand-waving “proof” of G¨odel’s ﬁrst incompleteness theorem (the
“semantic version” ought to sufﬁce). A fourth year class will probably attempt
to cover the entire Chapter I. A ﬁrst year graduate class has no more time than
the others at its disposal, but it usually goes much faster, skipping over familiar
ground, thus it will probably additionally cover Peano arithmeticand will get
to see how G¨odel’s second theorem follows from L¨ob’s derivability conditions.
Acknowledgments.I wish to offermy gratitude to all those who taught me,
a group led by my parents and too large to enumerate. I certainly include my
students here. I also include Raymond Wilder’s book on the foundations of
mathematics, which introduced me, long long ago, to this very exciting ﬁeld
and whetted my appetite for more (Wilder (1963)).
I should like to thank the staff at Cambridge University Press for their pro-
fessionalism, support, and cooperation, with special appreciation due to Lauren
Cowles and Caitlin Doggart, who made all the steps of this process, from ref-
ereeing to production, totally painless.
This volume is the last installment of a long project that would have not been
successful without the support and warmth of an understanding family (thank
you).
I ﬁnally wish to record my appreciation to Donald Knuth andLeslie Lamport
for the typesetting tools TEX and L
ATEX that they have made available to the tech-
nical writing community, making the writing of books such as this one almost
easy.
George Tourlakis
Toronto, March 2002

I
Basic Logic
Logic is the science of reasoning. Mathematical logic applies to mathematical
reasoning – the art and science of writingdowndeductions. Thisvolume is
about theform,meaning,use, andlimitationsof logical deductions, also called
proofs. While the user of mathematical logic will practise the various proof
techniques with a view of applyingthem in everyday mathematical practice,
the student of the subject will also want to know about the power and limitations
of the deductive apparatus. We will ﬁnd that there are some inherent limitations
in the quest to discover truth by purelyformal– that is,syntactic– techniques.
In the process we will also discover a close afﬁnity between formal proofs and
computationsthat persists all the way up to and including issues of limitations:
Not only is there a remarkable similarity between the types of respective limi-
tations (computations vs. uncomputable functions, and proofs vs. unprovable,
but “true”, sentences), but, in a way, you cannot have one type of limitation
without having the other.
The modern use of the term mathematical logic encompasses (at least) the
areas of proof theory (it studies the structure, properties, and limitations of
proofs), model theory (it studies the interplay between syntax and meaning – or
semantics – by looking at the algebraic structures where formal languages are
interpreted), recursion theory (or computability, which studies the properties
and limitations of algorithmic processes), and set theory. The fact that the last-
mentioned will totally occupy our attention in volume 2 is reﬂected in the
prominence of the term in the title of these lectures. It also reﬂects a tendency,
even today, to think of set theory as a branch in its own right, rather than as an
“area” under a wider umbrella.
1

2 I. Basic Logic
Volume 1 is a brief study of the other three areas of logic
†
mentioned above.
This is the point where an author usually apologizes for what has been omitted,
blaming space or scope (or competence) limitations. Let me start by outlin-
ing what is included: “Standard” phenomena such ascompleteness,compact-
nessand its startling application to analysis,incompletenessorunprovabil-
ity(including acompleteproof of thesecond incompleteness theorem), and a
fair amount ofrecursion theoryare thoroughly discussed. Recursion theory,
orcomputability, is of interest to a wide range ofaudiences, including stu-
dents with main areas of study such as computer science, philosophy, and, of
course, mathematical logic. It studies among other things the phenomenon of
uncomputability, which is closely related to that of unprovability, as we see in
Section I.9.
Among the topics that I have deliberately left out are certain algebraic tech-
niques in model theory (such as the method ofultrapowers), formal interpre-
tations of one theory into another,
‡
the introduction of “other” logics (modal,
higher order,intuitionistic, etc.), and several topics in recursion theory (oracle
computability, Turing reducibility, recursive operators, degrees, Post’s theorem
in the arithmetic hierarchy, the analytic hierarchy, etc.) – but then, the decision
to stop writing within 300 or so pages was ﬁrm. On the other hand, the topics
included here form a synergistic whole in thatI have (largely) included at every
stage material that is prerequisite to what follows. The absence of a section on
propositional calculusis deliberate, as it does not in my opinion further the
understanding of logic in any substantial way, while it delays one’s plunging
into what really matters. To compensate, I include all tautologies as “proposi-
tional” (or Boolean) logical axioms and present a mini-course on propositional
calculus in the exercises of this chapter (I.26–I.41, pp. 193–195), including the
completeness and compactness of the calculus.
It is inevitable that the language of setsintrudes in this chapter (as it indeed
does in all mathematics) and, more importantly, some of the results of (informal)
set theory are needed here (especially in our proofs of the completeness and
compactnessmetatheorems). Conversely,formalset theory of volume 2 needs
some of the results developed here. This “chicken or egg” phenomenon is often
called “bootstrapping” (not to be confused with “circularity” – which it is not
§
),
the term suggesting one pulling oneself up by one’s bootstraps.
¶
†
I trust that the reader will not object to my dropping the qualiﬁer “mathematical” from now on.
‡
Although this topic is included in volume 2 (Chapter I), since it is employed in the relative
consistency techniques applied there.
§
Only informal, or na¨ıve, set theory notation and results are needed in Chapter I at the meta-level,
i.e, outside the formal system that logic is.
¶
I am told that Baron M¨unchhausen was the ﬁrst one to apply this technique, with success.

I. Basic Logic 3
This is a good place to outline how our story will unfold: First, our objective is to
formalizethe rules of reasoning in general – as these apply to all mathematics –
and develop their properties. In particular, we will study the interaction between
formalized rules and their “intended meaning” (semantics), as well as the limi-
tations of these formalized rules: That is, how good (=potent) are they for
capturing the informal notions of truth?
Secondly, once we have acquired these tools of formalized reasoning, we start
behaving (mostly
†
)asusersof formal logic so that we can discover important
theorems of two important mathematical theories:Peano arithmetic(Chapter II)
andset theory(volume 2).
Byformalization(of logic) we understand the faithful representation or
simulation of the “reasoning processes” of mathematicsin general(purelogic),
or of a particular mathematical theory (appliedlogic: e.g., Peano arithmetic),
within an activity that – in principle – is driven exclusively by theformor syntax
of mathematical statements, totally ignoring their meaning.
We build, describe, and study the properties of thisartiﬁcial replicaof the
reasoning processes – the formal theory – within “everyday mathematics” (also
called “informal” or “real” mathematics), using the usual abundance of mathe-
matical symbolism, notions, and techniques available to us, augmented by the
descriptive power of English(or Greek, or French, or German, or Russian,
or..., as particular circumstances or geography might dictate). This milieu
within which we build, pursue, and study our theories is often called themeta-
theory, or more generally,metamathematics. The language we speak while at
it, this m´elange of mathematics and “natural language”, is themetalanguage.
Formalization turns mathematical theories into mathematical objects that
we can study. For example, such study may include interesting questions such
as “is the continuum hypothesis provable from the axioms of set theory?” or
“can we prove the consistency of (axiomatic) Peano arithmetic within Peano
arithmetic?”
‡
This is analogous to building a “model airplane”, a replica of the
real thing, with a view of studyingthrough the replicathe properties, power,
and limitations of the real thing.
But one can also use the formal theory togenerate theorems, i.e., discover
“truths” in the real domain by simply “running” the simulation that this theory-
replica is.
§
Running the simulation “by hand” (rather than using the program
†
Some tasks in Chapter II of this volume, and some others in volume 2, will be to treat the “theory”
at hand as an object of study rather than using it, as a machine, to crank out theorems.
‡
By the way, the answer to both these questions is “no” (Cohen (1963) for the ﬁrst, G¨odel (1938)
for the second).
§
The analogy implied in the terminology “running the simulation” is apt. For formal theories such
as set theory and Peano arithmetic we can build within real mathematics a so-called “provability

4 I. Basic Logic
of the previous footnote) means that you are acting as a “user” of the formal
system, a formalist, proving theorems through it. It turns out that once you get
the hang of it, it is easier and safer to reason formally than to do so informally.
The latter mode often mixes syntax and semantics (meaning), and there is
always the danger that the “user” may assign incorrect (i.e., convenient, but not
general) meanings to the symbols that he
†
manipulates, a phenomenon that has
distressed many a mathematics or computer science instructor.
“Formalism for the user” is hardly a revolutionary slogan. It was advocated
by Hilbert, the founder of formalism, partly as a means of – as he believed
‡
–
formulating mathematical theories in a manner that allows one to check them
(i.e., run “diagnostic tests” on them) for freedom from contradiction,
§
but also
asthe right way to “do” mathematics. By this proposal he hoped to salvage
mathematics itself, which, Hilbert felt, was about to be destroyed by the Brouwer
school of intuitionist thought. In a way, his program could bridgethe gap
between the classical and the intuitionist camps, and there is some evidence
that Heyting (an inﬂuential intuitionist and contemporary of Hilbert) thought
that such arapprochementwas possible. After all, since meaningis irrelevant to
a formalist, then all that he is doing (in a proof) is shufﬂing ﬁnite sequences of
symbols, never having to handle or argue about inﬁnite objects – a good thing,
as far as an intuitionist is concerned.
¶
predicate”, that is, a relationP(y,x) which is true of two natural numbersyandxjust in casey
codesa proof of the formulacodedbyx. It turns out thatP(y,x) has so simple a structure that it
is programmable, say in the C programming language. But then we can write a program (also in
C) as follows: “Systematically generate all the pairs of numbers (y,x). For each pair generated,
ifP(y,x) holds, then print the formula coded byx”. Letting this process run for ever, we obtain
a listing ofallthe theorems of Peano arithmetic or set theory! This fact does not induce any
insomnia in mathematicians, since this is an extremely impractical way to obtain theorems. By
the way, we will see in Chapter II that either set theory or Peano arithmetic is sufﬁciently strong
toformallyexpress a provability predicate, and this leads to the incompletableness phenomenon.
†
In this volume, the terms “he”, “his”, “him”, and their derivatives are by deﬁnition gender-neutral.
‡
This belief was unfounded, as G¨odel’s incompleteness theorems showed.
§
Hilbert’smetatheory– that is, the “world” or “lab”outside the theory, where the replica is
actually manufactured – wasﬁnitary. Thus – Hilbert advocated – all this theory building and
theory checking ought to be effected byﬁnitary means. This ingredient of his “program” was
consistent with peaceful coexistence with the intuitionists. And, alas, this ingredient was the one
that – as some writers put it – destroyed Hilbert’s program to found mathematics on his version
of formalism. G¨odel’s incompleteness theorems showed that a ﬁnitary metatheory is not up to
the task.
¶
True, a formalist applies classical logic, while an intuitionist applies a different logic where, for
example, double negation is not removable. Yet, unlike a Platonist, a Hilbert-style formalist does
not believe – or he does not have to disclose to his intuitionist friends that he might believe – that
inﬁnite sets existin the metatheory, as his tools are just ﬁnite symbol sequences. To appreciate the
tension here, consider this anecdote: It is said that when Kronecker – the father of intuitionism –
was informed of Lindemann’s proof (1882) thatπis transcendental, while he granted that this was
an interesting result, he also dismissed it, suggesting that “π” – whose decimal expansion is, of

I.1. First Order Languages 5
In support of the “formalism for the user” position we must deﬁnitely men-
tion the premier paradigm, Bourbaki’s monumental work (1966a), which is a
formalization of a huge chunk of mathematics, including set theory, algebra,
topology, and theory of integration. This work is strictly for theuserof mathe-
matics, not for the metamathematician whostudiesformal theories. Yet, it is
fully formalized, true to the spirit of Hilbert, and it comes in a self-contained
package, including a “Chapter 0” on formal logic.
More recently, the proposal to employ formal reasoning as a tool has been
gaining support in a number of computer science undergraduate curricula, where
logic and discrete mathematics are taught ina formalized setting, starting with
a rigorous course in the two logical calculi (propositional and predicate), em-
phasizing the point of view of theuserof logic (and mathematics) – hence with
an attendant emphasis on “calculating” (i.e., writing and annotating formal)
proofs. Pioneering works in this domain are the undergraduate text (1994) and
the paper (1995) of Gries and Schneider.
I.1. First Order Languages
In the most abstract (therefore simplest) manner of describing it, aformalized
mathematical theoryconsists of the following sets of things: A set of basic
or primitive symbols,V, used to buildsymbol sequences(also called strings,
or expressions, or words) “overV”. A set of strings,Wff, overV, called the
formulasof the theory. Finally, asubsetofWff, calledThm, the set oftheorems
of the theory.
†
Well, this is theextensionof a theory, that is, the explicit set of objects in it.
How is a theory “given”?
In most cases of interest to the mathematician it is given byVand two
sets of simplerules: formula-building rules and theorem-building rules. Rules
from the ﬁrst set allow us to build, orgenerate,WfffromV. The rules of the
second set generateThmfromWff. In short (e.g., Bourbaki (1966b)),a theory
consists of an alphabet of primitive symbols, somerulesused to generate the
“language of the theory”(meaning, essentially,Wff)from these symbols, and
someadditionalrules used to generate the theorems.We expand on this below:
course, inﬁnite but not periodic – “does not exist” (see Wilder (1963, p. 193)). We are not to pro-
pound the tenets of intuitionism here, but it is fair to state that inﬁnite setsarepossible in intuition-
istic mathematics as this has later evolved in the hands of Brouwer and his Amsterdam “school”.
However, such sets must be (like all sets of intuitionistic mathematics)ﬁnitely generated– just
as our formal languages and the set of theorems are (the latterprovidedour axioms are too) – in
a sense that may be familiar to some readers who have had a course in “automata and language
theory”. See Wilder (1963, p. 234)
†
For a less abstract, but more detailed view of theories see p. 38.

6 I. Basic Logic
I.1.1 Remark .What is a “rule”? We run the danger of becoming circular or too
pedantic if we overdeﬁne this notion. Intuitively, the rules we have in mind are
string manipulation rules, that is, “black boxes” (or functions) that receive string
inputs and respond with string outputs. For example, a well-known theorem-
building rule receives as input a formula and a variable, and returns (essentially)
the string composed of the symbol∀, immediately followed by the variable and,
in turn, immediately followed by the formula.
†
ε
(1) First off, the (ﬁrst order)formal language,L, where the theory is “spoken”,
‡
is a triple (V,Term,Wff), that is, it has three important components, each
of them a set.
Vis thealphabetor vocabulary of the language. It is the collection of the
basicsyntactic “bricks” (symbols) that we use to formexpressionsthat
areterms(members ofTerm)orformulas(members ofWff). We will
ensure that the processes that build terms or formulas, using the basic
building blocks inV, are intuitivelyalgorithmicor “mechanical”.
Terms will formally codify “objects”, while formulas will formally
codify “statements” about objects.
(2)Reasoningin the theory will be the process of discoveringtrue statements
about objects – that is,theorems. This discovery journey begins with certain
formulas which codify statements that we take for granted (i.e., we accept
without “proof” as “basic truths”). Such formulas are theaxioms. There are
two types of axioms:
Specialornonlogicalaxioms are to describe speciﬁc aspects of any
speciﬁc theory that we might be building. For example, “x+1ι =0”
is a special axiom that contributes towards the characterization of
number theory over the natural numbers,N.
The other kind of axiom will be found inalltheories. It is the kind that is
“universally valid”, that is,nottheory-speciﬁc (for example, “x=x”
is such a “universal truth”). For that reason this type of axiom will be
calledlogical.
(3) Finally, we will needrulesfor reasoning, actually calledrules of inference.
These are rules that allow us to deduce, or derive, a true statement from
other statements that we have already established as being true.
§
These
rules will be chosen to be oblivious to meaning, being only concerned with
†
This rule is usually called “generalization”.
‡
We will soon say what makes a language “ﬁrst order”.
§
The generous use of the term “true” here is only meant for motivation. “Provable” or “deducible”
(formula), or “theorem”, will be the technically precise terminology that we will soon deﬁne to
replace the term “true statement”.

I.1. First Order Languages 7
form. They will apply to statement “conﬁgurations” of certainrecognizable
formsand will produce (derive) new statements of somecorresponding
recognizable forms(See Remark I.1.1).
I.1.2 Remark.We may think of axioms of either logical or nonlogical type as
special cases of rules, that is, rules that receivenoinput in order to produce an
output. In this manner item (2) above is subsumed by item (3), and thus we are
faithful to our abstract deﬁnition of theory where axioms were not mentioned.
An example, outside mathematics, of an inputless rule is the rule invoked
when you typedateon your computer keyboard. This rule receives no input,
and outputs on your screen the current date.
ε
We next look carefully into (ﬁrst order) formal languages. There are two parts in each ﬁrst order alphabet. The ﬁrst, the collection of
thelogical symbols,iscommon to all ﬁrst order languagesregardless of which
theory is “spoken” in them. We describe this part immediately below.
Logical Symbols
LS.1.Object or individual variables.Anobject variableis any onesymbol
out of the non-ending sequencev
0,v1,v2,....In practice– whether
we are using logic as a tool or as an object of study – we agree to be
sloppy with notation and use,generically,x,y,z,u,v,wwith or without
subscripts or primes asnamesof object variables.
†
This is just a matter
of notational convenience. We allow ourselves to write, say,zinstead of,
say,v
1200000000560000009. Object variables (intuitively) “vary over” (i.e.,
are allowed to take values that are) the objects that the theory studies
(numbers, sets, atoms, lines, points, etc., as the case may be).
LS.2.The Boolean or propositional connectives.These are the symbols “¬”
and “∨”.
‡
They are pronouncednotandorrespectively.
LS.3.The existential quantiﬁer, that is, the symbol “∃”, pronouncedexistsor
for some.
LS.4.Brackets, that is, “(” and “)”.
LS.5.The equality predicate. This is the symbol “=”, which we use to indicate
that objects are “equal”. It is pronouncedequals.
†
Conventions such as this one are essentially agreements – effected in the metatheory – on how
to be sloppy and get away with it. They are offered in the interest of user-friendliness.
‡
The quotes arenotpart of the symbol. They serve to indicate clearly here, in particular in the
case of “∨”, what is part of the symbol and what is not (the following period).

8 I. Basic Logic
The logical symbols will have a ﬁxed interpretation. In particular, “=” will
always be expected to meanequals.
The theory-speciﬁc part of the alphabet is not ﬁxed, but varies from theory
to theory. For example, in set theory we just add the nonlogical (or special)
symbols,∈andU. The ﬁrst is a specialpredicate symbol(or just predicate) of
arity2, the second is a predicate symbol of arity 1.
†
In number theory we adopt instead the special symbolsS(intended meaning:
successor, or “+1” function),+,×,0,<, and (sometimes) a symbol for the
exponentiation operation(function)a
b
. The ﬁrst three arefunction symbolsof
arities 1, 2, and 2 respectively. 0 is aconstant symbol,<a predicate of arity 2,
and whatever symbol we might introduce to denotea
b
would have arity 2.
The following list gives the general picture.
Nonlogical Symbols
NLS.1.A (possibly empty) set of symbols forconstants. We normally use
the metasymbols
‡
a,b,c,d,e, with or without subscripts or primes, to
stand for constants unless we havein mind some alternative“standard”
formal notation in speciﬁc theories (e.g.,∅,0,ω).
NLS.2.A (possibly empty) set of symbols forpredicate symbolsorrelation
symbolsfor each possible “arity”n>0. We normally useP,Q,R
generically, with or without primes or subscripts, to stand for predicate
symbols. Note that=is in the logical camp. Also note that theory-
speciﬁc formal symbols are possible for predicates, e.g.,<,∈.
NLS.3.Finally, a (possibly empty) set of symbols forfunctionsfor each possi-
ble “arity”n>0. We normally usef,g,h, generically, with or without
primes or subscripts, to stand for function symbols. Note that theory-
speciﬁc formal symbols are possible for functions, e.g.,+,×.
I.1.3 Remark.(1) We have the option of assuming that each of thelogical
symbols that we named inLS.1–LS.5have no further “structure” and that the
symbols are, ontologically,identical to their names, that is, they are just these
exact signs drawn on paper (or on any equivalent display medium).
In this case, changing the symbols, say,¬and∃to∼andErespectively
results in a “different” logic, but one that is, trivially, “isomorphic” to the one
†
“Arity” is a term mathematicians have made up. It is derived from “ary” of “unary”, “binary”,
etc. It denotes the number of arguments needed by a symbol according to the dictates of correct
syntax. Function and predicate symbols need arguments.
‡
Metasymbols areinformal(i.e., outside the formal language) symbols that we use within
“everyday” or “real” mathematics – themetatheory – in order to describe, as we are doing here,
the formal language.

I.1. First Order Languages 9
we are describing: Anything that we may do in, or say about, one logic trivially
translates to an equivalent activity in, or utterance about, the other as long as
we systematically carry out the translations of all occurrences of¬and∃to∼
andErespectively (or vice versa).
An alternative point of view is that the symbol names arenotthe same as
(identical with) the symbols they are naming. Thus, for example, “¬” names
the connective we pronouncenot, but we do not know (or care) exactly what
the nature of this connective is (we only care about how it behaves). Thus, the
name “¬” becomes just a typographical expedient and may be replaced by other
names thatname the same object,not.
This point of view gives one ﬂexibility in, for example, deciding how the
variable symbolsare“implemented”. It often isconvenient to think that the
entire sequence of variable symbols was built from just two symbols, say, “v”
and “|”.
†
One way to do this is by saying thatv iis a name for the symbol
sequence
‡
“v|...|
ε
γι∨
i|’s
”
Or, preferably – see (2) below –v
imight be a name for the symbol sequence
“v|...|
ε
γι∨
i|’s
v”
Regardless of option,v
iandv jwill name distinct objects ifiι =j.
This isnotthe case for themetavariables (“abbreviated informal names”)
x,y,z,u,v,w.Unless we say so explicitly otherwise, x and ymayname the
same formal variable, say,v
131.
We will mostly abuse language and deliberately confuse names with the
symbols they name. For example, we will say, e.g., “letv
1007bean object
variable...” rather than “letv
1007namean objectvariable...”, thusappearing
to favour option one.
(2)Any two symbolsincluded in the alphabet aredistinct. Moreover, if any of
them are built from simpler “sub-symbols” – e.g.,v
0,v1,v2,...mightreally
namethe stringsvv, v|v, v||v,...– then none of them is asubstring(orsubex-
pression) of any other.
§
†
We intend these two symbols to be identical to their names. No philosophical or other purpose
will be served by allowing “more indirection” here (such as “vnamesu, which actually names
w, which actually is...”).
‡
Not including the quotes.
§
What we have stated under (2) arerequirements, not metatheorems! That is, they are nothing of
the sort that we canproveabout our formal language within everyday mathematics.

10 I. Basic Logic
(3) A formal language, just like a “natural” language (such as English or
Greek), is “alive” and evolving. The particular type of evolution we have in
mind is the one effected byformal deﬁnitions. Such deﬁnitions continuallyadd
nonlogical symbols to the language.
†
Thus, when we say that, e.g., “∈andUare the only nonlogical symbols of
set theory”, we are telling a small white lie. More accurately, we ought to have
said that “∈andUare the only ‘primitive’ nonlogical symbols of set theory”,
for we will add loads of other symbols such as∪,ω,∅,⊂,⊆.
This evolution affectsthe (formal) language ofanytheory, not just set
theory.
ε
Wait a minute! If formal settheory is“the foundation of all mathematics”, and
if, ostensibly, this chapter on logic assists us to found set theory itself, then
how come we are employingnatural numberslike 1200000000560000009 as
subscriptsin thenamesof object variables? How is it permissible to already talk
about “setsof symbols” when we are about tofounda theory ofsetsformally?
Surely we do not “have”
‡
any of these “items” yet, do we?
First off, the presence of subscripts such as 1200000000560000009 in
v
1200000000560000009
is a non-issue. One way to interpret what has been said in the deﬁnition is
to view the variousv
ias abbreviated names of the real thing, the latter being
strings that employ the symbolsvand|as in Remark I.1.3. In this connection
saying thatv
iis “implemented” as
v|...|
ε
γι∨
i|’s
v (1)
especially the use of “i” above, is only illustrative, thus totally superﬂuous. We
can say instead that strings of type (1)arethe variables which we deﬁne as
followswithoutthe help of the “natural numberi” (this is a variation of how
this is done in Bourbaki (1966b) and Hermes (1973)):
An “|-calculation” forms a string like this: Write a “|”.
§
This is the “current
string”. Repeat a ﬁnite number of times: Add (i.e., concatenate)one|imme-
diately to the right of the current string. Write this new string (it is nowthe
current string).
†
This phenomenon will be studied in some detail in what follows. By the way, any additions are
made to the nonlogical side of the alphabet. All the logical symbols have been given, once and
for all.
‡
“Do not have” in the sense of having not formally deﬁned – or proved to exist – or both.
§
Without the quotes. These were placed to exclude the punctuation following.

I.1. First Order Languages 11
Let us call any string that ﬁgures in some|-calculation a “|-string”. A variable
eitheristhe stringvv, or is obtained as the concatenation from left to right of
vfollowed by an|-string, followed byv.
All we now need is the ability to generate as many as necessary distinct
variables (this is the “non-ending sequence” part of the deﬁnition, p. 7): For
any two variables we get a new one that is different from either one by forming
the string “v, followed by the concatenation of the two|-parts, followed byv”.
Similarly if we had three, four,...variables. By the way, two strings of|are
distinct iff
†
both occur in the same|-calculation, one, but not both, as the last
string.
Another, more direct way to interpret what was said about object variables
on p. 7 is to take the deﬁnition literally, i.e., to suppose that it speaks about the
ontology of the variables.
‡
Namely, the subscript is just a a string of meaningless
symbols taken from the list below:
0,1,2,3,4,5,6,7,8,9
Again we can pretend that we know nothing about naturalnumbers, and when-
ever, e.g., we want a variable other than either ofv
123orv321,we may offer
either ofv
123321orv321123as such anewvariable.
O.K., so we havenotused natural numbers in the deﬁnition. But we did say
“sets” and also “non-ending sequence”, implying the presence ofinﬁnitesets!
As we have already noted, on one hand we have “real mathematics”, and on
the other hand we have syntacticreplicasof theories – the formal theories –
that we builtwithin real mathematics. Having built a formal theory, we can then
choose touseit (acting like formalists) to generate theorems, the latter being
codiﬁed as symbol sequences (formulas). Thus, the assertion “axiomatic set
theory is the foundation of all mathematics” is just a colloquialism proffered
in the metatheory that means that “within axiomatic set theory we can construct
the known sets of mathematics, such as the realsRand the complex numbers
C, and moreover we can simulate what we informally do whenever we are
working in real or complex analysis, algebra, topology, theory of measure and
integration, functional analysis,etc., etc.”
There is no circularity here, but simply an empirical boastful observationin
the metatheoryof what our simulator can do. Moreover, our metatheory does
†
If and only if.
‡
Why not just sayexactlywhat a deﬁnition is meant to say rather than leave it up to interpretation?
One certainly could, as in Bourbaki (1966b), make the ontology of variables crystal-clear right in
the deﬁnition. Instead, we have followed the custom of more recent writings and given the deﬁ-
nition in a quasi-sloppy manner that leaves the ontology of variables as a matter for speculation.
This gives one the excuse to write footnotes like this one and remarks like I.1.3.

12 I. Basic Logic
have sets and all sorts of other mathematical objects. In principle we can use any
among those towards building or discussing the simulator, the formal theory.
Thus, the question is not whether we can use sets, or natural numbers, in
our deﬁnitions, but whether restrictions apply. For example, can we use inﬁnite
sets?
If we are Platonists,then we have available in the metatheory all sorts of sets,
including inﬁnite sets, in particular the set of all natural numbers. We can use
any of these items, speak about them, etc., as we please, when we are describing
or building the formal theorywithin our metatheory.
Now, if we are not Platonists, then our “real” mathematical world is much
more restricted. In one extreme, we havenoinﬁnite sets.
†
We can still manage to deﬁne our formal language! After all, the “non-
ending” sequence of object variablesv
0,v1,v2,...can beﬁnitely generatedin
at least two different ways, as we have already seen. Thus we can explain (to
a true formalist or ﬁnitist) that “non-ending sequence” was an unfortunate slip
of the tongue, and that we really meantto give aprocedureof how to generate
on demand anewobject variable, different from whatever ones we may already
have.
Two parting comments are in order: One, we have been somewhat selective
in the use of the term “metavariable”. We have calledx,x

,ymetavariables,
but have implied that thev
iare formal variables, even if they are justnames
of formal objects such that we do not know or do not care what they look like.
Well, strictly speaking the abbreviationsv
iare also metavariables, but they are
endowed with a property that the “generic” metavariables likex,y,z

do not
have: Distinctv
inames denote distinct object variables (cf. I.1.3).
Two, we should clarify that a formal theory, whenused(i.e., the simulator
isbeing“run”) isageneratorofstrings,notadecider or“parser”.Thus, it
cangenerateany of the following: variables (if these are given by procedures),
formulas and terms (to be deﬁned), or theorems (to be deﬁned).Decisionissues,
no matter how trivial, the system is not built to handle. These belong tothe
metatheory. In particular, the theory does not see whatever numbers or strings
(like 12005) may be hidden in a variable name (such asv
12005).
Examples of decision questions: Is this string a term or a formula or a variable
(ﬁnitely generated as above)? All these questions are “easy”. They are algo-
rithmically decidable in the metatheory. Or, is this formula a theorem? This is
†
A ﬁnitist – and don’t forget that Hilbert-style metatheory was ﬁnitary, ostensibly for political
reasons – will let you have as many integers as you like in one serving, as long as the serving
isﬁnite. If you ask for more, you can have more, but never the set of all integers or an inﬁnite
subset thereof.

I.1. First Order Languages 13
algorithmically undecidable in the metatheory if it is a question about Peano
arithmetic or set theory.
I.1.4 Deﬁnition (Terminology about Strings).A symbol sequence orexpres-
sion(orstring) that is formed by using symbols exclusively out of a given set
†
Mis calleda string over the set, or alphabet, M.
IfAandBdenote strings (say, overM), then the symbolA∗B, or more
simplyAB, denotes the symbol sequence obtained by listing ﬁrst the symbols
ofAin the given left to right sequence, immediately followed by the symbols of
Bin the given left to right sequence. We say thatABis (more properly, denotes
or names) theconcatenationof the stringsAandBin that order.
We denote the fact that the strings (named)CandDareidentical sequences
(but we just say that they areequal) by writingC≡D. The symbolι ≡denotes
the negation of the string equality symbol≡. Thus, if # and ? are (we do mean
“are”) symbols from an alphabet, then
#??≡#?? but #?ι ≡#??
We can also employ≡in contexts such as “letA≡##?”, where we give the
nameAto the string ##?.
‡
In this book the symbol≡will be exclusivelyused in the metatheoryfor equality
of strings over some setM.
The symbolλnormally denotes theemptystring, and we postulate for it the
following behaviour:
A≡Aλ≡λA for all stringsA
We say thatA occurs in B,orisasubstring of B, iff there are stringsCandD
such thatB≡CAD.
For example, “(” occurs four times in the (explicit) string “¬(()∨)((”, at
positions2, 3, 7, 8. Each time this happens we have anoccurrenceof “(” in
“¬(()∨)((”.
IfC≡λ, we say thatAis apreﬁxofB. If moreoverDι ≡λ, then we say
thatAis aproper preﬁxofB.
ε
†
A set that supplies symbols to be used in building strings is notspecial. It is just a set. However,
it often has a special name: “alphabet”.
‡
Punctuation such as “.” is not part of the string. One often avoids such footnotes by enclosing
strings that are explicitly written as symbol sequences inside quotes. For example, ifAstands
for the string #, one writesA≡“#”. Note that we must not write “A”, unless we mean a string
whose only symbolis A.

14 I. Basic Logic
I.1.5 Deﬁnition (Terms).The set ofterms,Term, is thesmallestset of strings
over the alphabetVwith the following two properties:
(1) All of the items inLS.1orNLS.1(x,y,z,a,b,c, etc.) are included.
(2) Iffis a function
†
of aritynandt 1,t2,...,t nare included, then so is the
string “ft
1t2...tn”.
The symbolst,s, andu, with or without subscripts or primes, will denote
arbitrary terms. Since we are using them in themetalanguageto “vary over”
terms, we naturally call them metavariables. They also serve – as variables –
towards the deﬁnition (this one) of thesyntaxof terms. For this reason they are
also calledsyntactic variables.
ε
I.1.6 Remark.(1) We often abuse notation and writef(t 1,...,t n) instead of
ft
1...tn.
(2) Deﬁnition I.1.5 is aninductive deﬁnition.
‡
It deﬁnes a more or less
“complicated” term by assuming that we already know what “simpler” terms
look like. This is a standard technique employed in real mathematics. We will
have the opportunity to say more about such inductive deﬁnitions – and their
appropriateness – in a
-comment later on.
(3) We relate this particular manner of deﬁning terms to our working def-
inition of a theory (given on p. 6 immediately before Remark I.1.1 in terms
of “rules” of formation). Item (2) in I.1.5 essentially says that we build new
terms (from old ones) by applying the followinggeneral rule: Pick an arbitrary
function symbol, sayf. This has a speciﬁc formation rule associated with it
that, for the appropriate number,n, of an already existing ordered list of terms,
t
1,...,t n, will build the new term consisting off, immediately followed by
the ordered list of the given terms.
To be speciﬁc, suppose we are working in the language of number theory.
There is a function symbol+available there. The rule associated with+builds
the new term+tsfor any prior obtained termstands. For example,+v
1v13
and+v 121+v1v13are well-formed terms. We normally write terms of number
theory in “inﬁx” notation,
§
i.e.,t+s,v 1+v13andv 121+(v1+v13) (note the
intrusion of brackets, to indicate sequencing in the application of+).
†
We will omit from now on the qualiﬁcation “symbol” from terminology such as “function sym-
bol”, “constant symbol”, “predicate symbol”.
‡
Some mathematicians will absolutely insist that we call this arecursivedeﬁnition and reserve
the term “induction” for “inductionproofs”. This is seen to be unwarranted hair splitting if we
consider that Bourbaki (1966b) callsinduction proofs“d´emonstrations par r´ecurrence”. We will
be less dogmatic: Either name is all right.
§
Function symbol placed between the arguments.

I.1. First Order Languages 15
A by-product of what we have just described is thatthe arity of a function
symbol f is whatever number of terms the associated rule will require as input.
(4) A crucial word used in I.1.5 (which recurs in all inductive deﬁnitions) is
“smallest”. It means “least inclusive” (set). For example, we may easily think of
a set of strings that satisﬁes both conditions of the above deﬁnition, but which is
not“smallest” by virtue of having additional elements, such as the string “¬¬(”.
Pause.Why is “¬¬(”notin the smallest set as deﬁned above, and therefore
not a term?
The reader may wish to ponder further on the import of the qualiﬁcation
“smallest” by considering the familiar (similar) example ofN, the set of natural
numbers. The principle of induction inNensures that this set is thesmallest
with the properties:
(i) 0 is included, and
(ii) ifnis included, then so isn+1.
By contrast, all ofZ(set of integers),Q(set of rational numbers),R(set of real
numbers) satisfy (i) and (ii), but they are clearlynotthe “smallest” such.
ε
I.1.7 Deﬁnition (Atomic Formulas).The set ofatomic formulas,Af, contains
precisely:
(1) The stringst=sfor every possible choice of termst,s.
(2) The stringsPt
1t2...tnfor every possible choice ofn-ary predicatesP(for
all choices ofn>0) and all possible choices of termst
1,t2,...,t n.ε
We often abuse notation and writeP(t 1,...,t n) instead ofPt 1...tn.
I.1.8 Deﬁnition (Well-Formed Formulas).The set ofwell-formed formulas,
Wff, is thesmallestset of strings or expressions over the alphabetVwith the
following properties:
(a) All the members ofAfare included.
(b) IfAandBdenote strings (overV) that are included, then (A∨B) and
(¬A) are also included.
(c) IfAis
†
a string that is included andxisanyobject variable (which may or
may not occur (as asubstring) in the stringA), then the string ((∃x)A)is
also included. We say thatAis thescopeof (∃x).
ε
†
Denotes!

16 I. Basic Logic
I.1.9 Remark.
(1) The above is yet another inductive deﬁnition. Its statement (in the metalan-
guage) is facilitated by the use of so-calledsyntactic, or meta, variables –
AandB– used asnamesforarbitrary(indeterminate) formulas. In gen-
eral, we will let calligraphic capital lettersA,B,C,D,E,F,G(with or
without primes or subscripts) be names for well-formed formulas, or just
formulas, as we often say. The deﬁnition ofWffgiven above is standard.
In particular, it permits well-formed formulas such as ((∃x)((∃x)x=0)) in
the interest of making theformation rules“context-free”.
†
(2) The rules of syntax just given do not allow us to write things such as∃for
∃PwherefandPare function and predicate symbols respectively. That
quantiﬁcation is deliberately restricted toact solely on object variables
makes the languageﬁrst order.
(3) We have already indicated in Remark I.1.6 where the arities (of function and
predicate symbols) come from (Deﬁnitions I.1.5 and I.1.7 referredto them).
These are numbers that are implicit (“hardwired”) with the formation rules
for terms and atomic formulas. Each function and each predicate symbol
(e.g.,+,×,∈,<) has its own unique formation rule. This rule “knows” how
many terms are needed (on the input side) in order to form a term or atomic
formula. Therefore, since the theory,in use, applies rather than studies its
formation rules, it is, in particular, ignorant of arities of symbols.
Now that this jurisdictional point has been made (cf. the concluding
remarks about decision questions, on p. 12), we can consider an alternative
way of making arities of symbols known (in themetatheory): Rather than
embedding arities in the formation rules, we can hide them in the ontology
of the symbols, not making them explicit in the name.
For example, a new symbol, say∗, can be used to record arity. That
is, we can think of a predicate (or function) symbol as consisting of two
parts: an arity part and an “all the rest” part, the latter needed to render the
symbol unique.
‡
For example,∈may be actually the name for the symbol
“∈
∗∗
”, where this latter name is identical to the symbol it denotes, or “what
you see is what you get” – see Remark I.1.3(1) and (2), p. 8. The presence
of the two asterisks declares the arity. Some people say this differently:
They make available to the metatheory a “function”,ar, from “the set of
†
In some presentations, the formation rule in I.1.8(c) is “context-sensitive”: It requires thatxbe
notalready quantiﬁed inA.
‡
The reader may want to glimpse ahead, on p. 166, to see a possible implementation in the case
of number theory.

I.1. First Order Languages 17
all predicate symbols and functions” (of a given language) to the natural
numbers, so that for any function symbolfor predicate symbolP,ar(f)
andar(P) yield the arities offandPrespectively.
†
(4)Abbreviations
Abr1.The string ((∀x)A) abbreviates the string “(¬((∃x)(¬A)))”. Thus,
for any explicitly written formulaA, the former notation is infor-
mal (metamathematical), while the latter is formal (within the formal
language). In particular,∀is a metalinguistic symbol. “∀x” is theuni-
versal quantiﬁer.Ais its scope. The symbol∀is pronouncedfor all.
We also introduce – in the metalanguage – a number of additional Boolean
connectives in order to abbreviate certain strings:
Abr2.(Conjunction,∧)(A∧B) stands for (¬((¬A)∨(¬B))). The
symbol∧is pronouncedand.
Abr3.(Classical or material implication,→)(A→B) stands for
((¬A)∨B). (A→B) is pronouncedifA, thenB.
Abr4.(Equivalence,↔)(A↔B) stands for ((A→B)∧(B→A)).
Abr5.To minimize the use of brackets in the metanotation we adopt stan-
dardprioritiesof connectives:∀,∃, and¬have the highest, and then
we have (in decreasing order of priority)∧,∨,→,↔, and we agree
not to use outermost brackets. Allassociativitiesareright– that is,
if we writeA→B→C, then this is a (sloppy) counterpart for
(A→(B→C)).
(5) The language just deﬁned,L,isone-sorted, that is, it has a singlesortor
typeof object variable. Is this not inconvenient? After all, our set theory
(volume 2 of these lectures) will have bothatomsandsets. In other theories,
e.g., geometry, one has points, lines, and planes. One would have hoped to
have different “types” of variables, one for each.
Actually, to do this would amount to a totally unnecessary complication
of syntax. We can (and will) get away with justonesort of object variable.
For example, in set theory we will also introduce a 1-ary
‡
predicate,U,
whose job is to “test” an object for “sethood”.
§
Similar remedies are avail-
able to other theories. For example, geometry will manage with one sort of
variable and unary predicates “Point”, “Line”, and “Plane”.
†
In mathematics we understand a function as a set of input–output pairs. One can “glue” the two
parts of such pairs together, as in “∈
∗∗
” – where “∈” is the input part and “∗∗” is the output part,
the latter denoting “2” – etc. Thus, the two approaches are equivalent.
‡
More commonly calledunary.
§
People writing about, or teaching, set theory have made this word up. Of course, one means by
it the property of being a set.

18 I. Basic Logic
Aproposlanguage, some authors emphasize the importance of the
nonlogical symbols, taking at the same time the formation rules for
granted; thus they say that we have alanguage, say, “L={∈,U}” rather
than “L=(V,Term,Wff) whereVhas∈andUas its only nonlogi-
cal symbols”. That is, they use “language” for the nonlogical part of the
alphabet.
ε
A variable that is quantiﬁed isbound in the scope of the quantiﬁer. Non-
quantiﬁed variables arefree. We also give below, by induction on formulas,
precise (metamathematical) deﬁnitions of “free” and “bound”.
I.1.10 Deﬁnition (Free and Bound Variables).An object variablexoccurs
freein a termtor atomic formulaAiff it occurs intorAas a substring
(see I.1.4).
xoccurs free in (¬A) iff it occurs free inA.
xoccurs free in (A∨B) iff it occurs free in at least oneofAorB.
xoccurs free in ((∃y)A)iffxoccurs free inA,and yis not the same
variable asx.
†
Theyin ((∃y)A) is, of course,notfree – even if it might be so inA–as
we have just concluded in this inductive deﬁnition. We say that it isboundin
((∃y)A). Trivially, terms and atomic formulas have no bound variables.
ε
I.1.11 Remark.(1) Of course, Deﬁnition I.1.10 takes care of the deﬁned con-
nectives as well, via the obvious translation procedure.
(2)Notation.IfAis a formula, then we often writeA[y
1,...,y k] to indicate
our interest in the variablesy
1,...,y k, which may or may not be free inA.
Indeed, there may be other free variables inAthat we may have chosen not to
include in the list.
On the other hand, if we useroundbrackets, as inA(y
1,...,y k), then we
are implicitly asserting thaty
1,...,y kis thecomplete listof free variables that
occur inA.
ε
I.1.12 Deﬁnition.A term or formula isclosediff no free variables occur in it.
A closed formula is called asentence.
A formula isopeniff it contains no quantiﬁers (thus, an open formula may
also be closed).
ε
†
Recall thatxandyare abbreviations of names such asv 1200098andv 11009(which name distinct
variables). However, it could be that bothxandynamev
101. Therefore it isnotredundant to say
“and yis not the same variable asx”. By the way,xι ≡ysays the same thing, by I.1.4.

I.2. A Digression into the Metatheory 19
I.2. A Digression into the Metatheory:
Informal Induction and Recursion
We have already seen a number of inductive or recursive deﬁnitions in Sec-
tion I.1. The reader, most probably, has already seen or used such deﬁnitions
elsewhere.
We will organize the common important features of inductive deﬁnitions
in this section, for easy reference. We just want to ensure that our grasp of
these notions and techniques,at the metamathematical level, is sufﬁcient for
the needs of this volume.
One builds a setSbyrecursion,orinductively(or by induction), out of two
ingredients: a set ofinitial objects,I, and a set ofrulesoroperations,R.A
member ofR– a rule – is a (possibly inﬁnite)table,orrelation, like
y1...y nz
a1...a nan+1
b1...b nbn+1
.
.
.
.
.
.
. . .
If the above rule (table) is calledQ, then we use the notations
†
Q(a1,...,a n,an+1) andξa 1,...,a n,an+1ςηQ
interchangeably to indicate that theordered sequenceor “row”a
1,...,a n,an+1
is present in the table.
We say that “Q(a
1,...,a n,an+1) holds” or “Q(a 1,...,a n,an+1) is true”,
but we often also say that “Qapplied toa
1,...,a nyieldsa n+1”, or that “a n+1
is aresultoroutputofQ, when the latter receivesinput a 1,...,a n”. We often
abbreviate such inputs usingvector notation, namely,ϕa
n(or justϕa,ifnis
understood). Thus, we may writeQ(ϕa
n+1) forQ(a 1,...,a n,an+1).
A ruleQthat hasn+1 columns is called (n+1)-ary.
I.2.1 Deﬁnition.We say “a setTisclosed under an(n+1)-ary rule Q”to
mean that wheneverc
1,...,c nare all inT, thend∈Tforall dsatisfying
Q(c
1,...,c n,d). ε
With these preliminary understandings out of the way, we now state
†
“x∈A” means that “xis a member of – or is in –A” in the informal set-theoretic sense.

20 I. Basic Logic
I.2.2 Deﬁnition.Sisdeﬁned by recursion,orbyinduction, from initial objects
Iand set of rulesR, provided it is thesmallest(least inclusive) set with the
properties
(1)I⊆S,
†
(2)Sis closed under everyQinR. In this case we say thatSisR-closed.
We writeS=Cl(I,R), and say that “Sis theclosure ofIunderR”.
ε
We have at once:
I.2.3 Metatheorem (Induction onS).If S=Cl(I,R)and if some set T
satisﬁes
(1)I⊆T , and
(2)T is closed under every Q inR,
then S⊆T.
Pause.Why is the above ametatheorem?
The above principle of induction onSis often rephrased as follows: To prove
that a propertyP(x) holds for all members of Cl(I,R), just prove that
(a) every member ofIhas the property, and
(b) theproperty propagates with every rule inR, i.e., ifP(c
i) holds (is true)
fori=1,...,n, and ifQ(c
1,...,c n,d) holds, thendtoo has the property
P(x) – that is,P(d) holds.
Of course, this rephrased principle is valid, for if we letTbe the set of all
objects that have propertyP(x) – for which set one employs the well-established
symbol{x:P(x)}– then thisTsatisﬁes (1) and (2) of themetatheorem.
‡
I.2.4 Deﬁnition (Derivations and Parses).A(I,R)-derivation, or simplyde-
rivation–ifIandRare understood – is a ﬁnite sequence of objectsd
1,...,d n
†
From our knowledge of elementary informal set theory, we recall thatA⊆Bmeans that every
member ofAis also a member ofB.
‡
We are sailing too close to the wind here! It turns out that not all propertiesP(x) lead tosets
{x:P(x)}. Our explanation was na¨ıve. However, formal set theory, which is meant to save us from
our na¨ıvet´e, upholds the “principle” (a)–(b) using just a slightly more complicated explanation.
The reader can see this explanation in our volume 2 in the chapter on cardinality.

I.2. A Digression into the Metatheory 21
(n≥1) such that eachd
iis
(1) a member ofI,or
†
(2) for some (r+1)-aryQ∈R,Q(d j1
,...,d jr
,di) holds, andj l<ifor
l=1,...,r.
We say thatd
iisderivable within i steps.
A derivation of an objectAis also called aparseofa.
ε
Trivially, ifd 1,...,d nis a derivation, then so isd 1,...,d mfor any 1≤m<n.
Ifdis derivable withinnsteps, it is also derivable inksteps or less, for all
k>n, since we can lengthen a derivation arbitrarily by addingI-elements
to it.
I.2.5 Remark.The following metatheorem shows that there is a way to “con-
struct” Cl(I,R) iteratively, i.e., one element at a timeby repeated application
of the rules.
This result shows deﬁnitively that our inductive deﬁnitions of terms (I.1.5)
and well-formed formulas (I.1.8) fully conform with our working deﬁnition of
theory, as an alphabet and a set of rules that are used to build formulas and
theorems (p. 5).
ε
I.2.6 Metatheorem.
Cl(I,R)={x:xis(I,R)-derivable within some number of steps, n}
Proof.For notational convenience let us write
T={x:xis (I,R)-derivable within some number of steps,n}.
As we know from elementary na¨ıve set theory, we need to show here both
Cl(I,R)⊆Tand Cl(I,R)⊇Tto settle the claim.
(⊆)Wedo induction on Cl(I,R) (usingI.2.3). NowI⊆T, sinceevery
member ofIis derivable inn=1 step. (Why?)
Also,Tis closed under everyQinR. Indeed, let such an (r+1)-aryQbe
chosen, and assume
Q(a
1,...,a r,b)( i)
†
This “or” is inclusive: (1), or (2), or both.

22 I. Basic Logic
and{a
1,...,a r}⊆T. Thus, eacha ihasa(I,R)-derivation. Concatenate all
these derivations:
...,a
1,...,a 2,...,...,a r
The above is a derivation (why?). But then, so is
...,a
1,...,a 2,...,...,a r,b
by (i). Thus,b∈T.
(⊇) We argue this – that is, “ifd∈T, thend∈Cl(I,R)” – by induction
on the number of steps,n, in whichdis derivable.
Forn=1wehaved∈Iand we are done, sinceI⊆Cl(I,R).
Let us make the induction hypothesis (I.H.) that for derivations of≤nsteps
the claim is true. Let thendbe derivable withinn+1 steps. Thus, there is a
derivationa
1,...,a n,d.
Now, ifd∈I, we are done as above (is this a “real case”?) If on the other
handQ(a
j1
,...,a jr
,d), then fori=1,...,rwe havea ji
∈Cl(I,R)bythe
I.H.; henced∈Cl(I,R), since the closure is closed under allQ∈R.
ε
I.2.7 Example.One can see now thatN=Cl(I,R), whereI={0}andR
contains just the relationy=x+1 (inputx, outputy). Similarly,Z, the set
of all integers, is Cl(I,R), whereI={0}andRcontains just the relations
y=x+1 andy=x−1 (inputx, outputy).
For the latter, the inclusion Cl(I,R)⊆Zis trivial (by I.2.3). For⊇we
easily see that anyn∈Zhas a (I,R)-derivation (and then we are done by I.2.6).
For example, ifn>0, then 0,1,2,...,nis a derivation, while ifn<0, then
0,−1,−2,...,nis one. Ifn=0, then the one-term sequence 0 is a derivation.
Another interesting closure is obtained byI={3}and the two relations
z=x+yandz=x−y. This is the set{3k:k∈Z}(see Exercise I.1).
ε
Pause.So, taking the ﬁrst sentence of I.2.7 one step further, we note that we
have justprovedtheinduction principleforN, for that is exactly what the
“equation”N=Cl(I,R) says (by I.2.3). Do you agree?
There is another way to view the iterative construction of Cl(I,R): The
set is constructedin stages. Below we are using some more notation borrowed
from informal set theory. For any setsAandBwe writeA∪Bto indicate the
setunion, which consists of all the members found inAorBor in both. More
generally, if we have a lot of sets,X
0,X1,X2,...,that is, oneX ifor every
integeri≥0 – which we denote by the compact notation (X
i)i≥0– then we
may wish to form a set that includesallthe objects found as members all over
theX
i, that is (usinginclusive, or logical, “or”s below), form
{x:x∈X
0orx∈X 1or...}

I.2. A Digression into the Metatheory 23
or, more elegantly and precisely,
{x: for somei≥0,x∈X
i}
The latter is called the union of the sequence (X
i)i≥0and is often denoted by
∃
i≥0
Xior
∃
i≥0
Xi
Correspondingly, we write
∃
i≤n
Xior
∃
i≤n
Xi
if we only want to take a ﬁnite union, also indicated clumsily asX 0∪...∪X n.
I.2.8 Deﬁnition (Stages).In connection with Cl(I,R) we deﬁne the sequence
of sets (X
i)i≥0by induction onn, as follows:
X
0=I
X
n+1=
∈
∃
i≤n
Xi
∅
∪
∼
b: for someQ∈Rand someϕa
nin
∃
i≤n
Xi,Q(ϕa n,b)

That is, to formX
n+1we append to

i≤n
Xiall the outputs of all the relations
inRacting on all possible inputs, the latter taken from

i≤n
Xi.
We say thatX
iis built atstage i, from initial objectsIand rule-setR. ε
In words, at stage 0 we are given the initial objects (X 0=I). At stage 1 we
apply all possible relations to all possible objectsthat we have so far– they
form the setX
0– and build the 1st stage set,X 1, by appending the outputs to
what we have so far. At stage 2 we apply all possible relations to all possible
objectsthat we have so far– they form the setX
0∪X1– and build the 2nd
stage set,X
2, by appending the outputs to what we have so far. And so on.
When we work in the metatheory, we take for granted that we can have
simple inductive deﬁnitions on the natural numbers.The reader is familiar with
several such deﬁnitions, e.g.,
a
0
=1 (foraι =0 throughout)
a
n+1
=a·a
n

24 I. Basic Logic
We will (meta)prove a general theorem on the feasibility of recursive deﬁnitions
later on (I.2.13).
The following theorem connects stages and closures.
I.2.9 Metatheorem.With the X ias inI.2.8,
Cl(I,R)=
∃
i≥0
Xi
Proof.(⊆) We do induction on Cl(I,R). For the basis,I=X 0⊆

i≥0
Xi.
We show that

i≥0
XiisR-closed. LetQ∈RandQ(ϕa n,b) hold, for some
ϕa
nin

i≥0
Xi. Thus, by deﬁnition of union, there are integersj 1,j2,...,j n
such thata i∈Xji
,i=1,...,n.Ifk=max{j 1,...,j n}, thenϕa nis in

i≤k
Xi;
henceb∈X
k+1⊆

i≥0
Xi.
(⊇) It sufﬁces to prove thatX
n⊆Cl(I,R), a fact we can prove by induction
onn.Forn=0 it holds by I.2.2. As an I.H. we assume the claim for alln≤k.
The case fork+1:X
k+1is the union of two sets. One is

i≤k
Xi. This is a
subset of Cl(I,R) by the I.H. The other is

b: for someQ∈Rand someϕain

i≤k
Xi,Q(ϕa,b)

This too is a subset of Cl(I,R), by the preceding observation and the fact that
Cl(I,R)isR-closed.
ε
Worth Saying.An inductively deﬁned set can be built by stages.
I.2.10 Deﬁnition (Immediate Predecessors, Ambiguity).Ifd∈Cl(I,R)
and for someQanda
1,...,a rit is the case thatQ(a 1,...,a r,d), then the
a
1,...,a rareimmediate Q-predecessorsofd, or justimmediate predecessors
ifQis understood; for short, i.p.
A pair (I,R) is calledambiguousif somed∈Cl(I,R) satisﬁes any (or
all) of the following conditions:
(i) It has two (or more) distinct sets of immediateP-predecessors for some
ruleP.
(ii) It has both immediateP-predecessorsandimmediateQ-predecessors, for
Pι =Q.
(iii) It is a member ofI, yet it has immediate predecessors.
If (I,R) is not ambiguous, then it isunambiguous.
ε

I.2. A Digression into the Metatheory 25
I.2.11 Example.The pair ({00,0},{Q}), whereQ(x,y,z) holds iffz=xy
(where “xy” denotes the concatenation of the stringsxandy, in that order), is
ambiguous. For example, 0000 has the two immediate predecessor sets{00,00}
and{0,000}. Moreover, while 00 is an initial object, it does have immedi-
ate predecessors, namely, the set{0,0}(or, what amounts to the same thing,
{0}).
ε
I.2.12 Example.The pair (I,R), whereI={3}andRconsists ofz=x+y
andz=x−y, is ambiguous. Even 3 has (inﬁnitely many) distinct sets of i.p.
(e.g., any{a,b}such thata+b=3, ora−b=3).
The pairs that effect the deﬁnition ofTerm(I.1.5) andWff(I.1.8) are un-
ambiguous (see Exercises I.2 and I.3).
ε
I.2.13 Metatheorem (Deﬁnition by Recursion).Let(I,R)beunambiguous
andCl(I,R)⊆A, where A is some set. Let also Y be a set, and
†
h:I→Y
and g
Q, for each Q∈R, be given functions. For any(r+1)-ary Q, an input for
the function g
Qis a sequenceξa,b 1,...,b rςwhere a is in A and the b1,...,b r
are all inY . All the g Qyield outputsin Y .
Under these assumptions, there is auniquefunction f: Cl(I,R)→Y
such that
y=f(x)iff







y=h(x)andx∈I
or, for some Q∈R,
y=g
Q(x,o1,...,o r)andQ(a 1,...,a r,x)holds,
where o
i=f(a i),for i=1,...,r
(1)
The reader may wish to skip the proof on ﬁrst reading.
Proof. Existencepart.For each (r+1)-aryQ∈R,deﬁne↔Qby
‡
↔Q(ξa
1,o1ς,...,ξa r,orς,ξb,g Q(b,o1,...,o r)ς)iffQ(a 1,...,a r,b) (2)
For anya 1,...,a r,b, the above deﬁnition of↔Qis effected for all possible
choices ofo
1,...,o rsuch thatg Q(b,o1,...,o r) is deﬁned.
Collect now all the↔Qto form a set of rules↔R.
Let also↔I={ξx,h(x)ς:x∈I}.
†
The notationf:A→Bis common in informal (and formal) mathematics. It denotes a function
fthat receives “inputs” from the setAand yields “outputs” in the setB.
‡
For a relationQ, writing just “Q(a 1,...,a r,b)” is equivalent to writing “Q(a 1,...,a r,b) holds”.

26 I. Basic Logic
We will verify that the setF=Cl(↔I,↔R) is a 2-ary relation that for every
input yieldsat most oneoutput, and therefore is a function. For such a relation
it is customary to write, letting the context fend off the obvious ambiguity in
the use of the letterF,
y=F(x)iffF(x,y)( ∗)
We will further verify that replacingfin (1) above byFresults in a valid
equivalence (the “iff” holds). That is,Fsatisﬁes (1).
(a) We establish thatFis a relation composed of pairsξx,yς(xis input,yis
output), wherex∈Cl(I,R) andy∈Y. This follows easily by induction
onF(I.2.3), since↔I⊆F, and the property (of “containing such pairs”)
propagates witheach↔Q(recall that theg
Qyield outputs inY).
(b) We next show that “ifξx,yςηFandξx,zςηF, theny=z”, that is,Fis
“single-valued” or “well-deﬁned”, in short, it is afunction.
We again employ induction onF,thinking of the quoted statement as a
“property” of the pairξx,yς:
Suppose thatξx,yςη↔I, and let alsoξx,zςηF.
By I.2.6,ξx,zςη↔I,or↔Q(ξa
1,o1ς,...,ξa r,orς,ξx,zς), where
Q(a
1,...,a r,x) andz=g Q(x,o1,...,o r), for some (r+1)-ary↔Qand
ξa
1,o1ς,...,ξa r,orςinF.
The right hand side of the italicized “or” cannot hold for anunambiguous
(I,R), sincexcannot have i.p. Thusξx,zςη↔I; hencey=h(x)=z.
To prove that the property propagates with each↔Q, let
↔Q(ξa
1,o1ς,...,ξa r,orς,ξx,yς)
but also
↔P
ξς
b
1,o

1
ϕ
,...,
ς
b
l,o

l
ϕ
,
ς
x,z
ϕυ
whereQ(a
1,...,a r,x),P(b 1,...,b l,x), and
y=g
Q(x,o1,...,o r) andz=g P
ξ
x,o

1
,...,o

l
≥
(3)
Since (I,R) is unambiguous, we haveQ=P(hence also↔Q=↔P),r=l,
anda
i=bifori=1,...,r.
By I.H.,o
i=o

i
fori=1,...,r; hencey=zby (3).
(c) Finally, we show thatFsatisﬁes (1). We do induction on Cl(↔I,↔R) to prove:
(←)Ifx∈Iandy=h(x), thenF(x,y) (i.e.,y=F(x)inthe
alternative notation (∗)), since↔I⊆F. Let nexty=g
Q(x,o1,...,o r)
andQ(a
1,...,a r,x), where alsoF(a i,oi), fori=1,...,r. By (2),
↔Q(ξa
1,o1ς,...,ξa r,orς,ξx,g Q(x,o1,...,o r)ς); thus –Fbeing closed

I.2. A Digression into the Metatheory 27
under all the rules in≤R–F(x,g
Q(b,o1,...,o r)) holds; in short,F(x,y)
ory=F(x).
(→) Now we assume thatF(x,y) holds and we want to infer the right
hand side (ofiff) in (1). We employ Metatheorem I.2.6.
Case 1.Letξx,yςbeF-derivable
†
inn=1 step. Thenξx,yςη↔I. Thus
y=h(x).
Case 2.Suppose next thatξx,yςisF-derivable withinn+1 steps,
namely, we have a derivation
ξx
1,y1ς,ξx2,y2ς,...,ξx n,ynς,ξx,yς (4)
where↔Q(ξa
1,o1ς,...,ξa r,orς,ξx,yς) andQ(a 1,...,a r,x) (see (2)),
and each ofξa
1,o1ς,...,ξa r,orςappears in the above derivation, to
the left ofξx,yς. This entails (by (2)) thaty=g
Q(x,o1,...,o r). Since
theξa
i,oiςappear in (4),F(a i,oi) holds, fori=1,...,r. Thus,ξx,yς
satisﬁes the right hand side ofiffin (1), once more.
Uniquenesspart. Let the functionKalso satisfy (1). We show, by induction
on Cl(I,R), that
For allx∈Cl(I,R) and ally∈Y, y=F(x)iffy=K(x) (5)
(→) Letx∈I, andy=F(x). By lack of ambiguity, the case conditions
of (1) are mutually exclusive. Thus, it must be thaty=h(x). But then,y=K(x)
as well, sinceKsatisﬁes (1) too.
Let nowQ(a
1,...,a r,x) andy=F(x). By (1), there are (unique, as we now
know)o
1,...,o rsuch thato i=F(a i) fori=1,...,r, andy=g Q(x,o1,...,
o
r). By the I.H.,o i=K(a i). But then (1) yieldsy=K(x) as well (sinceK
satisﬁes (1)).
(←) Just interchange the lettersFandKin the above argument.
ε
The above clearly is valid for functionshandg Qthat may fail to be deﬁned
everywhere in their “natural” input sets. To be able to have this degree of
generality without having to state additionaldeﬁnitions (such asleft ﬁelds,
right ﬁelds,partial functions,total functions,nontotal functions, Kleene “weak
equality”), we have stated the recurrence (1) the way we did (to keep an eye on
both the input and output side of things) rather than the “usual”
f(x)=

h(x) ifx∈I
g
Q(x,f(a 1),...,f(a r))ifQ(a 1,...,a r,x) holds
†
Cl(↔I,↔R)-derivable.

28 I. Basic Logic
Of course, if all theg
Qandhare deﬁned everywhere on their input sets (i.e.,
they are “total”), thenfis deﬁned everywhere on Cl(I,R) (see Exercise I.4).
I.3. Axioms and Rules of Inference
Now that we have our language,L, we will embark on using it to formally
effectdeductions. These deductions start at theaxioms. Deductions employ
“acceptable” purely syntactic – i.e., based onform, not onmeaning– rules that
allow us to write a formula down (todeduceit) solely because certain other
formulasthat are syntactically related to itwere already deduced (i.e., already
written down). These string-manipulation rules are calledrules of inference.
We describe in this section the axioms and the rules of inference that we will
accept into our logical calculus and that are common to all theories.
We start with a precisedeﬁnition oftautologiesin our ﬁrst order languageL.
I.3.1 Deﬁnition (Prime Formulas in Wff. Propositional Variables).A for-
mulaA∈Wffis aprime formulaor apropositional variableiff it is either of
Pri1.atomic,
Pri2.a formula of the form ((∃x)A).
We use the lowercase lettersp,q,r(with or without subscripts or primes) to
denote arbitrary prime formulas (propositional variables) of our language.
ε
That is, a prime formula has either no propositional connectives, or if it does, it hides them inside the scope of (∃x).
We may think of a propositional variable as a “blob” that a myopic being
makes out of a formula described in I.3.1. The same being will see an arbitrary
well-formed formula as a bunch of blobs, brackets, and Boolean connectives
(¬,∨), “correctly connected” as stipulated below.
†I.3.2 Deﬁnition (Propositional Formulas).The set of propositional formulas
overV, denoted here byProp, is the smallest set such that:
(1) Every propositional variable (overV)isinProp.
(2) IfAandBare inProp, then so are (¬A) and (A∨B).
We use the lowercase lettersp,q,r(with or without subscripts or primes) to
denote arbitrary prime formulas (propositional variables) of our language.
ε
†
Interestingly, our myopecansee the brackets and the Boolean connectives.

I.3. Axioms and Rules of Inference 29
I.3.3 Metatheorem. Prop=Wff.
Proof.(⊆) We do induction onProp. Every item in I.3.2(1) is inWff.Wff
satisﬁes I.3.2(2) (see I.1.8(b)). Done.
(⊇) We do induction onWff. Every item in I.1.8(a) is a propositional variable
(overV), and hence is inProp.
Proptrivially satisﬁes I.1.8(b). It also satisﬁes I.1.8(c), for ifAis inProp,
then it is inWffby the⊆-direction, above. Then, by I.3.1, ((∃x)A) is a propo-
sitional variable and hence inProp. We are done once more.
ε
I.3.4 Deﬁnition (Propositional Valuations).We can arbitrarily assign a value
of0or1toeveryAinWff(orProp) as follows:
(1) Weﬁxan assignment of 0 or 1 toevery prime formula. We can think of this
as an arbitrary but ﬁxed functionv:{all prime formulas overL}→{0,1}
in the metatheory.
(2) We deﬁne by recursionan extension ofv, denoted by ¯v:
¯v((¬A))=1−¯v(A)
¯v((A∨B))=¯v(A)·¯v(B)
where “·” above denotes number multiplication.
We call, traditionally, the values 0 and 1 by the names “true” and “false”
respectively, and writetandfrespectively.
We also call a valuationvatruth (value) assignment.
We use the jargon “Atakes the truth valuet(respectively,f) under a valuation
v” to mean “¯v(A)=0 (respectively, ¯v(A)=1)”.
ε
The above inductive deﬁnition of ¯vrelies on the fact that Deﬁnition I.3.2 of
Propis unambiguous (I.2.10, p. 24), or that a propositional formula isuniquely
readable(orparsable) (see Exercises I.6 and I.7). It employs the metatheorem
on recursive deﬁnitions (I.2.13).
The reader may think that all this about unique readability is just an annoying
quibble. Actually it can be a matter of life and death. The ancient Oracle of
Delphi had the nasty habit of issuing ambiguous – not uniquely readable, that
is – pronouncements. One famous such pronouncement, rendered in English,
went like this: “You will go you will return not dying in the war”.
†
Given that
ancient Greeks did not use punctuation, the above has two diametrically opposite
meanings depending on whether you put a commabeforeorafter“not”.
†
The original was “Iξ εις αϕιξ ειςoυ θ νηξ εις εν πoλεµω
ι
”.

30 I. Basic Logic
The situation with formulas inPropwould have been as disastrous in the
absence of brackets – which serve as punctuation – because unique readability
would not be guaranteed: For example, for three distinct prime formulasp,q,r
we could ﬁnd avsuch that ¯v(p→q→r)isdifferentdepending on whether
we meant to insert brackets around “p→q” or around “q→r” (can you ﬁnd
such av?).
I.3.5 Remark (Truth Tables).Deﬁnition I.3.4 is often given in terms oftruth-
functions. For example, we could have deﬁned (in the metatheory, of course)
the functionF
¬:{t,f}→{t,f}by
F
¬(x)=

tifx=f
fifx=t
We could then say that ¯v((¬A))=F
¬(¯v(A)). One can similarly take care of
all the connectives (∨and all the abbreviations) with the help of truth functions
F
∨,F∧,F→,F↔. These functions are conveniently given via so-called truth-
tables as indicated below:
xy F¬(x)F∨(x,y)F∧(x,y)F→(x,y)F↔(x,y)
ff t f f t t
ft t t f t f
tf f t f f f
tt f t t t t
ε
I.3.6 Deﬁnition (Tautologies, Satisﬁable Formulas, Unsatisﬁable Formulas
in Wff).A formulaA∈Wff(equivalently, inProp)isatautologyiff for all
valuationsvone has ¯v(A)=t.
We call the set of all tautologies, as deﬁned here,Taut. The symbol|=
TautA
says “Ais inTaut”.
A formulaA∈Wff(equivalently, inProp)issatisﬁableiff for some valu-
ationvone has ¯v(A)=t. We say thatvsatisﬁesA.
Asetof formulas⊇is satisﬁable iff for some valuationv, one has ¯v(A)=t
for everyAin⊇. We say thatvsatisﬁes⊇.
A formulaA∈Wff(equivalently, inProp)isunsatisﬁableiff for all val-
uationsvone has ¯v(A)=f.Asetof formulas⊇is unsatisﬁable iff forall
valuationsvone has ¯v(A)=ffor someAin⊇.
ε

I.3. Axioms and Rules of Inference 31
I.3.7 Deﬁnition (Tautologically Implies, for Formulas in Wff).LetAand
⊇be respectively any formula and any set of formulas (overL).
The symbol⊇|=
TautA, pronounced “⊇tautologically impliesA”, means
thatevery truth assignmentvthat satisﬁes⊇also satisﬁesA.
ε
“Satisﬁable” and “unsatisﬁable” are terms introduced here in thepropositional
orBooleansense. These terms have a more complicated meaning when we
decide to “see” the object variables and quantiﬁers that occur in formulas.
We have at once
I.3.8 Lemma.
†
⊇|=TautAiff⊇∪{¬A}is unsatisﬁable (in the propositional
sense).If⊇=∅then⊇|= TautAsays just|= TautA, since the hypothesis “every truth
assignmentvthat satisﬁes⊇”, in the deﬁnition above, is vacuously satisﬁed.
For that reason we almost neverwrite∅|=
TautAand write instead|= TautA.
I.3.9 Exercise.For any formulaAand any two valuationsvandv

,¯v(A)=
¯v

(A)ifvandv

agree on all the propositional variables that occur inA.
In the same manner,⊇|=
TautAis oblivious tov-variations that do not affect
the variables that occur in⊇andA(see Exercise I.8).
ε
Before presenting the axioms, we need to introduce the concept ofsubstitu-
tion.
I.3.10 Tentative Deﬁnition (Substitutions of Terms). LetAbe a formula,x
an (object) variable, andta term.A[x←t] denotes the result of “replacing”
all free occurrencesofxinAby the termt,provided no variable of t was
“captured” (by a quantiﬁer) during substitution.
†
The word “lemma” has Greek origin, “λ´ηµµα”, plural “lemmata” (some people say “lemmas”)
from “λ´ηµµατ α”. It derives from the verb “λαµβ´ανω” (to take) and thus means “taken thing”.
In mathematical reasoning a lemma is a provable auxiliary statement that istakenand used as
a stepping stone in lengthy mathematical arguments – invoked therein by name, as in “...by
Lemma such and such...” – much as “subroutines” (or “procedures”) are taken and used as
auxiliary stepping stones to elucidate lengthy computer programs. Thus our purpose in having
lemmata is to shorten proofs by breaking them up into modules.

32 I. Basic Logic
If the proviso is valid, then we say that “tissubstitutable for x(inA)”, or
that “tisfree for x(inA)”. If the proviso is not valid, then the substitution is
undeﬁned.
ε
I.3.11 Remark.There are a number of issues about Deﬁnition I.3.10 that need
discussion or clariﬁcation.
Reasonable people will be satisﬁed with the above deﬁnition “as is”. How-
ever, there are some obscure points (enclosd in quotation marks above).
(1) What is this about “capture”? Well, suppose thatA≡(∃x)¬x=y. Let
t≡x.
†
ThenA[y←t]≡(∃x)¬x=x, which says something altogether
different than the original. Intuitively, this is unexpected (and undesirable):
Acodes a statement about the free variabley, i.e., a statement about all
objects which could be “values” (or meanings) ofy. One would have ex-
pected that, in particular,A[y←x]–if the substitution were allowed–
would make this very same statement about the values ofx. It does not.
‡
What happened is thatxwascaptured by the quantiﬁerupon substitution,
thus distortingA’s original meaning.
(2) Are we sure that the term “replace” is mathematically precise?
(3) IsA[x←t] always a formula, ifAis?
A re-visitation of I.3.10 via an inductive deﬁnition (by induction on terms
and formulas) settles (1)–(3) at once (in particular, the informal terms “replace”
and “capture” do not appear in the inductive deﬁnition). We deﬁne (again) the
symbolA[x←t], for any formulaA, variablex, and termt, this time by
induction on terms and formulas:
First off, let us deﬁnes[x←t], wheresis also a term, by cases:
s[x←t]≡













t ifs≡x
a ifs≡a, a constant
(symbol)
y ifs≡y, a variableι ≡x
fr
1[x←t]r 2[x←t]...r n[x←t]ifs≡fr 1...rn
Pause.Iss[x←t] always a term? That this is so follows directly by induction
on terms, using the deﬁnition by cases above and the I.H. that each ofr
i[x←t],
i=1,... ,n, is a term.
†
Recall that in I.1.4 (p. 13) we deﬁned the symbol “≡” to be equality on strings.
‡
The original says that for any objectythere is an object that is different from it;A[y←x] says
that there is an object that is different from itself.

I.3. Axioms and Rules of Inference 33
We turn now to formulas. The symbolsP,r,s(with or without subscripts)
below denote a predicate of arityn, a term, and a term (respectively):
A[x←t]≡

























s[x←t]=r[x←t]if A≡s=r
Pr
1[x←t]r 2[x←t]...ifA≡Pr 1...rn
rn[x←t]
(B[x←t]∨C[x←t]) ifA≡(B∨C)
(¬(B[x←t])) if A≡(¬B)
A ifA≡((∃y)B) andy≡x
((∃y)(B[x←t])) if A≡((∃y)B) andyι ≡x
andydoes not occur int
In all cases above, the left hand side is deﬁned iff the right hand side is.
Pause.We have eliminated “replaces” and “captured”. But isA[x←t] a for-
mula (whenever it is deﬁned)? (See Exercise I.9)
ε
I.3.12 Deﬁnition (Simultaneous Substitution).The symbol
A[y
1,...,y r←t1,...,t r]
or, equivalently,A[ϕy
r←ϕtr] – whereϕy ris an abbreviation ofy 1,...,y r–
denotessimultaneous substitutionof the termst
1,...,t rinto the variables
y
1,...,y rin the following sense: Letϕz rbe variables that do not occur at all
(either as free or bound) in any ofA,ϕt
r. ThenA[ϕy r←ϕtr] is short for
A[y
1←z1]...[y r←zr][z1←t1]...[z r←tr] (1)
ε
Exercise I.10 shows that we obtain the same string in (1) above, regardless of
our choice ofnew variablesϕz
r.
More Conventions.The symbol [x←t] lies in the metalanguage. This
metasymbol has the highest priority, so that, e.g.,A∨B[x←t] means
A∨(B[x←t]), (∃x)B[x←t] means (∃x)(B[x←t]), etc.
The reader is reminded about the conventions regarding the metanotations
A[ϕx
r] andA(ϕx r) (see I.1.11).In the contextof those notations, ift 1,...,t rare
terms, the symbolA[t
1,...,t r] abbreviatesA[ϕy r←ϕtr].
We are ready to introduce the (logical) axioms and rules of inference.

34 I. Basic Logic
Schemata.
†
Some of the axioms below will actually beschemata.Aformula
schema,orformula form, is a stringGof the metalanguage that containssyn-
tactic variables, such asA,P,f,a,t,x.
Whenever we replace all these syntactic variables that occur inGby speciﬁc
formulas, predicates, functions, constants, terms, or variables respectively, we
obtain a speciﬁc well-formed formula, a so-calledinstance of the schema.For
example, an instance of (∃x)x=ais (∃v
12)v12=0 (in the language of Peano
arithmetic). An instance ofA→Aisv
101=v114→v101=v114.
I.3.13 Deﬁnition (Axioms and Axiom Schemata).Thelogical axiomsareall
the formulas in the groupAx1andallthe possible instances of the schemata in
the remaining groups:
Ax1.All formulas inTaut.
Ax2.(Schema)
A[x←t]→(∃x)A for any termt
By I.3.10–I.3.11,the notation already imposes a condition on t, that it is
substitutable for x.
N.B. We often see the above written as
A[t]→(∃x)A[x]
or even
A[t]→(∃x)A
Ax3.(Schema)Foreachobject variablex, the formulax=x.
Ax4.(Leibniz’s characterization of equality – ﬁrst order version. Schema)For
any formulaA, object variablex, and termstands, the formula
t=s→(A[x←t]↔A[x←s])
N.B.The above is written usually as
t=s→(A[t]↔A[s])
We must remember that the notation alreadyrequiresthattandsbe free
forx.
We will denote the above set of logical axioms by←.
ε
†
Plural ofschema. This is of Greek origin,σχ´ηµα, meaning – e.g., in geometry – ﬁgure or
conﬁguration or even formation.

I.3. Axioms and Rules of Inference 35
The logical axioms for equality are not the strongest possible, but they are
adequate for the job. What Leibnizreallyproposed was the schemat=s↔
(∀P)(P[t]↔P[s]), which says, intuitively, that “two objectstandsare equal
iff, for every ‘propertyP’, both havePor neither hasP”.
Unfortunately, our system of notation (ﬁrst-order language) does not allow
quantiﬁcation over predicate symbols (which can have as “values” arbitrary
“properties”). But is notAx4read “for all formulasA” anyway? Yes, but with
one qualiﬁcation: “For all formulasAthat we can write down in our system of
notation”, and, alas, we cannot writeallpossible formulas ofreal mathematics
down, because they are too many.
†
While the symbol “=” is suggestive of equality, it isnotits shape that
qualiﬁes it as equality. It is the two axioms,Ax3andAx4, that make the symbol
behaveas we expect equality to behave, and any other symbol of any other
shape (e.g., Enderton (1972) uses “≈”) satisfying these two axiomsqualiﬁesas
formal equalitythat is intended to codify the metamathematical standard “=”.
I.3.14 Remark.InAx2andAx4we imposed the condition thatt(ands) must
be substitutable inx. Here is why:
TakeAto stand for (∀y)x=yandBto stand for (∃y)¬x=y. Then,tem-
porarily suspending the restriction on substitutability,A[x←y]→(∃x)Ais
(∀y)y=y→(∃x)(∀y)x=y
andx=y→(B↔B[x←y]) is
x=y→((∃y)¬x=y↔(∃y)¬y=y)
neither of which, obviously, is “valid”.
‡
There is a remedy in the metamathematics: Move the quantiﬁed variable(s)
out of harm’s way, by renaming them so that no quantiﬁed variable inAhas
the same name as any (free, of course) variable int(ors).
This renaming is formally correct (i.e., it does not change the meaning of
the formula), as we will see in thevariant(meta)theorem (I.4.13). Of course,
†
“Uncountably many”, in a precise technical sense developed in the chapter on cardinality in
volume 2 (see p. 62, of this volume for a brief informal “course” in cardinality). This is due to
Cantor’s theorem, which implies that there are uncountably manysubsets of
N. Each such subset
Agives rise to the formulax∈A in the metalanguage.
On the other hand, set theory’s formal system of notation, using just∈andUas start-up
(nonlogical) symbols, is only rich enough to write down a countably inﬁnite set of formulas
(cf. p. 62). Thus, our notation will fail to denote uncountably many “real formulas”x∈A.
‡
Speaking intuitively is enough for now. Validity will be deﬁned carefully pretty soon.

36 I. Basic Logic
it is always possible to effect this renaming, since we have countably many
variables, and only ﬁnitely many appear free int(ands) andA. This trivial
remedy allows us to render the conditions inAx2andAx4harmless. Essentially,
at(ors) is always substitutableafter renaming.
ε
It is customary to assume a Platonist metatheory, and we do so. We can then
say “countably many” variables without raising any eyebrows. Alternatively,
we know how to get a new variable that is different from all those in a given
ﬁnite set of variableswithout invoking an inﬁnite supply.
I.3.15 Deﬁnition (Rules of Inference).The following are the tworules of
inference. These rules are relations in the sense of Section I.2, with inputs from
the setWffand outputs also inWff. They are written traditionally as “fractions”.
We callthe“numerator” thepremise(s)and the “denominator” theconclusion.
We say that a rule of inference isappliedto the formula(s) in the numerator,
and that ityields(orresults in) the formula in the denominator.
Inf1.Modus ponens,orMP.For any formulasAandB,
A,A→B
B
Inf2.∃-introduction– pronouncedE-introduction. For any formulasAandB
such that x is not free inB,
A→B
(∃x)A→B
N.B. Recall the conventions on eliminating brackets!
ε
It is immediately clear that the deﬁnition above meets our requirement that the
rules of inference be “algorithmic”, in the sense thatwhetherthey are applicable
orhowthey are applicable can be decided and carried out in a ﬁnite number
of steps by just looking at theformof (potential input) formulas (not at the
“meaning” of such formulas).
We next deﬁne⊇-theorems, that is, formulas we canprove fromthesetof
formulas⊇(this⊇may be empty).
I.3.16 Deﬁnition (⊇-Theorems).The set of⊇-theorems,Thm
⊇, is the least
inclusive subset ofWffthat satisﬁes:
Th1.←⊆Thm
⊇(cf. I.3.13).
Th2.⊇⊆Thm
⊇. We call every member of⊇anonlogical axiom.
Th3. Thm
⊇isclosed undereach ruleInf1–Inf2.

Random documents with unrelated
content Scribd suggests to you:

The Project Gutenberg eBook of Socrate

This ebook is for the use of anyone anywhere in the United States
and most other parts of the world at no cost and with almost no
restrictions whatsoever. You may copy it, give it away or re-use it
under the terms of the Project Gutenberg License included with this
ebook or online at www.gutenberg.org. If you are not located in the
United States, you will have to check the laws of the country where
you are located before using this eBook.
Title: Socrate
Author: Antonio Labriola
Editor: Benedetto Croce
Release date: March 15, 2019 [eBook #59064]
Language: Italian
Credits: Produced by Carlo Traverso, Claudio Paganelli, Barbara
Magni and the Online Distributed Proofreading Team at
http://www.pgdp.net (This file was produced from images
generously made available by the Bibliothèque nationale
de France)
*** START OF THE PROJECT GUTENBERG EBOOK SOCRATE ***

SOCRATE

ANTONIO LABRIOLA
SOCRATE
nuova edizione
a cura di B. CROCE
Omnia meliora tunc fuere, cum minor copia
Plin., Hist. Nat., XXXV, 50.
BARI
GIUS. LATERZA & FIGLI
TIPOGRAFI-EDITORI-LIBRAI
1909

PROPRIETÀ LETTERARIA
MARZO MCMIX — 21246.

INDICE

AVVERTENZA DELL'EDITORE
Questa monografia su Socrate è (come l'autore stesso dice
nell'avvertenza da lui premessa alla stampa) una memoria,
presentata al concorso bandito nel 1869 dalla R. Accademia di
scienze morali e politiche di Napoli e premiata nel 1870. Fu inserita,
l'anno dopo, nel volume VI degli Atti di quell'Accademia, col titolo: La
dottrina di Socrate secondo Senofonte, Platone ed Aristotele.
Nel ristamparla, io adempio un desiderio, che più volte il Labriola
ebbe a manifestarmi negli ultimi anni di sua vita.
D'altra parte, la monografia del Labriola è il solo ampio lavoro
d'insieme, che la letteratura italiana possegga intorno a Socrate. Gli
altri lavori sull'argomento sono piccoli saggi o discussioni di punti
speciali, alcuno dei quali senza dubbio assai pregevole. Eccone un
catalogo, che credo quasi completo: G. M. Bertini, Considerazioni
sulla dottrina di S. (Memorie della R, Acc. d. Scienze di Torino, s. II,
vol. XVI, 1856, e in Opere varie, Biella, 1903); B. Spaventa, La
dottrina di S. (critica del lavoro precedente, in Rivista
contemporanea, a. IV, vol. VIII, 1856, e nel vol. Da Socrate a Hegel,
Bari, Laterza, 1905); F. Acri, La filosofia di S. (in Rivista sicula, 1870,
vol. III); R. Bonghi, S. nella difesa scrittane da Platone (Nuova
Antologia, del 1880; cfr. anche le traduzioni dei dialoghi platonici, e,
in ispecie, per la biografia, il volume contenente il Fedone; A.
Chiappelli , Il dubbio di S. sull'immortalità (in Filosofia delle scuole
ital., XXV, 1882); E. Morselli , Il demone di S. (Rivista di filosofia
scientifica, II, 1883-3); T. Mamiani , La morale di S. (in Filos. d. scuole
ital., 1884): A. Chiappelli , Il naturalismo di S., e le prime Nubi di
Aristofane (in Rendic. dei Lincei, 1885-6): M. Lessona, La morale e il

diritto in S. (Roma, 1886); R. Pasèuinelli , La dottrina di S. nella sua
relazione alla morale e alla politica (in Rivista ital. di filos., 1887); G.
Melli, S., conferenza (nell'Atene e Roma, a. VI, 1903); e una serie di
saggi di G. Zuccante, Intorno al principio informatore e al metodo
della filosofia di S. (in Riv. di filos. e sc. affini, 1902, febbr.); Il bello e
l'arte della dottrina di S. (Rendiconti d. R. Ist. Lomb., s. II, v. XXXV,
1902); La donna nella dottrina di S. (Riv. filos., 1903); Sul concetto
del bene in S. a proposito del suo asserito utilitarismo (ivi, 1904);
Dei veri motivi del processo e della condanna di S. (Rend. Ist.
Lomb., vol. XXXVIII, 1905); S. (in Dizion. di pedagogia di Credaro -
Martinazzoli, Milano, Vallardi, 1907); si veda anche, del medesimo
autore, il vol.: Fra il pensiero antico e il moderno (Milano, Hoepli,
1905).
La ristampa della monografia del Labriola, dunque, non potrà non
riuscire gradita agli studiosi e ai lettori colti; ai primi dei quali offrirà
una compiuta informazione degli studi su Socrate anteriori al 1870; e
ai secondi, un'immagine del carattere di Socrate e un'esposizione
della dottrina di lui, che rimane assai notevole per l'acume e
l'equilibrio del giudizio e per l'acuto senso storico
[1].
Napoli, gennaio 1909.
B. C.

AVVERTENZA DELL'AUTORE
Nel gennaio del 1869, la Sezione di scienze morali e politiche della
Società reale di Napoli stabilì per tema di concorso: «La dottrina di
Socrate secondo Senofonte, Platone ed Aristotele», assegnando il
mese di giugno 1870 come termine per la presentazione dei
manoscritti. Questa monografia, che ora vede la luce negli Atti
dell'Accademia stessa, ha avuto in sorte di ottenere la più gran parte
del premio, e di essere anteposta ai lavori di sei altri concorrenti
[2];
della quale determinazione noi rendiamo qui pubblica testimonianza
di gratitudine alla Sessione, che ci ha onorati col suo favorevole
giudizio.
Questo lavoro intanto, quantunque premiato e giudicato degno della
stampa, non risponde pienamente a quello che avevamo in animo di
fare; che in molti luoghi è difettoso e degno di correzione, e, quanto
alla forma, dovea essere rimaneggiato da capo a fondo. La
spontanea confessione, che facciamo, ci autorizza a produrre le
nostre scuse. Del tempo assegnato dall'Accademia buona parte andò
per noi perduta: gli ultimi mesi appunto, nei quali era nostro
proposito di rivedere a parte a parte la bozza già condotta a termine
nell'autunno del 1869, per introdurre nello scritto maggiore
uniformità di colorito e più gran copia di erudizione, e per portarlo
cui una forma letteraria più accettabile. Nella stampa, poi, non ci
siamo permessa modificazione alcuna, perchè, avendo l'Accademia,
col premiarlo, fatto suo il nostro lavoro, non ci era lecito pubblicarlo
negli Atti in una nuova forma. Nel dare, dunque, alla luce un lavoro,
che, a nostro parere, dovea essere corretto, colorito e migliorato, nel
darlo in somma quasi come l'avevamo abbozzato circa due anni fa,

speriamo che i lettori non vogliano usare con noi una critica troppo
scrupolosa, e che guardino con indulgenza i difetti parziali del nostro
libro.
La più gran parte dei lavori letterari, storici e filosofici, che più o
meno direttamente si riferiscono a Socrate, sono stati da noi o letti o
consultati
[3]; e ci è parso conveniente di segnare con l'asterisco le
note di seconda mano.

I.
LA PERSONALITÀ STORICA DI SOCRATE
Nota. — La caratteristica più completa e più perfetta della
personalità di Socrate si trova nella History of Greece di
Grote, vol. VIII, pp. 551-684. Lo Zeller: Die Philosophie der
Griechen, 2ª ed., vol. II, pp. 38-52 e 130-165, ha esposto con
brevità, e con molto gusto critico, i tratti più notevoli della
vita, e del processo di Socrate. Il libro di Lasaulx: Des
Sokrates Leben, Lehre und Tod, München, 1858, non è che
una congerie di particolari falsi e di giudizi stravaganti; vedi
specialmente pp. 5-26, 54-122. Il libro dell'Alberti: Sokrates,
Göttingen, 1869, per la pretensione di voler ristabilire
l'autorità storica del dialogo platonico, e per la forma
imprecisa ed incolore dell'esposizione, è un lavoro sfornito
d'ogni pregio critico e letterario; v. pp. 41-55, 115-149, 156 e
seg. Il Curtius: Griechische Geschichte, vol. III, p. 89 e seg.,
ha caratterizzato molto bene dal punto di vista storico la
posizione di Socrate. Le monografie di Ueberweg: Die
Bedeutung des Sokrates in der Bildungsgeschichte der
Menschheit, nei Protest. Monatsblätter, vol. XVI, fasc. 1º, p.
39 e seg.; e dello Steffensen: Ueber Sokrates, ibid., vol. XVII,
fasc. 2º, p. 76 e seg., contengono un ritratto vivace ed
animato. Il breve scritto di Schmidt: Sokrates, Halle, 1860,
non ha importanza di sorta.
1. Socrate e gli Ateniesi
[4]

L'anno 1º dell'Olimpiade 95ª nel mese Targelione (maggio 399 a. C.)
moriva nel desmoterio ateniese Socrate figlio di Sofronisco,
condannato a bere la cicuta, qual reo di violata religione e corruttore
della gioventù
[5]. Gl'intimi di lui, che rimaneano privi dell'uomo più
prudente e più giusto fra quanti fossero a quel tempo
[6], avevano
invano tentato di sottrarlo a così trista fine, offrendosi dapprima
mallevadori di una multa di trenta mine
[7], e cercando, poi che la
sentenza era stata pronunziata, procacciargli con la fuga albergo e
riposo in più sicura stanza
[8]. Socrate, che a mala pena s'era indotto
ad offrire la multa, rigettò recisamente il consiglio della fuga; e
rimase tranquillo in carcere fino al giorno della morte, che egli
incontrò con religiosa rassegnazione
[9]. La divinità gli vietava di fare
altrimenti! Egli era convinto che fuggire le conseguenze del processo
era come violare la legge, la cui santità dee rimanere inalterata,
anche quando gl'interpreti di essa siano ingiusti e parziali. La sua
coscienza non ammetteva incertezza o titubanza fra una moltitudine
di beni possibili, riposando su la infallibilità del giudizio morale, il cui
fondamento costante è la retta cognizione
[10]. Socrate era al
servigio della divinità, e la coscienza della missione affidatagli era in
lui tanto viva e potente, che, ove l'avesse lasciata inadempita, egli
avrebbe stimato di commettere un'azione riprovevole ed
irreligiosa
[11].
Era quello un tempo di restaurazione politica, e gli Ateniesi, che dal
fastigio della gloria e della potenza, per una serie d'errori e
d'ingiustizie, erano caduti nel più basso fondo d'ogni umiliazione,
scacciati i trenta tiranni, e ristabilita la forma popolare, intendevano
a tutt'uomo a purgare la città di tutti quelli elementi, che per un
verso o per un altro avessero corrotto o snervato, o reso inoperoso e
svogliato il popolo
[12]. E quest'opera fu intrapresa con moderazione,
generosità e costanza. La vendetta, lo spirito di parte, le ambizioni e
gl'interessi personali offesi non vennero punto a regolare la condotta
dei restitutori della libertà, che, intesi a ristabilire la costituzione
fondamentale dello Stato, dettero pruova di quanto fossero valse le
recenti sventure a mitigare lo spirito violento della democrazia

ateniese. L'arcontato di Euclide coronò gli sforzi della restaurazione,
e fece per poco sperare che i tempi di Cimone e di Pericle non
fossero del tutto finiti. Ma quest'opera di civile rinnovamento, per
quanto fosse stata compiuta con intenzioni umane e disinteressate,
non riuscì a ricomporre in perfetta armonia gli spiriti già travagliati
da profonde collisioni, perchè l'apparente conciliazione non avea di
che nudrire gli animi già stanchi e dimentichi delle antiche virtù. La
religione tradizionale era stata violentemente scossa nei tempi della
sfrenata libertà democratica, e tutto avea cospirato a smuoverla
dalle sue fondamenta. Le gravi sventure sofferte aveano favorito due
opposte tendenze: dispregio della religione tradizionale in alcuni,
superstizione eccessiva negli altri, stimando quelli che l'insuccesso
nelle imprese guerresche avesse sbugiardato gli dei, mentre questi,
al triste spettacolo della patria in decadenza, ed alla perdita del
sereno possesso delle tradizionali e virili virtù dei padri, non sapeano
cercare altrove un riparo, che in un abbandono angoscioso nelle
braccia delle divinità
[13]. La mania dei processi politici, frenata per
poco dal bisogno di calma e tranquillità che la restaurazione avea
indotto negli animi, si fece nuovamente imperiosa; e quattro anni
appena erano trascorsi dal ristabilimento della libertà, quando la
democrazia fece di Socrate la vittima innocente di un esagerato
principio di conservazione politica.
Questo doloroso spettacolo di una rinnovata democrazia, che si
macchia del delitto di una ingiusta condanna col toglier la vita ad un
uomo di virtù eccezionali, che avea consacrato sè medesimo al
miglioramento dei suoi concittadini, è stato argomento di somma
maraviglia sì negli antichi tempi come nei moderni
[14]; e questa
maraviglia ha fatto sì, che le circostanze tutte che prepararono ed
accompagnarono quella tragica catastrofe fossero studiate con
indagini severe e minuziose
[15]. Il risultato di queste ricerche è
stato, non certo la giustificazione, ma bene la spiegazione della
condotta degli Ateniesi verso Socrate; e quel processo e quella
condanna non possono ora più considerarsi come opera del
fanatismo religioso, o del furore partigiano, o degli artifizî di certi
uomini invidiosi
[16], perchè il loro fondamento era riposto

nell'inevitabile contrasto fra i principî conservativi della democrazia
ateniese, e la ricerca poggiata sul criterio del convincimento
personale, della quale Socrate s'era fatto l'apostolo
[17]. Questa
maniera di considerare la posizione di Socrate in Atene non importa
punto, che deva sacrificarsi la testimonianza dei discepoli di Socrate,
su la purezza delle intenzioni, e sullo spirito profondamente retto e
religioso del loro maestro, all'esigenza di una giustificazione assoluta
del popolo ateniese
[18]; ma vale certamente a farci valutare più
intimamente il valore storico della persona di Socrate, ed agevola la
intelligenza netta della sua dottrina
[19]. L'esame di questa quistione
non può entrare nei limiti del nostro lavoro; ed a noi basterà di
notare i tratti più notevoli della personalità di Socrate, solo perchè
apparisca necessario il contrasto con la democrazia
[20]
Socrate non avea niente di comune coi partiti che agitavano Atene, e
le sue personali relazioni non aveano niente a fare con le varie
tendenze politiche dei contemporanei. Sebbene Carmide e Crizia
fossero stati suoi uditori, e Teramane e Carìcle suoi amici, egli non
era stato per ciò fautore del loro dispotismo, anzi Crizia, ad onta
dell'antica amicizia, gli avea proibito di tener discorsi
[21]. Cherefonte
suo amico, e s'è lecita la parola, suo apostolo, tornava appunto
dall'esilio coi fautori del governo popolare, poco prima che Socrate
fosse condannato
[22]; e, con lui, Lisia, che, se non discepolo o
amico, secondo una probabile tradizione, era nel numero degli
ammiratori di Socrate
[23]. Alcibiade infine, ch'era continua minaccia
e spauracchio dei trenta, e che allora i reduci democratici cercavano
ricondurre in Atene quando l'oro di Sparta il fece spegnere, era stato
il più intimo dei suoi uditori; quello che, per la sua naturale
leggerezza e mutabilità, avea più d'ogni altro sentito la potenza
educatrice del carattere di Socrate
[24]. Tutto quello che formava la
vita, il benessere e la felicità dell'Ateniese, il continuo agitarsi per le
pubbliche faccende, e la brama di divenire influenti nelle adunanze
con l'arte della parola, non occupava l'animo di Socrate, che uso ad
appagarsi dell'intimo compiacimento della propria coscienza, non
volle mai scendere su l'arena delle dispute politiche.

Ai contemporanei egli appariva un uomo strano e singolare
[25], ed a
ragione uno storico ha detto, ch'egli non apparteneva a nessuna
classe di cittadini
[26]. Abbandonata in fatti ben per tempo l'arte
paterna della scoltura, non intese mai più ad apprenderne un'altra,
che lo fornisse dei mezzi necessarî per la sussistenza. Come
cittadino, non manca di adempire i doveri di pritane, anzi sfida il
furore popolare, e sa volere e far volere il giusto
[27]; ma egli non
cerca per ciò di acquistare influenza col suo ingegno, anzi pare che
distorni i cittadini dalla vita pubblica, col richiamarli alla meditazione,
e si attira così la taccia di fuorviare i giovani. A Potidea, a Delio, ad
Amfipoli combatte da valoroso soldato
[28], e fa nascere in tutti una
straordinaria ammirazione per la costanza con la quale soffre ogni
sorta di privazioni e d'intemperie; ma in tutto ciò non fa che
adempiere il dovere d'onesto cittadino, e, ricusando la corona che il
suo coraggio gli avea fatta meritare, la cede ad Alcibiade, cui avea
salvata la vita. Un bel giorno, quest'uomo singolare muoverà dei
dubbî sul concetto che gli altri si fanno comunemente del coraggio, e
metterà in imbarazzo anche coloro, che, fatte avendo delle
campagne, e riportate delle vittorie, non sanno dire che cosa sia il
coraggio
[29]. La sua estrema povertà lo costringe a vivere dei doni
spontanei degli amici; ma, mentr'egli forse rigetta con superbia
l'invito di principi stranieri che lo invitano alla loro corte, sdegna il
nome di maestro stipendiato, anzi non vuole essere tenuto per
maestro
[30]. E come poteva essere maestro, — e di che? Egli sapeva
solo di non saper niente; e per questa ragione appunto l'oracolo di
Delfo lo avea dichiarato il più sapiente fra gli uomini. Il suo sapere
appariva nella forma di un giudizio sospensivo, di una bella domanda
— τὶ ἐστι; che smascherava il ciarlatano, imbarazzava il presuntuoso,
ed irritava il sofista di mestiere, e che spesso, col suscitare il bisogno
dell'esame, non menava ad un risultato positivo.
I settant'anni della vita di Socrate passarono fra l'epoca più fortunata
e gloriosa della repubblica ateniese, ed il periodo infausto della
irreparabile decadenza. Nato dieci anni dopo la battaglia di Platea,
nella prima sua età Temistocle moriva in esilio, e Cimone, reduce
dall'esilio, raccoglieva gloria con le imprese della guerra e con le

proficue arti della pace. Nella età virile di Socrate, Pericle fu a capo
della Stato, moderatore e sovrano dell'opinione, con quella
grandezza e nobiltà di propositi, che gli facea vedere nello splendore
della patria la soddisfazione della propria ambizione, ch'era intesa ad
armonizzare le cure dello Stato ed il godimento dell'arte. La guerra
del Peloponneso, la spedizione di Sicilia, la caduta della libertà,
l'oligarchia, i trenta, il ritorno del partito popolare, — tutta questa
svariata e rapida vicenda passò sotto gli occhi di Socrate, che,
stando da mane a sera nell'agorà e in su le pubbliche vie, e
frequentando la bottega dell'armiere e dello scultore, del pari che la
casa della meretrice e degli ottimati, con le sue aride domande, col
suo perpetuo γνῶθι σαυτόν e τὶ ἐστι; parea ignorasse le glorie e le
sventure della patria.
E pur nondimeno Socrate era un prodotto naturale della coltura e
della vita ateniese; e se il suo carattere, e le sue convinzioni etiche e
religiose ci fanno apparire la sua persona come molto staccata e
distinta dal fondo comune della vita dei suoi contemporanei, deve
pur dirsi, che la facilità con la quale egli seppe formarsi una cerchia
d'amici devoti ch'erangli stretti da religiosa pietà, e da
arrendevolezza senza pari, non può avere la sua ragione soltanto nel
prestigio straordinario ch'egli esercitava, ma eziandio, e forse
principalmente, nella natura dei tempi. Una società nuova, più
angusta e al tempo stesso più intima e compatta, si andava allora
formando nel seno della grande società; e spezzato il filo tradizionale
della patria educazione, e varcati i limiti dell'ethos popolare, si
preparava al raccoglimento, mentre gli elementi dell'antica vita
entravano in lotta fra loro, per poi alterarsi, e dissolversi. Socrate
non è il cosciente iniziatore di questo movimento, nè il solo; anzi,
come è sempre avvenuto in tutte le epoche di rinnovamento o di
riforma morale e religiosa, egli, che con le sue esigenze ricercative si
allontanava tanto dall'etica puramente tradizionale ed abituale dei
suoi concittadini, fu così poco inclinato a credersi un riformatore, che
considerò come preordinato dalla divinità, ed inteso dalla sapienza
dei legislatori, quello che era risultato della sua personale
investigazione. Egli rimase quindi greco, anzi ateniese tutta la vita, e

con la stessa morte confermò la costanza ed armonia della sua
coscienza. Il Socrate umanitario dei filosofi del decimottavo secolo è
un prodotto di fantasia, che non ha fondamento nella storia; e le
opinioni di certi eruditi del nostro secolo, che hanno fatto di Socrate
un rivoluzionario, non meritano altro nome, che quello di dottrinali
aberrazioni.
Intendere come Socrate, che fu vittima di una accusa che facea di lui
un innovatore della religione e della pubblica morale, non fosse stato
nè un rivoluzionario nè un ozioso ricercatore, ed evitare al tempo
stesso l'errore di coloro che ne fanno il rinnovatore di non so che
antica morale, senza pensare che una morale non potea esservi
prima della ricerca sofistica e socratica, è forse tanto difficile per la
critica moderna, per quanto era ardua cosa pei contemporanei di
dischiudere la deforme statua del Sileno, per trovarvi dentro quella
vera e viva immagine, che rendeva perplesso l'incostante e volubile
Alcibiade
[31].
2. Edìcaòione e sîiäìppo deääa coscienòa di Socrate.
Imparare a leggere, e recitare poi a memoria le sentenze degli
antichi poeti; assuefarsi alla modulazione ed al canto, ch'era
destinato a formare nell'animo il senso dell'armonia; esercitare il
corpo con la ginnastica, per sviluppare con la regolarità dei
movimenti l'accordo dell'esterno con l'interno, ed il senso
dell'euritmo; in questi tre capi consisteva l'educazione
dell'Ateniese
[32], Solone, istitutore di questo sistema di educazione,
ne aveva affidata la vigilanza al venerando consesso dell'Areopago,
assicurando in tal guisa alla coscienza ateniese l'inviolato possesso di
una preziosa eredità morale. Gli Ateniesi, tuttochè rimutassero più
volte le forme politiche della loro costituzione, riguardarono sempre
con pietosa venerazione gli ordini di Solone; e gli stessi restauratori
della libertà, dopo la cacciata dei trenta, li tennero qual sicuro
fondamento della vita civile. La riforma di Efialte, col porre dei limiti
all'autorità dell'Areopago, lo aveva privato della vigilanza su la

educazione, entrando in quella vece i Sofronisti
[33] a funzionare da
moderatori di quegli antichi istituti. La pochezza dei mezzi per la
diffusione letteraria, e la vita ristretta in più angusti confini,
rendeano allora necessaria la concentrazione degli elementi educativi
che la coltura e la tradizione poteano offrire: sicchè lo sviluppo
dell'individuo, favorito dalla limitata istruzione, era di una grande
svariatezza e libertà
[34], e tanto più intenso, per quanto meno
sussidiato da una larga preparazione di scuola.
I primi anni della vita di Socrate precedettero la riforma di Efialte, e
non è a dubitarsi ch'egli s'ebbe l'istruzione legalmente stabilita sin
dal tempo di Solone. Senofonte, e qualche reminiscenza socratica
presso Platone fanno fede della educazione affatto ateniese di
Socrate; e fra gl'indizi non è di poco valore quello che può desumersi
dalle frequenti citazioni di Omero, di Esiodo, di Teognide e di
Simonide
[35], che, secondo la tendenza invalsa a quell'epoca,
servivano di occasione a delle analisi morali dei precetti che
potessero esser contenuti in questo o in quel luogo. Da questa prima
istruzione (che se non è esplicitamente attestata in persona del
giovanetto Socrate
[36], non c'è dubbio che abbia avuto luogo per lui
come per ogni altro Ateniese), fino al momento che, informato già a
solide convinzioni, egli appare su la scena pubblica, come autore di
una dottrina determinata e precisa nel suo carattere e nel suo
valore, come siasi sviluppato, e quali siano state le diverse fasi del
suo pensiero, e le sue lotte coi contemporanei e con sè stesso, la
critica storica non è più in grado di saperlo
[37]. La leggenda in vero
ha conservato finanche ì nomi dei maestri di Socrate, e gl'indizi della
loro influenza; ma alla luce della critica tutte queste varie tradizioni
sono apparse vuote di certezza, avendo esse per fondamento, o certi
presupposti dottrinali, o delle combinazioni equivoche di dati
storici
[38]. E del pari non si ha ragioni sufficienti, per riconoscere in
certe altre tradizioni la lontana ricordanza delle lotte sostenute da
Socrate, per raggiungere quello stato di perfetta costanza,
continenza ed equanimità, che tanto ammiravano in lui i testimoni
contemporanei: perchè quelle tradizioni, o sono del tutto inventate,

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

Lectures In Logic And Set Theory Volume 1 Mathematical Logic 1st Edition George Tourlakis

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Lectures In Logic And Set Theory Volume 1 Mathematical Logic 1st Edition George Tourlakis

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 13

Slide 15

Slide 16

Slide 17

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 59

Slide 60

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

TLE-9-Prepare-Salad-and-Dressing.pptxkkk

LESSON 1 ABOUT MEDIA AND INFORMATION.pptx