Elementary first-order theories of trees allowing at most, exactly $\mathrm{m}$, and any finite number of immediate descendants are introduced and proved mutually interpretable among themselves and with Robinson arithmetic, Adjunctive Set Theory with Extensionality and other well-known weak theories of numbers, sets, and strings.

When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and ${\mathcal {L}}_{\omega _1, \omega }$ -elementary? We find that these are exactly the classes that can be defined by an infinitary formula that has no infinitary disjunctions.

We show that the weakest versions of Foreman’s minimal generic hugeness axioms cannot hold simultaneously on adjacent cardinals. Moreover, conventional forcing techniques cannot produce a model of one of these axioms.

We aim at developing a systematic method of separating omniscience principles by constructing Kripke models for intuitionistic predicate logic $\mathbf {IQC}$ and first-order arithmetic $\mathbf {HA}$ from a Kripke model for intuitionistic propositional logic $\mathbf {IPC}$. To this end, we introduce the notion of an extended frame, and show that each IPC-Kripke model generates an extended frame. By using the extended frame generated by an IPC-Kripke model, we give a separation theorem of a schema from a set of schemata in $\mathbf {IQC}$ and a separation theorem of a sentence from a set of schemata in $\mathbf {HA}$. We see several examples which give us separations among omniscience principles.

In an article published in 1974, Menas conjectured that any stationary subset of can be split in many pairwise disjoint stationary subsets. Even though the conjecture was shown long ago by Baumgartner and Taylor to be consistently false, it is still haunting papers on . In which situations does it hold? How much of it can be proven in ZFC? We start with an abridged history of the conjecture, then we formulate a new version of it, and finally we keep weakening this new assertion until, building on the work of Usuba, we hit something we can prove.

We put in print a classical result that states that for most purposes, there is no harm in assuming the existence of saturated models in model theory. The presentation is aimed for model theorists with only basic knowledge of axiomatic set theory.

Reasoning with quantifier expressions in natural language combines logical and arithmetical features, transcending strict divides between qualitative and quantitative. Our topic is this cooperation of styles as it occurs in common linguistic usage and its extension into the broader practice of natural language plus ‘grassroots mathematics’.

