Logic for Philosophers, NYU, Spring 2015, graduate seminar PHIL-GA 1003

NYU PhilosophyThis seminar will be a graduate-level survey of topics in logic for philosophers, including propositional logic, modal logic, predicate logic, model theory, completeness, incompleteness, computability theory, set theory and the higher infinite. The material will thus be a mixture of philosophical logic and mathematical logic, and a goal of the course will be to develop the student’s ability to consider these ideas with clarity and precision.

The lectures will be largely self-contained, and some course materials will be distributed during the semester.  On some topics, material will be drawn from:

More Precisely, The Math You Need to do Philosophy, Eric Steinhart, Broadview.

On other topics, students may wish to supplement the lecture notes with other sources, and there are dozens of suitable texts for this purpose, as well as on-line information.

For focused help, students are also directed to the following excellent on-line resources:

  1. Math.StackExchange.com, an on-line question/answer forum for mathematics questions, which welcomes questions on logic, and most questions get high quality answers very quickly.
  2. MathOverflow.net, a similar site for research-level mathematics questions.

Weekly exercises.  Exercises will be assigned in connection with each lecture, and these are due by the following lecture.  It is fine and even advisable for you to work in groups, but kindly submit only solutions that you yourself have thoroughly mastered.

Final paper.  Students will write a final paper (about 8 pages) on an approved topic chosen in consultation with the instructor.  The instructor’s goal in assigning this paper is to give the students experience both in conducting research on a technical topic, as well as in writing on such a topic.  Suitable topics will be suggested, but they will generally consist not of giving a summary account or criticism of an advanced topic from the literature (this will be discouraged), but rather of considering a modest but novel topic or context—perhaps a variation of a better known theory—and then discovering and working out some interesting aspect of it. The idea is that the paper topic should be a little like undertaking research in logic.  The paper is due by the last day of the semester, and late work will not be accepted.

Grading. Grades will be based on the weekly exercises and the final paper (with a class participation element).  All work for this class, including the final paper, must be submitted by the last day of the semester.  No Incomplete grades will be given—no exceptions.

My intention is to post the weekly problem sets here, by updating this post.  I will make Google+ posts pointing to this page when it is updated, for a circle of subscribed members; send me a message on G+ to join the circle (or you can alternatively just subscribe to this blog, but then you’ll get notified of all my posts).


Lecture 1.  A picture of logic.  Propositional logic. Truth tables; tautologies; logical equivalence; well-formed formulas; induction on formulas; complete sets of connectives; every truth function is represented by a formula in disjunctive normal form; satisfiability; connections with P vs. NP.

Lecture 1 notes by a student

Exercises:

1. Make truth tables for (𝑝𝑞𝑟)((𝑝𝑞)𝑟) (𝑝(𝑡𝑞))((𝑞𝑟)𝑝) (((𝑝𝑞)𝑟)(𝑟(¬𝑞𝑟)))𝑟

2. Argue that every well-formed formula of propositional logic has the same number of left as right parentheses.  (According to the rules we gave in class for the formula-building operations.)

3. Argue that every well-formed formula of propositional logic has twice as many parentheses as binary logical connectives.

4. Argue that the collection of tautologies is closed under conjunction, disjunction, implication and biconditional. In other words, if 𝜑 and 𝜓 are tautologies, then so are 𝜑 𝜓, 𝜑 𝜓, 𝜑 𝜓 and 𝜑 𝜓.

5. Which of the converses of these are true? In other words, which of the following are correct:

  • If 𝐴 𝐵 is a tautology, then 𝐴 and 𝐵 are tautologies.
  • If 𝐴 𝐵 is a tautology, then 𝐴 and 𝐵 are tautologies.
  • If 𝐴 𝐵 is a tautology, then 𝐴 and 𝐵 are tautologies.
  • If 𝐴 𝐵 is a tautology, then 𝐴 and 𝐵 are tautologies.

6. Argue that every propositional assertion is logically equivalent to an assertion in conjunctive normal form (a conjunction of disjunction clauses, each of which is a disjunction of literals).  (Hint:  in class we proved that every propositional assertion is logically equivalent to an assertion in disjunction normal form.  Given 𝜑, consider ¬𝜑 in light of what we did in class.)

7. Determine which of the following sets of logical connectives are complete: {¬, },  {¬, }.  (The second one is a bit harder, and we’ll cover it in class next time.)

8.  Show that Nand and Nor are the only binary connectives that, by themselves individually, are complete.  (Hint:  if you have a binary connective 𝐴 𝐵 that is complete, then consider what the truth table of must be. What must it be on the top row? On the bottom row? How many possibilities remain?)

Possible paper topic connected with the Satisfiability problem and P vs. NP.  For example, you could write a paper explaining how the general satisfiability problem reduces to the 3-Sat problem.  (This is a classical result, but one that can be easily rediscovered independently.)


 

Lecture 2. Discussion of homework problems from last time, including a simple account of the disjunctive normal form theorem and the conjunctive normal form theorem.

New topic:  multi-valued logic; Lukasiewicz/Kleene logic.  Basic truth tables for 3-valued logic.  Discussion of various motivations, such as logic of missing information, logic of possible worlds, logic of unknown truth values, neither true nor false, both true and false; most of these stories are flawed and do not actually capture the logic. Tautologies and complete sets of connectives in 3-valued logic.  Notions of logical equivalence. No strict tautologies. Disjunctive normal form still works.  Weak tautologies are the same as classical tautologies.

Lecture 2 notes by a student

Exercises. 

  1. If 𝜑 is a propositional assertion in the language with ¬, , , , , and 𝜑(𝑝) =𝑈. Does there always exist a crispification of 𝑝 to 𝑝 with 𝜑(𝑝) =𝑇 and another crispification 𝑝 with 𝜑(𝑝) =𝐹? In other words, does the truth value 𝑈 mean that it could have been 𝑇 and it could have been 𝐹, depending on what way the input 𝑈 values are made crisp?
  2. Define a natural analogue of NAND and of NOR for Kleene logic. Does it obey the expected identities? Does it continue to be complete in Kleene logic in the narrow sense? In the wide sense?
  3. Verify the De Morgan laws in Lukasiewicz logic, namely, that ¬(𝐴 𝐵) ¬𝐴 ¬𝐵 and ¬(𝐴 𝐵) ¬𝐴 ¬𝐵, using to mean logically equivalent in the sense of having the same truth table.
  4. Verify the distributivity laws 𝑃(𝑄𝑅)=(𝑃𝑄)(𝑃𝑅) 𝑃(𝑄𝑅)=(𝑃𝑄)(𝑃𝑅) in Lukasiewicz logic.  (You probably don’t want to compute the truth table, since it has 27 rows; rather, reason about what must happen if 𝑃 is true; if 𝑃 is false; and if 𝑃 is 𝑈.)
  5. Find an expression in 𝑃, 𝑄 and 𝑅 that has value 𝑈, if any of them is 𝑈, and otherwise has value 𝐹.
  6. Is the truth table of every expression in Lukasiewicz logic determined (as it is in classical logic) by the location of the 𝑇’s? That is, if you know where the 𝑇’s are, can you determined whether the others are 𝐹 or 𝑈, just from knowing that the expression came from , ,¬, , ?

Possible paper topics.

  • Develop the logic of missing information.  The context would be that there is a genuine classical logic world, but we do not know some of the truth values of the atomic facts.  What is a sensible way to develop a logic for this situation? Is it truth-functional? Can we assign truth values to every statement in a sensible multi-valued logic? What are the notions of tautology, validity, completeness, and so on?
  • Explore the notion of complete sets of logical connectives in Lukasiewicz logic.  We know the standard set of connectives ¬, , , , is not complete, but can we augment it with another connective to make it complete? Is there a single connective in the 3-valued logic that is complete? (I have some good references for research on this topic.)

 

Lecture 3.  Fuzzy logic. Definitions of the logic. Disjunctive normal form theorem. Traditional connectives are not complete. No finite set  (nor even any countably infinite set, nor even any set of size continuum) is complete for fuzzy logic. Tautologies in fuzzy logic; weak tautologies (truth value 12); positive assertions (truth value is never 0). For assertions in traditional logical language, weak tautologies, positive and classical tautologies are the same. The proof uses logical homomorphisms, translating fuzzy logic to Lukasiewicz logic. We discussed various kinds of logical homomorphisms. General treatment of truth-functional logic: a space L of truth values, with logical functions ¬, , on that space.  Concepts of extensions L0 L1 and logical homomorphisms 𝜋 :L1 L0. Boolean algebras. Axioms of Boolean algebras. A few examples, including power sets.

Exercises.

  1. Verify in fuzzy logic that 𝑝𝑞(𝑝𝑞)(¬𝑝¬𝑞).
  2. Verify that the de Morgan laws continue to hold in fuzzy logic.¬(𝐴𝐵)(¬𝐴)(¬𝐵)¬(𝐴𝐵)(¬𝐴)(¬𝐵)
  3. Verify that the distributivity laws continue to hold in fuzzy logic.𝐴(𝐵𝐶)(𝐴𝐵)(𝐴𝐶)𝐴(𝐵𝐶)(𝐴𝐵)(𝐴𝐶)
  4. Argue that in fuzzy logic, just as in Lukasiewicz logic, there are no tautologies in the language having only the traditional five connectives: ¬, , , , .
  5. Consider the translation from fuzzy logic to Lukasiewicz logic, which takes the center interval (13,23) of fuzzy truth values to the truth value U; the numbers in the interval [0,13] to 𝐹 and numbers in [23,1] to 𝑇. Show that this is a logical homomorphism of fuzzy logic to Lukasiewicz logic.
  6. Show that there is no logical homomorphism of fuzzy logic to classical logic.
  7. Discuss the question of whether fuzzy logic is the logic of probabilistic reasoning. Suppose that we are in a probability space, where the underlying propositional variables are given a probability. Does fuzzy logic then give sensible probabilities for compound logical expressions using those variables? That is, if we know the probabilities of 𝑝, 𝑞 and 𝑟, then does fuzzy logic tell us the probability of compound expressions like 𝑝 (𝑞 𝑟)?

Suggested Paper topics.

  1. Investigate the nature of the fuzzy truth functions that one may define using the standard five connectives. Can one recognize or characterize them? How many binary connectives are realized?
  2. Investigate and discuss the issue of continuity of truth functions in fuzzy logic. Under what kind of semantics would one want to make use of or consider discontinuous truth functions?
  3. Discuss the issue or ordinal comparision versus cardinal comparison in fuzzy logic truth values.  One might consider logical homomorphisms of fuzzy logic to itself, which preserve the order of truth values, but which greatly magnify small differences or diminish large ones.

Lecture 4.  Relational logic; the theory of relations. Reflexivity, symmetry, transitivity; irreflexivity; asymmetry; anti-symmetry; anti-transitivity; equivalence relations; equivalence classes; partitions; every equivalence relation determines a partition and vice versa. Refinement of equivalence relations. Partial orders; strict orders; converse order; pre-order; comparability.

Lecture 4 student notes

Exercises.

  1. Are all eight combinations of the properties of reflexivity, symmetry and transitivity possible? Provide instances of relations exhibiting each combination that can occur.
  2. Criticize the following argument that every relation that is symmetric and transitive is also reflexive: If 𝐸 is symmetric, then 𝑎𝐸𝑏 implies 𝑏𝐸𝑎, and so if it is also transitive, it follows that 𝑎𝐸𝑎, and so it is reflexive. Is this argument correct? If not, what is a correct statement that a similar argument establishes?
  3. How are the concepts of asymmetric, anti-symmetric and “not symmetric” connected to each other? Which imply which others? Which of the eight conceivable combinations actually arise? Provide relations exhibiting each possible combination.
  4. How many equivalence relations are there on a 4 element set? It is possible easily to draw a small picture of each one. Organize this chart into the refinement hierarchy.
  5. Consider the claim that the living-in-the-same-city-as relation refines the living-in-the-same-country-as relation, on the set of all people.  Discuss the various problematic assumptions underlying this example. For example, if there were a person who lives in more than one country, or no country, or a person who lives in more than one city, or no city; or suppose that there is a city with parts in more than one country. For each of these situations and others you may think of, precisely which parts of the claims that these relations are both equivalence relations on the set of all people and that the first relation refines the second would be affected?
  6. Consider the relation of comparability for elements in a partial order.  Is it an equivalence relation? Consider each of the properties of relations that we have considered (reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, etc.) and argue that comparability always has that property or give an example partial order showing that the comparability relation need not have that property.

 


