Lectures on Set Theory, Beijing, June 2025

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

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.

Determinateness of truth does not come for free from determinateness of objects, Singapore, November 2024

 This will be a talk for the (In)determinacy in Mathematics conference at the National University of Singapore, 20-22 November 2024

Abstract. I shall discuss the question whether we may regard determinateness of truth as flowing from determinateness of objects in a mathematical structure. I shall showcase several results in the model theory of set theory and arithmetic that seem to speak against this. For example, there are two models of ZFC set theory that share exactly the same arithmetic structure of the natural numbers ⟨ℕ,+,·,0,1,<⟩, what they each view as the standard model of arithmetic, but they disagree about which arithmetic sentences are true in that structure. There are models of ZFC set theory with the same arithmetic structure and the same arithmetic truth, but which disagree on truth-about-truth, or that agree on that, but disagree on higher levels of iterated truth, at any desired level. There are models of set theory with the same natural numbers and real numbers, but which disagree on projective truth. There are models of ZFC that have a rank initial segment Vθ in common, but they disagree about whether it is a model of ZFC. All these examples show senses in which determinateness about objects does not seem to cause determinateness about truth. (This is joint work with Ruizhi Yang.)

Faculty respondent to paper of Ethan Jerzak on Paradoxical Desires, Oxford Graduate Philosophy Conference, November 2018

The Oxford Graduate Philosophy Conference will be held at the Faculty of Philosophy November 10-11, 2018, with graduate students from all over the world speaking on their papers, with responses and commentary by Oxford faculty.

I shall be the faculty respondent to the delightful paper, “Paradoxical Desires,” by Ethan Jerzak of the University of California at Berkeley, offered under the following abstract.

Ethan Jerzak (UC Berkeley): Paradoxical Desires
I present a paradoxical combination of desires. I show why it’s paradoxical, and consider ways of responding to it. The paradox saddles us with an unappealing disjunction: either we reject the possibility of the case by placing surprising restrictions on what we can desire, or we revise some bit of classical logic. I argue that denying the possibility of the case is unmotivated on any reasonable way of thinking about propositional attitudes. So the best response is a non-classical one, according to which certain desires are neither determinately satisfied nor determinately not satisfied. Thus, theorizing about paradoxical propositional attitudes helps constrain the space of possibilities for adequate solutions to semantic paradoxes more generally.

The conference starts with coffee at 9:00 am.  This session runs 11 am to 1:30 pm on Saturday 10 November in the Lecture Room.

Conference Program | Conference web page

Here are the notes I used for my response.

 

The hierarchy of logical expressivity

I’d like to give a simple account of what I call the hierarchy of logical expressivity for fragments of classical propositional logic. The idea is to investigate and classify the expressive power of fragments of the traditional language of propositional logic, with the five familiar logical connectives listed below, by considering subsets of these connectives and organizing the corresponding sublanguages of propositional logic into a hierarchy of logical expressivity.

  • conjunction (“and”), denoted
  • disjunction (“or”), denoted  
  • negation (“not”), denoted ¬
  • conditional (“if…, then”), denoted  
  • biconditional (“if and only if”), denoted  

With these five connectives, there are, of course, precisely thirty-two (32=25) subsets, each giving rise to a corresponding sublanguage, the language of propositional assertions using only those connectives. Which sets of connectives are equally as expressive or more expressive than which others? Which sets of connectives are incomparable in their expressivity? How many classes of expressivity are there?

Before continuing, let me mention that Ms. Zoë Auerbach (CUNY Graduate Center), one of the students in my logic-for-philosophers course this past semester, Survey of Logic for Philosophers, at the CUNY Graduate Center in the philosophy PhD program, had chosen to write her term paper on this topic.  She has kindly agreed to make her paper, “The hierarchy of expressive power of the standard logical connectives,” available here, and I shall post it soon.

