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)

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 present a version for κ-distributive ideals over a regular infinite cardinal κ of some of the combinatorial results of Mathias on happy families. We also study an associated notion of forcing, which is a generalization of Mathias forcing and of Prikry forcing.

This thesis divides naturally into two parts, each concerned with the extent to which the theory of $L$ can be changed by forcing.The first part focuses primarily on applying generic-absoluteness principles to how that definable sets of reals enjoy regularity properties. The work in Part I is joint with Itay Neeman and is adapted from our paper Happy and mad families in $L$, JSL, 2018. The project was motivated by questions about mad families, maximal families of infinite subsets of (...) $\omega $ of which any two have only finitely many members in common. We begin, in the spirit of Mathias, by establishing a strong Ramsey property for sets of reals in the Solovay model, giving a new proof of Törnquist’s theorem that there are no infinite mad families in the Solovay model.In Chapter 3 we stray from the main line of inquiry to briefly study a game-theoretic characterization of filters with the Baire Property.Neeman and Zapletal showed, assuming roughly the existence of a proper class of Woodin cardinals, that the boldface theory of $L$ cannot be changed by proper forcing. They call their result the Embedding Theorem, because they conclude that in fact there is an elementary embedding from the $L$ of the ground model to that of the proper forcing extension. With a view toward analyzing mad families under $\mathsf {AD}^+$ and in $L$ under large-cardinal hypotheses, in Chapter 4 we establish triangular versions of the Embedding Theorem. These are enough for us to use Mathias’s methods to show that there are no infinite mad families in $L$ under large cardinals and that $\mathsf {AD}^+$ implies that there are no infinite mad families. These are again corollaries of theorems about strong Ramsey properties under large-cardinal assumptions and $\mathsf {AD}^+$, respectively. Our first theorem improves the large-cardinal assumption under which Todorcevic established the nonexistence of infinite mad families in $L$. Part I concludes with Chapter 5, a short list of open questions.In the second part of the thesis, we undertake a finer analysis of the Embedding Theorem and its consistency strength. Schindler found that the the Embedding Theorem is consistent relative to much weaker assumptions than the existence of Woodin cardinals. He defined remarkable cardinals, which can exist even in L, and showed that the Embedding Theorem is equiconsistent with the existence of a remarkable cardinal. His theorem resembles a theorem of Harrington–Shelah and Kunen from the 1980s: the absoluteness of the theory of $L$ to ccc forcing extensions is equiconsistent with a weakly compact cardinal. Joint with Itay Neeman, we improve Schindler’s theorem by showing that absoluteness for $\sigma $ -closed $\ast $ ccc posets—instead of the larger class of proper posets—implies the remarkability of $\aleph _1^V$ in L. This requires a fundamental change in the proof, since Schindler’s lower-bound argument uses Jensen’s reshaping forcing, which, though proper, need not be $\sigma $ -closed $\ast $ ccc in that context. Our proof bears more resemblance to that of Harrington–Shelah than to Schindler’s.The proof of Theorem 6.2 splits naturally into two arguments. In Chapter 7 we extend the Harrington–Shelah method of coding reals into a specializing function to allow for trees with uncountable levels that may not belong to L. This culminates in Theorem 7.4, which asserts that if there are $X\subseteq \omega _1$ and a tree $T\subseteq \omega _1$ of height $\omega _1$ such that X is codable along T, then $L$ -absoluteness for ccc posets must fail.We complete the argument in Chapter 8, where we show that if in any $\sigma $ -closed extension of V there is no $X\subseteq \omega _1$ codable along a tree T, then $\aleph _1^V$ must be remarkable in L.In Chapter 9 we review Schindler’s proof of generic absoluteness from a remarkable cardinal to show that the argument gives a level-by-level upper bound: a strongly $\lambda ^+$ -remarkable cardinal is enough to get $L$ -absoluteness for $\lambda $ -linked proper posets.Chapter 10 is devoted to partially reversing the level-by-level upper bound of Chapter 9. Adapting the methods of Neeman, Hierarchies of forcing axioms II, we are able to show that $L$ -absoluteness for $\left |\mathbf {R}\right |\cdot \left |\lambda \right |$ -linked posets implies that the interval $[\aleph _1^V,\lambda ]$ is $\Sigma ^2_1$ -remarkable in L.prepared by Zach Norwood.E-mail: [email protected]. (shrink)