We begin with a brief review of $\mathsf {FO}(\#)$, first-order logic with counting operators and cardinality comparisons. This system is known to be of very high complexity, and drowns out finer aspects of the combination of logic and counting. We therefore move to a small fragment that can represent numerical syllogisms and basic reasoning about comparative size: monadic first-order logic with counting, $\mathsf {MFO}(\#)$. We provide normal forms that allow for axiomatization, determine which arithmetical notions can be defined on finite and on infinite models, and conversely, we discuss which logical notions can be defined out of purely arithmetical ones, and what sort of (non-)classical logics can be induced.

Next, we investigate a series of strengthenings of $\mathsf {MFO}(\#)$, again using normal form methods. The monadic second-order version is close, in a precise sense, to additive Presburger Arithmetic, while versions with the natural device of tuple counting take us to Diophantine equations, making the logic undecidable. We also define a system $\mathsf {ML}(\#)$ that combines basic modal logic over binary accessibility relations with counting, needed to formulate ubiquitous reasoning patterns such as the Pigeonhole Principle. We prove decidability of $\mathsf {ML}(\#)$, and provide a new kind of bisimulation matching the expressive power of the language.

As a complement to the fragment approach pursued here, we also discuss two other ways of lowering the complexity of $\mathsf {FO}(\#)$ by changing the semantics of counting in natural ways. A first approach replaces cardinalities by abstract but well-motivated values of ‘mass’ or other mereological aggregating notions. A second approach keeps the cardinalities but generalizes the meaning of counting to work in models that allow dependencies between variables.

Finally, we return to our starting point in natural language, confronting the architecture of our formal systems with linguistic quantifier vocabulary and syntax, as well as with natural reasoning modules such as the monotonicity calculus. In addition to these encounters with formal semantics, we discuss the role of counting in semantic evaluation procedures for quantifier expressions and determine, for instance, which binary quantifiers are computable by finite ‘semantic automata’. We conclude with some general thoughts on yet further entanglements of logic and counting in formal systems, on rethinking the qualitative/quantitative divide, and on connecting our analysis to empirical findings in cognitive science.

After discussing the limitations inherent to all set-theoretic reflection principles akin to those studied by A. Lévy et. al. in the 1960s, we introduce new principles of reflection based on the general notion of Structural Reflection and argue that they are in strong agreement with the conception of reflection implicit in Cantor’s original idea of the unknowability of the Absolute, which was subsequently developed in the works of Ackermann, Lévy, Gödel, Reinhardt, and others. We then present a comprehensive survey of results showing that different forms of the new principle of Structural Reflection are equivalent to well-known large cardinal axioms covering all regions of the large-cardinal hierarchy, thereby justifying the naturalness of the latter.

We investigate a variety of cut and choose games, their relationship with (generic) large cardinals, and show that they can be used to characterize a number of properties of ideals and of partial orders: certain notions of distributivity, strategic closure, and precipitousness.

Free choice sequences play a key role in the intuitionistic theory of the continuum and especially in the theorems of intuitionistic analysis that conflict with classical analysis, leading many classical mathematicians to reject the concept of a free choice sequence. By treating free choice sequences as potentially infinite objects, however, they can be comfortably situated alongside classical analysis, allowing a rapprochement of these two mathematical traditions. Building on recent work on the modal analysis of potential infinity, I formulate a modal theory of the free choice sequences known as lawless sequences. Intrinsically well-motivated axioms for lawless sequences are added to a background theory of classical second-order arithmetic, leading to a theory I call $MC_{LS}$. This theory interprets the standard intuitionistic theory of lawless sequences and is conservative over the classical background theory.

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are not necessarily direct or expected.

There seems to be a view that intuitionists not only take the Axiom of Choice (AC) to be true, but also believe it a consequence of their fundamental posits. Widespread or not, this view is largely mistaken. This article offers a brief, yet comprehensive, overview of the status of AC in various intuitionistic and constructivist systems. The survey makes it clear that the Axiom of Choice fails to be a theorem in most contexts and is even outright false in some important contexts. Of the systems surveyed, only intensional type theory renders AC a theorem, but the extent of AC in that theory does not include, for instance, real analysis. Only a small amount of extensionality is required in order for the obvious proof an intuitionist might offer for AC to break down.

For any subset $Z \subseteq {\mathbb {Q}}$, consider the set $S_Z$ of subfields $L\subseteq {\overline {\mathbb {Q}}}$ which contain a co-infinite subset $C \subseteq L$ that is universally definable in L such that $C \cap {\mathbb {Q}}=Z$. Placing a natural topology on the set ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$ of subfields of ${\overline {\mathbb {Q}}}$, we show that if Z is not thin in ${\mathbb {Q}}$, then $S_Z$ is meager in ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$. Here, thin and meager both mean “small”, in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fields L have the property that the ring of algebraic integers $\mathcal {O}_L$ is universally definable in L. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every $\exists $-definable subset of an algebraic extension of ${\mathbb Q}$ is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials.

We present a proof system for a multimode and multimodal logic, which is based on our previous work on modal Martin-Löf type theory. The specification of modes, modalities, and implications between them is given as a mode theory, i.e., a small 2-category. The logic is extended to a lambda calculus, establishing a Curry–Howard correspondence.

Currently the two popular ways to practice Robinson’s nonstandard analysis are the model-theoretic approach and the axiomatic/syntactic approach. It is sometimes claimed that the internal axiomatic approach is unable to handle constructions relying on external sets. We show that internal frameworks provide successful accounts of nonstandard hulls and Loeb measures. The basic fact this work relies on is that the ultrapower of the standard universe by a standard ultrafilter is naturally isomorphic to a subuniverse of the internal universe.

We answer some questions about graphs that are reducts of countable models of Anti-Foundation, obtained by considering the binary relation of double-membership $x\in y\in x$ . We show that there are continuum-many such graphs, and study their connected components. We describe their complete theories and prove that each has continuum-many countable models, some of which are not reducts of models of Anti-Foundation.