A mathematician’s year in Japan

  • J. D. Hamkins, A Mathematician’s Year in Japan, author-published, via Amazon Kindle Direct Publishing, 2015. (ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2)  
    @BOOK{Hamkins2015:AMathematiciansYearInJapan,
    author = {Joel David Hamkins},
    title = {A {Mathematician's} {Year} in {Japan}},
    publisher = {author-published, via Amazon Kindle Direct Publishing},
    year = {2015},
    month = {March},
    url = {http://www.amazon.com/dp/B00U618LM2},
    note = {ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2},
    }

Years ago, when I was still a junior professor, I had the pleasure to live for a year in Japan, working as a research fellow at Kobe University. During that formative year, I recorded brief moments of my Japanese experience, and every two weeks or so—this was well before the current blogging era—I sent my descriptive missives by email to friends back home. I have now collected together those vignettes of my life in Japan, each a morsel of my experience. The book is now out!


A Mathematician's Year in Japan, by Joel David Hamkins, available on Amazon Kindle BooksA Mathematician’s Year in Japan
Joel David Hamkins

Glimpse into the life of a professor of logic as he fumbles his way through Japan.

A Mathematician’s Year in Japan is a lighthearted, though at times emotional account of how one mathematician finds himself in a place where everything seems unfamiliar, except his beloved research on the nature of infinity, yet even with that he experiences a crisis.

Available on Amazon $4.49.

Please be so kind as to write a review there.
jo eh ru

Embeddings of the universe into the constructible universe, current state of knowledge, CUNY Set Theory Seminar, March 2015

This will be a talk for the CUNY Set Theory Seminar, March 6, 2015.

I shall describe the current state of knowledge concerning the question of whether there can be an embedding of the set-theoretic universe into the constructible universe.

V to L

Question.(Hamkins) Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ into the constructible universe $L$, when $V\neq L$?

The notion of embedding here is merely that $$x\in y\iff j(x)\in j(y),$$ and such a map need not be elementary nor even $\Delta_0$-elementary. It is not difficult to see that there can generally be no $\Delta_0$-elementary embedding $j:V\to L$, when $V\neq L$.

Nevertheless, the question arises very naturally in the context of my previous work on the embeddability phenomenon, Every countable model of set theory embeds into its own constructible universe, where the title theorem is the following.

Theorem.(Hamkins) Every countable model of set theory $\langle M,\in^M\rangle$, including every countable transitive model of set theory, has an embedding $j:\langle M,\in^M\rangle\to\langle L^M,\in^M\rangle$ into its own constructible universe.

The methods of proof also established that the countable models of set theory are linearly pre-ordered by embeddability: given any two models, one of them embeds into the other; or equivalently, one of them is isomorphic to a submodel of the other. Indeed, one model $\langle M,\in^M\rangle$ embeds into another $\langle N,\in^N\rangle$ just in case the ordinals of the first $\text{Ord}^M$ order-embed into the ordinals of the second $\text{Ord}^N$. (And this implies the theorem above.)

In the proof of that theorem, the embeddings $j:M\to L^M$ are defined completely externally to $M$, and so it was natural to wonder to what extent such an embedding might be accessible inside $M$. And I realized that I could not generally refute the possibility that such a $j$ might even be a class in $M$.

Currently, the question remains open, but we have some partial progress, and have settled it in a number of cases, including the following, on which I’ll speak:

  • If there is an embedding $j:V\to L$, then for a proper class club of cardinals $\lambda$, we have $(2^\lambda)^V=(\lambda^+)^L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$ and indeed no embedding $j:P(\omega)\to L$.
  • If there is an embedding $j:V\to L$, then the GCH holds above $\aleph_0$.
  • In the forcing extension $V[G]$ obtained by adding $\omega_1$ many Cohen reals (or more), there is no embedding $j:V[G]\to L$, and indeed, no $j:P(\omega)^{V[G]}\to V$. More generally, after adding $\kappa^+$ many Cohen subsets to $\kappa$, for any regular cardinal $\kappa$, then in $V[G]$ there is no $j:P(\kappa)\to V$.
  • If $V$ is a nontrivial set-forcing extension of an inner model $M$, then there is no embedding $j:V\to M$. Indeed, there is no embedding $j:P(\kappa^+)\to M$, if the forcing has size $\kappa$. In particular, if $V$ is a nontrivial forcing extension, then there is no embedding $j:V\to L$.
  • Every countable set $A$ has an embedding $j:A\to L$.

This is joint work of myself, W. Hugh Woodin, Menachem Magidor, with contributions also by David Aspero, Ralf Schindler and Yair Hayut.

See my related MathOverflow question: Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?

Talk Abstract

A conference in honor of W. Hugh Woodin’s 60th birthday, March 2015

I am pleased to announce the upcoming conference at Harvard celebrating the 60th birthday of W. Hugh Woodin.  See the conference web site for more information. Click on the image below for a large-format poster.

woodin_conference_poster

Moved to a new server, new WordPress installation

I’ve recently moved my site to a new server and apologize for the brief disruption in service. Many thanks to Sam Coskey and Peter Krautzberger for all the help with the move, and for all their help over the years with getting me started on WordPress at Boolesrings.  They really opened my eyes to the possibilities.

I am currently still fixing various technical issues with the new installation, but please post a comment if you see any issue that needs attention. My intention is that all links to jdh.hamkins.org will still work as before.

– Joel David Hamkins

 

 

A picture of logic, between mathematics and philosophy

A picture of logic between math and philosophyYears ago, when I was a student and young professor in Berkeley, one often heard it said that the subject of logic or at least metamathematics, according to the Tarski school, could be divided into four subjects: model theory, set theory, computability theory (then called recursion theory) and proof theory.

I have long felt that this taxonomy has become increasingly inadequate as a description, and so at the start of my course Logic for Philosophers yesterday, I tried to draw a somewhat fuller picture on the whiteboard.  You can see my diagram above, showing the main parts of logic, occupying regions both within mathematics, within philosophy and within computer science, as well as filling out regions that might be considered between these subjects.

OK, this picture is a first attempt, and I’ll try to improve it.  Please post comments and criticisms below.

It would certainly be possible to flesh out subareas of nearly all the subjects mentioned. We may imagine set theory, for example, broken into descriptive set theory, Borel equivalence relation theory, large cardinals, forcing, cardinal characteristics, and so on; and similarly we may break up the huge subjects of model theory, computability theory and proof theory. In particular, most subjects don’t fit neatly into a small region, since almost all the subjects have parts that touch areas very far away.  Computability theory, for example, touches not only complexity theory and computer science, but also model theory in computable model theory, as well as reverse mathematics, foundations of mathematics, proof theory and so on.  Category theory is a kind of diffuse superposition onto the entire diagram, with comparatively less direct interaction with these other areas.  Proof theory should be closer to reverse mathematics and to model theory, and probably closer to mathematics.

Logic for Philosophers, NYU, Spring 2015, graduate course 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:$\newcommand\iff{\leftrightarrow}$

1. Make truth tables for $$(p\wedge q\wedge r)\vee((p\wedge q)\to r)$$ $$(p\wedge(t\to q))\wedge((q\iff r)\vee p)$$ $$(((p\vee q)\vee r)\vee(r\to(\neg q\to r)))\to r$$

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 $\varphi$ and $\psi$ are tautologies, then so are $\varphi\wedge\psi$, $\varphi\vee\psi$, $\varphi\to\psi$ and $\varphi\iff\psi$.

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

  • If $A\to B$ is a tautology, then $A$ and $B$ are tautologies.
  • If $A\iff B$ is a tautology, then $A$ and $B$ are tautologies.
  • If $A\wedge B$ is a tautology, then $A$ and $B$ are tautologies.
  • If $A\vee B$ is a tautology, then $A$ and $B$ 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 $\varphi$, consider $\neg\varphi$ in light of what we did in class.)

7. Determine which of the following sets of logical connectives are complete: $\{\neg,\to\}$,  $\{\neg,\iff\}$.  (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 $A\star B$ that is complete, then consider what the truth table of $\star$ 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 $\varphi$ is a propositional assertion in the language with $\neg,\wedge,\vee,\to,\leftrightarrow$, and $\varphi(\vec p)=U$. Does there always exist a crispification of $\vec p$ to $\vec p^*$ with $\varphi(\vec p^*)=T$ and another crispification $\vec p^{**}$ with $\varphi(\vec p^{**})=F$? In other words, does the truth value $U$ mean that it could have been $T$ and it could have been $F$, depending on what way the input $U$ 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 $\neg(A\vee B)\equiv\neg A\wedge\neg B$ and $\neg(A\wedge B)\equiv\neg A\vee\neg B$, using $\equiv$ to mean logically equivalent in the sense of having the same truth table.
  4. Verify the distributivity laws $$P\wedge(Q\vee R)= (P\wedge Q)\vee(P\wedge R)$$ $$P\vee (Q\wedge R) = (P\vee Q)\wedge (P\vee R)$$ 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 $P$ is true; if $P$ is false; and if $P$ is $U$.)
  5. Find an expression in $P$, $Q$ and $R$ that has value $U$, if any of them is $U$, and otherwise has value $F$.
  6. Is the truth table of every expression in Lukasiewicz logic determined (as it is in classical logic) by the location of the $T$’s? That is, if you know where the $T$’s are, can you determined whether the others are $F$ or $U$, just from knowing that the expression came from $\wedge,\vee,\neg,\to,\leftrightarrow$?

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 $\neg,\wedge,\vee,\to,\leftrightarrow$ 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 $\geq\frac12$); 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 $\cal L$ of truth values, with logical functions $\neg,\wedge,\vee$ on that space.  Concepts of extensions ${\cal L}_0\subset{\cal L}_1$ and logical homomorphisms $\pi:{\cal L}_1\to {\cal L}_0$. Boolean algebras. Axioms of Boolean algebras. A few examples, including power sets.

Exercises.

  1. Verify in fuzzy logic that $$p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q).$$
  2. Verify that the de Morgan laws continue to hold in fuzzy logic.$$\neg(A\vee B)\equiv (\neg A)\wedge(\neg B)$$$$\neg(A\wedge B)\equiv(\neg A)\vee(\neg B)$$
  3. Verify that the distributivity laws continue to hold in fuzzy logic.$$A\wedge(B\vee C)\equiv (A\wedge B)\vee(A\wedge C)$$$$A\vee(B\wedge C)\equiv(A\vee B)\wedge(A\vee C)$$
  4. Argue that in fuzzy logic, just as in Lukasiewicz logic, there are no tautologies in the language having only the traditional five connectives: $\neg,\wedge,\vee,\to,\iff$.
  5. Consider the translation from fuzzy logic to Lukasiewicz logic, which takes the center interval $(\frac13,\frac23)$ of fuzzy truth values to the truth value U; the numbers in the interval $[0,\frac13]$ to $F$ and numbers in $[\frac23,1]$ to $T$. 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 $p$, $q$ and $r$, then does fuzzy logic tell us the probability of compound expressions like $p\to(q\vee r)$?

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 $E$ is symmetric, then $a\mathrel{E} b$ implies $b\mathrel{E} a$, and so if it is also transitive, it follows that $a\mathrel{E} a$, 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 $\leq$ and vice versa. Pre-orders (quasi-orders). With pre-orders, the interdefinability of $<$ with $\leq$ 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 $n$ elements?
  3. Suppose that $\leq$ is a partial pre-order. Define $a\sim b$ just in case $a\leq b$ and $b\leq a$. Argue that $\sim$ is an equivalence relation on the same domain.
  4. Does the interdefinability of $\leq$ and $<$ succeed with pre-orders? Suppose that $\leq$ is a transitive reflexive relation (that is, a pre-order). Define $a<b$ if $a\leq b$ and $a\neq b$. Will this necessarily be a partial order? If not, what is a better way to define a strict partial order $a<b$ in terms of $\leq$ for a pre-order $\leq$?
  5. Suppose that an author (mistakenly, in my view) defines that we are {\it indifferent} between $a$ and $b$ if neither $a$ nor $b$ is better than the other. That is, $a\approx b\iff a\not<b\wedge b\not< a$. Provide a preference relation for which this is not an equivalence relation. Specifically, we’d want the person to be indifferent between $a$ and $b$, and indifferent between $b$ and $c$, but not indifferent between $a$ and $c$.
  6. True or false: if $\leq$ is a partial ordering on a set, then $a\leq b$ if and only if $b\not <a$.
  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 $\mathbb{A}$ and $\mathbb{B}$ are partial orderings, there is a notion of $\mathbb{A}+\mathbb{B}$, which is the order placing a copy of $\mathbb{B}$ on top of a copy of $\mathbb{A}$; and $\mathbb{A}\times\mathbb{B}$ is the order consisting of $\mathbb{B}$ many copies of $\mathbb{A}$. There are numerous easy but interesting questions to ask about how features are preserved or not by these constructions, such as: if $\mathbb{A}$ and $\mathbb{B}$ are dense orders, then are $\mathbb{A}+\mathbb{B}$ also dense? $\mathbb{A}\times\mathbb{B}$? And what of discrete orders?

