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 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 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 very well 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 sets to infinite collections. 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 formal fashion. There are many choices for such theories. In this chapter we will discuss the commonly used axioms of Zermelo and Fraenkel.

This chapter serves as an interlude. Our goal in the following chapters is to present a formalized approach to numbers, and then we will look at the number systems again to see how tools of logic are used to uncover their essential features. We will be inspecting the structure of the number systems 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 simple finite structures—finite graphs—and we will examine them from the logical perspective. In other words, later, logic will help us to see structures; now, some simple structures will help us to see logic. An important concept of symmetry of a graph is introduced in Definition 2.1 followed by equally important Theorem 2.1. Both, the definition and the theorem, will be generalized later to arbitrary mathematical structures.

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 with the eyes of logic inside other structures. This chapter can be skipped on the first reading, but it should not be forgotten.

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 some 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 of both structures are concerned, the roles are reversed, the former is very tame while the latter quite wild, and those terms have well-understood 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 (ℕ,

The lattice problem for models of Peano Arithmetic ( $\mathsf {PA}$ ) is to determine which lattices can be represented as lattices of elementary submodels of a model of $\mathsf {PA}$, or, in greater generality, for a given model $\mathcal {M}$, which lattices can be represented as interstructure lattices of elementary submodels $\mathcal {K}$ of an elementary extension $\mathcal {N}$ such that $\mathcal {M}\preccurlyeq \mathcal {K}\preccurlyeq \mathcal {N}$. The problem has been studied for the last 60 years and the results and their proofs show an interesting interplay between the model theory of PA, Ramsey style combinatorics, lattice representation theory, and elementary number theory. We present a survey of the most important results together with a detailed analysis of some special cases to explain and motivate a technique developed by James Schmerl for constructing elementary extensions with prescribed interstructure lattices. The last section is devoted to a discussion of lesser-known results about lattices of elementary submodels of countable recursively saturated models of PA.

Machine generated contents note: 1. Introduction Juliette Kennedy and Roman Kossak; 2. Historical remarks on Suslin's problem Akihiro Kanamori; 3. The continuum hypothesis, the generic-multiverse of sets, and the [OMEGA] conjecture W. Hugh Woodin; 4. [omega]-Models of finite set theory Ali Enayat, James H. Schmerl and Albert Visser; 5. Tennenbaum's theorem for models of arithmetic Richard Kaye; 6. Hierarchies of subsystems of weak arithmetic Shahram Mohsenipour; 7. Diophantine correct open induction Sidney Raffer; 8. Tennenbaum's theorem and recursive reducts James H. Schmerl; 9. History of constructivism in the 20th century A. S. Troelstra; 10. A very short history of ultrafinitism Rose M. Cherubin and Mirco A. Mannucci; 11. Sue Toledo's notes of her conversations with Gödel in 1972-1975 Sue Toledo; 12. Stanley Tennenbaum's Socrates Curtis Franks; 13. Tennenbaum's proof of the irrationality of [the square root of] 2́.

Every infinite mathematical structure M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal{M} $$\end{document} has an extension M∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\mathcal{M}}^{\ast } $$\end{document} that has the same first-order properties as M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal{M} $$\end{document}, but is not isomorphic to M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal{M} $$\end{document}. In this sense, M∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\mathcal{M}}^{\ast } $$\end{document} can be considered a nonstandard extension of M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal{M} $$\end{document}. A short discussion of the idea of nonstandard models is followed by proofs of three easy standard results that use nonstandard extensions in essential ways. The aim is to explain basic model-theoretic concepts behind such proofs.

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.

We introduce a tool for analysing models of$\text {CT}^-$, the compositional truth theory over Peano Arithmetic. We present a new proof of Lachlan’s theorem that the arithmetical part of models of$\text {CT}^-$are recursively saturated. We also use this tool to provide a new proof of theorem from [8] that all models of$\text {CT}^-$carry a partial inductive truth predicate. Finally, we construct a partial truth predicate defined for a set of formulae whose syntactic depth forms a nonstandard cut which cannot be extended to a full truth predicate satisfying$\text {CT}^-$.

The articles in this issue can be divided into three groups. Krajewski’s article, Yong Cheng’s contribution, and a short note by Rudy Rucker, provide detailed mathematical analysis of Lucas-Penrose type arguments. In the second group, with articles by Arnon Avron, Stepan Holub, Panu Raaikiainen, and Albert Visser, the authors discuss the status and various methodological and technical problems of the anti-mechanist arguments. In essence: what does the problem of “minds vs. machines” really mean, and how can it, and how should it, be formulated? Moreover: How to evaluate the merit of arguments that mix formal mathematics and philosophical considerations? The third group consists of the articles that, while including issues from the other two groups, concentrate of more specific themes: an analysis of Georg Kreisel’s observation that it does not logically follow from the fact that a formal system is subject to the second Gödel incompleteness theorems that there are absolutely no means available to prove its consistency ; Per Martin-Löf’s proof that there are no absolute unknowables in constructive mathematics ; diagonal arguments and Chomsky’s approach to linguistic competence as contrasted with arithmetic competence ; and the role in the anti-mechanist arguments of difficulties in capturing the nature of natural numbers in formal systems.

The Logic & Structure project is about the language of mathematical logic and how it can be of use in the visual arts. It involves a conversation between a mathematical logician and a group of artists. The project is ongoing, and this is a report on its first two phases. This text has two parts. The first, “Logic”, is a short introduction to certain aspects of logic, as it was presented to the participants. The second part, “Structures”, describes some of the outcomes.The inspiration for the project comes from modern model theory whose advances revealed the extent to which formal methods may be helpful in describing and analysing mathematical structures. While the structures that are studied are often immensely complex, the formal language in which their properties can be expressed is simple. Its syntax is precisely defined and well understood, and this understanding often successfully guides us in our explorations of the rich world of mathematical objects. Our goal is to see the extent to which a similar approach could be of value when talking about works of art as structures. To this end, one could try to describe existing art objects in terms of suitably chosen formal languages, but we follow a reverse route. The language is described first, and the participating artists are asked to come up with artwork in which formal elements and their relations are chosen in advance, making it easier to identify those features of the created pieces that can be formally expressed. In other words, we are not thinking of applying formal methods to create art; rather we want to begin with samples that can serve as material for discussion.

To find "criteria of simplicity" was the goal of David Hilbert's recently discovered twenty-fourth problem on his renowned list of open problems given at the 1900 International Congress of Mathematicians in Paris. At the same time, simplicity and economy of means are powerful impulses in the creation of artworks. This was an inspiration for a conference, titled the same as this volume, that took place at the Graduate Center of the City University of New York in April of 2013. This volume includes selected lectures presented at the conference, and additional contributions offering diverse perspectives from art and architecture, the philosophy and history of mathematics, and current mathematical practice.

A subset of a model of PA is called neutral if it does not change the dcl relation. A model with undefinable neutral classes is called neutrally expandable. We study the existence and non‐existence of neutral sets in various models of PA. We show that cofinal extensions of prime models are neutrally expandable, and ω1‐like neutrally expandable models exist, while no recursively saturated model is neutrally expandable. We also show that neutrality is not a first‐order property. In the last section, we study a local version of neutral expandability.

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures