19
$\begingroup$

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.

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

  2. 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).

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

Improve this question
$\endgroup$
18
  • 6
    $\begingroup$ So are you literally just looking for a book that uses a different word than "set" when working in the metatheory? Obviously a book cannot give an "accurate definition" of every word before using it. $\endgroup$
    – Nate Eldredge
    Commented Sep 30, 2016 at 13:07
  • 4
    $\begingroup$ By the way, I disagree with your decision to crosspost and think it will very likely lead to duplication of effort. $\endgroup$
    – Nate Eldredge
    Commented Sep 30, 2016 at 13:15
  • 17
    $\begingroup$ As to duplication, people may spend time thinking about possible answers / references that have already been mentioned on the other site. I was about to pull down my copy of Kunen and see if it might address the issue to your satisfaction, when I discovered that a commenter on Math.SE had already mentioned it and you had rejected it. That would be duplication of effort, and that is the whole reason why crossposting is discouraged. $\endgroup$
    – Nate Eldredge
    Commented Sep 30, 2016 at 13:44
  • 6
    $\begingroup$ @NateEldredge, I gave links in both places. This is not a question where people have to think, they should just recall a textbook. And this is not a textbook on something rare, I think all logicians should know the answer. $\endgroup$
    – Sergei Akbarov
    Commented Sep 30, 2016 at 13:52
  • 4
    $\begingroup$ Dear Sergei, have you ever had a look at Chapter 1 of Bourbaki's Théorie des ensembles? Although the logic developed there does not go very far, I think this might be the type of text you try to find. $\endgroup$
    – Fred Rohrer
    Commented Sep 30, 2016 at 14:21

5 Answers 5

Reset to default
38
$\begingroup$

There's a fundamental difficulty with your claim that

a mathematician can't use a term before giving its accurate definition.

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Tim, my impression is that in this concrete case the difficulties are "grossly exaggerated". First, for normal people, even for mathematicians (but not specialists in logic, as I see) it is much easier to "take for granted" language, than sets (because language is simpler). And second, nothing prevents to write a text in the way that I describe: just postpone the discussion of Gödel's results to the time when Set theory is built, and the problem disappears. $\endgroup$
    – Sergei Akbarov
    Commented Sep 30, 2016 at 19:34
  • 5
    $\begingroup$ @SergeiAkbarov : Your approach requires that a text on logic also develop axiomatic set theory. That actually adds an additional burden. The traditional approach to logic focuses on formalizing arithmetic. Reading old papers and books, I get the impression that people used to find "integer" to be clearer than "symbol"; e.g., Kunen's book on set theory raises the question, "What is a symbol?" and "solves" that problem by defining symbols in terms of integers. So we should be cautious about assuming that our personal intuitions are shared universally. $\endgroup$
    – Timothy Chow
    Commented Sep 30, 2016 at 20:17
  • 9
    $\begingroup$ @SergeiAkbarov : Having said all that, I think that perhaps the time has come for a textbook to be written along the lines you suggest, because nowadays it seems that everybody understands, or thinks he understands, syntax, while skepticism about set theory is growing in popularity. $\endgroup$
    – Timothy Chow
    Commented Sep 30, 2016 at 20:19
  • 4
    $\begingroup$ @SergeiAkbarov : They do contain axiomatic set theory, but it's not treated in a way that is designed to "support" the meta-theoretical set-theoretical reasoning in the main flow of the text. As for proving Goedel's theorems, the incompleteness theorem can be done in primitive recursive arithmetic and so doesn't require set theory. The completeness theorem requires set theory in the trivial sense that it is (usually) stated set-theoretically. But for finite alphabets, it can be proved in $WKL_0$, a subsystem of second-order arithmetic, so the requisite set theory is weak. $\endgroup$
    – Timothy Chow
    Commented Sep 30, 2016 at 21:02
  • 2
    $\begingroup$ @SergeiAkbarov: I don't know of any textbook, but I personally think that the best way to start is as I described in math.stackexchange.com/a/1808558/21820, and the obvious reason is that ideal programs in this approach can be very well approximated by real-world programs on a computer. One can even go further and say that all practical formal systems correspond to a program that given input $(p,x)$ always halts and outputs whether $p$ is a proof of $x$. $\endgroup$
    – user21820
    Commented Oct 1, 2016 at 8:44
