Joining the Doctoral Faculty in Philosophy

I am recently informed that I shall be joining the Doctoral Faculty of the Philosophy Program at the CUNY Graduate Center, in addition to my current appointments in Mathematics and in Computer Science.  This means I shall now be able to teach graduate courses in philosophy at the Graduate Center and also to supervise Ph.D. dissertations in philosophy there.  I am pleased to become a part of the GC Philosophy Program, which is so highly ranked in the area of mathematical logic, and I look forward to making a positive contribution to the program.

 

Interviewed by Richard Marshall at 3:AM Magazine

I was recently interviewed by Richard Marshall at 3:AM Magazine, which was a lot of fun. You can see that his piece starts out, however, rather over-the-top…

3:AM MAGAZINE

playing infinite chess

Joel David Hamkins interviewed by Richard Marshall.

Joel David Hamkins is a maths/logic hipster, melting the logic/maths hive mind with ideas that stalk the same wild territory as Frege, Tarski, Godel, Turing and Cantor. He thinks we all can go there and that we all should. He gives tips about the Moebius strip to six year olds and plays around with his sons homework. He has discovered all sorts of wonders involving supertasks, infinite-time Turing machines, black-hole computations, the mathematics of the uncountable, the lost melody phenomenon of infintary computability (which really should be the name of a band), set theory and multiverses, infinite utilitarianism, and infinite chess. He’s also thinking about whether we really have an absolute notion of the finite and doubts if any of this is brain melting, which is just a testimony to his modesty. He also thinks that although maths is open to all he thinks mathematicians could use more metaphors and silly terminology to get their ideas across better than they do. All in all, this is the grooviest of the hard core maths/logic groovsters. Bodacious!

β†’ continue to the rest of the interview

The interview is now available at Marshall’s site 3:16, along with the full collection of his interviews.

Pluralism in mathematics: the multiverse view in set theory and the question of whether every mathematical statement has a definite truth value, Rutgers, March 2013

This is a talk for the Rutgers Logic Seminar on March 25th, 2013.  Simon Thomas specifically requested that I give a talk aimed at philosophers.

Abstract.  I shall describe the debate on pluralism in the philosophy of set theory, specifically on the question of whether every mathematical and set-theoretic assertion has a definite truth value. A traditional Platonist view in set theory, which I call the universe view, holds that there is an absolute background concept of set and a corresponding absolute background set-theoretic universe in which every set-theoretic assertion has a final, definitive truth value. I shall try to tease apart two often-blurred aspects of this perspective, namely, to separate the claim that the set-theoretic universe has a real mathematical existence from the claim that it is unique. A competing view, the multiverse view, accepts the former claim and rejects the latter, by holding that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe, and a corresponding pluralism of set-theoretic truths. After framing the dispute, I shall argue that the multiverse position explains our experience with the enormous diversity of set-theoretic possibility, a phenomenon that is one of the central set-theoretic discoveries of the past fifty years and one which challenges the universe view. In particular, I shall argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Some of this material arises in my recent articles:

The omega one of chess, CUNY, March, 2013

This is a talk for the New York Set Theory Seminar on March 1, 2013.

This talk will be based on my recent paper with C. D. A. Evans, Transfinite game values in infinite chess.

Infinite chess is chess played on an infinite chessboard.  Since checkmate, when it occurs, does so after finitely many moves, this is technically what is known as an open game, and is therefore subject to the theory of open games, including the theory of ordinal game values.  In this talk, I will give a general introduction to the theory of ordinal game values for ordinal games, before diving into several examples illustrating high transfinite game values in infinite chess.  The supremum of these values is the omega one of chess, denoted by  in the context of finite positions and by πœ”β„­π”₯ βˆΌ1 in the context of all positions, including those with infinitely many pieces. For lower bounds, we have specific positions with transfinite game values of πœ”, πœ”2, πœ”2 β‹…π‘˜ and πœ”3. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true πœ”1.

Transfinite game values in infinite chess

[bibtex key=EvansHamkins2014:TransfiniteGameValuesInInfiniteChess]

In this article, C. D. A. Evans  and I investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these valuesβ€”the omega one of chessβ€”denoted by πœ”β„­π”₯1 in the context of finite positions and by πœ”β„­π”₯∼1 in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of πœ”, πœ”2, πœ”2 β‹…π‘˜ and πœ”3. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true πœ”1.

The article is 38 pages, with 18 figures detailing many interesting positions of infinite chess. My co-author Cory Evans holds the chess title of U.S. National Master.

WΓ€stlund’s MathOverflow question | My answer there

Let’s display here a few of the interesting positions.

First, a simple new position with value πœ”.  The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1…Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#.  By playing the rook higher on the first move, black can force this main line of play have any desired finite length.  We have further variations with more black rooks and white king.

Value omega

Next, consider an infinite position with value πœ”2. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Value omega squared

Here is a similar position with value πœ”2, which we call, β€œreleasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Releasing the hoards

Next, by iterating this idea, we produce a position with value πœ”2 β‹…4.  We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the β€œlock and key” concept explained in the paper.

Omega-squared-times-4

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value πœ”2 β‹…π‘˜ for any desired π‘˜, making the position overall have value πœ”3.

Value omega cubed

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for whiteβ€”white has a computable strategy defeating any computable strategy of blackβ€”but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

Infinite tree

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal πœ”𝐢⁒𝐾1 in the context of finite positions, and true πœ”1 in the context of all positions.

Our idea for proving this conjecture, unfortunately, does not quite fit into two-dimensional chess geometry, but we were able to make the idea work in infinite **three-dimensional** chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true πœ”1.

Here is a part of the position. Imagine the layers stacked atop each other, with 𝛼 at the bottom and further layers below and above. The black king had entered at 𝛼e4, was checked from below and has just moved to 𝛽e5. Pushing a pawn with check, white continues with 1.𝛼e4+ K𝛾e6 2.𝛽e5+ K𝛿e7 3.𝛾e6+ Kπœ–e8 4.𝛿e7+, forcing black to climb the stairs (the pawn advance 1.𝛼e4+ was protected by a corresponding pawn below, since black had just been checked at 𝛼e4).

Climbing the stairs

The overall argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension β„€ Γ—β„€ Γ—π‘˜, for π‘˜ above 25 or so.

On the axiom of constructibility and Maddy’s conception of restrictive theories, Logic Workshop, February 2013

This is a talk for the CUNY Logic Workshop on February 15, 2013.

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

Set-theorists often argue against the axiom of constructibility 𝑉 =𝐿 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 specific proposal.  For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive.  Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the 𝑉 ≠𝐿 via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of 𝑉 =𝐿.  In particular, every countable model of set theory is a transitive set inside a model of 𝑉 =𝐿.  I shall conclude the talk by explaining various senses in which 𝑉 =𝐿 remains compatible with strength in set theory.

Math for six-year-olds

Today I went into my daughter’s first-grade classroom, full of six-year-old girls, and gave a presentation about MΓΆbius bands.

Make your own Mobius bandWe cut strips of paper and at first curled them into simple bands, cylinders, which we proved had two sides by coloring them one color on the outside and another color on the inside.  Next, we cut strips and curled them around, but added a twist, to make a true MΓΆbius band.

A MΓΆbius band

A MΓΆbius band

These, of course, have only one side, a fact that the children proved by coloring it one color all the way around. And we observed that a MΓΆbius band has only one edge.

A MΓΆbius-like band, with two twists

A MΓΆbius-like band, with two twists

We explored what happens with two twists, or more twists, and also what happens when you cut a MΓΆbius band down the center, all the way around.

MΓΆbius band cut down the center

MΓΆbius band cut down the center

It is very interesting to cut a MΓΆbius band on a line that is one-third of the way in from an edge, all the way around. What happens? Make your prediction before unraveling the pieces–how many pieces will there be? Will they be all the same size? How many twists will they have?

Overall, the whole presentation was a lot of fun. The girls were extremely curious about everything, and experimented with additional twists and additional ways of cutting.  It seemed to be just the right amount of mathematical thinking, cutting and coloring for a first-grade class.  To be sure, without prompting the girls made various MΓΆbius earrings, headbands and bracelets, which I had to admit were fairly cool. One girl asked, β€œis this really mathematics?”

It seems I may be back in the first-grade classroom this spring, and I have in mind to teach them all how to beat their parents at Nim.

Superstrong cardinals are never Laver indestructible, and neither are extendible, almost huge and rank-into-rank cardinals, CUNY, January 2013

This is a talk for the CUNY Set Theory Seminar on February 1, 2013, 10:00 am.

Abstract.  Although the large cardinal indestructibility phenomenon, initiated with Laver’s seminal 1978 result that any supercompact cardinal πœ… can be made indestructible by <πœ…-directed closed forcing and continued with the Gitik-Shelah treatment of strong cardinals, is by now nearly pervasive in set theory, nevertheless I shall show that no superstrong strong cardinalβ€”and hence also no 1-extendible cardinal, no almost huge cardinal and no rank-into-rank cardinalβ€”can be made indestructible, even by comparatively mild forcing: all such cardinals πœ… are destroyed by Add⁑(πœ…,1), by Add⁑(πœ…,πœ…+), by Add⁑(πœ…+,1) and by many other commonly considered forcing notions.

This is very recent joint work with Konstantinos Tsaprounis and Joan Bagaria.

nylogic.org | Set Theory Seminar |

The use and value of mathoverflow

FranΓ§ois Dorais has created a discussion on the MathOverflow discussion site, How is mathoverflow useful for me? in which he is soliciting response from MO users.  Here is what I wrote there:

The principal draw of mathoverflow for me is the unending supply of extremely interesting mathematics, an eternal fountain of fascinating questions and answers. The mathematics here is simply compelling.

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.

So, thanks very much mathoverflow! I am grateful.

 

The differential operator 𝑑𝑑⁒π‘₯ binds variables

Recently the question If π‘‘𝑑⁒π‘₯ is an operator, on what does it operate? was asked on mathoverflow.  It seems that some users there objected to the question, apparently interpreting it as an elementary inquiry about what kind of thing is a differential operator, and on this interpretation, I would agree that the question would not be right for mathoverflow. And so the question was closed down (and then reopened, and then closed again….sigh). (Update 12/6/12: it was opened again,and so I’ve now posted my answer over there.)

Meanwhile, I find the question to be more interesting than that, and I believe that the OP intends the question in the way I am interpreting it, namely, as a logic question, a question about the nature of mathematical reference, about the connection between our mathematical symbols and the abstract mathematical objects to which we take them to refer.  And specifically, about the curious form of variable binding that expressions involving 𝑑⁒π‘₯ seem to involve.  So let me write here the answer that I had intended to post on mathoverflow:

β€”β€”β€”β€”β€”β€”β€”β€”-

To my way of thinking, this is a serious question, and I am not really satisfied by the other answers and comments, which seem to answer a different question than the one that I find interesting here.

The problem is this. We want to regard 𝑑𝑑⁒π‘₯ as an operator in the abstract senses mentioned by several of the other comments and answers. In the most elementary situation, it operates on a functions of a single real variable, returning another such function, the derivative. And the same for π‘‘𝑑⁒𝑑.

The problem is that, described this way, the operators π‘‘𝑑⁒π‘₯ and 𝑑𝑑⁒𝑑 seem to be the same operator, namely, the operator that takes a function to its derivative, but nevertheless we cannot seem freely to substitute these symbols for
one another in formal expressions. For example, if an instructor were to write 𝑑𝑑⁒𝑑⁒π‘₯3 =3⁒π‘₯2, a student might object, β€œdon’t you mean 𝑑𝑑⁒π‘₯?” and the instructor would likely reply, β€œOh, yes, excuse me, I meant 𝑑𝑑⁒π‘₯⁒π‘₯3 =3⁒π‘₯2. The other expression would have a different meaning.”

But if they are the same operator, why don’t the two expressions have the same meaning? Why can’t we freely substitute different names for this operator and get the same result? What is going on with the logic of reference here?

The situation is that the operator 𝑑𝑑⁒π‘₯ seems to make sense only when applied to functions whose independent variable is described by the symbol β€œx”. But this collides with the idea that what the function is at bottom has nothing to do with the way we represent it, with the particular symbols that we might use to express which function is meant.  That is, the function is the abstract object (whether interpreted in set theory or category theory or whatever foundational theory), and is not connected in any intimate way with the symbol β€œπ‘₯”.  Surely the functions π‘₯ ↦π‘₯3 and 𝑑 ↦𝑑3, with the same domain and codomain, are simply different ways of  describing exactly the same function. So why can’t we seem to substitute them for one another in the formal expressions?

The answer is that the syntactic use of 𝑑𝑑⁒π‘₯ in a formal expression involves a kind of binding of the variable π‘₯.

Consider the issue of collision of bound variables in first order logic: if πœ‘β‘(π‘₯) is  the assertion that π‘₯ is not maximal with respect to <, expressed by βˆƒπ‘¦ π‘₯ <𝑦, then πœ‘β‘(𝑦), the assertion that 𝑦 is not maximal, is not correctly described as the assertion βˆƒπ‘¦ π‘¦ <𝑦, which is what would be obtained by simply replacing the occurrence of π‘₯ in πœ‘β‘(π‘₯) with the symbol 𝑦. For the intended meaning, we cannot simply syntactically replace the occurrence of π‘₯ with the symbol 𝑦, if that occurrence of π‘₯ falls under the scope of a quantifier.

Similarly, although the functions π‘₯ ↦π‘₯3 and 𝑑 ↦𝑑3 are equal as functions of a real variable, we cannot simply syntactically substitute the expression π‘₯3 for 𝑑3 in 𝑑𝑑⁒𝑑⁒𝑑3 to get 𝑑𝑑⁒𝑑⁒π‘₯3. One might even take the latter as a kind of ill-formed expression, without further explanation of how π‘₯3 is to be taken as a function of 𝑑.

So the expression 𝑑𝑑⁒π‘₯ causes a binding of the variable π‘₯, much like a quantifier might, and this prevents free substitution in just the way that collision does. But the case here is not quite the same as the way π‘₯ is a bound variable in βˆ«10π‘₯3 π‘‘⁒π‘₯, since π‘₯ remains free in 𝑑𝑑⁒π‘₯⁒π‘₯3, but we would say that ∫10π‘₯3 π‘‘⁒π‘₯ has the same meaning as βˆ«10𝑦3 π‘‘⁒𝑦.

Of course, the issue evaporates if one uses a notation, such as the πœ†-calculus, which insists that one be completely explicit about which syntactic variables are to be regarded as the independent variables of a functional term, as in πœ†β’π‘₯.π‘₯3, which means the function of the variable π‘₯ with value π‘₯3.  And this is how I take several of the other answers to the question, namely, that the use of the operator 𝑑𝑑⁒π‘₯ indicates that one has previously indicated which of the arguments of the given function is to be regarded as π‘₯, and it is with respect to this argument that one is differentiating.  In practice, this is almost always clear without much remark.  For example, our use of πœ•πœ•π‘₯ and πœ•πœ•π‘¦ seems to manage very well in complex situations, sometimes with dozens of variables running around, without adopting the onerous formalism of the πœ†-calculus, even if that formalism is what these solutions are essentially really about.

Meanwhile, it is easy to make examples where one must be very specific about which variables are the independent variable and which are not, as Todd mentions in his comment to David’s answer. For example, cases like

𝑑𝑑⁒π‘₯⁒∫π‘₯0(𝑑2+π‘₯3)π‘‘π‘‘π‘‘π‘‘β’π‘‘β’βˆ«π‘₯𝑑(𝑑2+π‘₯3)𝑑𝑑

are surely clarified for students by a discussion of the usage of variables in formal expressions and more specifically the issue of bound and free variables.

Student talks on infinitary computability

Students in my Infinitary Computability course will give talks on their term papers.  Talks will be held at the CUNY Graduate Center, Room 3307, 9:30-11:30.

Monday, December 3rd

  • Miha Habič will speak on β€œCardinal-Recognizing Infinite Time Turing Machines”, in which he develops the theory of infinite time Turing machines that are given information about when they have reached cardinal time.
  • Erin Carmody will speak on β€œNon-deterministic infinite time Turing machines”, in which she develops the theory of non-deterministic ITTM computation.
  • Alexy Nikolaev will speak on β€œEquivalence of ITTMs, and their simultation on a finite time computer,” in which we proves the equivalence of various formalizations of ITTMs.

Monday, December 10th

  • Manuel Alves will speak on infinite time computable model theory.
  • Syed Ali Ahmed will speak on the relation between BΓΌchi automata and infinite time Turing machines, including πœ”-regular languages and generalizations to longer transfinite strings.

Pluralism in set theory: does every mathematical statement have a definite truth value? GC Philosophy Colloquium, 2012

This will be my talk for the CUNY Graduate Center Philosophy Colloquium on November 28, 2012.

I will be speaking on topics from some of my recent articles:

I shall give a summary account of some current issues in the philosophy of set theory, specifically, the debate on pluralism and the question of the determinateness of set-theoretical and mathematical truth.  The traditional Platonist view in set theory, what I call the universe view, holds that there is an absolute background concept of set and a corresponding absolute background set-theoretic universe in which every set-theoretic assertion has a final, definitive truth value.  What I would like to do is to tease apart two often-blurred aspects of this perspective, namely, to separate the claim that the set-theoretic universe has a real mathematical existence from the claim that it is unique.  A competing view, which I call the multiverse view, accepts the former claim and rejects the latter, by holding that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe, and a corresponding pluralism of set-theoretic truths.  After framing the dispute, I shall argue that the multiverse position explains our experience with the enormous diversity of set-theoretic possibility, a phenomenon that is one of the central set-theoretic discoveries of the past fifty years and one which challenges the universe view. In particular, I shall argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Slides

The countable models of set theory are linearly pre-ordered by embeddability, Rutgers, November 2012

This will be a talk for the Rutgers Logic Seminar on November 19, 2012.

Abstract.  I will speak on my recent theorem that every countable model of set theory 𝑀, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding 𝑗 :𝑀 →𝐿𝑀 that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random β„š-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that 𝐿𝑀 contains a submodel that is a universal acyclic digraph of rank Ord𝑀. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length πœ”1 +1.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory 𝑀 is universal for all countable well-founded binary relations of rank at most Ord𝑀; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if 𝑀 is any nonstandard model of PA, then every countable model of set theoryβ€”in particular, every model of ZFCβ€”is isomorphic to a submodel of the hereditarily finite sets 𝐻⁑𝐹𝑀 of 𝑀. Indeed, 𝐻⁑𝐹𝑀 is universal for all countable acyclic binary relations.

Article | Rutgers Logic Seminar

A multiverse perspective on the axiom of constructiblity

[bibtex key=Hamkins2014:MultiverseOnVeqL]

This article expands on an argument that I made during my talk at the Asian Initiative for Infinity: Workshop on Infinity and Truth, held July 25–29, 2011 at the Institute for Mathematical Sciences, National University of Singapore, and will be included in a proceedings volume that is being prepared for that conference.

Abstract. I argue that the commonly held 𝑉 ≠𝐿 via maximize position, which rejects the axiom of constructibility 𝑉 =𝐿 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 𝑉 =𝐿 inside larger set-theoretic universes.

In section two, I provide a few new criticisms of Maddy’s proposed concept of `restrictive’ theories, pointing out that her concept of fairly interpreted in is not a transitive relation: there is a first theory that is fairly interpreted in a second, which is fairly interpreted in a third, but the first is not fairly interpreted in the third.  The same example (and one can easily construct many similar natural examples) shows that neither the maximizes over relation, nor the properly maximizes over relation, nor the strongly maximizes over relation is transitive.  In addition, the theory ZFC + β€œthere are unboundedly many inaccessible cardinals” comes out as formally restrictive, since it is strongly maximized by the theory ZF + β€œthere is a measurable cardinal, with no worldly cardinals above it.”

To support the main philosophical thesis of the article, I survey a series of mathemtical results,  which reveal various senses in which the axiom of constructibility 𝑉 =𝐿 is compatible with strength in set theory, particularly if one has in mind the possibility of moving from one universe of set theory to a much larger one.  Among them are the following, which I prove or sketch in the article:

Observation. The constructible universe 𝐿 and 𝑉 agree on the consistency of any constructible theory. They have models of the same constructible theories.

Theorem. The constructible universe 𝐿 and 𝑉 have transitive models of exactly the same constructible theories in the language of set theory.

Corollary. (Levy-Shoenfield absoluteness theorem)  In particular, 𝐿 and 𝑉 satisfy the same Ξ£1 sentences, with parameters hereditarily countable in 𝐿. Indeed, πΏπœ”πΏ1 and 𝑉 satisfy the same such sentences.

Theorem. Every countable transitive set is a countable transitive set in the well-founded part of an πœ”-model of V=L.

Theorem. If there are arbitrarily large πœ† <πœ”πΏ1 with πΏπœ† ⊧ZFC, then every countable transitive set 𝑀 is a countable transitive set inside a structure 𝑀+  that is a pointwise-definable model of ZFC + V=L, and 𝑀+ is well founded as high in the countable ordinals as desired.

Theorem. (Barwise)  Every countable model of  ZF has an end-extension to a model of ZFC + V=L.

Theorem. (Hamkins, see here)  Every countable model of set theory βŸ¨π‘€, βˆˆπ‘€βŸ©, including every transitive model, is isomorphic to a submodel of its own constructible universe βŸ¨πΏπ‘€, βˆˆπ‘€βŸ©. In other words,  there is an embedding 𝑗 :𝑀 →𝐿𝑀, which is elementary for quantifier-free assertions.

Another way to say this is that every countable model of set theory is a submodel of a model isomorphic to 𝐿𝑀. If we lived inside 𝑀, then by adding new sets and elements, our universe could be transformed into a copy of the constructible universe 𝐿𝑀.

(Plus, the article contains some nice diagrams.)

Related Singapore links:

Every countable model of set theory is isomorphic to a submodel of its own constructible universe, Barcelona, December, 2012

This will be a talk for a set theory workshop at the University of Barcelona on December 15, 2012, organized by Joan Bagaria.

VestΓ­bul Universitat de Barcelona

Abstract. Every countable model of set theory 𝑀, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding 𝑗 :𝑀 →𝐿𝑀 that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random β„š-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that 𝐿𝑀 contains a submodel that is a universal acyclic digraph of rank Ord𝑀. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other.  Indeed, the bi-embeddability classes form a well-ordered chain of length πœ”1 +1.  Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory 𝑀 is universal for all countable well-founded binary relations of rank at most Ord𝑀; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if 𝑀 is any nonstandard model of PA, then every countable model of set theoryβ€”in particular, every model of ZFCβ€”is isomorphic to a submodel of the hereditarily finite sets 𝐻⁑𝐹𝑀 of 𝑀. Indeed, 𝐻⁑𝐹𝑀 is universal for all countable acyclic binary relations.

Article | Barcelona research group in set theory