Lectures on Set Theory, Beijing, June 2025

This will be a lecture series at Peking University in Beijing in June 2025.

Announcement at Peking University

Course abstract. This will be a series of advanced lectures on set theory, treating diverse topics and particularly those illustrating how set theoretic ideas and conceptions shed light on core foundational matters in mathematics. We will study the pervasive independence phenomenon over the Zermelo-Fraenkel axioms of set theory, perhaps the central discovery of 20th century set theory, as revealed by the method of forcing, which we shall study in technical detail with numerous examples and applications, including iterated forcing. We shall look into all matters of the continuum hypothesis and the axiom of choice. We shall introduce the basic large cardinal axioms, those strong axioms of infinity, and investigate the interaction of forcing and large cardinals. We shall explore issues of definability and truth, revealing a surprisingly malleable nature by the method of forcing. Looking upward from a model of set theory to all its forcing extensions, we shall explore the generic multiverse of set theory, by which one views all the models of set theory as so many possible mathematical worlds, while seeking to establish exactly the modal validities of this conception. Looking downward in contrast transforms this subject to set-theoretic geology, by which one understands how a given set-theoretic universe might have arisen from its deeper grounds by forcing. We shall prove the ground-model definability theorem and the other fundamental results of set-theoretic geology. The lectures will assume for those participating a certain degree of familiarity with set-theoretic notions, including the basics of ZFC and forcing.

There will be ten lectures, each a generous 3 hours.

Lecture 1. Set Theory

This first lecture begins with fundamental notions, including the dramatic historical developments of set theory with Cantor, Frege, Russell, and Zermelo, and then the rise of the cumulative hierarchy and the iterative conception. The move to a first-order foundational theory. The Skolem paradox. The omission of urelements and the move to a pure set theory. We will establish the reflection phenomenon and the phenomenon of correctness cardinals, before providing some simple relative consistency results. We will compare the first-order approach to the various class theories and also lay out the spectrum of weak theories, including locally verifiable set theory, before discussing countabilism as an approach to set theory.

Lecture 2. Categoricity and the small large cardinals

We will discuss the central role and importance of categoricity in mathematics, highlighting this with results of Dedekind and Huntington, and with several examples of internal categorcity. Afterwards, we shall begin to introduce various small large cardinal notions—the inaccessible cardinals, the hyperinaccessibility hierarchy, Mahlo cardinals, worldly cardinals, other-worldly cardinals. We shall explain the connection with categoricity via Zermelo’s categoricity result. Going deeper, we discuss the possibility of categorical large cardinals and the enticing possibility of a fully categorical set theory.

Lecture 3. Forcing

We shall give an introduction to forcing, pursuing and comparing two approaches, via partial orders versus Boolean algebras. Forcing arises naturally from the iterative conception of the cumulative hierarchy, when undertaken in multi-valued logic. We shall see the principal introductory forcing examples, including the forcing to add a Cohen real, cardinal collapse forcing, forcing the failure of CH, forcing to add dominating reals, almost disjoint coding, iterated forcing, the forcing of Martin’s axiom, and the case of Suslin trees.

Lecture 4. Continuum Hypothesis

We tell the story of the continuum hypothesis, from Cantor’s initial conception and strategy, to Gödel’s proof of CH in the constructible universe, and ultimately Cohen’s forcing of ¬CH, establishing independence over ZFC. The CH is a forcing switch. We discuss the generalized continuum hypothesis GCH, and prove Easton’s theorem on the continuum function. Finally, we discuss various philosophical approaches to settling the CH problem, including Freiling’s axiom and the equivalence with ¬CH, and the role of the continuum hypothesis in providing a categorical theory of the hyperreals. Two equivalent formulations of CH in ZFC are not equivalent without AC.

Lecture 5. Axiom of Choice

We tell the story of the axiom of choice, beginning with a spectrum of equivalent formulations, including the linearity of cardinality. We discuss the abstract cardinal-assignment problem versus the cardinal-selection problem. We establish the truth of the axiom of choice in the constructible universe, as well as global choice, but ultimately the independence of the axiom of choice over ZF via forcing and the symmetric model construction method. Finally, we discuss the perfect predictor theorem and the box puzzle conundrum.