This paper deals mainly with generalizations of results in finitary combinatorics to infinite ordinals. It is well-known that for finite ordinals ∑bT<αβ is the number of 2-element subsets of an α-element set. It is shown here that for any well-ordered set of arbitrary infinite order type α, ∑bT<αβ is the ordinal of the set M of 2-element subsets, where M is ordered in some natural way. The result is then extended to evaluating the ordinal of the set (...) of all n-element subsets for each natural number n ≥ 2. Moreover, series ∑β<αf are investigated and evaluated, where α is a limit ordinal and the function f belongs to a certain class of functions containing polynomials with natural number coefficients. The tools developed for this result can be extended to cover all infinite α, but the case of finite α appears to be quite problematic. (shrink)

We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.

Aggregative consequentialism and several other popular moral theories are threatened with paralysis: when coupled with some plausible assumptions, they seem to imply that it is always ethically indifferent what you do. Modern cosmology teaches that the world might well contain an infinite number of happy and sad people and other candidate value-bearing locations. Aggregative ethics implies that such a world contains an infinite amount of positive value and an infinite amount of negative value. You can affect only (...) a finite amount of good or bad. In standard cardinal arithmetic, an infinite quantity is unchanged by the addition or subtraction of any finite quantity. So it appears you cannot change the value of the world. Modifications of aggregationism aimed at resolving the paralysis are only partially effective and cause severe side effects, including problems of “fanaticism”, “distortion”, and erosion of the intuitions that originally motivated the theory. Is the infinitarian challenge fatal? (shrink)

We discuss conceptual change and progress within mathematics, in particular how tools, structural concepts and representations are transferred between fields that appear to be unconnected or remote from each other. The theoretical background is provided by the frame concept, which is used in linguistics, cognitive science and artificial intelligence to model how explicitly given information is combined with expectations deriving from background knowledge. In mathematical proofs, we distinguish two kinds of frames, namely structural frames and ontological frames. The interaction between (...) both kinds of frames can drive mathematical interpretation. We first discuss two examples where structural frames (formulaic notation) drive ontological development (the discovery or exploration of mathematical objects). The development of Boole’s Boolean algebra may at first appear as a metaphorical treatment of the (then) new area of logic. In the analysis, we discuss how different (aspects of) certain algebraic frames change in the transfer, how arising difficulties are solved and overall argue that Boole uses the numerical algebra frame as a research template for the discovery of a system for calculations in logic. Following Ifrah, we analyse the discovery of zero as an extension to the number ontology as driven by the development of notation. Both structural and ontological frames are extended and simplified as notation progresses. Finally, we discuss two examples from infinite combinatorics, viz. topological graph theory, and one foundational issue. In both examples, the two simultaneous frames about one object are maintained independently. They motivate different research questions, but may also fruitfully interact: shifting between multiple synchronously maintained perspectives acts as a motor of innovation. The analysis shows how a frame-based approach allows to model how different perspectives drive mathematical innovation because they highlight different aspects, questions and heuristics. (shrink)

We continue the exploration of various aspects of divisibility of ultrafilters, adding one more relation to the picture: multiplicative finite embeddability. We show that it lies between divisibility relations \ and \. The set of its minimal elements proves to be very rich, and the \-hierarchy is used to get a better intuition of this richness. We find the place of the set of \-maximal ultrafilters among some known families of ultrafilters. Finally, we introduce new notions of largeness of subsets (...) of \, and compare it to other such notions, important for infinite combinatorics and topological dynamics. (shrink)

The dissertation under comment is a contribution to the area of Set Theory concerned with the interactions between the method of Forcing and the so-called Large Cardinal axioms.The dissertation is divided into two thematic blocks. In Block I we analyze the large-cardinal hierarchy between the first supercompact cardinal and Vopěnka’s Principle. In turn, Block II is devoted to the investigation of some problems arising from Singular Cardinal Combinatorics.We commence Part I by investigating the Identity Crisis phenomenon in the region (...) comprised between the first supercompact cardinal and Vopěnka’s Principle. As a result, we generalize Magidor’s classical theorems [2] to this higher region of the large-cardinal hierarchy. Also, our analysis allows to settle all the questions that were left open in [1]. Finally, we conclude Part I by presenting a general theory of preservation of $C^{}$ -extendible cardinals under class forcing iterations. From this analysis we derive several applications. For instance, our arguments are used to show that an extendible cardinal is consistent with “ $^{\mathrm {HOD}}<\lambda ^+$, for every regular cardinal $\lambda $.” In particular, if Woodin’s HOD Conjecture holds, and therefore it is provable in ZFC + “There exists an extendible cardinal” that above the first extendible cardinal every singular cardinal $\lambda $ is singular in HOD and $^{\textrm {{HOD}}}=\lambda ^+$, there may still be no agreement at all between V and HOD about successors of regular cardinals.In Part II and Part III we analyse the relationship between the Singular Cardinal Hypothesis with other relevant combinatorial principles at the level of successors of singular cardinals. Two of these are the Tree Property and the Reflection of Stationary sets, which are central in Infinite Combinatorics.Specifically, Part II is devoted to prove the consistency of the Tree Property at both $\kappa ^+$ and $\kappa ^{++}$, whenever $\kappa $ is a strong limit singular cardinal witnessing an arbitrary failure of the SCH. This generalizes the main result of [3] in two senses: it allows arbitrary cofinalities for $\kappa $ and arbitrary failures for the SCH.In the last part of the dissertation we introduce the notion of $\Sigma $ -Prikry forcing. This new concept allows an abstract and uniform approach to the theory of Prikry-type forcings and encompasses several classical examples of Prikry-type forcing notions, such as the classical Prikry forcing, the Gitik-Sharon poset, or the Extender Based Prikry forcing, among many others.Our motivation in this part of the dissertation is to prove an iteration theorem at the level of the successor of a singular cardinal. Specifically, we aim for a theorem asserting that every $\kappa ^{++}$ -length iteration with support of size $\leq \kappa $ has the $\kappa ^{++}$ -cc, provided the iterates belong to a relevant class of $\kappa ^{++}$ -cc forcings. While there are a myriad of works on this vein for regular cardinals, this contrasts with the dearth of investigations in the parallel context of singular cardinals. Our main contribution is the proof that such a result is available whenever the class of forcings under consideration is the family of $\Sigma $ -Prikry forcings. Finally, and as an application, we prove that it is consistent—modulo large cardinals—the existence of a strong limit cardinal $\kappa $ with countable cofinality such that $\mathrm {SCH}_\kappa $ fails and every finite family of stationary subsets of $\kappa ^+$ reflects simultaneously. (shrink)

We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.

When no single universal model for a set of structures exists at a given cardinal, then one may ask in which models of set theory does there exist a small family which embeds the rest. We show that for λ+-graphs (λ regular) omitting cliques of some finite or uncountable cardinality, it is consistent that there are small universal families and 2λ > λ+. In particular, we get such a result for triangle-free graphs.

No chance of seeing her for another fortnight and it is 11 days since I saw her. Went solitary walk felt miserable but to some extent staved it off by reflecting on |$\langle$|Continuum Problem|$\rangle$|1The occasion for this review article on the life and accomplishments of Frank Ramsey is the publication in the last eight years of three important books: a biography of Frank Ramsey by his sister, Margaret Paul, a book by Steven Methven on aspects of Ramsey’s philosophy, and the (...) recent biography of Ramsey written by Cheryl Misak. In a companion piece [Mancosu, 2020] I discuss Ramsey’s contacts with logicians in continental Europe and publish previously unpublished letters from Ramsey to Abraham Fraenkel and to Heinrich Behmann.1. INTRODUCTIONFrank Plumpton Ramsey (1903–1930) will be well known to the readers of this journal. His contributions to philosophy, mathematics, and economics have left a lasting legacy. In mathematical logic and philosophy of mathematics, Ramsey’s solution to the paradoxes by means of a simple theory of types [1926a] and Ramsey’s theorem in combinatorics (both finite and infinite [1930]) are among Ramsey’s most celebrated contributions. Ramsey is a key presence in accounts of Wittgenstein’s, Russell’s, and Moore’s lives and work. It is well known that it was Ramsey who translated the Tractatus into English and wrote what is still considered a very insightful review [1923] of the Tractatus. Wittgenstein mentioned the importance of his conversations with Ramsey in 1929 in Cambridge as having influenced his transition to the views presented in the Philosophical Investigations. Ramsey also contributed, in 1924, to the second edition of Principia Mathematica (see [Linsky, 2011]). While Ramsey’s friendship with Moore does not have an analogous concrete precipitate as the work on the Tractatus or Principia Mathematica, it is evident from the correspondence and other documents that Ramsey’s work in philosophy (truth, propositions, universals, etc.) influenced Moore. Of course, the direction of influence goes also the other way around. Wittgenstein, Russell, and Moore, among others, were essential in shaping Ramsey’s approach to philosophy. (shrink)

A biologically unavoidable sequence is an infinite gender sequence which occurs in every gendered, infinite genealogical network satisfying certain tame conditions. We show that every eventually periodic sequence is biologically unavoidable (this generalizes König's Lemma), and we exhibit some biologically avoidable sequences. Finally we give an application of unavoidable sequences to cellular automata.

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of finite structures. Some (...) topics in finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory. In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems. The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here. (shrink)

We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are p-divisible for infinitely many primes p, or groups of the form ⊕ p∈I Z(p ∞ ), where I is an infinite set of primes.

Language sciences have long maintained a close and supposedly necessary coupling between the infinite productivity of the human language faculty and recursive grammars. Because of the formal equivalence between recursion and non-recursive iteration; recursion, in the technical sense, is never a necessary component of a generative grammar. Contrary to some assertions this equivalence extends to both center-embedded relative clauses and hierarchical parse trees. Inspection of language usage suggests that recursive rule components in fact contribute very little, and likely nothing (...) significant, to linguistic creativity. Further than this, if the productivity of human language is considered as not rigidly bound, but not infinite, then the need for any sort of iteration in generative grammars vanishes and can be replaced with a Non-iterative Explicit Alternatives Rule grammar. The knock-on effects of dispensing with recursive grammar components are: that language diversity can simply be based on rule and lexicon combinatorics with no potentially infinite dimensions derived from recursive or iterative components of rules; the oddity of a vast, multiply-infinite competence set of ‘grammatical but unacceptable’ productions is gone; and the development of a language faculty based on rules that eschew iterative rule components avoids any need for explaining ‘special’ mechanisms. On the broader front of searching for the mechanisms of mind, our analysis can be similarly applied to the proposals for a recursive basis for mind as an explanation for humanity’s great leap forward. (shrink)

Topology uses simple geometric and algebraic ideas, but its huge success and vast ramifications make it a tough nut for historians of twentieth‐century mathematics. Two books have addressed it well: Dieudonné chronicles about one thousand key definitions and theorems, and essays in James focus on forty central themes. Both assume considerable mathematics, but neither offers a historical synthesis of the simplest core ideas. Now, Alain Herreman uses semiotics to watch these leading ideas develop through the founding works of Henri Poincaré, (...) Oswald Veblen, James Alexander, and Solomon Lefschetz. Herreman states outright that semiotics will not exhaust these meanings, but he makes it a revealing tool.The method is especially suited to Poincaré, who will define one technical term repeatedly in a single work, each time differently, as if it was the first, and perhaps no definition will match any use of the term in proofs. For Poincaré no term gets meaning from a definition. Each functions in relation to the others—that is, specifically in relation to other terms in Poincaré's work. It is no use invoking standards of rigor current in Poincaré's time and place or then‐current definitions. Poincaré was well known at the time for using neither: Poincaré's meanings must be derived from his writing, as Herreman does.Herreman bases his semiotics on Hjelmslev yet refutes Hjelmslev's concern that mathematics may be “monoplanar,” with no content beyond the signs themselves . The book depicts four levels of content at work in these authors: algebraic, geometric, arithmetic, and set theoretic. Herreman says a sign has algebraic content if its use depends on its written expression, the way polynomials are formal expressions added and multiplied by formal rules. Early topologists—here especially Alexander—sought purely combinatorial methods. Thus a “cube” is a set of six “faces,” twelve “edges,” and eight “vertices,” each taken as primitive and described only by a short table showing which ones meet which. Combinatorics typifies arithmetic content for Herreman. Yet a cube is also an infinite set of points. Herreman speaks of geometric content when a sign indicates both a set of parts and a set of points. Today we might use different notations for the set of points and the set of parts—Poincaré et al. did not. Herreman will not reconstruct their works or restate them in other words; rather, he uses these levels of content to organize extensive quotations and analyze the relations in each text as they move toward deeper union of the algebraic and geometric.The chapter on Lefschetz makes a great finale. Lefschetz is arguably Poincaré's closest and greatest student, though the two never met. Like Poincaré's, his work is at once compelling and baffling, decisive for the future of mathematics yet brutally difficult to absorb. Semiotics serves well in presenting this mathematician who “never stated a false theorem or gave a correct proof,” as his friends joked.The book does not go far into theorems. Yet it requires some background. A beginner might enjoy it with Alexandroff , a gem itself, written with unusually strong historic sense. Specialists will enjoy reading it with the original works for its fresh viewpoints and novel connections. It is a fine way to analyze the works, to see how they create their own meanings. (shrink)

We investigate degree of satisfiability questions in the context of Heyting algebras and intuitionistic logic. We classify all equations in one free variable with respect to finite satisfiability gap, and determine which common principles of classical logic in multiple free variables have finite satisfiability gap. In particular we prove that, in a finite non-Boolean Heyting algebra, the probability that a randomly chosen element satisfies $x \vee \neg x = \top $ is no larger than $\frac {2}{3}$. Finally, we generalize our (...) results to infinite Heyting algebras, and present their applications to point-set topology, black-box algebras, and the philosophy of logic. (shrink)

Elsasser outlines in an informal but meticulous fashion an organismic biology which promises, in his opinion, to combine the best features of epigenetic vitalism and preformationist mechanism. Mechanistic reductionism is for Elsasser an unverifiable metaphysical hypothesis; i.e., if the postulate of infinite homogenous classes is dropped from the axiomatics of Van Neumann's proof that the state of any system is, in principle, Quantum Mechanically determinable, it becomes combinatorically obvious that biological systems and classes are radically inhomogenous [[sic]], a fact (...) which operationally bars the way to any complete reductionism. The door is thus opened to an open-ended theoretical biology in which all questions do not have a truth-functional equivalent answer according to the axioms and laws of the science, and prediction in the science becomes statistical in a nonabsolute way. Elsasser is a physicist with more than a casual acquaintance with biology and his argument benefits by his obvious expertise in both of these areas. Philosophically, however, he is a lightweight and relies, in particular, too much on the ontological ice that might be cut by operationalism. Theories are not verified in the stringent operational sense; they are confirmed in a way which is not logically tied to the requirement that all laws be inductively established. Elsasser, however, has so much to say on the problem of reductionism in biology that is of obvious value that the book is easily recommended over these caveats.—E. A. R. (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)

How could physicalism be true of a world in which there are no fundamental physical phenomena? A familiar answer, due to Barbara Gail Montero and others, is that physicalism could be true of such a world if that world does not contain an infinite descent of mentality. Christopher Devlin Brown has produced a counterexample to that solution. We show how to modify the solution to accommodate Brown’s example: physicalism could be true of a world without fundamental physical phenomena if (...) that world does not contain an infinite descent of mentally constituted mentality. This solution is independently plausible and is available to physicalists of virtually all significant varieties. (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)

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)

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)