Lecture 5. Order theory. Mathematical and natural examples. Reflexive closure of a relation. Symmetric closure. Transitive closure. The reflexive/transitive closure of a relation is the same as the reachability relation. Strict partial orders. Defining < from and vice versa. Pre-orders (quasi-orders). With pre-orders, the interdefinability of < with breaks down. Example of distinct preference pre-orders with same strict preferences. Maximal and greatest elements. Minimal and least elements. Example of a partial order with a unique maximal element that is not greatest. Upper bounds; lower bounds; least upper bounds; greatest lower bounds. Lattices. Linear orders. Linearly graded partial orders.

Lecture 5 student notes

Exercises.

  1. Give an example of an anti-symmetric relation, whose reflexive/transitive closure is not anti-symmetric.
  2. Give a relation on five elements, using as few relational instances as possible, whose reflexive/transitive closure is the full relation (for which each of the five elements stands in the relation to all five elements). How many relational edges did you use? Can you make a general claim and argument for a domain with 𝑛 elements?
  3. Suppose that is a partial pre-order. Define 𝑎 𝑏 just in case 𝑎 𝑏 and 𝑏 𝑎. Argue that is an equivalence relation on the same domain.
  4. Does the interdefinability of and < succeed with pre-orders? Suppose that is a transitive reflexive relation (that is, a pre-order). Define 𝑎 <𝑏 if 𝑎 𝑏 and 𝑎 𝑏. Will this necessarily be a partial order? If not, what is a better way to define a strict partial order 𝑎 <𝑏 in terms of for a pre-order ?
  5. Suppose that an author (mistakenly, in my view) defines that we are {\it indifferent} between 𝑎 and 𝑏 if neither 𝑎 nor 𝑏 is better than the other. That is, 𝑎 𝑏 𝑎 𝑏 𝑏 𝑎. Provide a preference relation for which this is not an equivalence relation. Specifically, we’d want the person to be indifferent between 𝑎 and 𝑏, and indifferent between 𝑏 and 𝑐, but not indifferent between 𝑎 and 𝑐.
  6. True or false: if is a partial ordering on a set, then 𝑎 𝑏 if and only if 𝑏 𝑎.
  7. Give an example of a partial order that admits more than one linear grading order. In other words, provide a partial order that can be divided into levels in more than one way.

Suggested paper topics.

  1. The connection between preference relations and group preferences. For example, if you try to define a group preference by using majority rule on the individual preferences, then you don’t necessarily get a partial order.
  2. The algebra of partial orders. If 𝔸 and 𝔹 are partial orderings, there is a notion of 𝔸 +𝔹, which is the order placing a copy of 𝔹 on top of a copy of 𝔸; and 𝔸 ×𝔹 is the order consisting of 𝔹 many copies of 𝔸. There are numerous easy but interesting questions to ask about how features are preserved or not by these constructions, such as: if 𝔸 and 𝔹 are dense orders, then are 𝔸 +𝔹 also dense? 𝔸 ×𝔹? And what of discrete orders?

 

Lecture 6. First-order predicate logic. Formal language of a relational structure. Well-formed formulas. Induction on formulas. Parse trees. Unique readability. Free and bound variables. Scope. Sentences. Definition of satisfaction. Truth in a model.

Lecture 6 student notes

Exercises.

  1. In the language of the structure , , construct a formula with two free occurrences each of the variable symbols 𝑥, 𝑦 and 𝑧, and with two bound occurrences of 𝑥 and 𝑦, but where the bound appearances of 𝑥 fall under the scope of different quantifications over 𝑥. Next, construct a second formula with variables 𝑤,𝑥,𝑦,𝑧 each with one free occurrence and three bound occurrences, but make the bound occurrences of 𝑤,𝑥, respectively, fall under the scope of different quantifiers of these variables.
  2. Distinguish the structure +, , where + denotes the positive integers and 𝑛 𝑚 just in case 𝑛 divides 𝑚, from the structure 𝐹, , where 𝐹 is the collection of finite subsets of the natural numbers . That is, find a statement in the first-order language with one binary relation, which is true in +, and false in 𝐹, .
  3. For each of the following pairs or triples of structures, distinguish them by finding a sentence that is true in the first, but false in the second.  Exercise_graphs

Lecture 7. Signatures in first-order logic, with constants, functions and relations. terms. Models. Satisfaction. Distinguishing various structures by sentences. (Aside on the irrationality of 2.) The type of an element. Submodels. Reducts. Expansions. Elementary submodels. Leibniz principle on identity of indiscernibles. Leibnizian models. Isomorphisms. Elementary embeddings.

Lecture 7 students notes

Exercises.

  1. Kindly do the rest of problem 3 from lecture 6 above; some of those instances were not mentioned in the previous lecture.
  2. Distinguish the following structures in the first-order language having only multiplication, by finding for each structure a sentence true only in that structure:
    ,,,
  3. Show that 3 is irrational. (Hint: follow the argument for 2 given in lecture, but replace talk of even/odd with talk involving divisibility-by-3. After all, a number is even just in case it is divisible by 2.) What do you think is the general fact concerning whether 𝑛 is irrational for natural numbers 𝑛?
  4. Consider the chain of submodels +,<,<,<,<Are any of these submodels elementary submodels?
  5. Argue that , < is Leibnizian (any two elements are discernible, that is, they have different types).
  6. Let 𝐴, be a relational structure in which is an equivalence relation. Show that if 𝑎 𝑏, then 𝑎 and 𝑏 are indiscernible in this structure.
  7. Give an example of an infinite pre-order, which is not a partial order, in which any two elements are indiscernible.
  8. Using some of the examples from the other exercises, find a structure M and a submodel N M such that N M but N M.
  9. In the integers, is less-than fundamentally different from greater-than? Compare , < with , >. Are there any statements that can tell apart < from >? Specifically, argue that the structures , < and , > satisfy exactly the same truths. Conclusion: no first-order assertion can tell apart < from >. That is, , < , >.

 

Paper topics.

  1. Indiscernibility and identity.  Objects in a model are indiscernible with respect to a given formal language, if they satisfy all the same formulas in that language. There are numerous examples of structures having indiscernible non-identical elements, or in which all elements are indiscernible or none are, and it would be an interesting project to find examples illustrating the range of possibility.
  2. Is every structure characterized by the collection of first-order truths in it? Is this true for finite structures? This is actually a deep topic, and there are many interesting examples and ideas.

Lecture 8. Definability. Definable elements, definable subsets. Examples with small finite partial orders. Every element of , < is definable. No element of , < is definable. Homomorphisms, isomorphisms, automorphisms. If every object is definable, then the structure is Leibnizian. Is the converse true? No. Example of a Leibnizian structure with non-definable elements. < is definable in , <, but not in , <. The Peano structure ,𝑆,0. This structure admits elimination of quantifiers, by an argument proceeding via induction on formulas.

 

 

Exercises.

  1. Which are the definable elements of the following partial orders? For each definable element, provide a definition; if an element is not definable, explain how you know that. Two partial orders
  2. Consider the case of an equivalence relation having exactly one class of size one, exactly one class of size two, exactly one class of size three, etc. Are there any definable elements? What are the definable subsets?
  3. Show that every element is definable in , +. (Hint: it is easy to define 0; to define 1, note that 1 cannot be written as the sum of two other numbers, neither of which are 1; now use 1 to define all other numbers.)
  4. Show that multiplication is not definable from addition in , +. (Hint: If it were, then 1 would be definable. But argue that 1 is not definable in , +.)
  5. Show that “𝑥 is even” and “𝑥 is odd” are definable in , +. Using the elimination of quantifiers result from lecture, conclude that + is not definable in the Peano structure ,𝑆,0.
  6. Show that “𝑥 is prime” is definable in , .

Suggested Paper topics.

  1. Additional instances of elimination of quantifiers. For example, in , <, which is an interesting argument.
  2. Argue that in a finite structure, Leibnitzian is the same as every-object-is-definable.
  3. Discuss the Leibnitizian axiom of set theory: every two objects are discernible over the ordinals.
  4. On the significance of Tarski’s theorem that , +, ,0,1, < admits elimination of quantifiers. Discuss significance of having a decision procedure for Cartesian plane geometry.

Lecture 9. Continuation of quantifier elimination. Discussion of Tarski’s theorem on quantifier elimination for , +, ,0,1, <, and consequent decidability of Cartesian geometry.  Modal logic. Examples of natural modalities. Kripke semantics. Kripke models for propositional modal logic. Kripke frames. Axiom K (𝜑 𝜓) (𝜑 𝜓) and axiom Dual ¬𝜑 ¬𝜑 are true in all Kripke models. Axiom S 𝜑 𝜑 is valid on a frame just in case the frame is reflexive. Seriality D 𝜑 𝜑 is valid on a frame just in case the frame has no terminal worlds, accessing no other worlds. Axiom 4 𝜑 𝜑 is valid on a frame just in case the frame transitive. Axiom 5 𝜑 𝜑 is valid on a frame just in case the frame is symmetric. Axiom (.2) 𝜑 𝜑 expresses that the frame is directed. Axiom (.3) 𝜑 𝜓 ((𝜑 𝜓) (𝜑 𝜓) (𝜓 𝜑)) expresses that the frame is linear.  Predicate modal logic. The Barcan formula 𝑥𝜑(𝑥) 𝑥𝜑(𝑥) and the converse Barcan 𝑥𝜑(𝑥) 𝑥𝜑(𝑥), and the connection with growing vs. shrinking worlds.

Exercises.

  1. Determine the truth of the following assertions at the various worlds in the following Kripke model. (𝑝𝑝),𝑝,¬𝑝,𝑝𝑝,(𝑝¬𝑝)Kripke model 1
  2. Prove that every assertion of propositional modal
    logic is equivalent under the Kripke semantics to an assertion using only
    , ,¬.
  3. Show that [(𝜑) (𝜓)] (𝜑 𝜓) is valid on a partial pre-order frame just in case the frame is directed.

Paper topics. We have fewer exercises because it is time to be working on your papers.  Please make an appointment to discuss your topic with me, if you have not done so already.

  1. Combine modal logic Kripke semantics with multivalued logic.
  2. Investigate predicate modal logic, such as conditions for the Barcan formula and for its converse.
  3. Bimodalities obtained by using the accessibility relation and its inverse.
  4. Analyze various conceptions of temporal logic using modal logic, and investigate how one’s conception of the nature of possibility through time (such as linear, tree branching, others) arise in the resulting modal logic.

