[Math] Highly Rigorous Logic Book

Question

I am looking for a highly rigorous book on mathematical logic that goes into great detail, even at the foundations. I'm looking for something that say, develops propositional and first-order logic through discussion of free semigroups and words, rigorously proves unique readability, etc. Does such a book exist? Even some of the more rigorous books I've encountered have handwaived around alot. Thanks in advance for any response.

Answer 1

Kleene's Introduction to Metamathematics and Kleene's Mathematical Logic are two books that are well worth looking at for what you want. They're a bit dated, but I don't think this would be much of a problem for what you want. For what it's worth, on many occasions I've seen references (in papers and books) to one or both of Kleene's books for some technical or obscure point that is often overlooked or omitted in other texts.

The following excerpt from pp. 23-24 of Introduction to Metamathematics is an example of what I mean by a "technical or obscure point that is often overlooked or omitted in other texts".

(from pp. 23-24) In mathematical formulas parentheses are introduced in pairs to show which way the parts of the formula should be associated. In complicated cases different species of parentheses such as $(\;),$ $\{\;\},$ $[\;]$ may be employed; and very complicated cases may be avoided by various abbreviations. However, the question exists in principle whether, using one species of parentheses only, the association of a formula is unambiguously fixed by its parentheses. (The question is equivalent to a geometrical one concerning nesting of intervals.) To make the question precise, suppose we have $2n$ parentheses, $n$ of them being left parentheses $(,$ and $n$ of them right parentheses $),$ and that they occur in linear order from left to right. This is the way they would occur in a mathematical formula, the other symbols of the formula which we need not notice now being interspersed among them. We say that two pairs of parentheses separate each other, if they occur in the order $(_{i}\;(_{j}\;)_{i}\;)_{j},$ where the $i$’s identify either pair and the $j$’s the other, and other parentheses may occur interspersed among the four shown. We define a $1-1$ pairing of the $n$ left parentheses with the $n$ right parentheses (briefly, a pairing of the $2n$ parentheses) to be proper, if a left parenthesis is always paired with a right parenthesis to the right of it, and if no two of the pairs separate each other. It is almost immediate that if $2n$ parentheses are properly paired, on removing any of the pairs, the remaining parentheses are properly paired. Also the parentheses included between a given pair in the proper pairing of the $2n$ parentheses are properly paired. The following three lemmas contain the answer to the proposed question about some related information.

LEMMA 1. A proper pairing of $2n$ parentheses $(n>0)$ contains an innermost pair, i.e. a pair which includes no other of the parentheses between them.

[proof omitted in this excerpt]

LEMMA 2. A set of $2n$ parentheses admits at most one proper pairing.

[proof omitted in this excerpt]

LEMMA 3. If $2n$ parentheses and a consecutive subset of $2m$ of them both admit proper pairings, then the proper pairing in the subset forms a part of the proper pairing in the whole set, i.e. each parenthesis of the subset has the same mate in both pairings.

[proof omitted in this excerpt]