To focus the discussion, let us define what I call the (pre)order of logical expressivity on sets of connectives. Namely, for any two sets of connectives, I define that AB with respect to logical expressivity, just in case every logical expression in any number of propositional atoms using only connectives in A is logically equivalent to an expression using only connectives in B. Thus, AB means that the connectives in B are collectively at least as expressive as the connectives in A, in the sense that with the connectives in B you can express any logical assertion that you were able to express with the connectives in A. The corresponding equivalence relation AB holds when AB and BA, and in this case we shall say that the sets are expressively equivalent, for this means that the two sets of connectives can express the same logical assertions.

Expressivity hierarchy

The full set of connectives {,,¬,,} is well-known to be complete for propositional logic in the sense that every conceivable truth function, with any number of propositional atoms, is logically equivalent to an expression using only the classical connectives. Indeed, already the sub-collection {,,¬} is fully complete, and hence expressively equivalent to the full collection, because every truth function can be expressed in disjunctive normal form, as a disjunction of finitely many conjunction clauses, each consisting of a conjunction of propositional atoms or their negations (and hence altogether using only disjunction, conjunction and negation). One can see this easily, for example, by noting that for any particular row of a truth table, there is a conjunction expression that is true on that row and only on that row. For example, the expression p¬rs¬t is true on the row where p is true, r is false, s is true and t is false, and one can make similar expressions for any row in any truth table. Simply by taking the disjunction of such expressions for suitable rows where a T is desired, one can produce an expression in disjunctive normal form that is true in any desired pattern (use p¬p for the never-true truth function). Therefore, every truth function has a disjunctive normal form, and so {,,¬} is complete.

Pressing this further, one can eliminate either or by systematically applying the de Morgan laws
pq¬(¬p¬q)pq¬(¬p¬q),
which allow one to reduce disjunction to conjunction and negation or reduce conjunction to disjunction and negation. It follows that {,¬} and {,¬} are each complete, as is any superset of these sets, since a set is always at least as expressive as any of it subsets. Similarly, because we can express disjunction with negation and the conditional via pq¬pq, it follows that the set {,¬} can express , and hence also is complete. From these simple observations, we may conclude that each of the following fourteen sets of connectives is complete. In particular, they are all expressively equivalent to each other.
{,,¬,,}
{,,¬,}{,,¬,}{,,¬,}{,,¬,}
{,¬,}{,¬,}{,¬,}
{,,¬}{,,¬}{,,¬}
{,¬}{,¬}{,¬}

Notice that each of those complete sets includes the negation connective ¬. If we drop it, then the set {,,,} is not complete, since each of these four connectives is truth-preserving, and so any logical expression made from them will have a T in the top row of the truth table, where all atoms are true. In particular, these four connectives collectively cannot express negation ¬, and so they are not complete.

Clearly, we can express the biconditional as two conditionals, via pq(pq)(qp), and so the {,,,} is expressively equivalent to {,,}. And since disjunction can be expressed from the conditional with pq((pq)q), it follows that the set is expressively equivalent to {,}. In light of pqp(pq), it follows that {,} can express conjunction and hence is also expressively equivalent to {,,,}. Since
pq(pq)(pq), it follows that {,} can express and hence also , because pqq(qp). Similarly, using pq(pq)(pq), we can see that {,} can express and hence also is expressively equivalent to {,,}, which we have argued is equivalent to {,,,}.  For these reasons, the following sets of connectives are expressively equivalent to each other.
{,,,}
{,,}{,,}{,,}{,,}
{,}{,}{,}{,}
And as I had mentioned, these sublanguages are strictly less expressive than the full language, because these four connectives are all truth-preserving and therefore unable to express negation.

The set {,}, I claim, is unable to express any of the other fundamental connectives, because and are each false-preserving, and so any logical expression built from and will have F on the bottom row of the truth table, where all atoms are false. Meanwhile, , and ¬ are not false-preserving, since they each have T on the bottom row of their defining tables. Thus, {,} lies strictly below the languages mentioned in the previous paragraph in terms of logical expressivity.