Lecture 10. Theory theory. 𝑇 𝜑. Deduction theorem for logical consequence: Γ +𝜑 𝜓 Γ 𝜑 𝜓. The set of models of a theory, Mod(𝑇). The theory of a model Th(𝑀). The theory of a set of models, Th(Γ). Γ0 Γ1 Th(Γ1) Th(Γ0). 𝑇0 𝑇1 Mod(𝑇1) Mod(𝑇0). Γ Mod(Th(Γ)). 𝑇 Th(Mod(𝑇)). Mod(Th(Mod(𝑇)) =Mod(𝑇). Consequences of a theory. Complete theory. Satisfiable theory. Finitely satisfiable theory. Compactness theorem: A theory 𝑇 is finitely satisfiable if and only if it is satisfiable. Direct proof of compactness using Henkin constants. Every finitely satisfiable theory 𝑇 is contained in a finitely satisfiable complete Henkin theory. Every such theory has a model, built from the Henkin constants. Consequences of compactness. Finiteness is not first-order expressible. Every theory with arbitrarily large finite models has an infinite model. Upward Löwenheim-Skolem theorem. Elementary extensions of , +, ,0,1, <. Nonstandard analysis. Infinitesimals. Historical significance of nonstandard analysis for calculus.Lecture 10 student notes

Exercises.

  1. Show that Th(Mod(Th(Γ))) =Th(Γ), if Γ is any set of models.
  2. Let Conseq(𝑇) ={ 𝜑 𝑇 𝜑 }, the set of consequences of a theory 𝑇. Show that 𝑇 𝜓 if and only if Conseq(𝑇) 𝜓.
  3. Show that a theory 𝑇 is closed under consequences (that is, 𝑇 𝜎 implies 𝜎 𝑇) if and only if 𝑇 =Th(Mod(𝑇)). (Edit: an earlier version of this exercise was not correct.)
  4. Show that if 𝑇 𝜑, then there is a finite subtheory 𝑆 𝑇 such that 𝑆 𝜑. In another words, if a statement 𝜑 is a consequence of a theory 𝑇, then there is a finite part of the theory that is responsible for this.

Suggested paper topics.

  1. Nonstandard analysis. There are many topics here that would be suitable; please come and discuss with me. Using the compactness theorem, one could establish that various kinds of nonstandard natural exist.
  2. Undertake some theory theory in infinitary logic. Prove that compactness can fail; finiteness is expressible and so on.

Lecture 11. Proof theory. What is a proof? Various formal proof systems. Logical axioms, rules of inference, formal proof. Automated theorem proving. Importance of (1) soundness 𝑇 𝜑 implies 𝑇 𝜑; (2) completeness 𝑇 𝜑 implies 𝑇 𝜑; (3) decidability: we should be able to recognize whether something is a proof. The MM proof system (A. Miller) is sound and complete. Another more satisfactory proof system, with examples. Gödel’s completeness theorem, using Henkin’s proof. Every consistent theory can be extended to a complete consistent Henkin theory, and every such theory is satisfiable.

Lecture 11 students notes

Exercises.

  1. Construct a formal proof system that is sound, but not complete.
  2. Construct a formal proof system that is complete, but not sound.
  3. Construct a formal proof system that is sound and complete, but not decidable. (These first three exercises are meant to be very easy, and there is no need for the systems to be complicated at all. Think along the lines of having a system with no logical axioms or with every statement being an axiom or with having lots of rules of inference, or none. The right combinations will make the examples work.)
  4. Show that a theory 𝑇 is inconsistent (proves a contradiction 𝜑 ¬𝜑 for some 𝜑) just in case 𝑇 𝜓 for every 𝜓.
  5. Extra: Show that every formal proof system is equivalent to a formal proof system having no logical axioms. (Hint: add extra rules of inference with empty hypotheses.)
  6. Extra: Show that any formal proof system having no logical axioms and having rules of inference only with nonempty hypotheses, is not complete. (Hint: consider the proofs arising from the empty theory.)
  7. Extra: Show that no sound formal proof system having only logical axioms and no rules of inference is complete.

Suggested paper topics.

  1. Design your own formal proof system and prove the completeness theorem for it.
  2. Translating proofs from one system to another.
  3. Automated reasoning. Learn one of the standard proof-checker automated theorem proving systems and carry out a nontrivial formal proof in it.

turing_machineLecture 12. Computability theory. Primitive recursive functions; composition; primitive recursion, with examples. Turing machines. Sample programs. Other computational models: register machines, flowchart machines, recursive functions, idealized programming languages. Hierarchy vision of computability vs. threshold vision. Church-Turing thesis (weak and strong). Undecidability of the halting problem.

Lecture 12 student notes

Exercises

  1. Write a Turing machine program to compute the function 𝑑(𝑛) =0, when 𝑛 is even; otherwise, 𝑑(𝑛) =1, when 𝑛 is odd.
  2. Extra: Explain how the the class of Turing computable functions avoids the diagonalization argument of Gödel given for the primitive recursive functions. That is, we may still effectively enumerate 𝑓𝑛 all computable functions, and still attempt to define 𝑔(𝑛) =𝑓𝑛(𝑛) +1. Does this argument show that there are intuitively computable functions that are not Turing computable? Why does it work with primitive recursive functions and not with computable functions?

Paper topics

  1. Develop a new model of computability and prove that it is Turing complete.
  2. Topics in oracle computation and the Turing degrees.
  3. Topics in infinitary computability, such as Blum-Shub-Smale machines, or infinite time Turing machines.

Next week:  Gödel’s incompleteness theorems!


Lecture 13. Gödel’s incompleteness theorems. Hilbert program. Proof of first incompleteness via halting problem (due to Kleene). For any true computably axiomatizable theory 𝑇, there is a Turing machine program 𝑝 and input 𝑘 such that 𝑝 does not halt on input 𝑘, but 𝑇 does not prove this. MRDP theorem. Arithmetization of syntax. Gödel codes. Carnap’s fixed-point lemma. Gödel sentence, “I am not provable.” First incompleteness theorem. Second incompleteness theorem. Derivability conditions. Rosser’s theorem. Tarski’s theorem. Löb’s theorem. Independence phenomenon. Goodstein’s theorem. Kirby-Paris Hydra theorem.

Lecture 13 student notes

Exercises.

  1. Show that if 𝑇 is a computably axiomatizable theory extending PA, then 𝑇 is inconsistent just in case 𝑇 proves Con𝑇.

All students should be working on their final papers, with the topic chosen in consultation with me.  The papers are due by the end of finals week; no late work will be accepted. Please come to my office with drafts for comments and suggestions.

 


V_thetaLecture 14. Set theory and the higher infinite. The googol plex bang stack hierarchy. Hilbert’s hotel. Countable sets. Cantor’s theorem on the uncountability of the reals. Equinumerosity. Cantor-Schröder-Bernstein theorem. Ordinals. How to count. Cantor’s theorem that 𝑋 <𝑃(𝑋). General Comprehension principle. Russell’s paradox. Rise of ZFC. The continuum hypothesis. Gödel’s theorem on the constructible universe; Cohen’s development of forcing. The independence phenomenon. The singularist/pluralist debate in the philosophy of set theory.

Lecture 14 student notes

This was the last lecture; it was a great time! Final papers are due by the end of finals week. Please drop by my office for comments on a draft version of your paper.


Final Papers The students all wrote final papers on various topics connected with the seminar, and many of them were quite interesting. Let me summarize here several of the resulting titles and topics.

Mala Chatterjee, Łukasiewicz Logic & Strong Completeness.  Mala investigates complete sets of connectives for Łukasiewicz logic, introducing several novel connectives, denoted by +, and , which she shows can form various small complete sets of connectives for this logic.

Hugo Dumoulin, Logic Gates and the Turing Machine. Hugo constructs a subtractor using only logic gates and explains how logic gates can be used be used to simulate Turing machines.

Arden Koehler, Definability and distinguishability in finite and infinite structures.  Arden investigates the difference between Leibnizian structures (where any two objects have different types) and pointwise-definable structures (where every individual is definable) in first-order logic. In finite structures, the concepts are equivalent, but there are infinite structures, even in a finite language, which are Leibnizian, yet have no definable elements.

Annette Martin, A brief look at nonstandard models of true arithmetic. Annette develops the theory of nonstandard models of true arithmetic, establishing the overspill principle, determining the order type of every countable nonstandard model of arithmetic, proving that every nonstandard model of arithmetic has entire chains consisting of composite nonstandard numbers, and proving that there are uncountably many pairwise non-isomorphic countable nonstandard models of true arithmetic.

Nathan Pensler, What is the Logic of Missing Information?  Abstract: Is there a logic of missing information? In this paper, I’ll survey several logics and determine
whether any of them provide an adequate analysis of the concept. I first discuss Kleene and Łukasiewicz Logics. I argue that both systems fail as logics of missing information, due to counterexamples involving classical tautologies. I then discuss several new logics of missing information, all of which assign truth values to formulae relative to an informational background. I define what it is for a logic to be truth functional and prove that several logics of this type are truth functional just in case the informational background is severely restricted. I then explore a truth-functional logic of missing information. I conclude by exploring whether there is reason to prefer the truth functional logic of missing information to the non-truth functional logics.

David Storrs-Fox, The modal logic of a knight in chess.  David investigates the modal logic of a knight’s move, by considering the frame consisting of the squares on a chessboard (in both the finite and infinite cases) as the possible worlds and the knight’s move as the accessibility relation. After settling a large number of validities and invalidities for this chessboard interpretation, David proves that the squares on the 8×8 chessboard are distinguished by their modal validities, unless they are in rotational or reflective symmetry.

Casey Tirschfield, Select limitations of infinitary logic.   In this paper, Casey develops the basic syntax and semantics of the infinitary logics 𝐿𝜅,𝜇 and proved that the compactness theorem and the upward Löwenheim-Skolem theorems can both fail in the infinitary context.

Kameryn J Williams, Complete sets of connectives for generalized Łukasiewicz logics. Abstract: While , , ¬ form  complete set of connectives for classical propositional logic, this does not hold for Łukasiewicz’s three-valued propositional logic, nor its generalization to 𝑛-valued logic. We define a unary connective 𝔠 so that , , ¬, 𝔠 form a complete set of connectives for 𝑛-valued Lukasiewicz logic. We discuss generalizations of this to infinitary logics. If we allow infinite conjunctions and disjunctions of arbitrary size, this provides a complete set of connectives for real-valued Łukasiewicz logic. Restricting to countable conjunctions and disjunctions, the truth functions expressible with these connectives are precisely the Borel functions.

Jake Zuehl, What group preferences can arise by majority vote?  It is known by the Condorcet paradox that the group preferences determined by majority vote can be non-transitive, even when all individuals have linearly ordered preference relations. But exactly which relations can arise? In this paper, Jake proves that it is all and only the asymmetric irreflexive relations that arise as the majority-vote group preference relation by a group of individuals with linear preferences. He then proceeds to investigate bounds on the minimum number of voters required to realize a given relation.

Ehrenfeucht’s lemma in set theory

[bibtex key=FuchsGitmanHamkins2018:EhrenfeuchtsLemmaInSetTheory]

This is joint work with Gunter Fuchs and Victoria Gitman.

Abstract. Ehrenfeucht’s lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, then they satisfy different types. We consider here the analogue of Ehrenfeucht’s lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and in particular, Ehrenfeucht’s lemma holds fully for models of set theory satisfying 𝑉 =HOD. We show that the lemma can fail, however, in models of set theory with 𝑉 HOD, and it necessarily fails in the forcing extension to add a generic Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht’s lemma, namely, the principles of the form EL(𝐴,𝑃,𝑄), which asserts that whenever an object 𝑏 is definable in 𝑀 from some 𝑎 𝐴 using parameters in 𝑃, with 𝑏 𝑎, then the types of 𝑎 and 𝑏 over 𝑄 in 𝑀 are different. We also consider various analogues of Ehrenfeucht’s lemma obtained by using algebraicity in place of definability, where a set 𝑏 is \emph{algebraic} in 𝑎 if it is a member of a finite set definable from 𝑎 (as in J. D. Hamkins and C. Leahy, Algebraicity and implicit definability in set theory). Ehrenfeucht’s lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using similar analysis, we answer two open questions posed in my paper with Leahy, by showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.

Incomparable 𝜔1-like models of set theory

[bibtex key=FuchsGitmanHamkins2017:IncomparableOmega1-likeModelsOfSetTheory]

This is joint work with Gunter Fuchs and Victoria Gitman.

Abstract. We show that the analogues of the Hamkins embedding theorems, proved for the countable models of set theory, do not hold when extended to the uncountable realm of 𝜔1-like models of set theory. Specifically, under the hypothesis and suitable consistency assumptions, we show that there is a family of 2𝜔1 many 𝜔1-like models of ZFC, all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive 𝜔1-like model of ZFC that does not embed into its own constructible universe; and there can be an 𝜔1-like model of PA whose structure of hereditarily finite sets is not universal for the 𝜔1-like models of set theory.

In this article, we consider the question of whether the embedding theorems of my article, Every countable model of set theory embeds into its own constructible universe, which concern the countable models of set theory, might extend to the realm of uncountable models. Specifically, in that paper I had proved that (1) any two countable models of set theory are comparable by embeddability; indeed, (2) one countable model of set theory embeds into another just in case the ordinals of the first order-embed into the ordinals of the second; consequently, (3) every countable model of set theory embeds into its own constructible universe; and furthermore, (4) every countable model of set theory embeds into the hereditarily finite sets HF,𝑀 of any nonstandard model of arithmetic 𝑀 PA. The question we consider here is, do the analogous results hold for uncountable models? Our answer is that they do not. Indeed, we shall prove that the corresponding statements do not hold even in the special case of 𝜔1-like models of set theory, which otherwise among uncountable models often exhibit a special affinity with the countable models. Specifically, we shall construct large families of pairwise incomparable 𝜔1-like models of set theory, even though they all have the same ordinals; we shall construct 𝜔1-like models of set theory that do not embed into their own 𝐿; and we shall construct 𝜔1-like models of \PA\ that are not universal for all 𝜔1-like models of set theory.

The embedding theorems are expressed collectively in the theorem below. An embedding of one model 𝑀, 𝑀 of set theory into another 𝑁, 𝑁 is simply a function 𝑗 :𝑀 𝑁 for which 𝑥 𝑀𝑦 𝑗(𝑥) 𝑁𝑗(𝑦), for all 𝑥,𝑦 𝑀, and in this case we say that 𝑀, 𝑀 embeds into 𝑁, 𝑁; note by extensionality that every embedding is injective. Thus, an embedding is simply an isomorphism of 𝑀, 𝑀 with its range, which is a submodel of 𝑁, 𝑁. Although this is the usual model-theoretic embedding concept for relational structures, the reader should note that it is a considerably weaker embedding concept than commonly encountered in set theory, because this kind of embedding need not be elementary nor even Δ0-elementary, although clearly every embedding as just defined is elementary at least for quantifier-free assertions. So we caution the reader not to assume a greater degree of elementarity beyond quantifier-free elementarity for the embeddings appearing in this paper.

Theorem.

1. For any two countable models of set theory 𝑀, 𝑀 and 𝑁, 𝑁, one of them embeds into the other.

2. Indeed, such an 𝑀, 𝑀 embeds into 𝑁, 𝑁 if and only if the ordinals of 𝑀 order-embed into the ordinals of 𝑁.

3. Consequently, every countable model 𝑀, 𝑀 of set theory embeds into its own constructible universe 𝐿𝑀, 𝑀.

4. Furthermore, every countable model of set theory embeds into the hereditary finite sets HF,𝑀 of any nonstandard model of arithmetic 𝑀 PA. Indeed, HF𝑀 is universal for all countable acyclic binary relations.

One can begin to get an appreciation for the difference in embedding concepts by observing that ZFC proves that there is a nontrivial embedding 𝑗 :𝑉 𝑉, namely, the embedding recursively defined as follows 𝑗(𝑦)={ 𝑗(𝑥)  𝑥𝑦 }{{,𝑦}}.

We leave it as a fun exercise to verify that 𝑥 𝑦 𝑗(𝑥) 𝑗(𝑦) for the embedding 𝑗 defined by this recursion. (See my paper Every countable model of set theory embeds into its own constructible universe; but to give a hint here for the impatient, note that every 𝑗(𝑦) is nonempty and also 𝑗(𝑦); it follows that inside 𝑗(𝑦) we may identify the pair {,𝑦} 𝑗(𝑦); it follows that 𝑗 is injective and furthermore, the only way to have 𝑗(𝑥) 𝑗(𝑦) is from 𝑥 𝑦.} Contrast this situation with the well-known Kunen inconsistency, which asserts that there can be no nontrivial Σ1-elementary embedding 𝑗 :𝑉 𝑉. Similarly, the same recursive definition applied in 𝐿 leads to nontrivial embeddings 𝑗 :𝐿 𝐿, regardless of whether 0 exists. But again, the point is that embeddings are not necessarily even Δ0-elementary, and the familiar equivalence of the existence of 0 with a nontrivial “embedding” 𝑗 :𝐿 𝐿 actually requires a Δ0-elementary embedding.)

We find it interesting to note in contrast to the theorem above that there is no such embedding phenomenon in the the context of the countable models of Peano arithmetic (where an embedding of models of arithmetic is a function preserving all atomic formulas in the language of arithmetic). Perhaps the main reason for this is that embeddings between models of PA are automatically Δ0-elementary, as a consequence of the MRDP theorem, whereas this is not true for models of set theory, as the example above of the recursively defined embedding 𝑗 :𝑉 𝑉 shows, since this is an embedding, but it is not Δ0-elementary, in light of 𝑗() . For countable models of arithmetic 𝑀,𝑁 PA, one can show that there is an embedding 𝑗 :𝑀 𝑁 if and only if 𝑁 satisfies the Σ1-theory of 𝑀 and the standard system of 𝑀 is contained in the standard system of 𝑁. It follows that there are many instances of incomparability. Meanwhile, it is a consequence of statement (4) that the embedding phenomenon recurs with the countable models of finite set theory ZFC¬, that is, with HF,𝑀 for 𝑀 PA, since all nonstandard such models are universal for all countable acyclic binary relations, and so in the context of countable models of ZFC¬ there are precisely two bi-embeddability classes, namely, the standard model, which is initial, and the nonstandard countable models, which are universal.

Our main theorems are as follows.

Theorem.

1. If holds and ZFC is consistent, then there is a family C of 2𝜔1 many pairwise incomparable 𝜔1-like models of ZFC, meaning that there is no embedding between any two distinct models in C.

2. The models in statement (1) can be constructed so that their ordinals order-embed into each other and indeed, so that the ordinals of each model is a universal 𝜔1-like linear order. If ZFC has an 𝜔-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.

3. If holds and ZFC is consistent, then there is an 𝜔1-like model 𝑀 ZFC and an 𝜔1-like model 𝑁 PA such that 𝑀 does not embed into HF,𝑁.

4. If there is a Mahlo cardinal, then in a forcing extension of 𝐿, there is a transitive 𝜔1-like model 𝑀 ZFC that does not embed into its own constructible universe 𝐿𝑀.

Note that the size of the family C in statement (1) is as large as it could possibly be, given that any two elements in a pairwise incomparable family of structures must be non-isomorphic and there are at most 2𝜔1 many isomorphism types of 𝜔1-like models of set theory or indeed of structures of size 𝜔1 in any first-order finite language. Statement (2) shows that the models of the family C serve as 𝜔1-like counterexamples to the assertion that one model of set theory embeds into another whenever the ordinals of the first order-embed into the ordinals of the second.

The global choice principle in Gödel-Bernays set theory

I’d like to follow up on several posts I made recently on MathOverflow (see here, here and here), which engaged several questions of Gérard Lang that I found interesting. Specifically, I’d like to discuss a number of equivalent formulations of the global choice principle in Gödel-Bernays set theory. Let us adopt the following abbreviations for the usually considered theories:

  • GB is the usual Gödel-Bernays set theory without any choice principle.
  • GB+AC is GB plus the axiom of choice for sets.
  • GBC is GB plus the global choice principle.

The global choice principle has a number of equivalent characterizations, as proved in the theorem below, but for definiteness let us take it as the assertion that there is a global choice function, that is, a class 𝐹 which is a function such that 𝐹(𝑥) 𝑥 for every nonempty set 𝑥.

Note in particular that I do not use the set version of choice AC in the equivalences, since most of the statements imply AC for sets outright (except in the case of statement 7, where it is stated specifically in order to make the equivalence).

Theorem. The following are equivalent over GB.

  1. The global choice principle. That is, there is a class function 𝐹 such that 𝐹(𝑥) 𝑥 for every nonempty set 𝑥.
  2. There is a bijection between 𝑉 and Ord.
  3. There is a global well-ordering of 𝑉. That is, there is a class relation on 𝑉 that is a linear order, such that every nonempty set has a -least member.
  4. There is a global set-like well-ordering of 𝑉. There is a class well-ordering as above, such that all -initial segments are sets.
  5. Every proper class is bijective with Ord.
  6. Every class injects into Ord.
  7. AC holds for sets and Ord injects into every proper class.
  8. Ord surjects onto every class.
  9. Every class is comparable with Ord by injectivity; that is, one injects into the other.
  10. Any two classes are comparable by injectivity.

Proof. 

(1 2) Assume that 𝐹 is a global choice class function. Using the axiom of replacement, we may recursively define a class sequence of sets 𝑥𝛼 𝛼 Ord, where 𝑥𝛼 =𝐹(𝑋𝛼), where 𝑋𝛼 is the set of minimal-rank sets 𝑥 not among {𝑥𝛽 𝛽 <𝛼}. That is, we use 𝐹 to choose the next element among the minimal-rank sets not yet chosen. Thus, we have an injection of 𝑉 into Ord. If a set 𝑥 does not appear as some 𝑥𝛼 on this sequence, then no set of that rank or higher can appear, since we always add sets of the minimal rank not yet having appeared; thus, in this case we will have injected Ord into some 𝑉𝛽. But this is impossible by Hartog’s theorem, and so in fact we have bijection between Ord and 𝑉.

(2 3) If there is a bijection between Ord and 𝑉, then we may define a global well-ordering by 𝑥 <𝑦 if 𝑥 appears before 𝑦 in that enumeration.

(3 1) Let 𝐹(𝑥) be the least element of 𝑥 with respect to a fixed global well-ordering.

(3 4) If there is a global well-ordering <, then we may refine it to a set-like well-ordering, by defining 𝑥 𝑦 just in case the rank of 𝑥 is less than the rank of 𝑦, or they have the same rank and 𝑥 <𝑦. This relation is still a well-order, since the least member of any nonempty set 𝑋 will be the -least member of the set of members of 𝑋 having minimal rank. The relation is set-like, because the -predecessors of any set 𝑥 are amongst the sets having rank no larger than 𝑥, and this is a set.

(4 5) If there is a global set-like well-ordering < of 𝑉 and 𝑋 is a proper class, then < on 𝑋 is a well-ordering of 𝑋, and we may map any ordinal 𝛼 to the 𝛼𝑡 member of 𝑋. This will be a bijection of Ord with 𝑋.

(5 6) If every proper class is bijective with Ord, then 𝑉 is bijective with Ord, and so every set injects into Ord by restriction.

(6 7) If every class injects into Ord, then in particular, 𝑉 injects into Ord. The image of this injection is a proper class subclass of Ord, and all such classes are bijective with Ord by mapping 𝛼 to the 𝛼𝑡 member of the class, and so every proper class is bijective with Ord. So Ord injects the other way, and also AC holds.

(7 3) Suppose that AC holds and Ord injects into every proper class. Let 𝑊 be the class of all well-orderings of some rank-initial segment 𝑉𝛼 of the set-theoretic universe 𝑉. Since for each 𝛼 there are only a set number of such well-orderings of 𝑉𝛼, if we inject Ord into 𝑊, then there must be well-orderings of unboundedly many 𝑉𝛼 in the range of the injection. From this, we may easily construct a global well-ordering of 𝑉, by defining 𝑥 <𝑦 just in case 𝑥 has lower rank than 𝑦, or they have the same rank and 𝑥 <𝑦 in the first well-ordering of a sufficiently large 𝑉𝛼 to appear in the range of the injection.

(5 8) Immediate.