Ehrenfeucht's lemma in set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Ehrenfeucht’s lemma in set theory.” (manuscript under review)  
    @ARTICLE{FuchsGitmanHamkins:EhrenfeuchtsLemmaInSetTheory,
    author = {Gunter Fuchs and Victoria Gitman and Joel David Hamkins},
    title = {Ehrenfeucht's lemma in set theory},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    eprint = {1501.01918},
    note = {manuscript under review},
    url = {\url{http://jdh.hamkins.org/ehrenfeuchts-lemma-in-set-theory}},
    abstract = {},
    keywords = {},
    source = {},
    }

This is joint work with Gunter Fuchs and Victoria Gitman. $\newcommand\HOD{\text{HOD}}\newcommand\Ehrenfeucht{\text{EL}}$

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 $V=\HOD$. We show that the lemma can fail, however, in models of set theory with $V\neq\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 $\Ehrenfeucht(A,P,Q)$, which asserts that whenever an object $b$ is definable in $M$ from some $a\in A$ using parameters in $P$, with $b\neq a$, then the types of $a$ and $b$ over $Q$ in $M$ are different. We also consider various analogues of Ehrenfeucht’s lemma obtained by using algebraicity in place of definability, where a set $b$ is \emph{algebraic} in $a$ if it is a member of a finite set definable from $a$ (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 $\omega_1$-like models of set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Incomparable $\omega_1$-like models of set theory.” (manuscript under review)  
    @ARTICLE{FuchsGitmanHamkins:IncomparableOmega1-likeModelsOfSetTheory,
    author = {Gunter Fuchs and Victoria Gitman and Joel David Hamkins},
    title = {Incomparable $\omega_1$-like models of set theory},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    eprint = {1501.01022},
    note = {manuscript under review},
    url = {\url{http://jdh.hamkins.org/incomparable-omega-one-like-models-of-set-theory}},
    abstract = {},
    keywords = {},
    source = {},
    }

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 $\omega_1$-like models of set theory. Specifically, under the $\diamondsuit$ hypothesis and suitable consistency assumptions, we show that there is a family of $2^{\omega_1}$ many $\omega_1$-like models of $\text{ZFC}$, all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive $\omega_1$-like model of ZFC that does not embed into its own constructible universe; and there can be an $\omega_1$-like model of PA whose structure of hereditarily finite sets is not universal for the $\omega_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 $\langle\text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{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 $\omega_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 $\omega_1$-like models of set theory, even though they all have the same ordinals; we shall construct $\omega_1$-like models of set theory that do not embed into their own $L$; and we shall construct $\omega_1$-like models of \PA\ that are not universal for all $\omega_1$-like models of set theory.

The embedding theorems are expressed collectively in the theorem below. An embedding of one model $\langle M,{\in^M}\rangle$ of set theory into another $\langle N,{\in^N}\rangle$ is simply a function $j:M\to N$ for which $x\in^My\longleftrightarrow j(x)\in^Nj(y)$, for all $x,y\in M$, and in this case we say that $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$; note by extensionality that every embedding is injective. Thus, an embedding is simply an isomorphism of $\langle M,{\in^M}\rangle$ with its range, which is a submodel of $\langle N,{\in^N}\rangle$. 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 $\Delta_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 $\langle M,\in^M\rangle$ and $\langle N,\in^N\rangle$, one of them embeds into the other.

2. Indeed, such an $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$ if and only if the ordinals of $M$ order-embed into the ordinals of $N$.

3. Consequently, every countable model $\langle M,\in^M\rangle$ of set theory embeds into its own constructible universe $\langle L^M,\in^M\rangle$.

4. Furthermore, every countable model of set theory embeds into the hereditary finite sets $\langle \text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. Indeed, $\text{HF}^M$ 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 $j:V\to V$, namely, the embedding recursively defined as follows $$j(y)=\bigl\{\ j(x)\ \mid\ x\in y\ \bigr\}\cup\bigl\{\{\emptyset,y\}\bigr\}.$$

We leave it as a fun exercise to verify that $x\in y\longleftrightarrow j(x)\in j(y)$ for the embedding $j$ 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 $j(y)$ is nonempty and also $\emptyset\notin j(y)$; it follows that inside $j(y)$ we may identify the pair $\{\emptyset,y\}\in j(y)$; it follows that $j$ is injective and furthermore, the only way to have $j(x)\in j(y)$ is from $x\in y$.} Contrast this situation with the well-known Kunen inconsistency, which asserts that there can be no nontrivial $\Sigma_1$-elementary embedding $j:V\to V$. Similarly, the same recursive definition applied in $L$ leads to nontrivial embeddings $j:L\to L$, regardless of whether $0^\sharp$ exists. But again, the point is that embeddings are not necessarily even $\Delta_0$-elementary, and the familiar equivalence of the existence of $0^\sharp$ with a nontrivial “embedding” $j:L\to L$ actually requires a $\Delta_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 $\Delta_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 $j:V\to V$ shows, since this is an embedding, but it is not $\Delta_0$-elementary, in light of $j(\emptyset)\neq\emptyset$. For countable models of arithmetic $M,N\models\text{PA}$, one can show that there is an embedding $j:M\to N$ if and only if $N$ satisfies the $\Sigma_1$-theory of $M$ and the standard system of $M$ is contained in the standard system of $N$. 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 $\text{ZFC}^{\neg\infty}$, that is, with $\langle\text{HF},{\in}\rangle^M$ for $M\models\text{PA}$, since all nonstandard such models are universal for all countable acyclic binary relations, and so in the context of countable models of $\text{ZFC}^{\neg\infty}$ 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 $\diamondsuit$ holds and ZFC is consistent, then there is a family $\mathcal C$ of $2^{\omega_1}$ many pairwise incomparable $\omega_1$-like models of ZFC, meaning that there is no embedding between any two distinct models in $\mathcal 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 $\omega_1$-like linear order. If ZFC has an $\omega$-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.

3. If $\diamondsuit$ holds and ZFC is consistent, then there is an $\omega_1$-like model $M\models\text{ZFC}$ and an $\omega_1$-like model $N\models\text{PA}$ such that $M$ does not embed into $\langle\text{HF},{\in}\rangle^N$.

4. If there is a Mahlo cardinal, then in a forcing extension of $L$, there is a transitive $\omega_1$-like model $M\models\text{ZFC}$ that does not embed into its own constructible universe $L^M$.

Note that the size of the family $\mathcal 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^{\omega_1}$ many isomorphism types of $\omega_1$-like models of set theory or indeed of structures of size $\omega_1$ in any first-order finite language. Statement (2) shows that the models of the family $\mathcal C$ serve as $\omega_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

$\newcommand\Ord{\text{Ord}}
\newcommand\R{\mathbb{R}}
\newcommand\HOD{\text{HOD}}$

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 $F$ which is a function such that $F(x)\in x$ for every nonempty set $x$.

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 $F$ such that $F(x)\in x$ for every nonempty set $x$.
  2. There is a bijection between $V$ and $\Ord$.
  3. There is a global well-ordering of $V$. That is, there is a class relation $\triangleleft$ on $V$ that is a linear order, such that every nonempty set has a $\triangleleft$-least member.
  4. There is a global set-like well-ordering of $V$. There is a class well-ordering $\triangleleft$ as above, such that all $\triangleleft$-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\to 2$) Assume that $F$ is a global choice class function. Using the axiom of replacement, we may recursively define a class sequence of sets $\langle x_\alpha\mid\alpha\in\Ord\rangle$, where $x_\alpha=F(X_\alpha)$, where $X_\alpha$ is the set of minimal-rank sets $x$ not among $\{x_\beta\mid\beta<\alpha\}$. That is, we use $F$ to choose the next element among the minimal-rank sets not yet chosen. Thus, we have an injection of $V$ into $\Ord$. If a set $x$ does not appear as some $x_\alpha$ 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 $V_\beta$. But this is impossible by Hartog’s theorem, and so in fact we have bijection between $\Ord$ and $V$.

($2\to 3$) If there is a bijection between $\Ord$ and $V$, then we may define a global well-ordering by $x<y$ if $x$ appears before $y$ in that enumeration.

($3\to 1$) Let $F(x)$ be the least element of $x$ with respect to a fixed global well-ordering.

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

($4\to 5$) If there is a global set-like well-ordering $<$ of $V$ and $X$ is a proper class, then $<$ on $X$ is a well-ordering of $X$, and we may map any ordinal $\alpha$ to the $\alpha^{th}$ member of $X$. This will be a bijection of $\Ord$ with $X$.

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

($6\to 7$) If every class injects into $\Ord$, then in particular, $V$ 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 $\alpha$ to the $\alpha^{th}$ member of the class, and so every proper class is bijective with $\Ord$. So $\Ord$ injects the other way, and also AC holds.

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

($5\to 8$) Immediate.

($8\to 3$) If $\Ord$ surjects onto $V$, then there is a global well-ordering, defined by $x<y$ if the earliest appearance of $x$ in the surjection is earlier than that of $y$.

($6\to 9$) Immediate.

($9\to 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 $W$ used above, consisting of all well-orderings of a $V_\alpha$, then we saw before that we can build a well-ordering of $V$. And if $W$ injects into $\Ord$, then $W$ is well-orderable and we can also in this case build a well-ordering of $V$.

($5\to 10$) If $V$ 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\to 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 $V=L(\R)$, 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 $L(\R)$ is definable from ordinal and real parameters, and indeed, definable in some $V_\alpha^{L(\R)}$ by some real and ordinal parameters. Indeed, one needs only one ordinal and real parameter. If $W$ is any proper class, then there
must be a proper subclass $W_0\subset W$ 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 $W$. Thus, we may inject $\Ord$ into $W$, even though AC fails in $L(\R)$.

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 $W$ is a proper class, then there are unboundedly many ordinals
arising as the rank of an element of $W$, and so we may map each element $x\in W$ to $\alpha$, if the rank of $x$ is the $\alpha^{th}$ ordinal that is the rank of any element of $W$.

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 $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, 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 $V$ down to its grounds, the inner models $W$ over which $V$ might have arisen by forcing $V=W[G]$. 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, $\S2$ 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.

$\newcommand\P{\mathbb{P}}\newcommand\Q{\mathbb{Q}}\newcommand\R{\mathbb{R}}\newcommand\of{\subset}\newcommand\cross{\times}$

Observation. If $W$ is a countable model of ZFC set theory, then there are forcing extensions $W[c]$ and $W[d]$, 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 $W$ containing both $W[c]$ and $W[d]$. Thus, the family of forcing extensions of $W$ is not upward directed.

Proof. Since $W$ is countable, let $z$ be a real coding the entirety of $W$. Enumerate the dense subsets $\langle D_n\mid n<\omega\rangle$ of the Cohen forcing $\text{Add}(\omega,1)$ in $W$. We construct $c$ and $d$ in stages. We begin by letting $c_0$ be any element of $D_0$. Let $d_0$ consist of exactly as many $0$s as $|c_0|$, followed by a $1$, followed by $z(0)$, and then extended to an element of $D_0$. Continuing, $c_{n+1}$ extends $c_n$ by adding $0$s until the length of $d_n$, and then a $1$, and then extending into $D_{n+1}$; and $d_{n+1}$ extends $d_n$ by adding $0$s to the length of $c_{n+1}$, then a $1$, then $z(n)$, then extending into $D_{n+1}$. Let $c=\bigcup c_n$ and $d=\bigcup d_n$. Since we met all the dense sets in $W$, we know that $c$ and $d$ are $W$-generic Cohen reals, and so we may form the forcing extensions $W[c]$ and $W[d]$. But if $W\subset U\models\text{ZFC}$ and both $c$ and $d$ are in $U$, then in $U$ we may reconstruct the map $n\mapsto\langle c_n,d_n\rangle$, by giving attention to the blocks of $0$s in $c$ and $d$. From this map, we may reconstruct $z$ in $U$, which reveals all the ordinals of $W$ to be countable, a contradiction if $U$ and $W$ 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 $W$-generic Cohen reals $c_0$, $c_1$ and $c_2$, such that any two of them can be amalgamated, but the three of them cannot. More generally:

Observation. If $W$ is a countable model of ZFC set theory, then for any finite $n$ there are $W$-generic Cohen reals $c_0,c_1,\ldots,c_{n-1}$, such that any proper subset of them are mutually $W$-generic, so that one may form the generic extension $W[\vec c]$, provided that $\vec c$ omits at least one $c_i$, but there is no forcing extension $W[G]$ simultaneously extending all $W[c_i]$ for $i<n$. In particular, the sequence $\langle c_0,c_1,\ldots,c_{n-1}\rangle$ cannot be added by forcing over $W$.

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 $W$, with forcing of uniformly bounded size, is bounded above by a single forcing extension $W[G]$.

Theorem. If $W$ is a countable model of ZFC, then there is an increasing sequence of set-forcing extensions of $W$ having no upper bound in the generic multiverse of $W$. $$W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$$

Proof. Since $W$ is countable, there is an increasing sequence $\langle\gamma_n\mid n<\omega\rangle$ of ordinals that is cofinal in the ordinals of $W$. Let $G_n$ be $W$-generic for the collapse forcing $\text{Coll}(\omega,\gamma_n)$, as defined in $W$. (By absorbing the smaller forcing, we may arrange that $W[G_n]$ contains $G_m$ for $m<n$.) Since every ordinal of $W$ is eventually collapsed, there can be no set-forcing extension of $W$, and indeed, no model with the same ordinals as $W$, that contains every $W[G_n]$. QED

But that was cheating, of course, since the sequence of forcing notions is not even definable in $W$, as the class $\{\gamma_n\mid n<\omega\}$ is not a class of $W$. A more intriguing question would be whether this phenomenon can occur with forcing notions that constitute a set in $W$, or (equivalently, actually) whether it can occur using always the same poset in $W$. For example, if $W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$ is an increasing sequence of generic extensions of $W$ by adding Cohen reals, then does it follow that there is a set-forcing extension $W[G]$ of $W$ with $W[c_0]\cdots[c_n]\of W[G]$ for every $n$? For this, we begin by showing that one mustn’t ask for too much:

Observation. If $W$ is a countable model of ZFC, then there is a sequence of forcing extensions $W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$, adding a Cohen real at each step, such that there is no forcing extension of $W$ containing the sequence $\langle c_n\mid n<\omega\rangle$.

Proof. Let $\langle d_n\mid n<\omega\rangle$ be any $W$-generic sequence for the forcing to add $\omega$ many Cohen reals over $W$. Let $z$ be any real coding the ordinals of $W$. Let us view these reals as infinite binary sequences. Define the real $c_n$ to agree with $d_n$ on all digits except the initial digit, and set $c_n(0)=z(n)$. That is, we make a single-bit change to each $d_n$, so as to code one additional bit of $z$. Since we have made only finitely many changes to each $d_n$, it follows that $c_n$ is an $W$-generic Cohen real, and also $W[c_0]\cdots[c_n]=W[d_0]\cdots [d_n]$. Thus, we have $$W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots,$$ adding a generic Cohen real at each step. But there can be no forcing extension of $W$ containing $\langle c_n\mid n<\omega\rangle$, since any such extension would have the real $z$, revealing all the ordinals of $W$ to be countable. QED

We can modify the construction to allow $z$ to be $W$-generic, but collapsing some cardinals of $W$. For example, for any cardinal $\delta$ of $W$, we could let $z$ be $W$-generic for the collapse of $\delta$. Then, if we construct the sequence $\langle c_n\mid n<\omega\rangle$ as above, but inside $W[z]$, we get a sequence of Cohen real extensions $$W\of W[c_0]\of W[c_0][c_1]\of W[c_0][c_1][c_2]\of\cdots$$ such that $W[\langle c_n\mid n<\omega\rangle]=W[z]$, which collapses $\delta$.

But of course, the question of whether the models $W[c_0][c_1]\cdots[c_n]$ have an upper bound is not the same question as whether one can add the sequence $\langle c_n\mid n<\omega\rangle$, 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 $W$ is a countable model of \ZFC, and $$W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$$ is an increasing sequence of forcing extensions of $W$, with $G_n\of\Q_n\in W$ being $W$-generic. If the cardinalities of the $\Q_n$’s in $W$ are bounded in $W$, then there is a set-forcing extension $W[G]$ with $W[G_n]\of W[G]$ for all $n<\omega$.

Proof. Let us first make the argument in the special case that we have $$W\of W[g_0]\of W[g_0][g_1]\of\cdots\of W[g_0][g_1]\cdots[g_n]\of\cdots,$$ where each $g_n$ is generic over the prior model for forcing $\Q_n\in W$. That is, each extension $W[g_0][g_1]\cdots[g_n]$ is obtained by product forcing $\Q_0\cross\cdots\cross\Q_n$ over $W$, and the $g_n$ are mutually $W$-generic. Let $\delta$ be a regular cardinal with each $\Q_n$ having size at most $\delta$, built with underlying set a subset of $\delta$. In $W$, let $\theta=2^\delta$, let $\langle \R_\alpha\mid\alpha<\theta\rangle$ enumerate all posets of size at most $\delta$, with unbounded repetition, and let $\P=\prod_{\alpha<\theta}\R_\alpha$ be the finite-support product of these posets. Since each factor is $\delta^+$-c.c., it follows that the product is $\delta^+$-c.c. Since $W$ is countable, we may build a filter $H\of\P$ that is $W$-generic. In fact, we may find such a filter $H\of\P$ that meets every dense set in $\bigcup_{n<\omega}W[g_0][g_1]\cdots[g_n]$, since this union is also countable. In particular, $H$ and $g_0\cross\cdots\cross g_n$ are mutually $W$-generic for every $n<\omega$. The filter $H$ is determined by the filters $H_\alpha\of\R_\alpha$ that it adds at each coordinate.

Next comes the key step. Externally to $W$, we may find an increasing sequence $\langle \theta_n\mid n<\omega\rangle$ of ordinals cofinal in $\theta$, such that $\R_{\theta_n}=\Q_n$. This is possible because the posets are repeated unboundedly, and $\theta$ is countable in $V$. Let us modify the filter $H$ by surgery to produce a new filter $H^*$, by changing $H$ at the coordinates $\theta_n$ to use $g_n$ rather than $H_{\theta_n}$. That is, let $H^*_{\theta_n}=g_n$ and otherwise $H^*_\alpha=H_\alpha$, for $\alpha\notin\{\theta_n\mid n<\omega\}$. It is clear that $H^*$ is still a filter on $\P$. We claim that $H^*$ is $W$-generic. To see this, suppose that $A\of\P$ is any maximal antichain in $W$. By the $\delta^+$-chain condition and the fact that $\text{cof}(\theta)^W>\delta$, it follows that the conditions in $A$ have support bounded by some $\gamma<\theta$. Since the $\theta_n$ are increasing and cofinal in $\theta$, only finitely many of them lay below $\gamma$, and we may suppose that there is some largest $\theta_m$ below $\gamma$. Let $H^{**}$ be the filter derived from $H$ by performing the surgical modifications only on the coordinates $\theta_0,\ldots,\theta_m$. Thus, $H^*$ and $H^{**}$ agree on all coordinates below $\gamma$. By construction, we had ensured that $H$ and $g_0\cross\cdots\cross g_m$ are mutually generic over $W$ for the forcing $\P\cross\Q_0\cross\cdots\cross\Q_m$. This poset has an automorphism swapping the latter copies of $\Q_i$ with their copy at $\theta_i$ in $\P$, and this automorphism takes the $W$-generic filter $H\cross g_0\cross\cdots\cross g_m$ exactly to $H^{**}\cross H_{\theta_0}\cross\cdots \cross H_{\theta_m}$. In particular, $H^{**}$ is $W$-generic for $\P$, and so $H^{**}$ meets the maximal antichain $A$. Since $H^*$ and $H^{**}$ agree at coordinates below $\gamma$, it follows that $H^*$ also meets $A$. In summary, we have proved that $H^*$ is $W$-generic for $\P$, and so $W[H^*]$ is a set-forcing extension of $W$. By design, each $g_n$ appears at coordinate $\theta_n$ in $H^*$, and so $W[g_0]\cdots[g_n]\of W[H^*]$ for every $n<\omega$, as desired.

Finally, we reduce the general case to this special case. Suppose that $W[G_0]\of W[G_1]\of\cdots\of W[G_n]\of\cdots$ is an increasing sequence of forcing extensions of $W$, with $G_n\of\Q_n\in W$ being $W$-generic and each $\Q_n$ of size at most $\kappa$ in $W$. By the standard facts surrounding finite iterated forcing, we may view each model as a forcing extension of the previous model $$W[G_{n+1}]=W[G_n][H_n],$$ where $H_n$ is $W[G_n]$-generic for the corresponding quotient forcing $\Q_n/G_n$ in $W[G_n]$. Let $g\of\text{Coll}(\omega,\kappa)$ be $\bigcup_n W[G_n]$-generic for the collapse of $\kappa$, so that it is mutually generic with every $G_n$. Thus, we have the increasing sequence of extensions $W[g][G_0]\of W[g][G_1]\of\cdots$, where we have added $g$ to each model. Since each $\Q_n$ is countable in $W[g]$, it is forcing equivalent there to the forcing to add a Cohen real. Furthermore, the quotient forcing $\Q_n/G_n$ is also forcing equivalent in $W[g][G_n]$ to adding a Cohen real. Thus, $W[g][G_{n+1}]=W[g][G_n][H_n]=W[g][G_n][h_n]$, for some $W[g][G_n]$-generic Cohen real $h_n$. Unwrapping this recursion, we have $W[g][G_{n+1}]=W[g][G_0][h_1]\cdots[h_n]$, and consequently $$W[g]\of W[g][G_0]\of W[g][G_0][h_1]\of W[g][G_0][h_1][h_2]\of\cdots,$$ which places us into the first case of the proof, since this is now product forcing rather than iterated forcing. QED

Definition. A collection $\{W[G_n]\mid n<\omega\}$ of forcing extensions of $W$ is finitely amalgamable over $W$ if for every $n<\omega$ there is a forcing extension $W[H]$ with $W[G_m]\of W[H]$ for all $m\leq n$. It is amalgamable over $W$ if there is $W[H]$ such that $W[G_n]\of W[H]$ for all $n<\omega$.

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 $W$ is a countable model of ZFC and $\{W[G_n]\mid n<\omega\}$ is a finitely amalgamable collection of forcing extensions of $W$, using forcing of bounded size in $W$, then this collection is fully amalgamable. That is, there is a forcing extension $W[H]$ with $W[G_n]\of W[H]$ for all $n<\omega$.

Proof. Since the collection is finitely amalgamable, for each $n<\omega$ there is some $W$-generic $K$ such that $W[G_m]\of W[K]$ for all $m\leq n$. Thus, we may form the minimal model $W[G_0][G_1]\cdots[G_n]$ between $W$ and $W[K]$, and thus $W[G_0][G_1]\cdots [G_n]$ is a forcing extension of $W$. We are thus in the situation of the theorem, with an increasing chain of forcing extensions. $$W\of W[G_0]\of W[G_0][G_1]\of\cdots\of W[G_0][G_1]\cdots[G_n]\of\cdots$$ Therefore, by the theorem, there is a model $W[H]$ containing all these extensions, and in particular, $W[G_n]\of W[H]$, as desired. QED

Please go to the paper for more details and discussion.

Transfinite recursion as a fundamental principle in set theory

$\newcommand\dom{\text{dom}}
\newcommand\ran{\text{ran}}
\newcommand\restrict{\upharpoonright}$
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 $A$ is any set with well-ordering $<$ and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for all $b\in A$, where $s\upharpoonright b$ denotes the function $\langle s(a)\mid a<b\rangle$.

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 $F$, 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 $\langle A,<\rangle$ and a class function $F:V\to
V$. I claim that for every $b\in A$, there is a unique function $s:\{a\in A\mid a\leq b\}\to V$ obeying the recursive rule $s(d)=F(s\upharpoonright d)$ for all $d\leq b$. The reason is that there can be no least $b$ without such a unique function. If all $a<b$ 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 $t$ defined on all $a<b$, and satisfying the recursion rule for those values. We may then extend this function $t$ to be defined on $b$ itself, simply by defining $u(b)=F(t)$ and $u\upharpoonright b=t$, which thereby satisfies the recursion at $b$. Uniqueness again follows from the fact that there can be no least place of disagreement. Finally, using replacement again, let $s(b)$ be the unique value that arises at $b$ during the recursions that work up to and including $b$, and this function $s:A\to V$ 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 $A$ and a formula $\varphi$, where every $b\in A$ has a unique $y$ such that $\varphi(b,y)$. By the axiom of choice, there is a well-ordering $<$ of the set $A$. We shall now define the function $F:V\to V$. Given a function $s$, where $\dom(s)=\{a\in A\mid a<b\}$ for some $b\in A$, let $F(s)=y$ be the unique $y$ such that $\varphi(b,y)$; and otherwise let $F(s)$ be anything you like. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for every $b\in A$. In this case, it follows that $s(b)$ is the unique $y$ such that $\varphi(a,b)$. Thus, since $s$ is a set, it follows in ZC that $\ran(s)$ is a set, and so we’ve got the image of $A$ under $\varphi$ 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 $\langle A,<\rangle$ assigns an ordinal to each node $a\mapsto \alpha_a$ according to the recursive rule $\alpha_a=\{\alpha_b\mid b<a\}$. But one can also argue directly as follows, without using the axiom of choice. Assume Z and the principle of transfinite recursion. Suppose that $\langle A,<\rangle$ is a well-ordering. Define the class function $F:V\to V$ so that $F(s)=\ran(s)$, whenever $s$ is a function. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)=\ran(s\restrict b)$. One can now simply prove by induction that $s(b)$ is an ordinal and $s$ is an isomorphism of $\langle A,<\rangle$ with $\ran(s)$, 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 $A$ is any particular class with $<$ a set-like well-ordering of $A$ and $F:V\to V$ is any class function, then there is a class function $S:A\to V$ such that $S(b)=F(S\upharpoonright b)$ for every $b\in A$.

Proof. Since $\langle A,<\rangle$ is set-like, the initial segment $A\upharpoonright d=\{a\in A\mid a<d\}$, for any particular $d\in A$, is a set. It follows that the principle of transfinite recursion shows that there is a function $s_d:(A\upharpoonright d)\to V$ such that $s_d(b)=F(s_d\upharpoonright b)$ for every $b<d$. It is now easy to prove by induction that these $s_d$ must all cohere with one another, and so we may define the class $S(b)=s_d(b)$ for any $d$ above $b$ in $A$. (We may assume without loss that $A$ has no largest element, for otherwise it would be a set.) This provides a class function $S:A\to V$ satisfying the recursive definition as desired. QED

Although it appears explicitly as a second-order statement “there is a class function $S$…”, we may actually take this observation as a first-order theorem scheme, if we simply strengthen the conclusion to provide the explicit definition of $S$ that the proof provides. That is, the proof shows exactly how to define $S$, 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 $A$ and $F$ from parameters leads uniformly to a first-order definition of $S$ 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 $F:V\to V$ is any class function, then for any ordinal $\gamma$ there is a function $s:\gamma\to V$ such that $s(\beta)=F(s\upharpoonright\beta)$ for all $\beta<\gamma$.

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 $\langle V_{\omega_1},\in\rangle$ 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 $V_{\omega_1}$, as well as the axiom of choice, provided choice holds in $V$. Notice that there are comparatively few ordinals in $V_{\omega_1}$—only the countable ordinals exist there—but $V_{\omega_1}$ has much larger well-orderings. For example, one may find a well-ordering of the reals already in $V_{\omega+k}$ for small finite $k$, and well-orderings of much larger sets in $V_{\omega^2+17}$ and so on as one ascends toward $V_{\omega_1}$. So $V_{\omega_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 $F:V_{\omega_1}\to V_{\omega_1}$ is any class in this structure, and $\gamma$ is any ordinal, then we may define by recursion in $V$ the function $s(\beta)=F(s\restrict\beta)$, which gives a class $s:\omega_1\to V_{\omega_1}$ that is amenable in $V_{\omega_1}$. In particular, $s\restrict\gamma\in V_{\omega_1}$ for any $\gamma<\omega_1$, simply because $\gamma$ is countable and $\omega_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 $V_{\omega_1}$, rather than considering $V_{\omega+\omega}$, which is a more-often mentioned model of the Zermelo axioms. It is not difficult to see that $V_{\omega+\omega}$ does not satisfy the principle of transfinite recursion on the ordinals, because one can define the function $s(n)=\omega+n$ by recursion, setting $s(0)=\omega$ and $s(n+1)=s(n)+1$, but this function does not exist in $V_{\omega+\omega}$. 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 $\langle A,<\rangle$ is a well-ordered set, and $A$ is bijective with some ordinal, then $\langle A,<\rangle$ 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 $\langle A,<\rangle$, then $A$-replacement holds, meaning that if $F:V\to V$ is any class function, then the image $F”A$ is a set.

Proof of theorem. Suppose that $\langle A,<\rangle$ is a well-ordering, and that $A$ is bijective with some ordinal $\kappa$, and that $F:V\to V$ is a class function. Assume the principle of transfinite recursion for $\kappa$. We prove by induction on $d\in A$ that there is a unique function $s_d$ with $\dom(s)=\{a\in A\mid a\leq d\}$ and satisfying the recursive rule $s(b)=F(s\upharpoonright b)$. If this statement is true for all $d<d’$, then because the size of the predecessors of $d’$ in $\langle A,<\rangle$ is at most $\kappa$, we may by the lemma form the set $\{s_d\mid d<d’\}$, which is a set by $\kappa$-replacement. These functions cohere, and the union of these functions gives a function $t:(A\upharpoonright d’)\to V$ satisfying the recursion rule for $F$. Now extend this function one more step by defining $s(d’)=F(t)$ and $s\upharpoonright d’=t$, thereby handling the existence claim at $d’$. As in the main theorem, all these functions cohere with one another, and by $\kappa$-replacement we may form the set $\{s_d\mid d\in A\}$, whose union is the desired function $s:A\to V$ satisfying the recursion rule given by $F$, as desired. QED

For example, if you have the principle of transfinite recursion for ordinals, and $\omega$ exists, then every countable well-ordering is isomorphic to an ordinal. This explains why we had to go to $\omega_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 $\kappa$, every well-ordering of cardinality at most $\kappa$ 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 $\langle A,\lhd\rangle$ is a well-founded relation and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)$ for all $b\in A$, where $s\restrict b$ means the function $s$ restricted to the domain of elements $a\in A$ that are hereditarily below $b$ with respect to $\lhd$.

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 $\langle A,\lhd\rangle$, 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 $s:A\to V$ 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 $S:\text{Ord}\to V$ 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.

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