This is cross posted from MathStackExchange. Since this is a reference request, I believe there will not be duplications of efforts in answers. This is also related to the question here.
In textbooks on logic I see a tradition of using notions of set and map from the very beginning of the exposition, long before the set theory is formally constructed. This causes multiple misunderstandings for the reader (I remember these difficulties when I was a student, and even now I have questions, as you can see), since formally this is a violation of the principle that a mathematician can't use a term before giving its accurate definition. That is why I believe that there must be texts where this mistake is repaired. Can anybody advise me a textbook on logic with a "linear structure", without these "circles in definitions"?
I already told this to people at MSE, I don't see serious technical obstacles for such a book to exist: the author can just formulate the axioms of predicate calculus + axioms of set theory, then consider the corollaries (i.e. construct a first-order theory of sets), and only after that discuss what they call "semantics of logic" (i.e. everything connected to interpretations of first order languages). That is strange, I can't find such a textbook. I would appreciate very much if somebody could give a reference.
P.S. I have a feeling that I must specify the question, because people seem to do not quite understand what I ask. Look at these examples.
-
Elliott Mendelson in his Introduction to Mathematical Logic formulates and proves in Chapter 2 (Corollary 2.14) the Gödel completeness theorem. Of course, for formulating and proving this he needs the notion of logically valid formula. He gives this definition a little bit earlier (also in Chapter 2), and of course, he uses the notion of interpretation, which he defines with the help of the notions of set and function. These are not sets and functions in some "trivial, everyday sense" — these are "true sets" and "true functions" in the sense of Set theory. But he builds Set theory (and gives accurate definitions of sets and functions) only in Chapter 4, long after Gödel's theorem.
-
The same happens in the book by Joseph R. Shoenfield Mathematical logic. He also defines valid formulas, with the help of sets and functions, and also proves Gödel's completeness theorem (in his Chapter 4), and he does this long before constructing Set theory (which appears only in Chapter 9).
-
And this is everywhere, in all the textbooks on Logic that I know. The only difference is that sometimes the author does not build Set theory at all (like P.S.Novikov in his Elements of Mathematical Logic).
So my question is
Is there a book on logic where sets and functions are mentioned only after constructing ("true", axiomatic) Set theory?
I understand that the word "set" can be used in non-mathematical, everyday sense, but as I wrote above, Gödel completeness theorem is not that case. I also understand the desire to have a similar notion for simpler, "everyday" situations, say, for describing syntax of your language. But this desire does not imply the necessity to use the word "set", which appears in your text later as a term of a rigoruos, axiomatic theory (where it has a much more sophisticated meaning than in everyday life). The English language is rich enough (as well as other languages, Russian, French, etc.), it is always possible to find a better solution, which does not provoke misunderstandings, accusations and controversy. Finally, it is not nice to arrange the course of a mathematical discipline in that way, because students (and readers of your book) perceive this as a mockery.
A natural way to overcome this, I believe, is what I wrote before:
to construct a first-order theory of sets (with all axioms, including the axioms of predicate logic), and only after that to speak about things like "interpretation", "completeness", etc.
Is it possible that nobody did this up to now?
P.P.S. To people who vote to close: I hope you have convincing explanations of your motives.
Edit 24.02.2019. I would like to draw the attention of those who might be interested, to my own attempt to solve this problem. This is chapter 1 in my unfinished course of undergraduate mathematics. This text is designed for my students, that is why it is in Russian, unfortunately. My problem is that I am not an expert in this field and because of that I have to spend too much time on working with the details. And I actually do not have this time, I do this sporadically. This problem with Gödel's completeness theorems (theorems 1.1.22 and 1.1.23 in the text, separately for theories with finite and infinite systems of axioms) is now the only blank spot, if it were resolved, the textbook could be considered finished (I already asked this question at MO before, it is here). The best solution for me would be if someone published an article with accurate proof of these statements in their “highly formalized form” as they are presented in my text, so that I could just refer to his article. (But I must say that a part of the problem is that Gödel's theorem for a theory with an infinite system of axioms is even not accurately formulated in my text, since I was trying to avoid the standard trick of "embedding the given first order theory into arithmetics". I believe it can be replaced by an equivalent trick of "embedding into set theory", but the details are not well written in my text, because I don't see how to "translate this".) So if somebody could give an advise or a reference I would appreciate this very much.
Edit 17.11.2020. It seems to me, I did it. I would be grateful if some logicians could have a look at this text (chapter 2) and share critical comments. If need be I can translate this into English.
Best Answer
There's a fundamental difficulty with your claim that
Mathematical definitions are always in terms of things that are already understood. One could eliminate the use of the word "set" in developing axiomatic set theory, but you would still need to define (for example) terms such as "axiom." How would you do this? You could define the word "axiom" in terms of arithmetical concepts, but then what is the definition of an integer? Or you could define it in terms of syntactic concepts such as "symbol" and "string," but then what is the definition of a "symbol" or a "string" or a "sequence"?
If you want to do anything at all, then you have to start somewhere and take something for granted, and therefore you cannot take your principle that "a mathematician can't use a term before giving its accurate definition" literally.
Developing axiomatic set theory by using set-theoretic language might, depending on the student, be a pedagogical mistake, but it is not a logical mistake. The word "set" as it is used in the development of the theory is meant to refer to a concept that you already have a clear grasp of. The "sets" that are later introduced axiomatically are distinct from that. This is the distinction between theory and meta-theory.
There is actually an advantage to developing mathematical logic in set-theoretic terms, because it then lets you see that mathematical logic, like all other branches of mathematics, can be formalized using axiomatic set theory.
However, I agree with you that this can be confusing pedagogically. It seems that a lot of people nowadays are comfortable with taking syntactic concepts such as "symbol" and "string" and "sequence" and "rule" for granted, without demanding that these concepts be defined before they are used. Therefore one could ask for a treatment that does not refer to sets at all but that refers purely to syntax. This can still get tricky because at some point you are going to need to use some nontrivial reasoning about what happens when you manipulate strings according to syntactic rules; this will require identifying strings with integers and applying basic number-theoretic results. You might then get demands to define what integers are and questions about how you know what axioms apply to integers before you have fully developed a theory of axiomatic systems. There's no canonical way to address these demands since, as I said, something has to be taken for granted, and so I don't know that anyone has written a textbook quite like what you have in mind.
Having said that, I suggest that you try taking a look at Quine's Mathematical Logic, and in particular his section on "protosyntax." This is an attempt to develop the subject syntactically, which might be what you're looking for.
Note, by the way, that if you take this route, then some of the motivation for set theory is removed, because it is no longer apparent that set theory is really a foundation for everything. Instead, syntax becomes the foundation for everything. One can then ask if our theory of syntax is sound, and the same confusion will arise all over again, but now with "syntax" being the apparently circular concept rather than "set".