(8 3) If Ord surjects onto 𝑉, then there is a global well-ordering, defined by 𝑥 <𝑦 if the earliest appearance of 𝑥 in the surjection is earlier than that of 𝑦.

(6 9) Immediate.

(9 3) Assume every class is comparable with Ord via injectivity. It follows that AC holds for sets, since Ord cannot inject into a set, and if a set injects into Ord then it is well-orderable. Now, if Ord injects into the class 𝑊 used above, consisting of all well-orderings of a 𝑉𝛼, then we saw before that we can build a well-ordering of 𝑉. And if 𝑊 injects into Ord, then 𝑊 is well-orderable and we can also in this case build a well-ordering of 𝑉.

(5 10) If 𝑉 is bijective with Ord, then every class is bijective with Ord or with an ordinal, and these are comparable by injections. So any two classes are comparable by injections.

(10 9) Immediate.

QED

Let’s notice a few things.

First, we cannot omit the AC assertion in statement 7. To see this, consider the model 𝑉 =𝐿(), in a case where it does not satisfy AC. I claim that in this model, Ord injects into every proper class that is definable from parameters. The reason is that every object in 𝐿() is definable from ordinal and real parameters, and indeed, definable in some 𝑉𝐿()𝛼 by some real and ordinal parameters. Indeed, one needs only one ordinal and real parameter. If 𝑊 is any proper class, then there
must be a proper subclass 𝑊0 𝑊 whose elements are all defined by the same definition in this way. And by partitioning further, we may find a single real that works with various ordinal parameters using that definition to define a proper class of
elements of 𝑊. Thus, we may inject Ord into 𝑊, even though AC fails in 𝐿().

Second, the surjectivity analogues of a few of the statements are not equivalent to global choice. Indeed, ZF proves that every proper class surjects onto Ord, with no choice at all, since if 𝑊 is a proper class, then there are unboundedly many ordinals
arising as the rank of an element of 𝑊, and so we may map each element 𝑥 𝑊 to 𝛼, if the rank of 𝑥 is the 𝛼𝑡 ordinal that is the rank of any element of 𝑊.

An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014


This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Value omega cubedAbstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted 𝜔𝔥1, is not currently known.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

Upward closure in the toy multiverse of all countable models of set theory

The Multiverse by KaeltykThe toy multiverse of all countable models of set theory is upward closed under countably many successive forcing extensions of bounded size…

I’d like to explain a topic from my recent paper

G. Fuchs, J. D. Hamkins, J. ReitzSet-theoretic geology, to appear in the Annals of Pure and Applied Logic.

We just recently made the final revisions, and the paper is available if you follow the title link through to the arxiv. Most of the geology article proceeds from a downward-oriented focus on forcing, looking from a universe 𝑉 down to its grounds, the inner models 𝑊 over which 𝑉 might have arisen by forcing 𝑉 =𝑊[𝐺]. Thus, the set-theoretic geology project arrives at deeper and deeper grounds and the mantle and inner mantle concepts.

One section of the paper, however, has an upward-oriented focus, namely, §2 A brief upward glance, and it is that material about which I’d like to write here, because I find it to be both interesting and comparatively accessible, but also because the topic proceeds from a different perspective than the rest of the geology paper, and so I am a little fearful that it may get lost there.

First is the observation that I first heard from W. Hugh Woodin in the early 1990s.

Observation. If 𝑊 is a countable model of ZFC set theory, then there are forcing extensions 𝑊[𝑐] and 𝑊[𝑑], both obtained by adding a Cohen real, which are non-amalgamable in the sense that there can be no model of ZFC with the same ordinals as 𝑊 containing both 𝑊[𝑐] and 𝑊[𝑑]. Thus, the family of forcing extensions of 𝑊 is not upward directed.

Proof. Since 𝑊 is countable, let 𝑧 be a real coding the entirety of 𝑊. Enumerate the dense subsets 𝐷𝑛 𝑛 <𝜔 of the Cohen forcing Add(𝜔,1) in 𝑊. We construct 𝑐 and 𝑑 in stages. We begin by letting 𝑐0 be any element of 𝐷0. Let 𝑑0 consist of exactly as many 0s as |𝑐0|, followed by a 1, followed by 𝑧(0), and then extended to an element of 𝐷0. Continuing, 𝑐𝑛+1 extends 𝑐𝑛 by adding 0s until the length of 𝑑𝑛, and then a 1, and then extending into 𝐷𝑛+1; and 𝑑𝑛+1 extends 𝑑𝑛 by adding 0s to the length of 𝑐𝑛+1, then a 1, then 𝑧(𝑛), then extending into 𝐷𝑛+1. Let 𝑐 =𝑐𝑛 and 𝑑 =𝑑𝑛. Since we met all the dense sets in 𝑊, we know that 𝑐 and 𝑑 are 𝑊-generic Cohen reals, and so we may form the forcing extensions 𝑊[𝑐] and 𝑊[𝑑]. But if 𝑊 𝑈 ZFC and both 𝑐 and 𝑑 are in 𝑈, then in 𝑈 we may reconstruct the map 𝑛 𝑐𝑛,𝑑𝑛, by giving attention to the blocks of 0s in 𝑐 and 𝑑. From this map, we may reconstruct 𝑧 in 𝑈, which reveals all the ordinals of 𝑊 to be countable, a contradiction if 𝑈 and 𝑊 have the same ordinals. QED

Most of the results here concern forcing extensions of an arbitrary countable model of set theory, which of course includes the case of ill-founded models. Although there is no problem with forcing extensions of ill-founded models, when properly carried out, the reader may prefer to focus on the case of countable transitive models for the results in this section, and such a perspective will lose very little of the point of our observations.

The method of the observation above is easily generalized to produce three 𝑊-generic Cohen reals 𝑐0, 𝑐1 and 𝑐2, such that any two of them can be amalgamated, but the three of them cannot. More generally:

Observation. If 𝑊 is a countable model of ZFC set theory, then for any finite 𝑛 there are 𝑊-generic Cohen reals 𝑐0,𝑐1,,𝑐𝑛1, such that any proper subset of them are mutually 𝑊-generic, so that one may form the generic extension 𝑊[𝑐], provided that 𝑐 omits at least one 𝑐𝑖, but there is no forcing extension 𝑊[𝐺] simultaneously extending all 𝑊[𝑐𝑖] for 𝑖 <𝑛. In particular, the sequence 𝑐0,𝑐1,,𝑐𝑛1 cannot be added by forcing over 𝑊.

Let us turn now to infinite linearly ordered sequences of forcing extensions. We show first in the next theorem and subsequent observation that one mustn’t ask for too much; but nevertheless, after that we shall prove the surprising positive result, that any increasing sequence of forcing extensions over a countable model 𝑊, with forcing of uniformly bounded size, is bounded above by a single forcing extension 𝑊[𝐺].

Theorem. If 𝑊 is a countable model of ZFC, then there is an increasing sequence of set-forcing extensions of 𝑊 having no upper bound in the generic multiverse of 𝑊. 𝑊[𝐺0]𝑊[𝐺1]𝑊[𝐺𝑛]

Proof. Since 𝑊 is countable, there is an increasing sequence 𝛾𝑛 𝑛 <𝜔 of ordinals that is cofinal in the ordinals of 𝑊. Let 𝐺𝑛 be 𝑊-generic for the collapse forcing Coll(𝜔,𝛾𝑛), as defined in 𝑊. (By absorbing the smaller forcing, we may arrange that 𝑊[𝐺𝑛] contains 𝐺𝑚 for 𝑚 <𝑛.) Since every ordinal of 𝑊 is eventually collapsed, there can be no set-forcing extension of 𝑊, and indeed, no model with the same ordinals as 𝑊, that contains every 𝑊[𝐺𝑛]. QED

But that was cheating, of course, since the sequence of forcing notions is not even definable in 𝑊, as the class {𝛾𝑛 𝑛 <𝜔} is not a class of 𝑊. A more intriguing question would be whether this phenomenon can occur with forcing notions that constitute a set in 𝑊, or (equivalently, actually) whether it can occur using always the same poset in 𝑊. For example, if 𝑊[𝑐0] 𝑊[𝑐0][𝑐1] 𝑊[𝑐0][𝑐1][𝑐2] is an increasing sequence of generic extensions of 𝑊 by adding Cohen reals, then does it follow that there is a set-forcing extension 𝑊[𝐺] of 𝑊 with 𝑊[𝑐0][𝑐𝑛] 𝑊[𝐺] for every 𝑛? For this, we begin by showing that one mustn’t ask for too much:

Observation. If 𝑊 is a countable model of ZFC, then there is a sequence of forcing extensions 𝑊 𝑊[𝑐0] 𝑊[𝑐0][𝑐1] 𝑊[𝑐0][𝑐1][𝑐2] , adding a Cohen real at each step, such that there is no forcing extension of 𝑊 containing the sequence 𝑐𝑛 𝑛 <𝜔.

Proof. Let 𝑑𝑛 𝑛 <𝜔 be any 𝑊-generic sequence for the forcing to add 𝜔 many Cohen reals over 𝑊. Let 𝑧 be any real coding the ordinals of 𝑊. Let us view these reals as infinite binary sequences. Define the real 𝑐𝑛 to agree with 𝑑𝑛 on all digits except the initial digit, and set 𝑐𝑛(0) =𝑧(𝑛). That is, we make a single-bit change to each 𝑑𝑛, so as to code one additional bit of 𝑧. Since we have made only finitely many changes to each 𝑑𝑛, it follows that 𝑐𝑛 is an 𝑊-generic Cohen real, and also 𝑊[𝑐0][𝑐𝑛] =𝑊[𝑑0][𝑑𝑛]. Thus, we have 𝑊𝑊[𝑐0]𝑊[𝑐0][𝑐1]𝑊[𝑐0][𝑐1][𝑐2], adding a generic Cohen real at each step. But there can be no forcing extension of 𝑊 containing 𝑐𝑛 𝑛 <𝜔, since any such extension would have the real 𝑧, revealing all the ordinals of 𝑊 to be countable. QED

We can modify the construction to allow 𝑧 to be 𝑊-generic, but collapsing some cardinals of 𝑊. For example, for any cardinal 𝛿 of 𝑊, we could let 𝑧 be 𝑊-generic for the collapse of 𝛿. Then, if we construct the sequence 𝑐𝑛 𝑛 <𝜔 as above, but inside 𝑊[𝑧], we get a sequence of Cohen real extensions 𝑊𝑊[𝑐0]𝑊[𝑐0][𝑐1]𝑊[𝑐0][𝑐1][𝑐2] such that 𝑊[𝑐𝑛 𝑛 <𝜔] =𝑊[𝑧], which collapses 𝛿.

But of course, the question of whether the models 𝑊[𝑐0][𝑐1][𝑐𝑛] have an upper bound is not the same question as whether one can add the sequence 𝑐𝑛 𝑛 <𝜔, since an upper bound may not have this sequence. And in fact, this is exactly what occurs, and we have a surprising positive result:

Theorem. Suppose that 𝑊 is a countable model of \ZFC, and 𝑊[𝐺0]𝑊[𝐺1]𝑊[𝐺𝑛] is an increasing sequence of forcing extensions of 𝑊, with 𝐺𝑛 𝑛 𝑊 being 𝑊-generic. If the cardinalities of the 𝑛’s in 𝑊 are bounded in 𝑊, then there is a set-forcing extension 𝑊[𝐺] with 𝑊[𝐺𝑛] 𝑊[𝐺] for all 𝑛 <𝜔.

Proof. Let us first make the argument in the special case that we have 𝑊𝑊[𝑔0]𝑊[𝑔0][𝑔1]𝑊[𝑔0][𝑔1][𝑔𝑛], where each 𝑔𝑛 is generic over the prior model for forcing 𝑛 𝑊. That is, each extension 𝑊[𝑔0][𝑔1][𝑔𝑛] is obtained by product forcing 0 × ×𝑛 over 𝑊, and the 𝑔𝑛 are mutually 𝑊-generic. Let 𝛿 be a regular cardinal with each 𝑛 having size at most 𝛿, built with underlying set a subset of 𝛿. In 𝑊, let 𝜃 =2𝛿, let 𝛼 𝛼 <𝜃 enumerate all posets of size at most 𝛿, with unbounded repetition, and let =𝛼<𝜃𝛼 be the finite-support product of these posets. Since each factor is 𝛿+-c.c., it follows that the product is 𝛿+-c.c. Since 𝑊 is countable, we may build a filter 𝐻 that is 𝑊-generic. In fact, we may find such a filter 𝐻 that meets every dense set in 𝑛<𝜔𝑊[𝑔0][𝑔1][𝑔𝑛], since this union is also countable. In particular, 𝐻 and 𝑔0 × ×𝑔𝑛 are mutually 𝑊-generic for every 𝑛 <𝜔. The filter 𝐻 is determined by the filters 𝐻𝛼 𝛼 that it adds at each coordinate.

Next comes the key step. Externally to 𝑊, we may find an increasing sequence 𝜃𝑛 𝑛 <𝜔 of ordinals cofinal in 𝜃, such that 𝜃𝑛 =𝑛. This is possible because the posets are repeated unboundedly, and 𝜃 is countable in 𝑉. Let us modify the filter 𝐻 by surgery to produce a new filter 𝐻, by changing 𝐻 at the coordinates 𝜃𝑛 to use 𝑔𝑛 rather than 𝐻𝜃𝑛. That is, let 𝐻𝜃𝑛 =𝑔𝑛 and otherwise 𝐻𝛼 =𝐻𝛼, for 𝛼 {𝜃𝑛 𝑛 <𝜔}. It is clear that 𝐻 is still a filter on . We claim that 𝐻 is 𝑊-generic. To see this, suppose that 𝐴 is any maximal antichain in 𝑊. By the 𝛿+-chain condition and the fact that cof(𝜃)𝑊 >𝛿, it follows that the conditions in 𝐴 have support bounded by some 𝛾 <𝜃. Since the 𝜃𝑛 are increasing and cofinal in 𝜃, only finitely many of them lay below 𝛾, and we may suppose that there is some largest 𝜃𝑚 below 𝛾. Let 𝐻 be the filter derived from 𝐻 by performing the surgical modifications only on the coordinates 𝜃0,,𝜃𝑚. Thus, 𝐻 and 𝐻 agree on all coordinates below 𝛾. By construction, we had ensured that 𝐻 and 𝑔0 × ×𝑔𝑚 are mutually generic over 𝑊 for the forcing ×0 × ×𝑚. This poset has an automorphism swapping the latter copies of 𝑖 with their copy at 𝜃𝑖 in , and this automorphism takes the 𝑊-generic filter 𝐻 ×𝑔0 × ×𝑔𝑚 exactly to 𝐻 ×𝐻𝜃0 × ×𝐻𝜃𝑚. In particular, 𝐻 is 𝑊-generic for , and so 𝐻 meets the maximal antichain 𝐴. Since 𝐻 and 𝐻 agree at coordinates below 𝛾, it follows that 𝐻 also meets 𝐴. In summary, we have proved that 𝐻 is 𝑊-generic for , and so 𝑊[𝐻] is a set-forcing extension of 𝑊. By design, each 𝑔𝑛 appears at coordinate 𝜃𝑛 in 𝐻, and so 𝑊[𝑔0][𝑔𝑛] 𝑊[𝐻] for every 𝑛 <𝜔, as desired.

Finally, we reduce the general case to this special case. Suppose that 𝑊[𝐺0] 𝑊[𝐺1] 𝑊[𝐺𝑛] is an increasing sequence of forcing extensions of 𝑊, with 𝐺𝑛 𝑛 𝑊 being 𝑊-generic and each 𝑛 of size at most 𝜅 in 𝑊. By the standard facts surrounding finite iterated forcing, we may view each model as a forcing extension of the previous model 𝑊[𝐺𝑛+1]=𝑊[𝐺𝑛][𝐻𝑛], where 𝐻𝑛 is 𝑊[𝐺𝑛]-generic for the corresponding quotient forcing 𝑛/𝐺𝑛 in 𝑊[𝐺𝑛]. Let 𝑔 Coll(𝜔,𝜅) be 𝑛𝑊[𝐺𝑛]-generic for the collapse of 𝜅, so that it is mutually generic with every 𝐺𝑛. Thus, we have the increasing sequence of extensions 𝑊[𝑔][𝐺0] 𝑊[𝑔][𝐺1] , where we have added 𝑔 to each model. Since each 𝑛 is countable in 𝑊[𝑔], it is forcing equivalent there to the forcing to add a Cohen real. Furthermore, the quotient forcing 𝑛/𝐺𝑛 is also forcing equivalent in 𝑊[𝑔][𝐺𝑛] to adding a Cohen real. Thus, 𝑊[𝑔][𝐺𝑛+1] =𝑊[𝑔][𝐺𝑛][𝐻𝑛] =𝑊[𝑔][𝐺𝑛][𝑛], for some 𝑊[𝑔][𝐺𝑛]-generic Cohen real 𝑛. Unwrapping this recursion, we have 𝑊[𝑔][𝐺𝑛+1] =𝑊[𝑔][𝐺0][1][𝑛], and consequently 𝑊[𝑔]𝑊[𝑔][𝐺0]𝑊[𝑔][𝐺0][1]𝑊[𝑔][𝐺0][1][2], which places us into the first case of the proof, since this is now product forcing rather than iterated forcing. QED

Definition. A collection {𝑊[𝐺𝑛] 𝑛 <𝜔} of forcing extensions of 𝑊 is finitely amalgamable over 𝑊 if for every 𝑛 <𝜔 there is a forcing extension 𝑊[𝐻] with 𝑊[𝐺𝑚] 𝑊[𝐻] for all 𝑚 𝑛. It is amalgamable over 𝑊 if there is 𝑊[𝐻] such that 𝑊[𝐺𝑛] 𝑊[𝐻] for all 𝑛 <𝜔.

The next corollary shows that we cannot improve the non-amalgamability result of the initial observation to the case of infinitely many Cohen reals, with all finite subsets amalgamable.

Corollary. If 𝑊 is a countable model of ZFC and {𝑊[𝐺𝑛] 𝑛 <𝜔} is a finitely amalgamable collection of forcing extensions of 𝑊, using forcing of bounded size in 𝑊, then this collection is fully amalgamable. That is, there is a forcing extension 𝑊[𝐻] with 𝑊[𝐺𝑛] 𝑊[𝐻] for all 𝑛 <𝜔.

Proof. Since the collection is finitely amalgamable, for each 𝑛 <𝜔 there is some 𝑊-generic 𝐾 such that 𝑊[𝐺𝑚] 𝑊[𝐾] for all 𝑚 𝑛. Thus, we may form the minimal model 𝑊[𝐺0][𝐺1][𝐺𝑛] between 𝑊 and 𝑊[𝐾], and thus 𝑊[𝐺0][𝐺1][𝐺𝑛] is a forcing extension of 𝑊. We are thus in the situation of the theorem, with an increasing chain of forcing extensions. 𝑊𝑊[𝐺0]𝑊[𝐺0][𝐺1]𝑊[𝐺0][𝐺1][𝐺𝑛] Therefore, by the theorem, there is a model 𝑊[𝐻] containing all these extensions, and in particular, 𝑊[𝐺𝑛] 𝑊[𝐻], as desired. QED

Please go to the paper for more details and discussion.

Transfinite recursion as a fundamental principle in set theory


InfinityAt the Midwest PhilMath Workshop this past weekend, I heard Benjamin Rin (UC Irvine) speak on transfinite recursion, with an interesting new perspective.  His idea was to consider transfinite recursion as a basic principle in set theory, along with its close relatives, and see how they relate to the other axioms of set theory, such as the replacement axiom. In particular, he had the idea of using our intuitions about the legitimacy of transfinite computational processes as providing a philosophical foundation for the replacement axiom.

This post is based on what I learned about Rin’s work from his talk at the workshop and in our subsequent conversations there about it.  Meanwhile, his paper is now available online:

Benjamin Rin, Transfinite recursion and the iterative conception of set, Synthese, October, 2014, p. 1-26. (preprint).

Since I have a little different perspective on the proposal than Rin did, I thought I would like to explain here how I look upon it.  Everything I say here is inspired by Rin’s work.

To begin, I propose that we consider the following axiom, asserting that we may undertake a transfinite recursive procedure along any given well-ordering.

The Principle of Transfinite Recursion. If 𝐴 is any set with well-ordering < and 𝐹 :𝑉 𝑉 is any class function, then there is a function 𝑠 :𝐴 𝑉 such that 𝑠(𝑏) =𝐹(𝑠 𝑏) for all 𝑏 𝐴, where 𝑠 𝑏 denotes the function 𝑠(𝑎) 𝑎 <𝑏.

We may understand this principle as an infinite scheme of statements in the first-order language of set theory, where we make separate assertions for each possible first-order formula defining the class function 𝐹, allowing parameters. It seems natural to consider the principle in the background theory of first-order Zermelo set theory Z, or the Zermelo theory ZC, which includes the axiom of choice, and in each case let me also include the axiom of foundation, which apparently is not usually included in Z.   (Alternatively, it is also natural to consider the principle as a single second-order statement, if one wants to work in second-order set theory.)

Theorem. (ZC) The principle of transfinite recursion is equivalent to the axiom of replacement. In other words,

ZC + transfinite recursion  =  ZFC.

Proof. Work in the Zermelo set theory ZC. The converse implication amounts to the well-known observation in ZF that transfinite recursion is legitimate. Let us quickly sketch the argument. Suppose we are given an instance of transfinite recursion, namely, a well-ordering 𝐴, < and a class function 𝐹 :𝑉 𝑉. I claim that for every 𝑏 𝐴, there is a unique function 𝑠 :{𝑎 𝐴 𝑎 𝑏} 𝑉 obeying the recursive rule 𝑠(𝑑) =𝐹(𝑠 𝑑) for all 𝑑 𝑏. The reason is that there can be no least 𝑏 without such a unique function. If all 𝑎 <𝑏 have such a unique function, then by uniqueness they must cohere with one another, since any difference would show up at a least stage and thereby violate the recursion rule, and so by the replacement axiom of ZFC we may assemble these smaller functions into a single function 𝑡 defined on all 𝑎 <𝑏, and satisfying the recursion rule for those values. We may then extend this function 𝑡 to be defined on 𝑏 itself, simply by defining 𝑢(𝑏) =𝐹(𝑡) and 𝑢 𝑏 =𝑡, which thereby satisfies the recursion at 𝑏. Uniqueness again follows from the fact that there can be no least place of disagreement. Finally, using replacement again, let 𝑠(𝑏) be the unique value that arises at 𝑏 during the recursions that work up to and including 𝑏, and this function 𝑠 :𝐴 𝑉 satisfies the recursive definition.

Conversely, assume the Zermelo theory ZC plus the principle of transfinite recursion, and suppose that we are faced with an instance of the replacement axiom. That is, we have a set 𝐴 and a formula 𝜑, where every 𝑏 𝐴 has a unique 𝑦 such that 𝜑(𝑏,𝑦). By the axiom of choice, there is a well-ordering < of the set 𝐴. We shall now define the function 𝐹 :𝑉 𝑉. Given a function 𝑠, where dom(𝑠) ={𝑎 𝐴 𝑎 <𝑏} for some 𝑏 𝐴, let 𝐹(𝑠) =𝑦 be the unique 𝑦 such that 𝜑(𝑏,𝑦); and otherwise let 𝐹(𝑠) be anything you like. By the principle of transfinite recursion, there is a function 𝑠 :𝐴 𝑉 such that 𝑠(𝑏) =𝐹(𝑠 𝑏) for every 𝑏 𝐴. In this case, it follows that 𝑠(𝑏) is the unique 𝑦 such that 𝜑(𝑎,𝑏). Thus, since 𝑠 is a set, it follows in ZC that ran(𝑠) is a set, and so we’ve got the image of 𝐴 under 𝜑 as a set, which verifies replacement. QED

In particular, it follows that the principle of transfinite recursion implies that every well-ordering is isomorphic to a von Neumann ordinal, a principle Rin refers to as ordinal abstraction. One can see this as a consequence of the previous theorem, since ordinal abstraction holds in ZF by Mostowski’s theorem, which for any well-order 𝐴, < assigns an ordinal to each node 𝑎 𝛼𝑎 according to the recursive rule 𝛼𝑎 ={𝛼𝑏 𝑏 <𝑎}. But one can also argue directly as follows, without using the axiom of choice. Assume Z and the principle of transfinite recursion. Suppose that 𝐴, < is a well-ordering. Define the class function 𝐹 :𝑉 𝑉 so that 𝐹(𝑠) =ran(𝑠), whenever 𝑠 is a function. By the principle of transfinite recursion, there is a function 𝑠 :𝐴 𝑉 such that 𝑠(𝑏) =𝐹(𝑠 𝑏) =ran(𝑠 𝑏). One can now simply prove by induction that 𝑠(𝑏) is an ordinal and 𝑠 is an isomorphism of 𝐴, < with ran(𝑠), which is an ordinal.

Let me remark that the principle of transfinite recursion allows us also to perform proper-class length recursions.

Observation. Assume Zermelo set theory Z plus the principle of transfinite recursion. If 𝐴 is any particular class with < a set-like well-ordering of 𝐴 and 𝐹 :𝑉 𝑉 is any class function, then there is a class function 𝑆 :𝐴 𝑉 such that 𝑆(𝑏) =𝐹(𝑆 𝑏) for every 𝑏 𝐴.

Proof. Since 𝐴, < is set-like, the initial segment 𝐴 𝑑 ={𝑎 𝐴 𝑎 <𝑑}, for any particular 𝑑 𝐴, is a set. It follows that the principle of transfinite recursion shows that there is a function 𝑠𝑑 :(𝐴 𝑑) 𝑉 such that 𝑠𝑑(𝑏) =𝐹(𝑠𝑑 𝑏) for every 𝑏 <𝑑. It is now easy to prove by induction that these 𝑠𝑑 must all cohere with one another, and so we may define the class 𝑆(𝑏) =𝑠𝑑(𝑏) for any 𝑑 above 𝑏 in 𝐴. (We may assume without loss that 𝐴 has no largest element, for otherwise it would be a set.) This provides a class function 𝑆 :𝐴 𝑉 satisfying the recursive definition as desired. QED

Although it appears explicitly as a second-order statement “there is a class function 𝑆…”, we may actually take this observation as a first-order theorem scheme, if we simply strengthen the conclusion to provide the explicit definition of 𝑆 that the proof provides. That is, the proof shows exactly how to define 𝑆, and if we make the observation state that that particular definition works, then what we have is a first-order theorem scheme. So any first-order definition of 𝐴 and 𝐹 from parameters leads uniformly to a first-order definition of 𝑆 using the same parameters.

Thus, using the principle of transfinite recursion, we may also take proper class length transfinite recursions, using any set-like well-ordered class that we happen to have available.

Let us now consider a weakening of the principle of transfinite recursion, where we do not use arbitrary well-orderings, but only the von Neumann ordinals themselves.

Principle of transfinite recursion on ordinals. If 𝐹 :𝑉 𝑉 is any class function, then for any ordinal 𝛾 there is a function 𝑠 :𝛾 𝑉 such that 𝑠(𝛽) =𝐹(𝑠 𝛽) for all 𝛽 <𝛾.

This is a weakening of the principle of transfinite recursion, since every ordinal is well-ordered, but in Zermelo set theory, not every well-ordering is necessarily isomorphic to an ordinal. Nevertheless, in the presence of ordinal abstraction, then this ordinal version of transfinite recursion is clearly equivalent to the full principle of transfinite recursion.

Observation. Work in Z. If every well-ordering is isomorphic to an ordinal, then the principle of transfinite recursion is equivalent to its restriction to ordinals.

Meanwhile, let me observe that in general, one may not recover the full principle of transfinite recursion from the weaker principle, where one uses it only on ordinals.

Theorem. (ZFC) The structure 𝑉𝜔1, satisfies Zermelo set theory ZC with the axiom of choice, but does not satisfy the principle of transfinite recursion. Nevertheless, it does satisfy the principle of transfinite recursion on ordinals.

Proof. It is easy to verify all the Zermelo axioms in 𝑉𝜔1, as well as the axiom of choice, provided choice holds in 𝑉. Notice that there are comparatively few ordinals in 𝑉𝜔1—only the countable ordinals exist there—but 𝑉𝜔1 has much larger well-orderings. For example, one may find a well-ordering of the reals already in 𝑉𝜔+𝑘 for small finite 𝑘, and well-orderings of much larger sets in 𝑉𝜔2+17 and so on as one ascends toward 𝑉𝜔1. So 𝑉𝜔1 does not satisfy the ordinal abstraction principle and so cannot satisfy replacement or the principle of transfinite recursion. But I claim nevertheless that it does satisfy the weaker principle of transfinite recursion on ordinals, because if 𝐹 :𝑉𝜔1 𝑉𝜔1 is any class in this structure, and 𝛾 is any ordinal, then we may define by recursion in 𝑉 the function 𝑠(𝛽) =𝐹(𝑠 𝛽), which gives a class 𝑠 :𝜔1 𝑉𝜔1 that is amenable in 𝑉𝜔1. In particular, 𝑠 𝛾 𝑉𝜔1 for any 𝛾 <𝜔1, simply because 𝛾 is countable and 𝜔1 is regular. QED

My view is that this example shows that one doesn’t really want to consider the weakened principle of transfinite recursion on ordinals, if one is working in the Zermelo background ZC, simply because there could be comparatively few ordinals, and this imposes an essentially arbitrary limitation on the principle.

Let me point out, however, that there was a reason we had to go to 𝑉𝜔1, rather than considering 𝑉𝜔+𝜔, which is a more-often mentioned model of the Zermelo axioms. It is not difficult to see that 𝑉𝜔+𝜔 does not satisfy the principle of transfinite recursion on the ordinals, because one can define the function 𝑠(𝑛) =𝜔 +𝑛 by recursion, setting 𝑠(0) =𝜔 and 𝑠(𝑛 +1) =𝑠(𝑛) +1, but this function does not exist in 𝑉𝜔+𝜔. This feature can be generalized as follows:

Theorem. Work in the Zermelo set theory Z. The principle of transfinite recursion on ordinals implies that if 𝐴, < is a well-ordered set, and 𝐴 is bijective with some ordinal, then 𝐴, < is order-isomorphic with an ordinal.

In other words, we get ordinal abstraction for well-orderings whose underlying set is bijective with an ordinal.

First, the proof of the first theorem above actually shows the following local version:

Lemma. (Z) If one has the principle of transfinite recursion with respect to a well-ordering 𝐴, <, then 𝐴-replacement holds, meaning that if 𝐹 :𝑉 𝑉 is any class function, then the image 𝐹𝐴 is a set.

Proof of theorem. Suppose that 𝐴, < is a well-ordering, and that 𝐴 is bijective with some ordinal 𝜅, and that 𝐹 :𝑉 𝑉 is a class function. Assume the principle of transfinite recursion for 𝜅. We prove by induction on 𝑑 𝐴 that there is a unique function 𝑠𝑑 with dom(𝑠) ={𝑎 𝐴 𝑎 𝑑} and satisfying the recursive rule 𝑠(𝑏) =𝐹(𝑠 𝑏). If this statement is true for all 𝑑 <𝑑, then because the size of the predecessors of 𝑑 in 𝐴, < is at most 𝜅, we may by the lemma form the set {𝑠𝑑 𝑑 <𝑑}, which is a set by 𝜅-replacement. These functions cohere, and the union of these functions gives a function 𝑡 :(𝐴 𝑑) 𝑉 satisfying the recursion rule for 𝐹. Now extend this function one more step by defining 𝑠(𝑑) =𝐹(𝑡) and 𝑠 𝑑 =𝑡, thereby handling the existence claim at 𝑑. As in the main theorem, all these functions cohere with one another, and by 𝜅-replacement we may form the set {𝑠𝑑 𝑑 𝐴}, whose union is the desired function 𝑠 :𝐴 𝑉 satisfying the recursion rule given by 𝐹, as desired. QED

For example, if you have the principle of transfinite recursion for ordinals, and 𝜔 exists, then every countable well-ordering is isomorphic to an ordinal. This explains why we had to go to 𝜔1 to find a model satisfying transfinite recursion on ordinals. One can understand the previous theorem as showing that although the principle of transfinite recursion on ordinals does not prove ordinal abstraction, it does prove many instances of it: for every ordinal 𝜅, every well-ordering of cardinality at most 𝜅 is isomorphic to an ordinal.

It is natural also to consider the principle of transfinite recursion along a well-founded relation, rather than merely a well-ordered relation.

The principle of well-founded recursion. If 𝐴, is a well-founded relation and 𝐹 :𝑉 𝑉 is any class function, then there is a function 𝑠 :𝐴 𝑉 such that 𝑠(𝑏) =𝐹(𝑠 𝑏) for all 𝑏 𝐴, where 𝑠 𝑏 means the function 𝑠 restricted to the domain of elements 𝑎 𝐴 that are hereditarily below 𝑏 with respect to .

Although this principle may seem more powerful, in fact it is equivalent to transfinite recursion.

Theorem. (ZC) The principle of transfinite recursion is equivalent to the principle of well-founded recursion.

Proof. The backward direction is immediate, since well-orders are well-founded. For the forward implication, assume that transfinite recursion is legitimate. It follows by the main theorem above that ZFC holds. In this case, well-founded recursion is legitimate by the familiar arguments. For example, one may prove in ZFC that for every node in the field of the relation, there is a unique solution of the recursion defined up to and including that node, simply because there can be no minimal node without this property.  Then, by replacement, one may assemble all these functions together into a global solution. Alternatively, arguing directly from transfinite recursion, one may put an ordinal ranking function for any given well-founded relation 𝐴, , and then prove by induction on this rank that one may construct functions defined up to and including any given rank, that accord with the recursive rule. In this way, one gets the full function 𝑠 :𝐴 𝑉 satisfying the recursive rule. QED

Finally, let me conclude this post by pointing out how my perspective on this topic differs from the treatment given by Benjamin Rin. I am grateful to him for his idea, which I find extremely interesting, and as I said, everything here is inspired by his work.

One difference is that Rin mainly considered transfinite recursion only on ordinals, rather than with respect to an arbitrary well-ordered relation (but see footnote 17 in his paper). For this reason, he had a greater need to consider whether or not he had sufficient ordinal abstraction in his applications. My perspective is that transfinite recursion, taken as a basic principle, has nothing fundamentally to do with the von Neumann ordinals, but rather has to do with a general process undertaken along any well-order. And the theory seems to work better when one undertakes it that way.

Another difference is that Rin stated his recursion principle as a principle about iterating through all the ordinals, rather than only up to any given ordinal. This made the resulting functions 𝑆 :Ord 𝑉 into class-sized objects for him, and moved the whole analysis into the realm of second-order set theory. This is why he was led to prove his main equivalence with replacement in second-order Zermelo set theory. My treatment shows that one may undertake the whole theory in first-order set theory, without losing the class-length iterations, since as I explained above the class-length iterations form classes, definable from the original class functions and well-orders. And given that a completely first-order account is possible, it seems preferable to undertake it that way.

