The papers are listed in reverse chronological order, except that I put two surveys at the beginning to make them easier to find.
Nearly Countable Cardinals
PostScript or PDF
An expository talk, for a general mathematical audience, about cardinal characteristics of the continuum.
Combinatorial Cardinal Characteristics of the Continuum (to appear as a chapter in the Handbook of Set Theory (ed. M. Foreman, M. Magidor, and A. Kanamori))
PostScript or PDF
This survey of the theory of cardinal characteristics of the continuum is to appear as a chapter in the "Handbook of Set Theory." As the title indicates, I concentrate on the combinatorial characteristics; Tomek Bartoszynski has written a chapter on the category and measure characteristics.
Power-Dedekind Finiteness
This paper, not intended for publication, presents some results about the sets whose power sets are Dedekind-finite. In finite-support Fraenkel-Mostowski models, these coincide with the orbit-finite sets, but we consider them in the more general context of arbitrary models of set theory without the axiom of choice.
Axioms and Models for an Extended Set Theory, joint with D. L. Childs
We present the axioms of extended set theory (XST) and the ideas underlying the axioms. The fundamental difference from classical set theory (ZFC) is that XST is based on a ternary membership relation, "x is an element of y with scope s." XST allows sets to have more elements with large scopes than with small scopes; this facilitates the formalization of some aspects of category theory. We also present an interpretation of XST in ZFC plus ``there exist arbitrarily large inaccessible cardinals,'' thereby proving the consistency of XST relative to this mild large-cardinal extension of ZFC.
Voting Rules for Infinite Sets and Boolean Algebras (in "Advances in Logic (The North Texas Logic Conference)" ed. S. Gao, S. Jackson, and Y. Zhang, A.M.S. (Contemporary Math. 425) (2007) pp. 87-103)
A voting rule in a Boolean algebra B is an upward closed subset that contains, for each element x in B, exactly one of x and -x. We study several aspects of voting rules, with special attention to their relationship with ultrafilters. In particular, we study the set-theoretic hypothesis that all voting rules in the Boolean algebra of subsets of the natural numbers modulo finite sets are nearly ultrafilters. We define the notion of support of a voting rule and use it to describe voting rules that are, in a sense, as different as possible from ultrafilters. Finally, we consider how much of the axiom of choice is needed to guarantee the existence of voting rules.
Inaccessible Cardinals Without the Axiom of Choice, joint with Ioanna Dimitriou and Benedikt Loewe (Fund. Math. 194 (2007) pp. 179-189)
We consider four notions of strong inaccessibility that are equivalent in ZFC and show that they are not equivalent in ZF. We determine all the provable implications between the four.
Mad Families and Their Neighbors, joint with Tapani Hyttinen and Yi Zhang
We study several sorts of maximal almost disjoint families, both on a countable set and on uncountable, regular cardinals. We relate the associated cardinal invariants with bounding and dominating numbers and also with the uniformity of the meager ideal and some of its generalizations.
The number of near-coherence classes of ultrafilters is either finite or 2^c, joint with Taras Banakh (in "Set Theory. Centre de Recerca Matem\`atica, Barcelona, 2003--2004," ed. J. Bagaria and S. Todorcevic, Trends in Mathematics, Birkhauser (2006) 257-273).
We prove that the number of near-coherence classes of non-principal ultrafilters on the natural numbers is either finite or 2^c, where c is the cardinal of the continuum. Moreover, in the latter case the Stone-Cech compactification of a countable discrete space contains a closed subset consisting of 2^c pairwise non-nearly-coherent ultrafilters. We obtain some additional information about such closed sets under certain assumptions involving the cardinal characteristics u and d. Applying our main result to the Stone-Cech remainder of a closed half-line we obtain that the number of composants of this remainder is either finite or 2^c.
Ultrafilters and Partial Products of Infinite Cyclic Groups, joint with Saharon Shelah
PostScript or PDF
We consider, for infinite cardinals k and m, the additive group of sequences of integers, of length k, with non-zero entries in fewer than m positions. Our main result characterizes, in terms of the cardinals, when one such group can be embedded in another. The proof involves some set-theoretic results, one about families of finite sets and one about families of ultrafilters.
Why sets?, joint with Yuri Gurevich (Bull. Europ. Assoc. Theoret. Comp. Sci. 84 (2004) 139-156)
Sets play a key role in foundations of mathematics. Why? To what extent is it an accident of history? Imagine that you have a chance to talk to mathematicians from a far away planet. Would their mathematics be set-based? What are the alternatives to the set-theoretic foundation of mathematics? Besides, set theory seems to play a significant role in computer science, in particular in database theory and formal methods. Is there a good justification for that? We discuss these and some related issues.
Unsplit Families, Dominating Families, and Ultrafilters
PostScript or PDF
We study some weakenings of the finite intersection property for families of subsets of the natural numbers. The weakenings involve (1) requiring intersections for only a fixed number of sets from the family and (2) requiring the sets to have elements near each other rather than actually intersecting. These weakenings fit into a chain of implications, none of which are reversible under CH, but almost all of which are consistently reversible. We also connect these properties with weakened domination properties for families for functions on the natural numbers. For unsplit families of sets, the chain of implications collapses from infinitely many properties to just four.
Sums, Products, and Choice for Finite Sets
PostScript or PDF
We work in set theory without the axiom of choice, so infinite sums and products of cardinal numbers may not be well defined. We consider the special case of sums or products of countably many copies of the same finite cardinal number n. We characterize the sets of integers that can, consistently with ZF, occur as the set of n such that the product (or the sum) of countably many copies of n is well defined.
This paper is not intended for publication. Of the main results, one is due not to me but to Paul Howard, and the other is essentially already in my paper "Cohomology detects failures of the axiom of choice" (Trans. Amer. Math. Soc. 279 (1983) 257--269).
Nearly Adequate Sets (in "Logic and Algebra", edited by Yi Zhang, Contemporary Math. 302 (2002) 33-48)
PostScript or PDF
When a cardinal characteristic of the continuum is defined as the minimum cardinality of any family of reals with a certain property, we call families with this property "adequate" for that characteristic. In many cases, there are weakenings of "adequate" that still imply that the family's cardinality is at least the characteristic in question. We analyze a few such weakenings. Our main results are partition theorems relating these weakenings to each other or to the original notions of adequacy.
Finite Preimages Under the Natural Map from beta(N x N) to (beta N)x(beta N), joint with Gugu Moche (Topology Proceedings 26 (2001-2002) 407-432)
PostScript or PDF
Let i from beta(NxN) to (beta N)x(beta N) be the continuous extension
of the identity map of NxN. We provide elementary proofs of several
sharp results about the possible sizes of preimages of points (p,q) in
N*xN*. Among these are:
If (p,q) has only two preimages, then both p and q are P-points, but,
assuming the existence of at least 3 non-isomorphic, selective
ultrafilters on N, there are p and q such that (p,q) has only 3
preimages but p is not a P-point.
If (p,q) has at most 5 preimages, then at least one of p and q is a
P-point, but assuming the existence of at least 4 non-isomorphic
selective ultrafilters on N, there are p and q such that neither of
them is a P-point and (p,q) has only 6 preimages.
If (p,p) has at most 8 preimages then p is a
P-point, but assuming the existence of infinitely many non-isomorphic,
selective ultrafilters on N, there is a non-P-point p such that (p,p)
has only 9 preimages.
Divisibility of Dedekind Finite Sets, joint with David Blair and Paul Howard (Journal of Mathematical Logic 5 (2005) 58-74)
PostScript or PDF
A Dedekind-finite set is said to be divisible by a natural number n if it can be partitioned into pieces of size n. We study several aspects of this notion, as well as the stronger notion of being partitionable into n pieces of equal size. Among our results are that the divisors of a Dedekind-finite set can consistently be any set of natural numbers (containing 1 but not 0), that a Dedekind-finite power of 2 cannot be divisible by 3, and that a Dedekind-finite set can be congruent modulo 3 to all of 0, 1, and 2 simultaneously. (In these results, 2 and 3 serve as typical examples; the full results are more general.)
A Note on Extensions of Asymptotic Density, joint with Ryszard Frankiewicz, Grzegorz Plebanek, and Czeslaw Ryll-Nardzewski (Proc. Amer. Math. Soc. 130 (2002) 1581-1587)
PostScript or PDF
By a density we mean any extension of the asymptotic density to a finitely additive measure defined on all sets of natural numbers. We consider densities associated to ultrafilters on the natural numbers and investigate two additivity properties of such densities. In particular, we show that there is a density whose associated L_1 space is complete.
Needed Reals and Recursion in Generic Reals (Ann. Pure Appl. Logic 109 (2001) 77-88)
PostScript or PDF
Let A be a binary relation on reals. Call a set X of reals adequate for A if every real is A-related to one in X. (Many cardinal characteristics of the continuum are defined as the smallest cardinality of any set adequate for a certain relation.) Call a real r needed for A if every set adequate for A has an element relative to which r is recursive. We study the reals needed for various relations A that arise in the theory of cardinal characteristics. We also study the related question of what can be said about a real in the ground model if it is recursive in generic reals of various sorts.
On the cofinality of ultrapowers, joint with Heike Mildenberger (J. Symbolic Logic 64 (1999) 727-736)
PostScript or PDF
We prove some restrictions on the possible cofinalities of ultrapowers of the natural numbers with respect to ultrafilters on the natural numbers. The restrictions involve three cardinal characteristics of the continuum, the splitting number s, the unsplitting number r, and the groupwise density number g. We also prove some related results for reduced powers with respect to filters other than ultrafilters.
Reductions Between Cardinal Characteristics (Set Theory (Annual Boise Extravaganza in Set Theory Conference, 1992-94) (ed. T. Bartoszynski and M. Scheepers) Contemporary Math. 192 (1996) 31-49)
PostScript or PDF
We discuss two general aspects of the theory of cardinal characteristics of the continuum, especially of proofs of inequalities between such characteristics. The first aspect is to express the essential content of these proofs in a way that makes sense even in models where the inequalities hold trivially (e.g., because the continuum hypothesis holds). For this purpose, we use a Borel version of Vojtas's theory of generalized Galois-Tukey connections. The second aspect is to analyze a sequential structure often found in proofs of inequalities relating one characteristic to the minimum (or maximum) of two others. Vojtas's max-min diagram, abstracted from such situations, can be described in terms of a new, higher-type object in the category of generalized Galois-Tukey connections. It turns out to occur also in other proofs of inequalities where no minimum (or maximum) is mentioned.
Propositional Connectives and the Set Theory of the Continuum (CWI Quarterly (Special issue for SMC 50 Jubilee) 9 (1996) 25-30)
PostScript or PDF
This talk is a survey of two topics of recent interest in mathematical logic, namely linear logic and cardinal characteristics of the continuum. I shall try to explain enough about each of them to be able to point out how they are connected. Since the underlying ideas of the two topics are quite different, I regard the existence of a connection as surprising.
Baer Meets Baire: Applications of Category Arguments and Descriptive Set Theory to Z^{aleph_0}, joint with John Irwin (Abelian Groups and Modules (ed. K. M. Rangaswamy and D. Arnold) Marcel Dekker 193-202)
PostScript or PDF
We apply the Baire category theorem and other classical results of descriptive set theory to the study of the structure of the group Z^{aleph_0} of infinite sequences of integers and some of its subgroups.
Baire Category for Monotone Sets (From Foundations to Applications (European Logic Colloquium 1993) (ed. W. Hodges, J. M. E. Hyland, C. Steinhorn, and J. Truss) Oxford Univ. Press (1996) 59-69)
PostScript or PDF
We study Baire category for subsets of 2^omega that are downward-closed with respect to the almost-inclusion ordering (on the power set of the natural numbers, identified with 2^omega). We show that it behaves better in this context than for general subsets of 2^omega. In the downward-closed context, the ideal of meager sets is prime and b-complete (where b is the bounding number), while the complementary filter is g-complete (where g is the groupwise density cardinal). We also discuss other cardinal characteristics of this ideal and this filter, and we show that analogous results for measure in place of category are not provable in ZFC.
Questions and Answers -- A Category Arising in Linear Logic, Complexity Theory, and Set Theory (Advances in Linear Logic (ed. J.-Y. Girard, Y. Lafont, and L. Regnier) London Math. Soc. Lecture Notes 222 (1995) 61-81)
PostScript or PDF
A category used by de Paiva to model linear logic also occurs in Vojtas's analysis of cardinal characteristics of the continuum. Its morphisms have been used in describing reductions between search problems in complexity theory. We describe this category and how it arises in these various contexts. We also show how these contexts suggest certain new multiplicative connectives for linear logic. Perhaps the most interesting of these is a sequential composition suggested by the set-theoretic application.
Cardinal Characteristics and the Product of Countably Many Infinite Cyclic Groups (J. Algebra 169 (1994) 512-540)
PostScript or PDF
We study, from a set-theoretic point of view, those subgroups of the infinite direct product Z^{aleph_0} for which all homomorphisms to Z annihilate all but finitely many of the standard unit vectors. Specifically, we relate the smallest possible size of such a subgroup to several of the standard cardinal characteristics of the continuum. We also study some related properties and cardinals, both group-theoretic and set-theoretic. One of the set-theoretic properties and the associated cardinal are combinatorially natural, independently of any connection with algebra.
On the divisible parts of quotient groups (Abelian Group Theory and Related Topics (ed. R. Goebel, P. Hill, and W. Liebert) Contemporary Math. 171 (1994) 37-50)
PostScript or PDF
Techniques of combinatorial set theory are applied to the following algebraic problem. Suppose G is an abelian group such that, for all countable subgroups C, the divisible part of the quotient G/C is countable. What can one conclude about the size of the divisible part of G/K when the cardinality of the subgroup K is a given uncountable cardinal?
Partition Theorems for Spaces of Variable Words, joint with Vitaly Bergelson and Neil Hindman (Proc. London Math. Soc. (3) 68 (1994) 449-476)
PostScript or PDF
Furstenberg and Katznelson applied methods of topological dynamics to Ramsey theory, obtaining a density version of the Hales-Jewett partition theorem. Inspired by their methods, but using spaces of ultrafilters instead of their metric spaces, we prove a generalization of a theorem of Carlson about variable words. We extend this result to partitions of finite or infinite sequences of variable words, and we apply these extensions to strengthen a partition theorem of Furstenberg and Katznelson about combinatorial subspaces of the set of words.
Ultrafilters: Where Topological Dynamics = Algebra = Combinatorics (Topology Proc. 18 (1993) 33-56)
PostScript or PDF
We survey some connections between topological dynamics, semigroups of ultrafilters, and combinatorics. As an application, we give a proof, based on ideas of Bergelson and Hindman, of the Hales-Jewett partition theorem.
Simple cardinal characteristics of the continuum (Set Theory of the Reals (ed. H. Judah) Israel Math. Conf. Proc. 6 (1993) 63-90)
PostScript or PDF
We classify many cardinal characteristics of the continuum according to the complexity, in the sense of descriptive set theory, of their definitions. The simplest characteristics (boldface Sigma^0_2 and, under suitable restrictions, Pi^0_2) are shown to have pleasant properties, related to Baire category. We construct models of set theory where (unrestricted) boldface Pi^0_2-characteristics behave quite chaotically and no new characteristics appear at higher complexity levels. We also discuss some characteristics associated with partition theorems and we present, in an appendix, a simplified proof of Shelah's theorem that the dominating number is less than or equal to the independence number.
Ultrafilters related to Hindman's finite-unions theorem and its extensions (Logic and Combinatorics (ed. S. Simpson) Contemp. Math. 65 (1987) 89-124)
We investigate ultrafilters, on the set of finite subsets of the natural numbers, that are analogous to the strongly summable ultrafilters introduced by Hindman in the same volume. In particular, we study their relationship to various sorts of special ultrafilters on the natural numbers and to certain strengthenings of Hindman's finite-unions theorem due to Milliken and Taylor. The investigation also leads to some new strengthenings of Hindman's theorem. (I thank Peter Krautzberger for preparing a downloadable version of this old paper and the next two.)
Existence of bases implies the axiom of choice (Axiomatic Set Theory (ed. J. E. Baumgartner, D. A. Martin, and S. Shelah) Contemp. Math. 31 (1984) 31-34)
The axiom of choice follows, in Zermelo-Fraenkel set theory, from the assertion that every vector space has a basis.
Long ago, I started writing a book on ultrafilters. The project never got past Chapter 1, and even Chapter 1 existed only in handwritten form. This chapter contains basic, general information about ultrafilters. In the hope that it might be useful for some people, I had it scanned (which had to be done manually, one page at a time, so I emphatically thank Robin Welshans who did the scanning), and I'm making it available here. It consists of eight sections, as separate pdf files.
Independent sets and functions
A model-theoretic view of some special ultrafilters (Logic Colloquium '77 (ed. A. Macintyre, L. Pacholski, and J. Paris) North-Holland, Studies in Logic and the Foundations of Mathematics 96 (1978) 79-90)
Combinatorial definitions of special sorts of ultrafilters can often be formulated rather neatly in terms of the associated ultrapowers, and some of the combinatorial lemmas used in the study of such ultrafilters have simpler and more natural formulations as assertions about ultrapowers. The purpose of this paper is to survey a number of such forrmulations and to indicate how they can be used to prove combinatorial results.
Orderings of Ultrafilters (Ph.D. thesis, Harvard University (1970))