Lecture 6. Definability

We shall define and discuss the formal notion of definability in mathematics and set theory. Can every set be definable? We exhibit the phenomenon of pointwise definable models and their relevance for the Math Tea argument. We define the inner model HOD and explore its interaction with forcing, forcing V=HOD and also forcing V≠HOD. We reveal the coquettish nature of HOD, establishing the nonabsoluteness of HOD, showing furthermore that every model of set theory is the HOD of another model. We show how forcing generic filters can be definable in their forcing extensions. Finally, we shall exhibit a spectrum of paradoxical examples revealing various subtleties in the notion of definability.

Lecture 7. Truth

What is truth? We establish Tarski’s theorem on the nondefinability of truth, and establish the second incompleteness theorem via the Grelling-Nelson paradox. We analyze the connection between truth predicates and correctness cardinals. What is the consistency strength of having a truth predicate? Can a model of set theory contain its own theory as an element? Must it? We define the truth telling game. We shall force a definable truth predicate for HOD. We shall establish the nonabsoluteness of satisfaction.

Lecture 8. Forcing and large cardinals

Can large cardinals settle CH? Gödel had hoped so, but this is refuted by the Levy-Solovay theorem. We will prove forcing preservation theorems for large cardinals, and nonabsoluteness theorems. On the difference between lifting and extending measures. Laver indestructibility and the lottery preparation, via master condition arguments.

Lecture 9. Set-theoretic geology

Looking down, we shall give an introduction to set-theoretic geology. We will prove the ground model definability theorem, using the cover and approximation properties. We shall define the Mantle and prove that every model of set theory is the Mantle of another model. We will discuss Bukovski’s theorem characterizing forcing extensions and prove Usuba’s theorems on the downward directedness of grounds.

Lecture 10. Set-theoretic potentialism

Looking up, we view forcing as a modality, viewing every model of set theory in the context of its generic multiverse. We shall investigate the modal logic of forcing with independent buttons and switches. We shall explore the other natural interpretations of set-theoretic potentialism and investigate their modal validities.

Comments or suggestions welcome.

How we might have viewed the continuum hypothesis as a fundamental axiom necessary for mathematics, Oxford Phil Maths seminar, May 2025

This was a talk for the Philosophy of Mathematics Seminar at the University of Oxford, 19 May 2025.

Abstract. I shall describe a simple historical thought experiment showing how our attitude toward the continuum hypothesis could easily have been very different than it is. If our mathematical history had been just a little different, I claim, if certain mathematical discoveries had been made in a slightly different order, then we would naturally view the continuum hypothesis as a fundamental axiom of set theory, necessary for mathematics and indeed indispensable for calculus.

I shall be speaking on my paper: How the continuum hypothesis could have been a fundamental axiom

How the continuum hypothesis could have been a fundamental axiom

Joel David Hamkins, “How the continuum hypothesis could have been a fundamental axiom,” Journal for the Philosophy of Mathematics (2024), DOI:10.36253/jpm-2936, arxiv:2407.02463.

Abstract. I describe a simple historical thought experiment showing how we might have come to view the continuum hypothesis as a fundamental axiom, one necessary for mathematics, indispensable even for calculus.

See also this talk I gave on the topic at the University of Oslo:

Mathematics, Philosophy of Set Theory and Infinity, Back to the Stone Age interview, May 2024

I was interviewed by Francesco Cavina for the Back to the Stone Age series on May 17, 2024, with a sweeping discussion of the philosophy of set theory, infinity, the continuum hypothesis, beauty in mathematics, and much more.

The continuum hypothesis could have been a fundamental axiom, CFORS Grad Conference, Oslo, June 2024

I shall be giving a keynote lecture for the CFORS Grad Conference at the University of Oslo, 19-20 June 2024.

Abstract. I shall describe a simple historical thought experiment showing how our attitude toward the continuum hypothesis could easily have been very different than it is. If our mathematical history had been just a little different, I claim, if certain mathematical discoveries had been made in a slightly different order, then we would naturally view the continuum hypothesis as a fundamental axiom of set theory, one furthermore necessary for mathematics and indeed, indispensable for calculus.

The paper is now available at How the continuum hypothesis could have been a fundamental axiom.

How the continuum hypothesis could have been a fundamental axiom, UC Irvine Logic & Philosoph of Science Colloquium, March 2024

This will be a talk for the Logic and Philosophy of Science Colloquium at the University of California at Irvine, 15 March 2024.

Abstract. With a simple historical thought experiment, I should like to describe how we might easily have come to view the continuum hypothesis as a fundamental axiom, one necessary for mathematics, indispensable even for calculus.

The paper is now available at How the continuum hypothesis could have been a fundamental axiom.

Paradox, Infinity, & The Foundations of Mathematics, interview with Robinson Erhardt, January 2023

This was an interview with Robinson Erhardt on Robinson’s Podcast, part of his series of interviews with various philosophers, including many philosophers of mathematics and more.

We had a wonderfully wide-ranging discussion about the philosophy of mathematics, the philosophy of set theory, pluralism, and many other topics. The main focus was the topic of infinity, following selections from my new book, The Book of Infinity, currently being serialized on my substack, joeldavidhamkins.substack.com, with discussion of Zeno’s paradox, the Chocolatier’s Game, Hilbert’s Grand Hotel and more.

Robinson compiled the following outline with links to special parts of the interview:

  • 00:00 Introduction
  • 2:52 Is Joel a Mathematician or a Philosopher?
  • 6:13 The Philosophical Influence of Hugh Woodin
  • 10:29 The Intersection of Set Theory and Philosophy of Math
  • 16:29 Serializing the Book of the Infinite
  • 20:05 Zeno of Elea, Continuity, and Geometric Series
  • 39:39 Infinite Games and the Chocolatier
  • 53:35 Hilbert’s Hotel
  • 1:10:26 Cantor’s Theorem
  • 1:31:37 The Continuum Hypothesis
  • 1:43:02 The Set-Theoretic Multiverse
  • 2:00:25 Berry’s Paradox and Large Numbers
  • 2:16:15 Skolem’s Paradox and Indescribable Numbers
  • 2:28:41 Pascal’s Wager and Reasoning Around Remote Events
  • 2:49:35 MathOverflow
  • 3:04:40 Joel’s Impeccable Fashion Sense

Read the book here: joeldavidhamkins.substack.com.

Infinity, University of Notre Dame, Spring 2023

Infinity

Philosophy 20607 01 (32582)

University of Notre Dame                                                                              Spring 2023

Instructor: Joel David Hamkins, O’Hara Professor of Philosophy and Mathematics
3:30-4:45 Tuesdays + Thursdays, DeBartolo Hall 208

Course Description. This course will be a mathematical and philosophical exploration of infinity, covering a wide selection of topics illustrating this rich, fascinating concept—the mathematics and philosophy of the infinite.

Along the way, we shall find paradox and fun—and all my favorite elementary logic conundrums and puzzles. It will be part of my intention to reveal what I can of the quirky side of mathematics and logic in its connection with infinity, but with a keen eye open for when issues happen to engage with philosophically deeper foundational matters.

The lectures will be based on the chapters of my forthcoming book, The Book of Infinity, currently in preparation, and currently being serialized and made available on the Substack website as I explain below.

Topics. Among the topics we shall aim to discuss will be:

  • The Book of Numbers
  • Zeno’s paradox
  • The infinite coastline paradox
  • Supertasks
  • Largest number contest
  • The googol plex chitty bang stack hierarchy
  • Galileo’s Salviati on infinity
  • Hilbert’s Grand Hotel
  • The uncountable
  • How to count (to infinity and beyond!)
  • Slaying the Hydra
  • Transfinite recursion
  • The continuum hypothesis
  • The axiom of choice
  • Orders of infinity
  • The lattice of subsets of ℕ
  • Potential versus actual infinity
  • Confounding puzzles of infinity
  • Infinite liars
  • Infinite utilitarianism
  • Infinite computation
  • Infinite games
  • Indescribable numbers
  • Extremely remote events of enormous consequence
  • The sand reckoner
  • Paradox in high dimension
  • The outer limits of reason
  • Puzzles of epistemic logic and the problem of common knowledge

Mathematical background. The course will at times involve topics and concepts of a fundamentally mathematical nature, but no particular mathematical background or training will be assumed. Nevertheless, it is expected that students be open to mathematical thinking and ideas, and furthermore it is a core aim of the course to help develop the student’s mastery over various mathematical concepts connected with infinity.  

Readings. The lectures will be based on readings from the topic list above that will be made available on my Substack web page, Infinitely More. Readings for the topic list above will be gradually released there during the semester. Each reading will consist of a chapter essay my book-in-progress, The Book of Infinity, which is being serialized on the Substack site specifically for this course. In some weeks, there will be supplemental readings from other sources.

Student access. I will issue subscription invitations to the Substack site for all registered ND students using their ND email, with free access to the site during the semester, so that students can freely access the readings.  Students are free to manage their subscriptions however they see fit. Please inform me of any access issues. There are some excellent free Substack apps available for Apple iOS and Android for reading Substack content on a phone or other device.

Discussion forum. Students are welcome to participate in the discussion forums provided with the readings to discuss the topics, the questions, to post answer ideas, or engage in the discussion there. I shall try to participate myself by posting comments or hints.

Homework essays. Students are expected to engage fully with every topic covered in the class. Every chapter concludes with several Questions for Further Thought, with which the students should engage. It will be expected that students complete approximately half of the Questions for Further thought. Each question that is answered should be answered essay-style with a mini-essay of about half a page or more.

Extended essays. A student may choose at any time to answer one of the Questions for Further Thought more fully with a more extended essay of two or three pages, and in this case, other questions on that particular topic need not be engaged. Every student should plan to exercise this option at least twice during the semester.

Final exam.  There will be a final exam consisting of questions similar to those in the Questions for Further Thought, covering every topic that was covered in the course. The final grade will be based on the final exam and on the submitted homework solutions.

Open Invitation. Students outside of Notre Dame are welcome to follow along with the Infinity course, readings, and online discussion. Simply subscribe at Infinitely More, keep up with the readings and participate in the discussions we shall be having in the forums there.

The rearrangement number: how many rearrangements of a series suffice to validate absolute convergence? Warwick Mathematics Colloquium, October 2018

This will be a talk for the Mathematics Colloquium at the University of Warwick, to be held October 19, 2018, 4:00 pm in Lecture Room B3.02 at the Mathematics Institute. I am given to understand that the talk will be followed by a wine and cheese reception.Abstract. The Riemann rearrangement theorem asserts that a series nan is absolutely convergent if and only if every rearrangement nap(n) of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. How many rearrangements p suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and an account of Freiling’s axiom of symmetry.

This talk is based in part on joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

Models of set theory with the same reals and the same cardinals, but which disagree on the continuum hypothesis

Terry_Marks,_Nightmare_in_a_MirrorI’d like to describe a certain interesting and surprising situation that can happen with models of set theory.

Theorem. If ZFC set theory is consistent, then there are two models of ZFC set theory M and N for which

  • M and N have the same real numbers RM=RN.
  • M and N have the ordinals and the same cardinals ααM=αN
  • But M thinks that the continuum hypothesis CH is true, while N thinks that CH is false.

This is a little strange, since the two models have the set R in common and they agree on the cardinal numbers, but M thinks that R has size 1 and N will think that R has size 2.  In particular, M can well-order the reals in order type ω1 and N can do so in order-type ω2, even though the two models have the same reals and they agree that these order types have different cardinalities.

Another abstract way to describe what is going on is that even if two models of set theory, even transitive models, agree on which ordinals are cardinals, they needn’t agree on which sets are equinumerous, for sets they have in common, even for the reals.

Let me emphasize that it is the requirement that the models have the same cardinals that makes the problem both subtle and surprising. If you drop that requirement, then the problem is an elementary exercise in forcing: start with any model V, and first force CH to fail in V[H] by adding a lot of Cohen reals, then force to V[G] by collapsing the continuum to 1. This second step adds no new reals and forces CH, and so V[G] and V[H] will have the same reals, while V[H] thinks CH is true and V[G] thinks CH is false. The problem becomes nontrivial and interesting mainly when you insist that cardinals are not collapsed.

In fact, the situation described in the theorem can be forced over any given model of ZFC.

Theorem. Every model of set theory VZFC has two set-forcing extensions V[G] and V[H] for which

  • V[G] and V[H] have the same real numbers RV[G]=RV[H].
  • V[G] and V[H] have the same cardinals ααV[G]=αV[H]
  • But V[G] thinks that the continuum hypothesis CH is true, while V[H] thinks that CH is false.

Proof. Start in any model VZFC, and by forcing if necessary, let’s assume CH holds in V. Let HAdd(ω,ω2) be V-generic for the forcing to add ω2 many Cohen reals. So V[H] satisfies ¬CH and has the same ordinals and cardinals as V.

Next, force over V[H] using the forcing from V to collapse ω2 to ω1, forming the extension V[H][g], where g is the generic bijection between those ordinals. Since we used the forcing in V, which is countably closed there, it makes sense to consider V[g].  In this extension, the forcing Add(ω,ω1V) and Add(ω,ω2V) are isomorphic. Since H is V[g]-generic for the latter, let G=g[H] be the image of this filter in Add(ω,ω1), which is therefore V[g]-generic for the former. So V[g][G]=V[g][H]. Since the forcing Add(ω,ω1) is c.c.c., it follows that V[G] also has the same cardinals as V and hence also the same as in V[H].

If we now view these extensions as V[G][g]=V[H][g] and note that the coutable closure of g in V implies that g adds no new reals over either V[G] or V[H], it follows that RV[G]=RV[H]. So the two models have the same reals and the same cardinals. But V[G] has CH and V[H] has ¬CH, in light of the forcing, and so the proof is complete. QED

Let me prove the following surprising generalization.

Theorem. If V is any model of ZFC and V[G] is the forcing extension obtained by adding κ many Cohen reals, for some uncountable κ, then for any other uncountable cardinal λ, there is another forcing extension V[H] where H is V-generic for the forcing to add λ many Cohen reals, yet RV[G]=RV[H].

Proof. Start in V[G], and let g be V[G]-generic to collapse λ to κ, using the collapse forcing of the ground model V. This forcing is countably closed in V and therefore does not add reals over V[G]. In V[g], the two forcing notions Add(ω,κ) and Add(ω,λ) are isomorphic. Thus, since G is V[g]-generic for the former poset, it follows that the image H=g[G] is V[g]-generic for the latter poset. So V[H] is generic over V for adding λ many Cohen reals. By construction, we have V[G][g]=V[H][g], and since g doesn’t add reals, it follows that RV[G]=RV[H], as desired. QED

I have a vague recollection of having first heard of this problem many years ago, perhaps as a graduate student, although I don’t quite recall where it was or indeed what the construction was — the argument above is my reconstruction (which I have updated and extended from my initial post). If someone could provide a reference in the comments for due credit, I’d be appreciative.  The problem appeared a few years ago on MathOverflow.

The rearrangement number: how many rearrangements of a series suffice to verify absolute convergence? Mathematics Colloquium at Penn, September 2016

This will be a talk for the Mathematics Colloquium at the University of Pennsylvania, Wednesday, September 14, 2016, 3:30 pm, tea at 3 pm, in the mathematics department.

UPenn Campus
Abstract. The well-known Riemann rearrangement theorem asserts that a series nan is absolutely convergent if and only if every rearrangement nap(n) of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. But how many rearrangements p suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and, time permitting, an account of Freiling’s axiom of symmetry.

This talk is based in part on current joint work with Jörg Brendle, Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

Related MathOverflow post: How many rearrangements must fail to alter the value of a sum before you conclude that none do?

Freiling’s axiom of symmetry, or throwing darts at the real line, Graduate Student Colloquium, April 2016

This will be a talk I’ll give at the CUNY Graduate Center Graduate Student Colloquium on Monday, April 11 (new date!), 2016, 4-4:45 pm.  The talk will be aimed at a general audience of mathematics graduate students.

By PeterPan23 [Public domain], via Wikimedia Commons

Abstract. I shall give an elementary presentation of Freiling’s axiom of symmetry, which is the principle asserting that if xAx is a function mapping every real x[0,1] in the unit interval to a countable set of such reals Ax[0,1], then there are two reals x and y for which xAy and yAx.  To argue for the truth of this principle, Freiling imagined throwing two darts at the real number line, landing at x and y respectively: almost surely, the location y of the second dart is not in the set Ax arising from that of the first dart, since that set is countable; and by symmetry, it shouldn’t matter which dart we imagine as being first. So it may seem that almost every pair must fulfill the principle. Nevertheless, the principle is independent of the axioms of ZFC and in fact it is provably equivalent to the failure of the continuum hypothesis.  I’ll introduce the continuum hypothesis in a general way and discuss these foundational matters, before providing a proof of the equivalence of ¬CH with the axiom of symmetry. The axiom of symmetry admits natural higher dimensional analogues, such as the case of maps (x,y)Ax,y, where one seeks a triple (x,y,z) for which no member is in the set arising from the other two, and these principles also have an equivalent formulation in terms of the size of the continuum.

Freiling axiom of symmetry on MathOverflow | On Wikipedia | Graduate Student Colloquium


The rearrangement number: how many rearrangements of a series suffice to verify absolute convergence? Vassar Math Colloquium, November 2015

This will be a talk for the Mathematics Colloquium at Vassar College, November 10, 2015, tea at 4:00 pm, talk at 4:15 pm, Rockefeller Hall 310

Abstract. The Riemann rearrangement theorem asserts that a series nan is absolutely convergent if and only if every rearrangement nap(n) of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. How many rearrangements p suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum introduced just recently, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and an account of Freiling’s axiom of symmetry.

This talk is based in part on current joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

My Lecture Notes are available. 

The axiom of determinacy for small sets

Lewis ChessmenI should like to argue that the axiom of determinacy is true for all games having a small payoff set. In particular, the size of the smallest non-determined set, in the sense of the axiom of determinacy, is the continuum; every set of size less than the continuum is determined, even when the continuum is enormous.

We consider two-player games of perfect information. Two players, taking turns, play moves from a fixed space X of possible moves, and thereby together build a particular play or instance of the game a=a0,a1,Xω. The winner of this instance of the game is determined according to whether the play a is a member of some fixed payoff set UXω specifying the winning condition for this game. Namely, the first player wins in the case aU.

A strategy in such a game is a function σ:X<ωX that instructs a particular player how to move next, given the sequence of partial play, and such a strategy is a winning strategy for that player, if all plays made against it are winning for that player. (The first player applies the strategy σ only on even-length input, and the second player only to the odd-length inputs.) The game is determined, if one of the players has a winning strategy.

It is not difficult to see that if U is countable, then the game is determined. To see this, note first that if the space of moves X has at most one element, then the game is trivial and hence determined; and so we may assume that X has at least two elements. If the payoff set U is countable, then we may enumerate it as U={s0,s1,}. Let the opposing player now adopt the strategy of ensuring on the nth move that the resulting play is different from sn. In this way, the opposing player will ensure that the play is not in U, and therefore win. So every game with a countable payoff set is determined.

Meanwhile, using the axiom of choice, we may construct a non-determined set even for the case X={0,1}, as follows. Since a strategy is function from finite binary sequences to {0,1}, there are only continuum many strategies. By the axiom of choice, we may well-order the strategies in order type continuum. Let us define a payoff set U by a transfinite recursive procedure: at each stage, we will have made fewer than continuum many promises about membership and non-membership in U; we consider the next strategy on the list; since there are continuum many plays that accord with that strategy for each particular player, we may make two additional promises about U by placing one of these plays into U and one out of U in such a way that this strategy is defeated as a winning strategy for either player. The result of the recursion is a non-determined set of size continuum.

So what is the size of the smallest non-determined set? For a lower bound, we argued above that every countable payoff set is determined, and so the smallest non-determined set must be uncountable, of size at least 1. For an upper bound, we constructed a non-determined set of size continuum. Thus, if the continuum hypothesis holds, then the smallest non-determined set has size exactly continuum, which is 1 in this case. But what if the continuum hypothesis fails? I claim, nevertheless, that the smallest non-determined set still has size continuum.