Meanwhile, using only we cannot express , since any expression in p and q using only will have the property that any false atom will make the whole expression false (this uses the associativity of ), and pq does not have this feature. Similarly, cannot express , since any expression using only is true if any one of its atoms is true, but pq is not like this. For these reasons, {} and {} are both strictly weaker than {,} in logical expressivity.

Next, I claim that {,} cannot express , and the reason is that the logical operations of and each have the property that any expression built from that has at least as many T’s as F’s in the truth table. This property is true of any propositional atom, and if φ has the property, so does φψ and ψφ, since these expressions will be true at least as often as φ is. Since {,} cannot express , this language is strictly weaker than {,,,} in logical expressivity. Actually, since as we noted above pq((pq)q), it follows that {,} is expressively equivalent to {}.

Meanwhile, since is false-preserving, it cannot express , and so {} is strictly less expressive than {,}, which is expressively equivalent to {}.

Consider next the language corresponding to {,¬}. I claim that this set is not complete. This argument is perhaps a little more complicated than the other arguments we have given so far. What I claim is that both the biconditional and negation are parity-preserving, in the sense that any logical expression using only ¬ and will have an even number of T’s in its truth table. This is certainly true of any propositional atom, and if true for φ, then it is true for ¬φ, since there are an even number of rows altogether; finally, if both φ and ψ have even parity, then I claim that φψ will also have even parity. To see this, note first that this biconditional is true just in case φ and ψ agree, either having the pattern T/T or F/F. If there are an even number of times where both are true jointly T/T, then the remaining occurrences of T/F and F/T will also be even, by considering the T’s for φ and ψ separately, and consequently, the number of occurrences of F/F will be even, making φψ have even parity. If the pattern T/T is odd, then also T/F and F/T will be odd, and so F/F will have to be odd to make up an even number of rows altogether, and so again φψ will have even parity. Since conjunction, disjunction and the conditional do not have even parity, it follows that {,¬} cannot express any of the other fundamental connectives.

Meanwhile, {} is strictly less expressive than {,¬}, since the biconditional is truth-preserving but negation is not. And clearly {¬} can express only unary truth functions, since any expression using only negation has only one propositional atom, as in ¬¬¬p. So both {} and {¬} are strictly less expressive than {,¬}.

Lastly, I claim that is not expressible from . If it were, then since is also expressible from , we would have that {,} is expressible from , contradicting our earlier observation that {} is strictly less expressive than {,}, as this latter set can express , but cannot, since every expression in has at least as many T’s as F’s in its truth table.

These observations altogether establish the hierarchy of logical expressivity shown in the diagram displayed above.

It is natural, of course, to want to extend the hierarchy of logical expressivity beyond the five classical connectives. If one considers all sixteen binary logical operations, then Greg Restall has kindly produced the following image, which shows how the hierarchy we discussed above fits into the resulting hierarchy of expressivity. This diagram shows only the equivalence classes, rather than all 65536=216 sets of connectives.

Full binary expressivity lattice

If one wants to go beyond merely the binary connectives, then one lands at Post’s lattice, pictured below (image due to Emil Jeřábek), which is the countably infinite (complete) lattice of logical expressivity for all sets of truth functions, using any given set of Boolean connectives. Every such set is finitely generated.Post-lattice.svg

Same structure, different truths, Stanford University CSLI, May 2016

This will be a talk for the Workshop on Logic, Rationality, and Intelligent Interaction at the CSLI, Stanford University, May 27-28, 2016.

Abstract. To what extent does a structure determine its theory of truth? I shall discuss several surprising mathematical results illustrating senses in which it does not, for the satisfaction relation of first-order logic is less absolute than one might have expected. Two models of set theory, for example, can have exactly the same natural numbers and the same arithmetic structure N,+,,0,1,<, yet disagree on what is true in this structure; they have the same arithmetic, but different theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe Vδ, in common, yet disagree about whether it is a model of ZFC. These theorems and others can be proved with elementary classical model-theoretic methods, which I shall explain. Indefinite arithmetic truthOn the basis of these observations, Ruizhi Yang (Fudan University, Shanghai) and I argue that the definiteness of the theory of truth for a structure, even in the case of arithmetic, cannot be seen as arising solely from the definiteness of the structure itself in which that truth resides, but rather is a higher-order ontological commitment.

Slides | Main article: Satisfaction is not absolute | CLSI 2016 | Abstract at CLSI

The absolute truth about non-absolute truth, JAF – Weak Arithmetics Days, New York, July 2015

This will be a talk for the Journées sur les Arithmétiques Faibles – Weak Arithmetics Days conference, held in New York at the CUNY Graduate Center, July 7 – 9, 2015.

Abstract. I will discuss several fun theorems and folklore results illustrating that the satisfaction relation of first-order logic is less absolute than one might have expected. Two models of set theory, for example, can have the same natural numbers N,+,,0,1,<, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order and hence disagree about ω1CK; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe Vδ, in common, yet disagree about whether it is a model of ZFC. These theorems and others can be proved with elementary classical model-theoretic methods. Indefinite arithmetic truthOn the basis of these observations, Ruizhi Yang (Fudan University, Shanghai) and I have argued that the definiteness of the theory of truth for a structure, even in the case of arithmetic, cannot be seen as arising solely from the definiteness of the structure itself in which that truth resides, but rather is a higher-order ontological commitment.

Slides |  Main article: Satisfaction is not absolute

Does definiteness-of-truth follow from definiteness-of-objects? NY Philosophical Logic Group, NYU, November 2014

This will be a talk for the New York Philosophical Logic Group, November 10, 2014, 5-7pm, at the NYU Philosophy Department, 5 Washington Place, Room 302.

Indefinite arithmetic truth

Abstract. This talk — a mix of mathematics and philosophy — concerns the extent to which we may infer definiteness of truth in a mathematical context from definiteness of the underlying objects and structure of that context. The philosophical analysis is based in part on the mathematical observation that the satisfaction relation for model-theoretic truth is less absolute than often supposed.  Specifically, two models of set theory can have the same natural numbers and the same structure of arithmetic in common, yet disagree about whether a particular arithmetic sentence is true in that structure. In other words, two models can have the same arithmetic objects and the same formulas and sentences in the language of arithmetic, yet disagree on their corresponding theories of truth for those objects. Similarly, two models of set theory can have the same natural numbers, the same arithmetic structure, and the same arithmetic truth, yet disagree on their truths-about-truth, and so on at any desired level of the iterated truth-predicate hierarchy.  These mathematical observations, for which I shall strive to give a very gentle proof in the talk (using only elementary classical methods), suggest that a philosophical commitment to the determinate nature of the theory of truth for a structure cannot be seen as a consequence solely of the determinateness of the structure in which that truth resides. The determinate nature of arithmetic truth, for example, is not a consequence of the determinate nature of the arithmetic structure N = {0,1,2,…} itself, but rather seems to be an additional higher-order commitment requiring its own analysis and justification.

This work is based on my recent paper, Satisfaction is not absolute, joint with Ruizhi Yang (Fudan University, Shanghai).

Kelley-Morse set theory implies Con(ZFC) and much more

I should like to give a brief account of the argument that KM implies Con(ZFC) and much more. This argument is well-known classically, but unfortunately seems not to be covered in several of the common set-theoretic texts.

First, without giving a full formal axiomatization, let us review a little what KM is.  (And please see Victoria Gitman’s post on variant axiomatizations of KM.)  In contrast to Zermelo-Frankael (ZFC) set theory, which has a purely first-order axiomatization, both Kelley-Morse (KM) set theory and Gödel-Bernays (GBC) set theory are formalized in the second-order language of set theory, where we have two sorts of objects, namely sets and classes, in addition to the usual set membership relation . A model of KM will have the form M,M,S, where M is the collection of sets in the model, and S is a collection of classes in the model; each class AS is simply the subset of M.  Both KM and GBC will imply that M,M is a model of ZFC.  Both GBC and KM assert the global choice principle, which asserts that there is a class that is a well-ordering of all the sets (or equivalently that there is a class bijection of all the sets with the class of ordinals). Beyond this, both GBC and KM have a class comprehension principle, asserting that for certain formulas φ, having finitely many set and class parameters, that {xφ(x)} forms a class. In the case of GBC, we have this axiom only for φ having only set quantifiers, but in KM we also allow formulas φ that have quantification over classes (which are interpreted in the model by quanfying over S). Both theories also assert that the intersection of a class with a set is a set (which amounts to the separation axiom, and this follows from replacement anyway).  In addition, both GBC and KM have a replacement axiom, asserting that if u is a set, and for every au there is a unique set b for which φ(a,b), where φ has finitely many class and set parameters, then {bauφ(a,b)} is a set. In the case of GBC, we have the replacement axiom only when all the quantifiers of φ are first-order quantifiers only, quantifying only over sets, but in KM we allow φ to have second-order quantifiers.  Thus, both GBC and KM can be thought of as rather direct extensions of ZFC to the second-order class context, but KM goes a bit further by applying the ZFC axioms also in the case of the new second-order properties that become available in that context, while GBC does not.

The theorem I want to discuss is:

Theorem. KM proves Con(ZFC).

Indeed, ultimately we’ll show in KM that there is transitive model of ZFC, and furthermore that the universe V is the union of an elementary chain of elementary rank initial segments VθV, each of which, in particular, is a transitive model of ZFC.

We’ll prove it in several steps, which will ultimately reveal stronger results and a general coherent method and idea.

KM has a truth predicate for first-order truth. The first step is to argue in KM that there is a truth predicate Tr for first-order truth, a class of pairs (φ,a), where φ is a first-order formula in the language of set theory and a is an assignment of the free variabes of φ to particular sets, such that the class Tr gets the right answer on the quantifier-free formulas and obeys the recursive Tarskian truth conditions for Boolean combinations and first-order quantification, that is, the conditions explaining how the truth of a formula is determined from the truth of its immediate subformulas.

To construct the truth predicate, begin with the observation that we may easily define, even in ZFC, a truth predicate for quantifier-free truth, and indeed, even first-order Σn truth is Σn-definable, for any meta-theoretic natural number n. In KM, we may consider the set of natural numbers n for which there is a partial truth predicate T, one which is defined only for first-order formulas of complexity at most Σn, but which gives the correct answers on the quantifier-free formulas and which obeys the Tarskian conditions up to complexity Σn.  The set of such n exists, by the separation axiom of KM, since we can define it by a property in the second-order language (this would not work in GBC, since there is a second-order quantifier asking for the existence of the partial truth predicate).  But now we simply observe that the set contains n=0, and if it contains n, then it contains n+1, since from any Σn partial truth predicate we can define one for Σn+1. So by induction, we must have such truth predicates for all natural numbers n.  This inductive argument really used the power of KM, and cannot in general be carried out in GBC or in ZFC.

A similar argument shows by induction that all these truth predicates must agree with one another, since there can be no least complexity stage where they disagree, as the truth values at that stage are completely determined via the Tarski truth conditions from the earlier stage.  So in KM, we have a unique truth predicate defined on all first-order assertions, which has the correct truth values for quantifier-free truth and which obeys the Tarskian truth conditions.

The truth predicate Tr agrees with actual truth on any particular assertion. Since the truth predicate Tr agrees with the actual truth of quantifier-free assertions and obeys the Tarskian truth conditions, it follows by induction in the meta-theory (and so this is a scheme of assertions) that the truth predicate that we have constructed agrees with actual truth for any meta-theoretically finite assertion.

The truth predicate Tr thinks that all the ZFC axioms are all true.  Here, we refer not just to the truth of actual ZFC axioms (which Tr asserts as true by the previous paragraph), but to the possibly nonstandard formulas that exist inside our KM universe. We claim nevertheless that all such formulas the correspond to an axiom of ZFC are still decreed true by the predicate Tr.  We get all the easy axioms by the previous paragraph, since those axioms are true under KM.  It remains only to verify that Tr asserts as true all instances of the replacement axiom. For this, suppose that there is a set u, such that Tr thinks every au has a unique b for which Tr thinks φ(a,b).  But now by KM (actually we need only GB here), we may apply the replacement axiom with Tr a predicate, to find that {bauTr thinks thatφ(a,b)} is a set, whether or not φ is an actual finite length formula in the metatheory. It follows that Tr will assert this instance of replacement, and so Tr will decree all instances of replacement as being true.

KM produces a closed unbounded tower of transitive models of ZFC. This is the semantic approach, which realizes the universe as the union of an elementary chain of elementary substructures Vθ. Namely, by the reflection theorem, there is a closed unbounded class of ordinals θ such that Vθ,,TrVθΣ1V,,Tr.  (We could have used Σ2 or Σ17 here just as well.)  It follows that TrVθ fulfills the Tarskian truth conditions on the structure Vθ,, and therefore agrees with the satisfaction in that structure.  It follows that VθV for first-order truth, and since ZFC was part of what is asserted by Tr, we have produced here a transitive model of ZFC. More than this, what we have is a closed unbounded class of ordinals θ, which form an elementary chain Vθ0Vθ1Vλ, whose union is the entire universe.  Each set in this chain is a transitive model of ZFC and much more.

An alternative syntactic approach. We could alternatively have reasoned directly with the truth predicate as follows.  First, the truth predicate is complete, and contains no contradictions, simply because part of the Tarskian truth conditions are that ¬φ is true according to Tr if and only if φ is not true according to Tr, and this prevents explicit contradictions from ever becoming true in Tr, while also ensuring completeness.  Secondly, the truth predicate is closed under deduction, by a simple induction on the length of the proof.  One must verify that certain logical validities are decreed true by Tr, and then it follows easily from the truth conditions that Tr is closed under modus ponens. The conclusion is that the theory asserted by Tr contains ZFC and is consistent, so Con(ZFC) holds. Even though Tr is a proper class, the set of sentences it thinks are true is a complete consistent extension of ZFC, and so Con(ZFC) holds.  QED

The argument already shows much more than merely Con(ZFC), for we have produced a proper class length elementary tower of transitive models of ZFC.  But it generalizes even further, for example, by accommodating class parameters.  For any class A, we can construct in the same way a truth predicate TrA for truth in the first-order language of set theory augmented with a predicate for the class A.

In particular, KM proves that there is a truth predicate for truth-about-truth, that is, for truth-about-Tr, and for truth-about-truth-about-truth, and so on, iterating quite a long way. (Of course, this was also clear directly from the elementary tower of transitive models.)

The elementary tower of transitive elementary rank initial segments VθV surely addresses what is often seen as an irritating limitation of the usual reflection theorem in ZFC, that one gets only Σn-reflection VθΣnV rather than this kind of full reflection, which is what one really wants in a reflection theorem.  The point is that in KM we are able to refer to our first-order truth predicate Tr and overcome that restriction.

Doesn’t the existence of a truth predicate violate Tarski’s theorem on the non-definability of truth?  No, not here, since the truth predicate Tr is not definable in the first-order language of set theory. Tarski’s theorem asserts that there can be no definable class (even definable with set parameters) that agrees with actual truth on quantifier-free assertions and which satisfies the recursive Tarskian truth conditions.  But nothing prevents having some non-definable class that is such a truth predicate, and that is our situation here in KM.

Although the arguments here show that KM is strictly stronger than ZFC in consistency strength, it is not really very much stronger, since if κ is an inaccessible cardinal, then it is not difficult to argue in ZFC that Vκ,,Vκ+1 is a model of KM. Indeed, there will be many smaller models of KM, and so the consistency strength of KM lies strictly between that of ZFC, above much of the iterated consistency hierarchy, but below that of ZFC plus an inaccessible cardinal.

Satisfaction is not absolute, Dartmouth Logic Seminar, January 2014

dartmouth_campusThis will be a talk for the Dartmouth Logic Seminar on January 23rd, 2014.

Abstract. I will discuss a number of theorems showing that the satisfaction relation of first-order logic is less absolute than might have been supposed. Two models of set theory can have the same natural numbers, for example, and the same standard model of arithmetic N,+,,0,1,<, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree on whether it is a well-order; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have a rank initial segment of the universe Vδ, in common, yet disagree about whether it is a model of ZFC. The theorems are proved with elementary classical model-theoretic methods, and many of them can be considered folklore results in the subject of models of arithmetic.

Indefinite arithmetic truthOn the basis of these mathematical results, Ruizhi Yang (Fudan University, Shanghai) and I have argued that the definiteness of truth in a structure, such as with arithmetic truth in the standard model of arithmetic, cannot arise solely from the definiteness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

Main article: Satisfaction is not absolute

Satisfaction is not absolute

[bibtex key=HamkinsYang:SatisfactionIsNotAbsolute]

Abstract. We prove that the satisfaction relation Nφ[a] of first-order logic is not absolute between models of set theory having the structure N and the formulas φ all in common. Two models of set theory can have the same natural numbers, for example, and the same standard model of arithmetic N,+,,0,1,<, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and the same arithmetic truths, yet disagree on their truths-about-truth, at any desired level of the iterated truth-predicate hierarchy; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have the same Hω2, or the same rank-initial segment Vδ,, yet disagree on which assertions are true in these structures.

On the basis of these mathematical results, we argue that a philosophical commitment to the determinateness of the theory of truth for a structure cannot be seen as a consequence solely of the determinateness of the structure in which that truth resides. The determinate nature of arithmetic truth, for example, is not a consequence of the determinate nature of the arithmetic structure N={0,1,2,} itself, but rather, we argue, is an additional higher-order commitment requiring its own analysis and justification.

Many mathematicians and philosophers regard the natural numbers 0,1,2,, along with their usual arithmetic structure, as having a privileged mathematical existence, a Platonic realm in which assertions have definite, absolute truth values, independently of our ability to prove or discover them. Although there are some arithmetic assertions that we can neither prove nor refute—such as the consistency of the background theory in which we undertake our proofs—the view is that nevertheless there is a fact of the matter about whether any such arithmetic statement is true or false in the intended interpretation. The definite nature of arithmetic truth is often seen as a consequence of the definiteness of the structure of arithmetic N,+,,0,1,< itself, for if the natural numbers exist in a clear and distinct totality in a way that is unambiguous and absolute, then (on this view) the first-order theory of truth residing in that structure—arithmetic truth—is similarly clear and distinct.

Feferman provides an instance of this perspective when he writes (Feferman 2013, Comments for EFI Workshop, p. 6-7) :

In my view, the conception [of the bare structure of the natural numbers] is completely clear, and thence all arithmetical statements are definite.

It is Feferman’s `thence’ to which we call attention.  Martin makes a similar point (Martin, 2012, Completeness or incompleteness of basic mathematical concepts):

What I am suggesting is that the real reason for confidence in first-order completeness is our confidence in the full determinateness of the concept of the natural numbers.

Many mathematicians and philosophers seem to share this perspective. The truth of an arithmetic statement, to be sure, does seem to depend entirely on the structure N,+,,0,1,<, with all quantifiers restricted to N and using only those arithmetic operations and relations, and so if that structure has a definite nature, then it would seem that the truth of the statement should be similarly definite.

Nevertheless, in this article we should like to tease apart these two ontological commitments, arguing that the definiteness of truth for a given mathematical structure, such as the natural numbers, the reals or higher-order structures such as Hω2 or Vδ, does not follow from the definite nature of the underlying structure in which that truth resides. Rather, we argue that the commitment to a theory of truth for a structure is a higher-order ontological commitment, going strictly beyond the commitment to a definite nature for the underlying structure itself.

We make our argument in part by proving that different models of set theory can have a structure identically in common, even the natural numbers, yet disagree on the theory of truth for that structure.

Theorem.

  • Two models of set theory can have the same structure of arithmetic N,+,,0,1,<M1=N,+,,0,1,<M2,yet disagree on the theory of arithmetic truth.
  • Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is a well-order.
  • Two models of set theory that have the same natural numbers and the same reals, yet disagree on projective truth.
  • Two models of set theory can have a transitive rank initial segment in common Vδ,M1=Vδ,M2,yet disagree about whether it is a model of ZFC.

The proofs use only elementary classical methods, and might be considered to be a part of the folklore of the subject of models of arithmetic. The paper includes many further examples of the phenomenon, and concludes with a philosophical discussion of the issue of definiteness, concerning the question of whether one may deduce definiteness-of-truth from definiteness-of-objects and definiteness-of-structure.

 

Satisfaction is not absolute, CUNY Logic Workshop, September 2013

This will be a talk for the CUNY Logic Workshop on September 27, 2013.

Abstract.  I will discuss a number of theorems showing that the satisfaction relation of first-order logic is less absolute than might have been supposed. Two models of set theory M1 and M2, for example, can agree on their natural numbers N,+,,0,1,<M1=N,+,,0,1,<M2, yet disagree on arithmetic truth: they have a sentence σ in the language of arithmetic that M1 thinks is true in the natural numbers, yet M2 thinks ¬σ there. Two models of set theory can agree on the natural numbers N and on the reals R, yet disagree on projective truth. Two models of set theory can have the same natural numbers and have a computable linear order in common, yet disagree about whether this order is well-ordered. Two models of set theory can have a transitive rank initial segment Vδ in common, yet disagree about whether this Vδ is a model of ZFC. The theorems are proved with elementary classical methods.

This is joint work with Ruizhi Yang (Fudan University, Shanghai). We argue, on the basis of these mathematical results, that the definiteness of truth in a structure, such as with arithmetic truth in the standard model of arithmetic, cannot arise solely from the definiteness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

Article

Exploring the Frontiers of Incompleteness, Harvard, August 2013

I will be participating in the culminating workshop of the Exploring the Frontiers of Incompleteness conference series at Harvard University, to take place August 31-September 1, 2013.  Rather than conference talks, the program will consist of extended discussion sessions by the participants of the year-long series, with the discussion framed by very brief summary presentations.  Peter Koellner asked me to prepare such a presentation on the multiverse conception, and you can see the slides in The multiverse perspective in set theory (Slides).

My previous EFI talk was The multiverse perspective on determinateness in set theory, based in part on my paper The set-theoretical multiverse.

Satisfaction is not absolute, Connecticut, October 2013

This will be a talk for the Logic Seminar in the Mathematics Department at the University of Connecticut in Storrs on October 25, 2013.

Abstract. The satisfaction relation Nφ[a] of first-order logic, it turns out, is less absolute than might have been supposed.  Two models of set theory, for example, can agree on their natural numbers and on what they think is the standard model of arithmetic N,+,,0,1,<, yet disagree on their theories of arithmetic truth, the first-order truths of this structure.  Two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth.  Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is well-ordered.  Two models of set theory can have a transitive rank initial segment Vδ in common, yet disagree about whether it is a model of ZFC.  The arguments rely mainly on elementary classical methods.

This is joint work with Ruizhi Yang (Fudan University, Shanghai), and our manuscript will be available soon, in which we prove these and several other very general facts showing that satisfaction is not absolute.  On the basis of these mathematical results, we mount a philosophical argument that a commitment to the determinateness of truth in a structure, such as the case of arithmetic truth in the standard model of arithmetic, cannot result solely from the determinateness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

University of Connecticut Logic Seminar | Article