This chapter challenges Cantor’s notion of the ‘power’, or ‘cardinality’, of an infinite set. According to Cantor, two infinite sets have the same cardinality if and only if there is a one-to-one correspondence between them. Cantor showed that there are infinite sets that do not have the same cardinality in this sense. Further, he took this result to show that there are infinite sets of different sizes. This has become the standard understanding of the result. The (...) chapter challenges this, arguing that we have no reason to think there are infinite sets of different sizes. It begins with an initial argument against Cantor’s claim that there are infinite sets of different sizes and then proceeds, by way of an analogy between Cantor’s mathematical result and Russell’s paradox, to a more direct argument. (shrink)

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

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

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.

Attempts a faithful account of Bruno's thought as expressed in his writings and to give an analysis of his thought as he developed it in regard to the issue of the infinitive.

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

Alexander Pruss and I have proposed an analysis of omnipotence which makes no use of the problematic terms 'power' and 'ability'. However, this raises an obvious worry: if our analysis is not related to the notion of power, then how can it count as an analysis of omnipotence, the property of being all-powerful, at all? In this paper, I show how omnipotence can be understood as the possession of infinite power (general, universal, or unlimited power) rather than the possession (...) of particular powers. I then argue that the ordinary notions of particular powers or abilities can be understood as applying vague limitations to the notion of infinite power. The vagueness of these limitations is the source of the well-known difficulties in the analysis of ability. (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)

Attempts a faithful account of Bruno's thought as expressed in his writings and to give an analysis of his thought as he developed it in regard to the issue of the infinitive.

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)