Update. (August 17, 2018) I’ve now realized how to eliminate the need for the axiom of choice in the arguments above. Namely, the main argument above shows that the principle of transfinite recursion implies the principle of well-ordered replacement, meaning the axiom of replacement for instances where the domain set is well-orderable.  The point now is that in recent work with Alfredo Roque Freire, I have realized that The principle of well-ordered replacement is equivalent to full replacement over Zermelo set theory with foundation. We may therefore deduce:

Corollary. The principle of transfinite recursion is equivalent to the replacement axiom over Zermelo set theory with foundation.

We do not need the axiom of choice for this.

MathOverflow, the eternal fountain of mathematics: reflections on a hundred kiloreps


profile for Joel David Hamkins at MathOverflow, Q&A for professional mathematiciansIt seems to appear that I have somehow managed to pass  the 100,000 score milestone for reputation on MathOverflow.  A hundred kiloreps!  Does this qualify me for micro-celebrity status?  I have clearly been spending an inordinate amount of time on MO…  Truly, it has been a great time.

MathOverflow, an eternal fountain of mathematics, overflows with fascinating questions and answers on every imaginable mathematical topic, drawing unforeseen connections, seeking generalizations, clarification, or illustrative examples, questioning assumptions, or simply asking for an explanation of a subtle mathematical point.  The mathematics is sophisticated and compelling.  How could a mathematician not immediately plunge in?

I first joined MathOverflow in November 2009, when my colleague-down-the-hall Kevin O’Bryant dropped into my office and showed me the site.  He said that it was for “people like us,” research mathematicians who wanted to discuss mathematical issues with other professionals, and he was completely right.  Looking at the site, I found Greg Kuperberg’s answer to a question on the automorphism tower problem in group theory, which was one of the first extremely popular questions at that time, the top-rated question.  I was hooked immediately, and I told Kevin on that very first day that it was clear that MathOverflow was going to take a lot of time.

I was pleased to find right from the beginning that, although there were not yet many logicians participating on MO, there were nevertheless many logic questions, revealing an unexpectedly broad interest in math logic issues amongst the general mathematical community.  I found questions about definability, computability, undecidability, logical independence, about the continuum hypothesis and the axiom of choice and about large cardinals, asked by mathematicians in diverse research areas, who seemed earnestly to want to know the answer.  How pleased I was to find such a level of interest in the same issues that fascinated me; and how pleased I was also to find that I was often able to answer.

In the early days, I may have felt a little that I should be a kind of ambassador for logic, introducing the subject or aspects of it to those who might not know all about it yet; for example, in a few answers I explained and introduced the topic of cardinal characteristics of the continuum and the subject of Borel equivalence relation theory, since I had felt that mathematicians outside logic might not necessarily know much about it, even when it offered connections to things they did know about.  I probably wouldn’t necessarily answer the same way today, now that MO has many experts in those subjects and a robust logic community.  What a pleasure it has become.

A while back I wrote a post The use and value of MathOverflow in response to an inquiry of François Dorais, and I find the remarks I made then are as true for me today as ever.

I feel that mathoverflow has enlarged me as a mathematician.  I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics.  I’ve read some really great answers that opened up new perspectives for me.  But just as importantly, I’ve learned a lot when coming up with my own answers.  It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through.  How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer.  Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts.  This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk.  This kind of knowledge has helped me to improve my mathematical writing in general.

Thanks very much again, MathOverflow!  I am grateful.

A few posts come to mind:

There have been so many more great questions and posts.  If you are inclined, feel free to post comments below linking to your favorite MO posts!

Concerning the MO reputation system, I suppose some might suspect me of harboring unnatural thoughts on reputation — after all, I once proposed (I can’t find the link now) that the sole basis of tenure and promotion decisions for mathematics faculty, as well as choice of premium office space, should be:  MO reputation, ha! — but in truth, I look upon it all as a good silly game.  One may take reputation as seriously as one takes any game seriously, and many mathematicians can indeed take a game seriously.  My honest opinion is that the reputation and badge system is an ingenious piece of social engineering.  The designers must have had a good grasp on human psychology, an understanding of the kinds of reasons that might motivate a person to participate in such a site; one thinks, for example, of the intermittent reward theory.  I find it really amazing what the stackexchange designers have created, and who doesn’t love a good game?

Announcement on History of MathOverflow

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

When does every definable set have a definable member? CUNY Set Theory Seminar, October 2014

This will be a talk for the CUNY set theory seminar, October 10, 2014, 12pm  GC 6417.

Abstract. Although the concept of `being definable’ is not generally expressible in the language of set theory, it turns out that the models of ZF in which every definable nonempty set has a definable element are precisely the models of V=HOD.  Indeed, V=HOD is equivalent to the assertion merely that every Π2-definable set has an ordinal-definable element. Meanwhile, this is not true in the case of Σ2-definability, because every model of ZFC has a forcing extension satisfying 𝑉 HOD in which every Σ2-definable set has an ordinal-definable element.

This is joint work with François G. Dorais and Emil Jeřábek, growing out of some questions and answers on MathOverflow, namely,

Definable collections without definable members
A question asked by Ashutosh five years ago, in which François and I gradually came upon the answer together.
Is it consistent that every definable set has a definable member?
A similar question asked last week by (anonymous) user38200
Can 𝑉 HOD if every Σ2-definable set has an ordinal-definable member?
A question I had regarding the limits of an issue in my answer to the previous question.

In this talk, I shall present the answers to all these questions and place the results in the context of classical results on definability, including a review of basic concepts for graduate students.

My research collaborators

CollaborationI have been very fortunate in my research to have had the opportunity to work closely with a number of insightful researchers. I’ve learned a great deal from them, and I’m truly grateful.

So I’ve gathered here a list of my collaborators. In almost all cases, the collaboration resulted in a published joint research article, which you can find on my list of publications (in a few instances, for collaborations currently underway, a paper is not necessarily yet available).  Several of my collaborations have been sustained long-term affairs, leading to a series of joint publications on various topics over several years.  Naturally, I am hopeful that all my collaborations will continue to be fruitful for many years into the future.

The rule-making game

They said a king once ruled the forest, by Lizzie ThomasLet me tell you about a new game that we’ve been playing in our family, the rule-making game.  It is a talking game, requiring no pieces or objects of any kind, and it can easily be played whilst walking or traveling.  My children and I recently played several rounds of it walking around London on a recent visit there.

The game has no rules, initially, nor even any definite procedure — it is different every time — but things usually become clear soon enough.  It usually makes a better game to cooperate on the first several turns to lay the groundwork.

Let me explain how to play simply by example:

Papa:  The first rule is that the players shall take turns making rules, and that every rule shall have a rule number, which is incremented on each turn.

Horatio:  The second rule is that the players must state their rules in the form, “The first rule is…” or “the second rule is…” and so on, and that players are not allowed to ask what is the current rule number, or they lose.

Hypatia:  The third rule is that the other players must say, “thank you” after another player makes a rule.

     (… “thank you”…. “thank you”….)

Papa: The fourth rule is that the rules must not contradict each other, and no rule is allowed that abrogates an earlier rule.

     (… “thank you”…. “thank you”….)

Horatio:  The fifth rule is that after making an odd-numbered rule, the player must stomp on the ground.

     (STOMP… “thank you”…. “thank you”….)

Hypatia: The sixth rule is that no player may win immediately after their own rule.

     (… “thank you”…. “thank you”….)

Papa:  The seventh rule is that right after a player stomps according to rule five, the other two players must hop.

     (STOMP … “thank you”…. “thank you”….HOP….HOP…)

Horatio:  The eighth rule is that if a player loses, then the game continues without that person.

     (… “thank you”…. “thank you”….)

Hypatia: The ninth rule is that after stating a rule, the other two players must state a different color.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “blue”… “green”…)

Papa:  The tenth rule is that furthermore, those colors must never repeat, and they must be stated simultaneously, on the count of 1-2-3.

     (… “thank you”…. “thank you”…. “1-2-3: neon green / violet”)

Horatio: The eleventh rule is that if there is only one player left, then that player wins.

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: red/orange”)

Hypatia:  The twelfth rule is that every player must jump up and down (…jump…) while stating their rule. (….jump jump jump…)

     (… “thank you”…. “thank you”…. “1-2-3: pink/turquoise”)

Papa: (jump jump…) The thirteenth rule is that (…jump…) in the case of dispute (…jump…), the question of whether or not someone has violated or followed a rule shall be decided by majority vote (…jump…).

     (STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: yellow/brown”)

Horatio: (jump….) The fourteenth rule is that (…jump…) before stating their rule, the players must state a country, and that whoever repeats a country loses (…jump…)

     (… “thank you”…. “thank you”…. “1-2-3: black/gray”)

Hypatia:  (jump…)  Germany.  The fifteenth rule is that (…jump…) there can be at most twenty-five rules.

(STOMP … “thank you”…. “thank you”….HOP…HOP… “1-2-3: sky blue / peach”)

Papa:  (jump…)  United States.  The sixteenth rule is that (…jump…) if all current players lose at the same time after a rule, then the player previous to that rule-maker is declared the “honorary winner”.  (…jump…)

(… “thank you”…. “thank you”…. “1-2-3: white / white”)

Oh no! Since both Horatio and Hypatia said “white”, they both lose.  And then Papa also loses in light of rule six. So we’ve all lost!  But then, in light of rule sixteen, Hypatia is declared the honorary winner! Hooray for Hypatia!

I hope you all get the idea.  Please enjoy!  And report your crazy or interesting rules in the comments below.

The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

Releasing the hordesI shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The span of infinity, roundtable discussion at The Helix Center, October 2014

I was a panelist at The Span of Infinity, a roundtable discussion held at The Helix Center, at the New York Psychoanalytic Society & Institute, 247 E 82nd Street, on October 25, 2014, 2:30 – 4:30 pm.

The Helix Center describes the discussion topic as:

Perhaps no thing conceived in the mind has enjoyed a greater confluence of cosmological, mathematical, philosophical, psychological, and theological inquiry than the notion of the infinite. The epistemological tension between the concrete and the ideal, between the phenomenological and the ontological, is nowhere clearer in outline yet more obscure in content. These inherent paradoxes limn the vital, eternal questions we will explore about humankind’s place in the universe and the comprehensibility of existence.

The Helix Center Roundtable Series is described by:

Our roundtable format is designated the Theaetetus Table, an extempore discussion among five participants, all leaders in their respective fields, and named for the classical Greek mathematician and eponym for the Platonic dialogue investigating the nature of knowledge, who proved that there are five regular convex polyhedra, or Platonic solids. Each Theaetetus Table aspires to emulate the dialogue’s unhurried search for wisdom; and, like the five Platonic solids held to be the fundamental building blocks of the classical elements, the contributions of our five participants become the fundamental constituents of interdisciplinary insights emerging in the alchemy of the roundtable, insights that, in turn, transform the elemental thinking of those participants. The gathering of five discussants also symbolizes the five interrelated qualities of mind our interdisciplinary forums are intended to facilitate in our participants, and inculcate in our audience: curiosity, playfulness, inspiration, reflection, and wonder.

The video of the actual event is now available:

The pluralist perspective on the axiom of constructibility, MidWest PhilMath Workshop, Notre Dame, October 2014

University of Notre DameThis will be a featured talk at the Midwest PhilMath Workshop 15, held at Notre Dame University October 18-19, 2014.  W. Hugh Woodin and I will each give one-hour talks in a session on Perspectives on the foundations of set theory, followed by a one-hour discussion of our talks.

Abstract. I shall argue that the commonly held 𝑉 𝐿 via maximize position, which rejects the axiom of constructibility V = L on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of V = L inside larger set-theoretic universes.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible. Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory. In this talk, I shall criticize Maddy’s proposal, pointing out that neither the fairly-interpreted-in relation nor the (strongly) maximizes-over relation is transitive, and furthermore, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s account, contrary to what had been desired. Ultimately, I shall argue that the V≠L via maximize position loses its force on a multiverse conception of set theory with an upwardly extensible concept of set, in light of the classical facts that models of set theory can generally be extended to models of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Slides