9
$\begingroup$

I also had the same question for quite a long time. I looked at many books in logic and set theory, but none of them resolves this issue properly IMO. However, it was more or less clear that one can do this by a purely syntactic treatment of elementary logic (as is also explained in Timothy Chow's answer). But it seems that nobody has written a text along these lines. So I decided to do it myself. The notes are available through my homepage:

Foundations of Mathematics

These notes are still in progress, but the main issues are considered in the first two chapters, and they are almost complete. I will greatly appreciate any suggestions, comments, or corrections.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Mohammad, I am happy that there are people who are trying to implement this program. But as far as I can see, your text does not contain Gödel's theorems (on completeness and incompleteness). Actually, they are the most difficult part of this work. $\endgroup$
    – Sergei Akbarov
    Commented Oct 26, 2018 at 7:16
  • $\begingroup$ @SergeiAkbarov, I plan to add more chapters to the notes, but I have not thought about the details yet. However, one possible approach that comes to my mind is to construct the 1st order logic inside ZFC, and then use it to prove Godel's theorems. This way we can treat the language that we built in the beginning as a meta-language. $\endgroup$
    – Mohammad Safdari
    Commented Oct 26, 2018 at 8:25
  • $\begingroup$ Mohammad, I also forsee some criticism from logicians. Perhaps, it will be good if we could speak directly by email. $\endgroup$
    – Sergei Akbarov
    Commented Oct 26, 2018 at 16:05
  • 1
    $\begingroup$ I admire your goal and that you decided to write a text book which you think is missing. But I think that J Barkley Rosser did most of the ground work already, in Logic for Mathematicians (1953). Not the easiest readable text book ever, but after you get accustomed to his own brand of notation, you will find that most of what you state, has been stated and proved in that book already. Note that Rosser's intention is exactly the same as yours: describe the framework that can act as a basis for mathematics, including set theory (he chooses New Foundations instead of the more common ZF setup). $\endgroup$
    – Maestro13
    Commented Dec 28, 2018 at 10:34
  • 3
    $\begingroup$ @Maestro13 Thanks. I am definitely aware that the ideas for such a development of Mathematics have been known for quite a long time (and I mentioned it in the introduction), but I felt that these ideas have not been presented properly in a text. I have seen Rosser's book, and enjoyed reading it, but as you said it is not an easy read. Especially I think students will have a tough time trying to go through it. My goal is partly to write a text which can be used as a textbook too. $\endgroup$
    – Mohammad Safdari
    Commented Dec 29, 2018 at 11:53
8
$\begingroup$

The problem with Gödel completeness theorem is that it is realy about sets already. It says that every consistent set of formulae has a model. Moreover, this theorem is actually non-trivial from set-theoretic perspective since it requires a weak form of the axiom of choice known as the Boolean prime ideal theorem. So you can't state this theorem without some notion of a set and you can't prove it without some elaborate logic that supports this notion.

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ Well, you need some notion of a set, either formal, introduced in an axiomatic set theory, or informal. But if you use an informal definition, then I think it will be quite hard to prove this theorem since you need an informal justification of the Boolean prime ideal theorem. $\endgroup$
    – Valery Isaev
    Commented Sep 30, 2016 at 20:55
  • 1
    $\begingroup$ I think you can prove the theorem for countable languages without any form of choice. $\endgroup$
    – Michael Greinecker
    Commented Sep 30, 2016 at 20:59
  • 1
    $\begingroup$ @MichaelGreinecke : Yes, it still requires some mild assumptions, but that besides the point. The point is that particularly this theorem uses sets in some non-trivial way. But most of the other basic results in logic can be formulated and proved in a more elementary way, using only arithmetics. $\endgroup$
    – Valery Isaev
    Commented Sep 30, 2016 at 21:10
  • 1
    $\begingroup$ @user62782 : I don't agree with your implicit assumption that introducing the axiom of choice necessitates "formal" or "axiomatic" set theory. In my own education, I learned how to construct arguments using Zorn's lemma long before encountering axiomatic set theory. $\endgroup$
    – Timothy Chow
    Commented Oct 1, 2016 at 0:04
  • 8
    $\begingroup$ @Michael Greinecker: You are likely aware of this, but the the sake of leaving a comment for others to see - no choice is needed, but some nontrivial (i.e. noneffective) set existence axioms are. In general, there are computable theories in countable languages that have no computable models. One example is Peano arithmetic for which the addition and multiplication in a nonstandard model cannot be computable, but by adding false axioms we can force a model to be nonstandard. So some nontrivial assumptions need to exist in the metatheory to prove the completeness theorem in the countable case. $\endgroup$
    – Carl Mummert
    Commented Oct 8, 2016 at 22:38
6
$\begingroup$

Bourbaki's book on set theory is kind of terrible, but it does develop set theory in this super-formalistic way that you're looking for.

I suggest the French second edition instead of the English first edition, since the second edition is a lot easier to follow (and has fewer typos).

I think it's worth adding the warning that actually reading this book is almost totally unrewarding, unless it's something you'd like to see done once. Logicians do not think this way, nor do they really seem to like this book (see for example the two polemics against it by ARD Mathias).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Well, this is a matter of opinion (yours is, I admit, widely spread :) $\endgroup$
    – Duchamp Gérard H. E.
    Commented Feb 8, 2019 at 10:47
  • $\begingroup$ Also, if Bourbaki really wanted to do structuralist mathematics, they could have done categories :-P $\endgroup$
    – David Roberts ♦
    Commented Feb 8, 2019 at 12:41
  • 4
    $\begingroup$ @DuchampGérardH.E. I read (and actually own a copy of) the English version, which is really quite awful. I remember looking at the French second edition much later, and I was pleasantly surprised that it was much more readable (even though I don't speak French). But at any rate, it feels like Bourbaki treated this book mostly as an exercise for himself. I don't think it's really possible to learn set theory from it (unlike Bourbaki's other books, which I generally enjoy). $\endgroup$
    – Harry Gindi
    Commented Feb 8, 2019 at 18:38
  • $\begingroup$ Well, you may be right, I played the devil's advocate because it is the (beloved) book of my childhood. I got your points however. $\endgroup$
    – Duchamp Gérard H. E.
    Commented Feb 8, 2019 at 23:32
5
$\begingroup$

Funny that no one mentions Rosser's Logic for Mathematicians (1953). Try find a pdf on the web for download, or a second hand hard copy offered online. J Barkley Rosser first describes (to the grains of a grain of sand) what a logical system of statements and proofs used by mathematicians should look like. Only then he goes ahead stating axioms for creating sets. He uses Quine's New Foundations (I guess because he likes to state as few axioms as possible so he rejected using ZF). Then he progresses to use sets in statements and proofs. In particular, he proves that the axiom of choice is equivalent to the known list of other statements (every set can be well-ordered; Zorn's lemma; etcetera). The syntax he uses for statements is non-orthodox: he wishes to use as few brackets as possible (I agree) but replaces that by a system of dots which you have to see a number of times before you grasp the idea. But the text is really worth ploughing through. Of course, a couple of months after the book was published, Specker disproved the full axiom of choice in NF. That should nevertheless not deter the use of NF as a basis for mathematics, as there are less rigid variants (only for denumerable sets, or only for sets with cardinality not too close to that of the universe) of the axiom of choice that could still survive in NF (just as AC is relatively consistent with ZF but cannot be proved in it).

Online link to pdf: https://archive.org/details/logicformathemat00ross/page/n5

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .