This paper is intended to give for a general mathematical audience a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly (...) universality and renormalization issues in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws. (shrink)

ABSTRACT The Gödel–Dummett logic and Łukasiewicz one are two main many-valued logics used by the fuzzy logic community. Our goal is a quantitative comparison of these two. In this paper, we will mostly consider the 3-valued Gödel–Dummett logic as well as the 3-valued Łukasiewicz one. We shall concentrate on their implicational-negation fragments which are limited to formulas formed with a fixed finite number of variables. First, we investigate the proportion of the number of true formulas of a certain length n (...) to the number of all formulas of such length built with exactly one variable. Then, we investigate such proportion for satisfiable formulas. Second, we generalise our investigation on formulas written with $ k\ge 1 $ k ≥ 1 variables. The primary goal of the paper is the research on the asymptotic behaviour of these fractions when the length n tends to infinity. If such limits exists, they are real numbers between 0 and 1, which are called the density of truth or the density of SAT. To compare the density of truth and the density of satisfiable formulas for both fragments of 3-valued Gödel–Dummett's and Łukasiewicz's logics we use the powerful theory of analytic combinatorics. This paper is a natural continuation of the previous brief conference note by Kostrzycka and Zaionc (2020) as well as enriched with some previous results from Kostrzycka and Zaionc (2003). In the conference note we computed analytically the density of truth and the density of SAT (with a determined precision) for 3-valued Łukasiewicz's logic restricted to a language with only one variable. In Kostrzycka and Zaionc (2003) we computed the same values for exactly the same fragment of the 3-valued Gödel–Dummett logic. This paper answers the more general questions of the existence of density of truth and density of SAT for both many-valued logics with an arbitrary finite number of variables. Therefore this paper gives an an interesting picture of two main families of finite-valued fuzzy logics problems treated quantitatively. This picture is taken from the perspective of classical logic. It shows that unexpectedly there is quantitatively a little distance between these two approaches. (shrink)

The Gödel–Dummett logic and Łukasiewicz one are two main many-valued logics used by the fuzzy logic community. Our goal is a quantitative comparison of these two. In this paper, we will mostly consider the 3-valued Gödel–Dummett logic as well as the 3-valued Łukasiewicz one. We shall concentrate on their implicational-negation fragments which are limited to formulas formed with a fixed finite number of variables. First, we investigate the proportion of the number of true formulas of a certain length n to (...) the number of all formulas of such length built with exactly one variable. Then, we investigate such proportion for satisfiable formulas. Second, we generalise our investigation on formulas written with k≥1 variables. The primary goal of the paper is the research on the asymptotic behaviour of these fractions when the length n tends to infinity. If such limits exists, they are real numbers between 0 and 1, which are called the density of truth or the density of SAT. To compare the density of truth and the density of satisfiable formulas for both fragments of 3-valued Gödel–Dummett's and Łukasiewicz's logics we use the powerful theory of analytic combinatorics. This paper is a natural continuation of the previous brief conference note by Kostrzycka and Zaionc (Citation2020) as well as enriched with some previous results from Kostrzycka and Zaionc (Citation2003). In the conference note we computed analytically the density of truth and the density of SAT (with a determined precision) for 3-valued Łukasiewicz's logic restricted to a language with only one variable. In Kostrzycka and Zaionc (Citation2003) we computed the same values for exactly the same fragment of the 3-valued Gödel–Dummett logic. This paper answers the more general questions of the existence of density of truth and density of SAT for both many-valued logics with an arbitrary finite number of variables. Therefore this paper gives an an interesting picture of two main families of finite-valued fuzzy logics problems treated quantitatively. This picture is taken from the perspective of classical logic. It shows that unexpectedly there is quantitatively a little distance between these two approaches. (shrink)

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, and (...) proven to be extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...) the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (shrink)

We consider logical expressions built on the single binary connector of implication and a finite number of literals . We prove that asymptotically, when the number of variables becomes large, all tautologies have the following simple structure: either a premise equal to the goal, or two premises which are opposite literals.

In this paper we prove general exact unprovability results that show how a threshold between provability and unprovability of a finite well-quasi-orderedness assertion of a combinatorial class is transformed by the sequence-construction, multiset-construction, cycle-construction and labeled-tree-construction. Provability proofs use the asymptotic pigeonhole principle, unprovability proofs use Weiermann-style compression techniques and results from analytic combinatorics.

It is conventionally understood that computers play a rather limited role in theoretical mathematics. While computation is indispensable in applied mathematics and the theory of computing and algorithms is rich and thriving, one does not, even today, expect to find computers in theoretical mathematics settings beyond the theory of computing. Where computers are used, by those studying combinatorics , algebra, number theory, or dynamical systems, the computer most often assumes the role of an automated and speedy theoretician, performing manipulations (...) and checking cases in a way assumed to be possible for human theoreticians, if only they had the time, the memory, and the precision. Automated proofs have become standard tools in mathematical logic, and it is often expected that proofs be published in a computer-checkable format. It is not surprising, then, that most philosophical work on computers in theoretical mathematics has been on computers' roles as supplementary mathematicians. Donald MacKenzie's 2001 book Mechanizing Proof demonstrates the rich potential for social and historical studies to complement the substantial analytic debate in this area of philosophy. But what of computers in theoretical mathematics behaving as computers, and not as mere mechanized mathematicians? Very little role is commonly assumed for computers working as supplements to mathematicians, rather than as supplementary mathematicians themselves. Accordingly, very little philosophy has attempted to grapple with theoretical mathematics in which computers play an essential but essentially non-theoretical role. My presentation will draw on work I conducted as a researcher in harmonic analysis on fractals at Cornell University. I will analyze the explicit and implicit conceptual apparatus employed in my and my fellow researchers' use of computers in the theoretical study of second order differential equations, such as those for sound and heat flow, on various fractal analogues of the Sierpinski gasket. Such gaskets are easy to visualize in very crude approximation in a low number of dimensions. As one increases the complexity of the gasket or the refinement of one's analysis, visualization and precise computation become impossible, and soon computers are unable to produce even approximate data to model differential equations in these situations. We thus had to carefully choose analytic approaches and methods to make our theoretical mathematics amenable to computer simulation. In my case, studying the transformation of the gaskets as they are expanded into increasingly high dimensions, computer simulation eventually required that the problem be reimagined entirely in terms of interlinked systems of parameters. This computer-approximation-driven theoretical orientation shaped my mathematical intuitions toward the problem and guided my fellow researchers and me in both theoretical and computational directions. We discovered both that computer approximation could be incredibly powerful as an aid to intuition, and that it can be incredibly difficult to transfer computer-oriented mathematics back into the purely theoretical standards of our area of specialty. I will address the philosophical implications of computer-driven theoretical mathematics, asking how computer experiments can shape both the content and standards of theoretical sciences. (shrink)

Over the past two decades, gamblers have begun taking mathematics into account more seriously than ever before. While probability theory is the only rigorous theory modeling the uncertainty, even though in idealized conditions, numerical probabilities are viewed not only as mere mathematical information, but also as a decision-making criterion, especially in gambling. This book presents the mathematics underlying the major games of chance and provides a precise account of the odds associated with all gaming events. It begins by explaining in (...) simple terms the meaning of the concept of probability for the layman and goes on to become an enlightening journey through the mathematics of chance, randomness and risk. It then continues with the basics of discrete probability, combinatorics and counting arguments for those interested in the supporting mathematics. These mathematic sections may be skipped by readers who do not have a minimal background in mathematics; these readers can skip directly to the Guide to Numerical Results to pick the odds and recommendations they need for the desired gaming situation. Doing so is possible due to the organization of that chapter, in which the results are listed at the end of each section, mostly in the form of tables. The chapter titled The Mathematics of Games of Chance presents these games not only as a good application field for probability theory, but also in terms of human actions where probability-based strategies can be tried to achieve favorable results. Through suggestive examples, the reader can see what are the experiments, events and probability fields in games of chance and how probability calculus works there. The main portion of this work is a collection of probability results for each type of game. Each game s section is packed with formulas and tables. Each section also contains a description of the game, a classification of the gaming events and the applicable probability calculations. The primary goal of this work is to allow the reader to quickly find the odds for a specific gaming situation, in order to improve his or her betting/gaming decisions. Every type of gaming event is tabulated in a logical, consistent and comprehensive manner. The complete methodology and complete or partial calculations are shown to teach players how to calculate probability for any situation, for every stage of the game for any game. Here, readers can find the real odds, returned by precise mathematical formulas and not by partial simulations that most software uses. Collections of odds are presented, as well as strategic recommendations based on those odds, where necessary, for each type of gaming situation. The book contains much new and original material that has not been published previously and provides great coverage of probabilities for the following games of chance: Dice, Slots, Roulette, Baccarat, Blackjack, Texas Hold em Poker, Lottery and Sport Bets. Most of games of chance are predisposed to probability-based decisions. This is why the approach is not an exclusively statistical one, but analytical: every gaming event is taken as an individual applied probability problem to solve. A special chapter defines the probability-based strategy and mathematically shows why such strategy is theoretically optimal.". (shrink)

One of the traditional ways mathematical ideas and even new areas of mathematics are created is from experiments. One of the best-known examples is that of the Fermat hypothesis, which was conjectured by Fermat in his attempts to find integer solutions for the famous Fermat equation. This hypothesis led to the creation of a whole field of knowledge, but it was proved only after several hundred years. This book, based on the author's lectures, presents several new directions of mathematical research. (...) All of these directions are based on numerical experiments conducted by the author, which led to new hypotheses that currently remain open, i.e., are neither proved nor disproved. The hypotheses range from geometry and topology (statistics of plane curves and smooth functions) to combinatorics (combinatorial complexity and random permutations) to algebra and number theory (continuous fractions and Galois groups). For each subject, the author describes the problem and presents numerical results that led him to a particular conjecture. In the majority of cases there is an indication of how the readers can approach the formulated conjectures (at least by conducting more numerical experiments). Written in Arnold's unique style, the book is intended for a wide range of mathematicians, from high school students interested in exploring unusual areas of mathematics on their own, to college and graduate students, to researchers interested in gaining a new, somewhat nontraditional perspective on doing mathematics. In the interest of fostering a greater awareness and appreciation of mathematics and its connections to other disciplines and everyday life, MSRI and the AMS are publishing books in the Mathematical Circles Library series as a service to young people, their parents and teachers, and the mathematics profession. Titles in this series are co-published with the Mathematical Sciences Research Institute (MSRI). (shrink)

Drug design methods have made significant new advances over the last ten years, mainly in the areas of molecular modelling. In more recent times important developments in theory have led to a different type of modelling becoming possible, the so‐called de novo or automated design algorithms. In this new method the programs perform much of the chemist's thinking, in finding appropriately sized chemical groups to fit into a target site. However this is a combinatoric problem which has no general analytical (...) solution; it is ripe for optimization. Other advances, such as combinatorial chemical synthesis and screening, will dramatically influence the search for new lead structures for target sites, which at present are poorly understood. Already these methods are being applied to peptide libraries. Peptides do not make good drug compounds because of their poor bioavailability; further, their flexibility reduces their affinity. In some cases peptide backbones can be removed and replaced with rigid non‐peptide scaffolds. (shrink)

ABSTRACT: The 3rd BCE Stoic logician "Chrysippus says that the number of conjunctions constructible from ten propositions exceeds one million. Hipparchus refuted this, demonstrating that the affirmative encompasses 103,049 conjunctions and the negative 310,952." After laying dormant for over 2000 years, the numbers in this Plutarch passage were recently identified as the 10th (and a derivative of the 11th) Schröder number, and F. Acerbi showed how the 2nd BCE astronomer Hipparchus could have calculated them. What remained unexplained is why Hipparchus’ (...) logic differed from Stoic logic, and consequently, whether Hipparchus actually refuted Chrysippus. This paper closes these explanatory gaps. (1) I reconstruct Hipparchus’ notions of conjunction and negation, and show how they differ from Stoic logic. (2) Based on evidence from Stoic logic, I reconstruct Chrysippus’ calculations, thereby (a) showing that Chrysippus’ claim of over a million conjunctions was correct; and (b) shedding new light on Stoic logic and – possibly – on 3rd century BCE combinatorics. (3) Using evidence about the developments in logic from the 3rd to the 2nd centuries, including the amalgamation of Peripatetic and Stoic theories, I explain why Hipparchus, in his calculations, used the logical notions he did, and why he may have thought they were Stoic. OPEN ACCESS LINK. (shrink)

Seventeenth-century “chance combinatorics” was a self-contained theory. It had an objective notion of chance derived from physical devices with chance properties, such as casts of dice, combinatorics to count chances and, to interpret their significance, a rule for converting these counts into fair wagers. It lacked a notion of chance as a measure of belief, a precise way to connect chance counts with frequencies and a way to compare chances across different games. These omissions were not needed for (...) the theory’s interpretation of chance counts: determining which are fair wagers. The theory provided a model for how indefinitenesses could be treated with mathematical precision in a special case and stimulated efforts to seek a broader theory. (shrink)

We study the distributivity of the bounded ideal on Pkλ and answer negatively to a question of Johnson in [13]. The size of non-normal ideals with the partition property is also studied.

This book covers a wide variety of topics in combinatorics and graph theory.

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our (...) main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. (shrink)

We characterize the completely determined Borel subsets of HYP as exactly the [Formula: see text] subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, (...) this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author. (shrink)

Marion Scheepers, in his studies of the combinatorics of open covers, introduced the property asserting that a cover of type can be split into two covers of type . In the first part of this paper we give an almost complete classification of all properties of this form where and are significant families of covers which appear in the literature , using combinatorial characterizations of these properties in terms related to ultrafilters on . In the second part of the (...) paper we consider the questions whether, given and , the property is preserved under taking finite or countable unions, arbitrary subsets, powers or products. Several interesting problems remain open. (shrink)

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence Φ iff Φ holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all Φ for which the associated sequence (...) of propositional formulas 〈Φ〉 n , encoding that Φ holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all Φ feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy Φ thus gives a super polynomial lower bound for the size of P-proofs of 〈Φ〉 n . We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R * (log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures. (shrink)

Ramsey type theorems are theorems of the form: if certain sets are partitioned at least one of the parts has some particular property. In its finite form, Ramsey's theory will ask how big the partitioned set should be to assure this fact. Proofs of such theorems usually require a process of multiple choice, so that this apparently pure combinatoric field is rich in proofs that use ideal guides in making the choices. Typically they may be ultrafilters or points in the (...) compactification of the given set. It is, therefore, not surprising that nonstandard elements are much more natural guides in some of the proofs and in the general abstract treatment.In Section 1 we start off with some very natural examples of Ramsey type exercises that illustrate our idea. In Section 2 we give a nonstandard proof of the infinite Ramsey theorem. Section 3 tries to do the same for Hindman's theorem, and points out, where nonstandard analysis must use some hard standard facts to make the proof go through. (shrink)

We recall the notions of weak and strong Euler characteristics on a first order structure and make explicit the notion of a Grothendieck ring of a structure. We define partially ordered Euler characteristic and Grothendieck ring and give a characterization of structures that have non-trivial partially ordered Grothendieck ring. We give a generalization of counting functions to locally finite structures, and use the construction to show that the Grothendieck ring of the complex numbers contains as a subring the ring of (...) integer polynomials in continuum many variables. We prove the existence of a universal strong Euler characteristic on a structure. We investigate the dependence of the Grothendieck ring on the theory of the structure and give a few counter-examples. Finally, we relate some open problems and independence results in bounded arithmetic to properties of particular Grothendieck rings. (shrink)

We recall the notions of weak and strong Euler characteristics on a first order structure and make explicit the notion of a Grothendieck ring of a structure. We define partially ordered Euler characteristic and Grothendieck ring and give a characterization of structures that have non-trivial partially ordered Grothendieck ring. We give a generalization of counting functions to locally finite structures, and use the construction to show that the Grothendieck ring of the complex numbers contains as a subring the ring of (...) integer polynomials in continuum many variables. We prove the existence of a universal strong Euler characteristic on a structure. We investigate the dependence of the Grothendieck ring on the theory of the structure and give a few counter-examples. Finally, we relate some open problems and independence results in bounded arithmetic to properties of particular Grothendieck rings. (shrink)

In this paper we introduce a new property of families of functions on the Baire space, called pseudo-dominating, and apply the properties of these families to the study of cardinal characteristics of the continuum. We show that the minimum cardinality of a pseudo-dominating family is min{.

Mathematical Essays in Honor of Gian-Carlo Rota, Boston, Basel, Berlin, ... Crapo, H. (1993), On the Anick-Rota Representation of the Bracket Ring of the ...

We lay the combinatorial foundations for [5] by setting up and proving the essential properties of the coding apparatus for singular cardinals. We also prove another result concerning the coding apparatus for inaccessible cardinals.

We show that the modal propositional logic G, originally introduced to describe the modality "it is provable that", is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □ κ holds for all $\kappa ; on the other hand, it (...) is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation. (shrink)

Classes of forcings which add a real by forcing with branching conditions are examined, and conditions are found which guarantee that the generic real is of minimal degree over the ground model. An application is made to almost-disjoint coding via a real of minimal degree.

The ‘syntax’ and ‘combinatorics’ of my title are what Curry (1961) referred to as phenogrammatics and tectogrammatics respectively. Tectogrammatics is concerned with the abstract combinatorial structure of the grammar and directly informs semantics, while phenogrammatics deals with concrete operations on syntactic data structures such as trees or strings. In a series of previous papers (Muskens, 2001a; Muskens, 2001b; Muskens, 2003) I have argued for an architecture of the grammar in which finite sequences of lambda terms are the basic data (...) structures, pairs of terms syntax, semantics for example. These sequences then combine with the help of simple generalizations of the usual abstraction and application operations. This theory, which I call Lambda Grammars and which is closely related to the independently formulated theory of Abstract Categorial Grammars (de Groote, 2001; de Groote, 2002), in fact is an implementation of Curry’s ideas: the level of tectogrammar is encoded by the sequences of lambda-terms and their ways of combination, while the syntactic terms in those sequences constitute the phenogrammatical level. In de Groote’s formulation of the theory, tectogrammar is the level of abstract terms, while phenogrammar is the level of object terms. (shrink)

We construct a model in which the singular cardinal hypothesis fails at ℵωℵω. We use characterizations of genericity to show the existence of a projection between different Prikry type forcings.

We characterize some large cardinal properties, such as μ-measurability and P 2 (κ)-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on P κ (2 κ ). This leads to the characterization of 2 κ -supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, Full κ , of P κ (2 κ ), whose elements code measures on cardinals less than κ. (...) The hypothesis that Full κ is stationary (a weaker assumption than 2 κ -supercompactness) is equivalent to a higher order Lowenheim-Skolem property, and settles a question about directed versus chain-type unions on P κ λ. (shrink)

We compute the model-theoretic Grothendieck ring, \\), of a dense linear order with or without end points, \\), as a structure of the signature \, and show that it is a quotient of the polynomial ring over \ generated by \\) by an ideal that encodes multiplicative relations of pairs of generators. This ring can be embedded in the polynomial ring over \ generated by \. As a corollary we obtain that a DLO satisfies the pigeon hole principle for definable (...) subsets and definable bijections between them—a property that is too strong for many structures. (shrink)