Roman Kossak

This book is about a formal approach to mathematical structures. Formal methods are by their very nature formal. When studying mathematical logic, initially one often has to grit ones teeth and absorb certain preliminary definitions on faith. Concepts are given precise definitions, and their meaning is revealed later, after one has had a chance to see their utility. We will try to follow a different route. Before all formalities are introduced, in this chapter, we will take a detour to see examples of mathematical statements and some elements of the language that is used to express them.

In the previous chapter, we introduced and named an actually infinite set. The set of natural numbers ℕ={0,1,2,…}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {N}}=\{0,1,2,\dots \}$$\end{document}. What is the structure of this set? We will give a simple answer to this question, and then we will proceed with a reconstruction of the arithmetic structures of the integers and the rational numbers in terms of first-order logic. The reconstruction is technical and rather tedious, but it serves as a good example of how some mathematical structures can bee seen inside other structures with the eyes of logic. This chapter can be skipped on the first reading, but it should not be forgotten.

This chapter serves as an interlude. Our goal in the following chapters is to show how tools of logic can used to uncover essential features of familiar number structures. We will be inspecting number structures with our logic glasses on, but we need to get used to wearing those glasses. In this chapter we will take a look at some easy to visualize structures—finite graphs—and we will examine them from the logical perspective. In other words, later, logic will help us to see structures; now, simple structures will help us to see logic. A concept of symmetry of a graph is introduced in Definition 2.1 followed by Theorem 2.1, which is crucial for many further developments. Both, the definition and the theorem, will be generalized later to arbitrary mathematical structures.

In the previous chapter we saw how a large portion of mathematics can be formalized in first-order logic. The very fact that the construction of the classical number structures can be formalized this way makes first-order logic relevant, but is it necessary? For centuries mathematics has been developing successfully without much attention paid to formal rigor, and it is still practiced this way. When intuitions don’t fail us, there is no need for excessive formalism, but what happens when they do? Intuition can be misleading, especially when infinity is involved. In this chapter, we will see how seemingly innocuous assumptions about actually infinite sets lead to consequences that are not easy to accept. Then, we will go back to our discussion of a formal approach that will help to make some sense out of it.

In previous chapters we introduced mathematical structures, and we followed with a detailed description of basic number structures. Now it is time to look at structures in general. The classical number structures fit the definition: a set with a set of relations on it. But what about other structures? Are they all sets? Can a set of relations always be associated with them? Clearly not. Not everything in this world is a set. I am a structured living organism, but I am definitely not a set. Nevertheless, once a serious investigation of set theory got underway, it revealed a fantastically rich universe of sets, and it showed that, in a certain sense, every structure can be thought of a set with a set of relations on it. To explain how it is possible, we need to get a closer look at sets. As we saw in the previous chapter, the deceptively simple intuitive concept of set (collection) leads to unexpected consequences when we apply the well understood properties of finite collections to infinite sets. The role of axiomatic set theory is to provide basic and commonly accepted principles from which all other knowledge about infinity should follow in a rigorous fashion. There are many choices for such theories. In this chapter we will discuss the commonly used axioms of Zermelo and Fraenkel.

In Chap. 1, we used addition and multiplication of the natural numbers to introduce first-order logic. Now, equipped with formal logic, we will go back to reconstruct the natural numbers and other number systems that are built on them. The set of natural numbers with a set of two relations—addition and multiplication—is a fundamental mathematical structure. In the previous discussion, we took the structure of natural numbers for granted, and we saw how some of its features can be described using first-order logic. Now we will examine the notion of natural number more carefully. It will not be as easy as one could expect.

In this final chapter we will discuss connections between definability in first-order logic and in Lω1,ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L_{\omega _1,\omega }}$$\end{document}, as well as the number of symmetric images of functions and relations. There will be no proofs of general results, but we will see how they work with the aid of examples from previous sections.

This book is about mathematical logic, but so far the discussion has focused only on first-order logic as a formal language in which properties of structures can be expressed. Finding a language that can serve this purpose was just the first and not an insignificant step towards realization of Hilbert’s program. This chapter is about the second step: formalizing the notion of logical consequence. We will describe the model-theoretic approach, which allows us to give short proofs of several major results by bypassing the necessary technicalities of proof theory, but first a few words must be said about the proof-theoretic account.