Theorem. Every game whose winning condition is a set of size less than the continuum is determined.

Proof. Suppose that UXω is the payoff set of the game under consideration, so that U has size less than continuum. If X has at most one element, then the game is trivial and hence determined. So we may assume that X has at least two elements. Let us partition the elements of Xω according to whether they have exactly the same plays for the second player. So there are at least continuum many classes in this partition. If U has size less than continuum, therefore, it must be disjoint from at least one (and in fact from most) of the classes of this partition (since otherwise we would have an injection from the continuum into U). So there is a fixed sequence of moves for the second player, such that any instance of the game in which the second player makes those moves, the result is not in U and hence is a win for the second player. This is a winning strategy for the second player, and so the game is determined. QED

This proof generalizes the conclusion of the diagonalization argument against a countable payoff set, by showing that for any winning condition set of size less than continuum, there is a fixed play for the opponent (not depending on the play of the first player) that defeats it.

The proof of the theorem uses the axiom of choice in the step where we deduce that U must be disjoint from a piece of the partition, since there are continuum many such pieces and U had size less than the continuum. Without the axiom of choice, this conclusion does not follow. Nevertheless, what the proof does show without AC is that every set that does not surject onto R is determined, since if U contained an element from every piece of the partition it would surject onto R. Without AC, the assumption that U does not surject onto R is stronger than the assumption merely that it has size less the continuum, although these properties are equivalent in ZFC.  Meanwhile, these issues are relevant in light of the model suggested by Asaf Karagila in the comments below, which shows that it is consistent with ZF without the axiom of choice that there are small non-determined sets. Namely, the result of Monro shows that it is consistent with ZF that R=AB, where both A and B have cardinality less than the continuum. In particular, in this model the continuum injects into neither A nor B, and consequently neither player can have a strategy to force the play into their side of this partition. Thus, both A and B are non-determined, even though they have size less than the continuum.

The continuum hypothesis and other set-theoretic ideas for non-set-theorists, CUNY Einstein Chair Seminar, April, 2015

At Dennis Sullivan’s request, I shall speak on set-theoretic topics, particularly the continuum hypothesis, for the Einstein Chair Mathematics Seminar at the CUNY Graduate Center, April 27, 2015, in two parts:

  • An introductory background talk at 11 am, Room GC 6417
  • The main talk at 2 – 4 pm, Room GC 6417

I look forward to what I hope will be an interesting and fruitful interaction. There will be coffee/tea and lunch between the two parts.

Abstract. I shall present several set-theoretic ideas for a non-set-theoretic mathematical audience, focusing particularly on the continuum hypothesis and related issues.

At the introductory background talk, in the morning (11 am), I shall discuss and prove the Cantor-Bendixson theorem, which asserts that every closed set of reals is the union of a countable set and a perfect set (a closed set with no isolated points), and explain how it led to Cantor’s development of the ordinal numbers and how it establishes that the continuum hypothesis holds for closed sets of reals. We’ll see that there are closed sets of arbitrarily large countable Cantor-Bendixson rank. We’ll talk about the ordinals, about ω1, the long line, and, time permitting, we’ll discuss Suslin’s hypothesis.

At the main talk, in the afternoon (2 pm), I’ll begin with a discussion of the continuum hypothesis, including an explanation of the history and logical status of this axiom with respect to the other axioms of set theory, and establish the connection between the continuum hypothesis and Freiling’s axiom of symmetry. I’ll explain the axiom of determinacy and some of its applications and its rich logical situation, connected with large cardinals. I’ll briefly mention the themes and goals of the subjects of cardinal characteristics of the continuum and of Borel equivalence relation theory.  If time permits, I’d like to explain some fun geometric decompositions of space that proceed in a transfinite recursion using the axiom of choice, mentioning the open questions concerning whether there can be such decompositions that are Borel.

Dennis has requested that at some point the discussion turn to the role of set theory in the foundation for mathematics, compared for example to that of category theory, and I would look forward to that. I would be prepared also to discuss the Feferman theory in comparison to Grothendieck’s axiom of universes, and other issues relating set theory to category theory.