One of the primary questions that motivated the development of model theory was: Which structures are determined by their first-order properties? While Theorem A.1 (located in the appendix) shows that all structures with finite domains are so determined, even if their language is infinite, all structures with infinite domains are never determined by their first-order properties. If a theory in a countable language has a countable model, then it not only has both countable and uncountable models, but models of arbitrary infinite cardinality. Models with domains of different cardinalities are never isomorphic—thus, if by counting we mean assigning a cardinal number to some collection of objects, then there are too many nonisomorphic models to count. The situation changes if the size of the domain is fixed. In this chapter we will discuss two essential cases: models with countable domains and models with domains the size of the set of real numbers. To avoid some set-theoretic complications, we will only consider theories in finite or countable languages.

All further discussion will be based on a formal definition of relation, given in Definition 7.1. Then, in Definition 7.2, we introduce the central notion of definability in structures, and we proceed with examples of structures with small domains, including the two element algebraic field F2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_2$$\end{document}.

In the previous chapter we saw examples of mathematical structures that are simple enough to allow a complete analysis of the parametrically definable subsets of their domains. Those structures are of interest, but the real objects of study in mathematics are richer structures such as (ℚ,+,⋅)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$({\mathbb {Q}},+,\cdot )$$\end{document} or (ℝ,+,⋅)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$({\mathbb {R}},+,\cdot )$$\end{document}. To talk about them we first need to take a closer look into their definable sets. Definable sets in each structure form a geometry in which the operations on sets are unions, intersections, complements, Cartesian products, and projections from higher to lower dimensions. We will see how those operations correspond in a natural way to Boolean connectives and quantifiers, and how the name “geometry” is justified when it is applied to sets definable in the field of real numbers. The last two sections are devoted to a discussion of the negative solution to Hilbert’s 10th problem.

In this chapter we will compare two classical structures: the field of complex numbers (ℂ,+,⋅)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$({\mathbb {C}},+,\cdot )$$\end{document} and the standard model of arithmetic (ℕ,+,⋅)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$({\mathbb {N}},+,\cdot )$$\end{document}. The former is vast and mysterious, the latter deceptively simple. As it turns out, as far as the model-theoretic properties are concerned, the roles are reversed, the former is tame while the latter quite wild, and those terms have precise meanings. In recent years, tameness has become a popular word in model theory. Tameness is not defined formally, but a structure is considered tame if the geometry of its definable sets is well-described and understood. Tameness has different levels. The most tame structures are the minimal ones. All parametrically definable unary relations in a minimal structure are either finite or cofinite. The examples of minimal structures that we have seen so far are the structures with no relations on them—the trivial structures—and (ℕ,

This textbook is a second edition of the successful, Mathematical Logic: On Numbers, Sets, Structures, and Symmetry. It retains the original two parts found in the first edition, while presenting new material in the form of an added third part to the textbook. The textbook offers a slow introduction to mathematical logic, and several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions. Part I, Logic Sets, and Numbers, shows how mathematical logic is used to develop the number structures of classical mathematics. All necessary concepts are introduced exactly as they would be in a course in mathematical logic; but are accompanied by more extensive introductory remarks and examples to motivate formal developments. The second part, Relations, Structures, Geometry, introduces several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions, and shows how they are used to study and classify mathematical structures. The added Part III to the book is closer to what one finds in standard introductory mathematical textbooks. Definitions, theorems, and proofs that are introduced are still preceded by remarks that motivate the material, but the exposition is more formal, and includes more advanced topics. The focus is on the notion of countable categoricity, which analyzed in detail using examples from the first two parts of the book. This textbook is suitable for graduate students in mathematical logic and set theory and will also be of interest to mathematicians who know the technical aspects of the subject, but are not familiar with its history and philosophical background.

In Chap. 10.1007/978-3-319-97298-5_1, we used addition and multiplication of the natural numbers to introduce first-order logic. Now, equipped with formal logic, we will go back and we will reconstruct the natural numbers and other number systems that are built on them. This looks circular, and to some extent it is. The set of natural numbers with a set of two relations—addition and multiplication—is a fundamental mathematical structure. In the previous discussion, we took the structure of natural numbers for granted, and we saw how some of its features can be described using first-order logic. Now we will examine the notion of natural number more carefully. It will not be as easy as one could expect.

In the previous chapter we saw how a large portion of mathematics can be formalized in first-order logic. The very fact that the construction of the classical number structures can be formalized this way makes first-order logic relevant, but is it necessary? For centuries mathematics has been developing successfully without much attention paid to formal rigor, and it is still practiced this way. When intuitions don’t fail us, there is no need for excessive formalism, but what happens when they do? In modern mathematics intuition can be misleading, especially when actual infinity is involved. In this chapter, we will see how seemingly innocuous assumptions about actually infinite sets lead to consequences that are not easy to accept. Then, we will go back to our discussion of a formal approach that will help to make some sense out of it.