User joel david hamkins - MathOverflow

Answer by Joel David Hamkins for What new primitive recursive functions are needed to reconcile Turing time complexity with Godel time complexity?

2013-06-19T02:55:14Z

Since there are computable total functions that are not primitive recursive, one cannot make the two notions of time complexity coincide. If we add any primitive recursive function as an initial function in the primitive recursive hierarchy, the resulting hierarchy will still consist entirely of primitive recursive functions. And so we may take any computable total function that is not primitive recursive, and this function can have no "recursive definition" as a primitive recursive function and thus has no Gödel complexity.

Furthermore, if one entertains the idea of addressing this issue by adding a computable function $g$ that is not primitive recursive, and building the primitive recursive hierarchy on top of that function, then again it will not succeed, since the class of computable total functions is not the same as those that are primitive recursive relative to any fixed computable total function $g$. One can prove this by observing that we have a computable function that is universal for all such functions, simply by unwrapping the primitive recursive definitions and evaluating them. And so by diagonalization there will be a computable total function that is different from any function obtainable by performing primitive recursion over $g$.

Answer by Joel David Hamkins for Nearly all math classes are lecture+problem set based; this seems particularly true at the graduate level. What are some concrete examples of techniques other than the "standard math class" used at the Graduate level?

2013-06-13T15:00:58Z

It may be only a minor thing in the space of examples that you seem to be considering, but I have had a lot of success with my practice of requiring students in my graduate courses to write a substantial term paper on an original topic.

The aim is for them to undertake a simulacrum of the research experience. I definitely do not want them to just give me an account of some difficult topic on which they read elsewhere. Rather, we try to find a suitable original but manageable topic, which they will have to figure out themselves, and then write up their results in the form of a paper.

I insist that these term papers give the appearance of a standard research article, with proper title, abstract, grant or support acknowledgement, proper introduction, definitions, statement of main results and proof, with references and so on. Furthermore, I insist that the students use TeX, which I insist they learn on their own if they do not yet know it.

The most difficult part for the instructor is to find suitable topics. One rich source of topics is to take a standard topic that is well-treated elsewhere, but then make a small change in the set-up, giving the student having the task to work out how things behave in this slightly revised setting. For example, in a computability theory class, there is a standard definition of the busy beaver function, with many results known, but one can insist on a slightly different model of Turing machine (such as one-way infinite tape instead of two, or change the halt rule, or have extra symbols or extra tape), where the standard calculations are no longer relevant, but many of the ideas will have a new analogue in this new setting. But also there are usually many suitable topics if one just thinks with curiosity about some of the main ideas in the course and some relevant examples.

I always insist that the topics be pre-approved by me in advance, because I want to avoid the situation of a student just writing up something difficult they read, but rather have them really do real mathematical research on their own. Often, I meet with each student several times and we make some discoveries together, which they then work out more completely for their paper.

After students submit their final draft (I do not call it a first draft, since I want them to do several drafts on their own before showing me anything, and I don't want to look at anything that they regard as a "first draft"), then I give comments in the style of a referee report, and they make final revisions before submitting the "publication" version, which I sometimes gather into a Kinko's style bound issue Proceedings of Graduate Set Theory, Fall 2014 or whatever, and distribute to them and to the department.

Finally, on the last lecture of the course, we usually have student talks of them making presentations on their work. For example, see the student talks given for my course on infinitary computability last fall.

I think it works quite well, and gives the students some real experience of what it is like to do mathematical research. In a few exceptional cases, the terms papers have subsequently turned into actual journal publications, when the students got some strong enough and interesting enough results, and that has been really special.

The workflow for me is to assign normal problem sets in the early part of the course, and then start suggesting topics, with the students coming to me and we discuss possibilities. Then, as the work on the paper ramps up, the problem sets taper off, until they are submitted, with additional problem sets at the end of the course, except when they are making their revisions.

(And I never accept papers after the end of the course.)

Answer by Joel David Hamkins for What would remain of current mathematics without axiom of power set?

2013-06-13T12:58:46Z

Several standard theories intensely studied by set theorists do not have the power set axiom.

One of these is the theory ZFC without the power set axiom, usually denoted $\text{ZFC}^-$. One should take care with the proper axiomatization of this theory, as we discuss in What is the theory ZFC without the powerset?, V. Gitman, J.D. Hamkins, T. Johnstone; the main point being that one should use collection+separation and not just replacement, since these are no longer equivalent without the power set axiom.

Part of the attraction of $\text{ZFC}^-$, which is much stronger than the theory KP discussed below, but still lacks power set, is an abundance of natural models, such as the following:

HC, the universe of hereditarily countable sets. This is the land of the countable, where everything is countable. The sets in HC are precisely those sets that are countable and have only countable members and members-of-members and so on. Quite a bit of mathematics can be fruitfully undertaken in HC.
More generally, $H_{\kappa^+}$, the universe of sets of hereditarily size at most $\kappa$. This universe satisfies $\text{ZFC}^-$, but can have some power sets, namely, as long as the power set has size at most $\kappa$. But meanwhile, there is a largest cardinal in this univese, $\kappa$ itself, and the powerset of $\kappa$ does not exist.
More generally, $H_\delta$ for any regular cardinal $\delta$. When $\delta$ is an inaccessible cardinal, this is the same as $V_\delta$, the rank initial segment of the universe in the von Neumann hierarchy, and in this case it is a model of ZFC and a Grothendieck universe.

These models and other models of $\text{ZFC}^-$ are used in arguments throughout set theory, from iterated ultrapowers in large cardinals to their use in forcing axioms and elsewhere.

Another commonly studied theory without the power set axiom is Kripke-Platek set theory KP, which is a very weak set theory at the heart of the subject known as admissible set theory, in which an enormous amount of classical mathematics can be undertaken. There are numerous natural models of KP, such as:

The hyperarithmetic universe $L_{\omega_1^{CK}}$, of sets that are coded by well-founded hyperarithemtic relations on the natural numbers. This is the smallest admissible set, the smallest transitive model of KP. One interesting thing about this world is that every ordinal is not only hyperarithmetic, but actually computable.
There are many other admissible ordinals $\alpha$, ordinals for which $L_\alpha\models$KP.
One can relativize the admissibility concept to oracles $x$, forming $\omega_1^x$, the least admissible ordinal in $x$, so that $L_{\omega_1^x}[x]$ is the smallest model of KP containing $x$.
The universes $L_\lambda$ and $L_\zeta$ arising in the theory of infinite time Turing machines, where $L_\lambda$ is the collection of sets coded by a well-founded infinite-time writable relation on $\omega$, and $L_\zeta$ are the sets coded by a well-founded infinite-time eventually writable relation. These universes both satisfy natural strengthenings of KP, but not the power set axiom.

And there are numerous other set theories without the power set axioms, including various strengthenings of KP that still lack the power set axiom and have natural models that are used for various purposes.

All these models are intensely studied, and set theorists pay detailed attention to what is or is not possible to achieve in the models, depending on how strong it is. The crux of many arguments is whether the given model is strong enough to undertake a given set-theoretic construction or not. For example, one will often pay attention to the details of a mathematical construction to find out if it can be performed using only $\Sigma_1$-collection instead of, say, $\Sigma_2$-collection, in order to know whether or not it can be performed inside one of these models.

Let me add that although set theorists are giving enormous attention to these set theories without the power axiom, the reason isn't usually because of doubt about the truth of the power set axiom, but rather it is just that they want to undertake certain constructions inside these natural models, and so they need to know whether these models are strong enough to undertake that construction or not.

So one can be interested in set theory without the power set axiom without having doubt about that axiom. We study set theories without power set, while retaining it in our main background theory, because we want to know what is possible to achieve without power sets in those models.

Lastly, concerning your remarks about definability, I refer you as I mentioned in the comments to an answer I wrote to a similar proposal, which I believe show that naive treatment of the concept of definability is ultimately flawed.

Answer by Joel David Hamkins for Game of Chess and axiomatic systems

2013-06-12T12:58:57Z

Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of phenomenon you seek in Q1, Q2 and Q3 does seem to occur in the context of infinite chess, where one plays from a finite position on an infinite board. This would be a somewhat vaster state space than you had suggested, since it is infinite, but the argument that Steven mentions shows that an infinite state space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

Is there any superstable configuration in the game of life?

2013-06-04T00:58:31Z

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.

There are numerous configurations in the game of life that are known to be stable---such as blocks, beehives, blinkers and toads---in the sense that if they appear on an otherwise empty board or on part of the board that remains otherwise empty, then they will persevere (or at least reappear on some period) into the indefinite future. All of the common examples of such configurations, however, seem to disintegrate when placed into a hostile environment; when they are hit by a glider or other spaceship, for example, these common stable configurations can be completely ruined.

My question is whether there is any superstable configuration, which can survive even in any hostile environment.

Question 1. Is there any superstable configuration in the game of life?

Specifically, let us define that a finite configuration is superstable, if it can survive in any environment, no matter how hostile, meaning that if it should ever appear on the board, then it will definitely reappear later in exactly that same position, regardless of what else is happening on the board. Perhaps the position is somehow isolated, absorbing whatever is happening around it; or perhaps it is a strong source of some kind, spewing out gliders or other objects, regardless of what else is around it; or perhaps it is some core surrounded by encircling vacuum-cleaners, traveling patterns that sweep up whatever might interfere.

This question is related to Gil Kalai's, in that if there are such superstable configurations, then we will expect that the infinite random position will have them with some (albeit very small) density, which will enable us to prove lower bounds on the density of the expected living infinite random position.

One can also imagine a glider version of superstability, where the pattern survives, but with some nonzero displacement:

Question 2. Is there any superstable glider?

That is, is there a finite pattern that, regardless of the environment in which it is placed, will repeat itself at some future time with some displacement? A strong form of such a superstable glider would ask also that it be a vacuum cleaner, meaning that it glides around in any given environment while leaving only empty cells in its wake.

Question 2b. Is there a superstable glider vacuum?

I can imagine a small glider that erases everything in its path; or perhaps there is a kind of moving wall, which steadily pushes against whatever it faces, leaving emptiness behind. If there were such a superstable glider vacuum that also moved in a definite direction, then of course there could be no superstable stationary position, since otherwise we could vacuum it up.

Another alternative would seem to be that every finite configuration in the game of life is destructible, in the sense that one can design for it an especially hostile environment, leading to eventual death.

Question 3. Is every finite configuration destructible?

In other words, can every finite configuration in the game of life be extended to a larger configuration whose development leads in finite time to a position with no living cells? A weaker version of this would ask merely that the configuration be extended to a configuration such that eventually, the original configuration does not recur on any subportion of the board.

Answer by Joel David Hamkins for Trivial forcings which are not very trivial

2013-06-10T11:16:58Z

It is a standard result (e.g. Jech's Set Theory, lemma 15.43) that every intermediate model $W$ of ZFC with $M\subset W\subset M[G]$ has the form $W=M[G\cap\mathbb{C}]$ for some complete subalgebra $\mathbb{C}$ of the complete Boolean algebra $\mathbb{B}$ for the forcing giving rise to $G$.

In particular, since $x\subset M$ we know that $M[x]\models \text{ZFC}$, and so in particular there is a partial order $P\in M$ which (we can easily arrange) is nontrivial and adds $x$ via $G\cap P$. This achieves nontriviality and relevance (2 and 3).

Now, my observation is that your triviality condition 1 is also easy to obtain by modifying $P$, to add a single new atom below every element of $P$, but with a node that is not in $M$. For example, in $M[G]$, let $P^+$ be the poset $P$ together with a new atom, $G$, considered as a single point below every element of $P$. So $P^+$ is atomic, and hence trivial, but $P^+\cap M=P$, which satisfies your requirements in 2 and 3.

So the answer is yes.

Answer by Joel David Hamkins for Research topics restricted to students at top universities?

2013-06-07T00:31:45Z

Perhaps your advisor had meant merely that the group who work in area B are very strong and have a rich knowledge, and it is difficult for outsiders to enter into or compete with that group because they won't have risen to the high expertise to which that group had brought itself? You seem to present the issue as one of political intrigue and exclusion, but it may not be like this at all. There are surely many mathematical groups, who by working intensely on a focused topic bring themselves to a high level of expertise on that topic. If this is the situation, then it would seem by your other remarks that you can make contacts with that group and begin to study with them and thereby involve yourself in their expertise.

That said, I also believe that it is wise to listen to one's advisor's suggestions about topics of investigation. It may be that your advisor simply feels that he will not be able to help you as much in area B, simply because he doesn't himself have the knowledge necessary to guide you in that area. Thus, your plan to work in area B is essentially amounting to not working with your current advisor, and instead having only an email advisor, who may not ultimately give you the attention that you will want and need later on, and that may not be the best situation. But if there is someone in that group who can server as your mentor, then it may work out.

Regarding questions (i), I think this kind of concern is likely misplaced. In my experience, any mathematician with talent will eventually be recognized for it, regardless of whatever connections they may or may not have.

Answer by Joel David Hamkins for A Question Regarding the Relation Between 0-sharp and Koepke's Bounded Truth Predicate.

2013-06-06T22:19:45Z

The answer is no, one can have models of ZFC set theory with a definable truth predicate for first-order truth in $L$, but without having $0^\sharp$.

One way to build such a model is like this. In Kelly-Morse KM set theory, you can prove the existence of a truth predicate for first-order truth for the whole universe $V$, and then by forcing you can code this class into the GCH pattern, for example, in order to make it definable. The result is a forcing extension $V[G]$ which has a first-order definable class predicate for first-order truth in the ground model $V$. From this, one can easily define a truth predicate for first-order truth in $L$.

But meanwhile, KM is weaker than $0^\sharp$ in consistency strength, and so we can find such a model $V$ and hence also $V[G]$ without $0^\sharp$. The theory KM is weaker than $0^\sharp$ because its consistency follows from the existence of a single inaccessible cardinal: if $\kappa$ is inaccessible, then $V_\kappa$ is a model of KM when equipped with its full second-order part $V_{\kappa+1}$. In contrast, $0^\sharp$ implies the consistency of a proper class of inaccessible cardinals (and more), since under $0^\sharp$ the Silver indiscernibles are all inaccesible in $L$.

This kind of example shows another direct way to build the desired model. Start with $\kappa$ inaccessible. So $V_\kappa$ is a model of ZFC, and remains a model of ZFC(S) even when we add the satisfaction class S for first-order truth in $V_\kappa$. Now we may force to make S definable in a forcing extension $V_\kappa[G]$. In $V_\kappa[G]$, we have a definable class for first-order truth in $V_\kappa$, from which we can define satisfaction in its $L$. But we needn't have $0^\sharp$, since in fact we could have started with $V=L$.

Answer by Joel David Hamkins for Class forcing: Pelletier vs Friedman

2013-06-06T12:43:39Z

Since you are interested in comparing various approaches to class forcing, I would recommend that you also take a look at the dissertation of Jonas Reitz, which has an extended, detailed appendix presenting class forcing for both ZFC and GBC models. Reitz follows a line similar to the Pelletier approach, defining the extension in the case that the class partial order $\mathbb{P}$ is a tower of complete set-sized subposets, using these subposets to stratify the final model in way that is fundamentally similar to what you describe.

Ultimately, the main focus for Reitz is on the class forcing notions $\mathbb{P}$ that are what he calls progressively closed, meaning that for every cardinal $\delta$, the forcing has a complete subposet---in particular, a set---whose quotient is forced to be $\lt\delta$-closed (see the details in his dissertation). This kind of forcing is particularly nice, in that every set that is added by the full class forcing is also added by some set-sized complete subposet, and the hypothesis allows one to handle various arguments much more easily than otherwise. Furthermore, many of the most natural class forcing notions that arise in set theory are in fact progressively closed, such as the canonical forcing of the GCH, the forcing of V=HOD by coding sets into the GCH pattern, the universal Laver preparation, Easton forcing to control the GCH pattern and many others.

The important fact about progressively closed class forcing is that, as Reitz proves, the corresponding forcing extensions by them will always satisfy ZFC and even GBC.

One must make some kind of extra assumption like that, even in the Pelletier approach, where $\mathbb{P}$ is a tower of complete subposets, since otherwise one may not have ZFC in the extension. To see this, consider the case of adding ORD many Cohen reals, which stratifies very nicely in just the way you describe in your question (although it is not progressively closed), but which does not have ZFC in the extension, since even power set will fail at $\omega$---the set of reals in the resulting model will form a proper class!

The Friedman approach is aimed at a more general situation, where he is specifically interested in class forcing that is not progressively closed, and which admits no stratification of the sort for which you are looking. For example, a motivating instance for him, I believe, is the case of Jensen's "coding the universe" forcing, which is definitely not progressively closed, and has the property that it adds sets that are not generic for any set-sized poset in the ground model. Because of this more general setting, he has to pay attention to when the forcing relation will be definable with respect to the class forcing notion, and when the partial order will ensure the power set axiom, and these are the issues at which the tameness concepts are aimed.

The main difficulty with attempting to use a purely Boolean-valued model approach with class forcing is that one generally doesn't actually have a complete Boolean algebra in this context. The reason is that one usually conceives of a forcing notion first and most naturally as a partial order $\mathbb{P}$, rather than as a Boolean algebra. When this is a set, it is a simple matter to take the Boolean completion $\mathbb{B}$, for example as the regular open algebra, and so working with $\mathbb{P}$ or $\mathbb{B}$ makes little difference. But when the forcing partial order $\mathbb{P}$ is a proper class, then it may not be possible to find a completion of $\mathbb{P}$ in any suitable sense. Generally, objects in the completion correspond to antichains in the partial order, and the collection of all (class-sized) antichains may not itself be a class; they are too big themselves and there are too many of them.

For this reason, one is tempted to extend the universe upward, adding extra layers on top, so that one can make sense of the forcing in a set-theoretic context, but the difficulty is that one cannot always expect to extend the universe upward in that way while retaining a nice theory.

Answer by Joel David Hamkins for Ontological status of some "sets" in ZFC

2013-06-04T23:50:26Z

Although you've been given a hard time in the comments, I think that this is actually a serious question in the philosophy of mathematics, whose answer depends on one's philosophical position concerning the nature of mathematical truth.

What is the nature of existence for the mathematical objects that we define?

There are a variety of natural positions to stake out, so let me describe at least a few of them. There are of course many more; I mention several perspectives specifically on CH in my answer to Gil Kalai's question on solutions to the continuum hypothesis, which you may find relevant.

As you describe the example, the puzzling thing here is that you seem to have defined a fairly simple set, yet we also find ourselves unable to answer some fairly simple questions about it, such as whether it has one or two elements. To my way of thinking, the philosophical question about the ontological status of your set is very similar to the philosophical question about the ontological status of the truth of $\phi$ itself; the two simply go together. So we could ask the question like this:

When a statement $\phi$ is independent of ZFC, what is the ontological status of the truth of $\phi$?

For example, does it still make sense to say that $\phi$ is definitely true or false, but definitely only one of these? Ontology has to do with the nature of reality---in our case, mathematical reality---independently of, say, our knowledge about it. But provability and non-provability (and thus independence) seem to have to do with our ability to know certain things, and thus relate to epistemological rather than ontological concerns.

Let me describe a few of the philosophical positions that are commonly held about this kind of question.

Traditional set-theoretic Platonism. On the traditional Platonist view, sets exist in a unique real Platonic realm---the realm consisting of all sets---and every set-theoretic assertion has a definitive truth value in this realm. On this account, there is a fact of the matter about whether CH is true or false, or whether your assertion $\phi$ is true or false. On this account, the set you have described is either in fact identical to $\{1\}$ or is identical to $\{1,2\}$. The fact that $\phi$ is independent of the ZFC axioms merely illustrates our lack of knowledge about which one of these sets you have actually described. On this account, the set is definitely one of them or the other, depending on whether it is the case that $\phi$ is true or not, and exactly one of these is the case. The independence of $\phi$ is an irrelevant distraction from whether $\phi$ is true. On this view, the pervasive independence phenomenon is seen as a side-show about our epistemological weakness---the weakness of our theories---rather than indicating any issue about the singular nature of mathematical truth.

Formalism. On this view, there is no realm of real existence for mathematical objects like sets, and rather the mathematical process consists of the manipulation of sequences of symbols, such as the definition in your question. On this view, assertions of existence in mathematics are merely a way of speaking, and no actual existence of mathematical objects is being asserted. Formalism thus trivializes the ontology of the mathematical objects that mathematics is about.

Plural realism, or the multiverse view. On the plural realist or multiverse conception of set-theoretic truth, one holds that there are diverse concepts of set, each giving rise to its own set-theoretic universe, a plurality of set-theoretic worlds with their own set-theoretic truth, but which can be connected in various ways, such as by forcing or by large cardinal embeddings. On this account, your sentence $\phi$ may be true in some of these worlds and false in other worlds, and your set will accordingly change its nature depending on the current set-theoretic background concept of set under which it is being interpreted. You can read more about the multiverse perspective in set theory in some of my recent papers, especially "The set-theoretic multiverse", RSL 2012.

Answer by Joel David Hamkins for $L_{\omega_1,\omega}$ sentence with many automorphism in $\aleph_0$ and few automorphism in $\aleph_\omega$

2013-05-29T22:51:31Z

It appears that we can already do this in first-order logic, without making any use of the infinitary language.

Namely, the unique countable endless dense linear order $\langle\mathbb{Q},\lt\rangle$ has continuum many order automorphisms, but Shelah has reportedly proved that for every uncountable cardinality $\lambda$, there is a rigid endless dense linear order of cardinality $\lambda$, that is, having a trivial automorphism group. (See the remarks on page 347 of this article; perhaps someone can give a better reference.) In particular, there will be an endless dense linear order of size $\aleph_\omega$ with no nontrivial automorphisms at all.

Answer by Joel David Hamkins for Pointwise algebraic models of set theory

2011-07-29T00:57:25Z

Update, May 27, 2013. Cole Leahy and I have now written a joint paper arising from issues originating in this question, and here is an excerpt from the post I made on my blog about it, which is adapted from the introduction of the paper.

J. D. Hamkins and C. Leahy, Algebraicity and implicit definability in set theory (also at the arxiv), under review.

We aim in this article to analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity and its companion concept of implicit definability. In place of the class HOD of hereditarily ordinal definable sets, for example, we consider the class HOA of hereditarily ordinal-algebraic sets. In place of the pointwise definable models of set theory, we examine its (pointwise) algebraic models. And in place of Gödel's constructible universe L, obtained by iterating the definable power set operation, we introduce the implicitly constructible universe Imp, obtained by iterating the algebraic or implicitly definable power set operation. In each case we investigate how the change from definability to algebraicity affects the nature of the resulting concept. We are especially intrigued by Imp, for it is a new canonical inner model of ZF whose subtler properties are just now coming to light. Open questions about Imp abound.

Before proceeding further, let us review the basic definability definitions. In the model theory of first-order logic, an element $a$ is definable in a structure $M$ if it is the unique object in $M$ satisfying some first-order property $\varphi$ there, that is, if $M\models\varphi[b]$ just in case $b=a$. More generally, an element $a$ is algebraic in $M$ if it has a property $\varphi$ exhibited by only finitely many objects in $M$, so that $\{b\in M \mid M\models\varphi[b]\}$ is a finite set containing $a$. For each class $P\subset M$ we can similarly define what it means for an element to be $P$-definable or $P$-algebraic by allowing the formula $\varphi$ to have parameters from $P$.

In the second-order context, a subset or class $A\subset M^n$ is said to be definable in $M$, if $A=\{\vec a\in M\mid M\models\varphi[\vec a]\}$ for some first-order formula $\varphi$. In particular, $A$ is the unique class in $M^n$ with $\langle M,A\rangle\models\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, in the language where we have added a predicate symbol for $A$. Generalizing this condition, we say that a class $A\subset M^n$ is implicitly definable in $M$ if there is a first-order formula $\psi(A)$ in the expanded language, not necessarily of the form $\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, such that $A$ is unique such that $\langle M,A\rangle\models\psi(A)$. Thus, every (explicitly) definable class is also implicitly definable, but the converse can fail. Even more generally, we say that a class $A\subset M^n$ is algebraic in $M$ if there is a first-order formula $\psi(A)$ in the expanded language such that $\langle M,A\rangle\models\psi(A)$ and there are only finitely many $B\subset M^n$ for which $\langle M,B\rangle\models\psi(B)$. Allowing parameters from a fixed class $P\subset M$ to appear in $\psi$ yields the notions of $P$-definability, implicit $P$-definability, and $P$-algebraicity in $M$. Simplifying the terminology, we say that $A$ is definable, implicitly definable, or algebraic over (rather than in) $M$ if it is $M$-definable, implicitly $M$-definable, or $M$-algebraic in $M$, respectively. A natural generalization of these concepts arises by allowing second-order quantifiers to appear in $\psi$. Thus we may speak of a class $A$ as second-order definable, implicitly second-order definable, or second-order algebraic. Further generalizations are of course possible by allowing $\psi$ to use resources from other strong logics.

The main theorems of the paper are:

Theorem. The class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets: $$\text{HOA}=\text{HOD}.$$

Theorem. Every pointwise algebraic model of ZF is a pointwise definable model of ZFC+V=HOD.

In the latter part of the paper, we introduce what we view as the natural algebraic analogue of the constructible universe, namely, the implicitly constructible universe, denoted Imp, and built as follows:

$$\text{Imp}_0 = \emptyset$$

$$\text{Imp}_{\alpha + 1} = P_{imp}(\text{Imp}_\alpha)$$

$$\text{Imp}_\lambda = \bigcup_{\alpha < \lambda} \text{Imp}_\alpha, \text{ for limit }\lambda$$

$$\text{Imp} = \bigcup_\alpha \text{Imp}_\alpha.$$

Theorem. Imp is an inner model of ZF with $L\subset\text{Imp}\subset\text{HOD}$.

Theorem. It is relatively consistent with ZFC that $\text{Imp}\neq L$.

Theorem. In any set-forcing extension $L[G]$ of $L$, there is a further extension $L[G][H]$ with $\text{gImp}^{L[G][H]}=\text{Imp}^{L[G][H]}=L$.

Open questions about Imp abound. Can $\text{Imp}^{\text{Imp}}$ differ from $\text{Imp}$? Does $\text{Imp}$ satisfy the axiom of choice? Can $\text{Imp}$ have measurable cardinals? Must $0^\sharp$ be in $\text{Imp}$ when it exists? (An affirmative answer arose in conversation with Menachem Magidor and Gunter Fuchs, and we hope that $\text{Imp}$ will subsume further large cardinal features. We anticipate a future article on the implicitly constructible universe.) Which large cardinals are absolute to $\text{Imp}$? Does $\text{Imp}$ have fine structure? Should we hope for any condensation-like principle? Can CH or GCH fail in $\text{Imp}$? Can reals be added at uncountable construction stages of $\text{Imp}$? Can we separate $\text{Imp}$ from HOD? How much can we control $\text{Imp}$ by forcing? Can we put arbitrary sets into the $\text{Imp}$ of a suitable forcing extension? What can be said about the universe $\text{Imp}(\mathbb{R})$ of sets implicitly constructible relative to $\mathbb{R}$ and, more generally, about $\text{Imp}(X)$ for other sets $X$? Here we hope at least to have aroused interest in these questions.

Original answer:

It is a very nice question.

If you restrict to well-founded models, and this includes your $L_\alpha$ examples, then a model is pointwise definable if and only if it is pointwise algebraic. The forward implication is clear. For the backward implication, suppose that $M$ is pointwise algebraic; let us prove that $M$ is pointwise definable by induction on rank. Consider any element $a$, and assume all sets of lower rank are definable in $M$. Since $M$ is algebraic, there is a definable finite collection $a_0,a_1,\ldots, a_n$ that includes $a=a_0$, with this set of minimal finite size. These sets must all have the same rank, since otherwise we could make a smaller definable family including $a$, and so all their elements are definable. Thus, if $a\neq a_i$, there must be some element in one of them that is not in the other. But that element is definable, and so we can again make a smaller family by adding to the definition the requirement that the set must contain (or omit, whatever $a$ does) that new element. This would make a smaller definable set, violating the minimality of the finite set, unless indeed our minimal set had only one element. So $a$ is definable after all.

This argument works only in well-founded models, however, since the induction is not internal.

Update. In a conversation with Leo Harrington at math tea here at the National University of Singapore, where I am visiting, we worked out the general ZFC case with the following observation:

Theorem. Every pointwise algebraic model of ZFC is pointwise definable.

Proof. Suppose that $M\models\text{ZFC}$ and is pointwise algebraic. Note that this implies that every ordinal of $M$ is definable, since if we can define a finite set of ordinals containing some ordinal $\alpha$, then since the ordinals are definably linearly ordered, $\alpha$ is the $k^{th}$ member of that set and hence definable. Now, we argue that every set $A$ of ordinals in $M$ is pointwise definable. Well, since $A$ is algebraic, it is a member of a finite definable set. But the lexical order on sets of ordinals is definable and linear, and so again we may find a definition of $A$, since it will be the $k^{th}$ element in that finite set for some $k$. Thus, every set of ordinals in $M$ is definable in $M$. But by ZFC, every set $a$ is coded by a set of ordinals, and since that set of ordinals is definable, it follows that the original set $a$ is also definable. Thus, every set in $M$ is definable without parameters. QED

After this, I realized that we can actually omit the use of choice.

Corollary. Every pointwise algebraic model of ZF is a pointwise definable model of ZFC+ V=HOD.

Proof. Suppose that $M\models\text{ZF}$ and is pointwise algebraic. It follows as in the theorem above that every ordinal of $M$ is definable without parameters. Thus, every object in the HOD of $M$ is also definable in $M$ without parameters. If $M$ is not equal to its HOD, then let $A$ be an $\in$-minimal element of $M-\text{HOD}$. Since $A$ is algebraic, there is a finite definable set containing $A$. By minimality, every element of $A$ is in HOD, and so we have a definable well-ordering on the elements of the members of the definable set containing $A$. Thus, there is a definable linear ordering (induced from the lexical order on the definable HOD order) on the subsets of HOD, and so $A$ is the $k^{th}$ element of the finite definable set for some finite $k$, and so $A$ is definable in $M$ without parameters. In this case, since $A\subset\text{HOD}$, it would mean that $A$ should be an element of HOD, contrary to assumption. Thus, $M=\text{HOD}^M$, and so $M$ is a model of ZFC+V=HOD, and also pointwise definable by the theorem.QED

Answer by Joel David Hamkins for Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

2013-05-26T20:19:59Z

The answer is yes in ZFC. We can construct a dense infinite set $A\subset\mathbb{R}$ such that the only order-preserving map $f:A\to A$ is the identity. In particular, $A$ is not order-isomorphic with any proper subset of itself.

To see this, note first that any order-preserving map $f:B\to\mathbb{R}$ defined on a dense set $B\subset\mathbb{R}$ can be extended to a total order-preserving map $\bar f:\mathbb{R}\to\mathbb{R}$ defined on the closure of $B$, by defining $\bar f(x)=\sup_{y\leq x, y\in B}f(y)$. Further, note that any such monotone map will have at most countably many points of discontinuity, since every discontinuity will be a jump discontinuity. Thus, there are precisely continuum many such order-preserving functions $\mathbb{R}\to\mathbb{R}$, since any one of them is determined by countably much information about their values on a countable dense set and the information about what their values are on the countably many points of discontinuity.

We may therefore enumerate all order-preserving functions $f_\alpha:\mathbb{R}\to\mathbb{R}$ in a sequence of length continuum, $\alpha\lt\mathfrak{c}$.

Let's now build the set $A$ by a transfinite process, making promises at each stage about some reals being definitely in $A$ and other promises about keeping some reals out of $A$, in such a way that we kill off $f_\alpha$ at stage $\alpha$ as a possible order-preserving map from $A$ to $A$. We may begin at stage $0$ by placing all the rational numbers into $A$, so that it will definitely be dense. Suppose we have carried out our process up to stage $\alpha$, and $f_\alpha$ is the next non-identity order-preserving map $\mathbb{R}\to\mathbb{R}$ presented for our consideration. Since $f_\alpha$ is order-preserving and not the identity, it must be that there is an interval $(a,b)$ with $(f(a),f(b))$ disjoint from $(a,b)$. Since we've made fewer than continuum many promises so far, there must be an $x\in (a,b)$ such that we've made no promises about $x$ or $f_\alpha(x)$. In this case, we place $x$ into $A$ and promise to keep $f_\alpha(x)$ out of $A$. This will prevent $f_\alpha$ from being an order-isomorphism of $A$ to a proper subset of $A$.

The end result is that $A$ is dense, but is strongly rigid in the sense that there is no non-identity order-preserving map from $A$ to $A$. In particular, $A$ is not order-isomorphic with any proper subset of itself.

Answer by Joel David Hamkins for Closure of one relation w.r.t other

2013-05-25T02:22:12Z

(This is more of a comment than an answer, but too long for the comment box.)

Your property is saying precisely that $[(R\circ R')\upharpoonright\text{dom}(R)]\subseteq R$.

I'm not sure I like your "closure" terminology, since that suggests that you start with a relation, and then close it. But there are in general many relations $R$ that satisfy your property with a given relation $R'$. For example,

the empty relation $R$ has your property with respect to any $R'$.
similarly, the full relation $R$ also has this property.
Also, if $R$ is the transitive closure of $R'$, then this property holds.

So you do not seem to be starting with something and then taking a "closure", but rather asserting that the given relation $R$ is itself already closed under this kind of application with $R'$.

Answer by Joel David Hamkins for What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

2013-05-24T19:37:41Z

Let me get things started with some simple observations.

Note that given any countable sequence of functions $f_n$, we can by diagonalization construct a function eventually dominating all of them, $f(x)=\max_{n\leq x}f_n(x)$. It follows that we may by transfinite recursion construct an embedding of $\omega_1$ into your order: at successor stages, add one to the previous function; at limit stages, use the diagonalization just described.

So actually, since $\mathbb{R}$ is order-isomorphic to bounded intervals of itself, we can therefore also embed $\omega_1$ into the order many times, on top of one another. So this gives strictly larger ordinals mapping in.

More generally, the bounding number $\mathfrak{b}$ is the size of the smallest unbounded family of functions, and any family of size less than $\mathfrak{b}$ will be bounded above. Thus, the recursive construction actually shows that we can find an embedding of $\mathfrak{b}$ into $\mathbb{N}^{\mathbb{N}}$ under eventual domination. Thus, we also get strictly larger ordinals than $\mathfrak{b}$ embedding in, by using the bounded-interval trick again.

There are diverse independence results concerning the exact value of $\mathfrak{b}$. Under CH, it is the same as the continuum, of course, but when CH fails, it can be far larger than $\omega_1$.

Using Péter's idea, once we have a map from $\mathfrak{b}$ into the order, then we may conclude that the class of ordinals that map into the order is closed under sums of length $\mathfrak{b}$. Thus, any ordinal up to $\mathfrak{b}^+$ is is order-embeddable into $\mathbb{R}^\mathbb{R}$ under eventual domination. So $\mathfrak{b}^+$ is a lower bound for your desired ordinal.

I guess the same idea shows that whenever an ordinal $\kappa$ embeds in, then the class of ordinals will be closed under sums of length $\kappa$, and so all ordinals up to $\kappa^+$ will also map in. Thus, the smallest ordinal not embedding in must be a cardinal, and furthermore, it must be a regular cardinal for the same reason.

Update. It is relatively consistent that the answer is $\mathfrak{c}^+$, even when the continuum $\mathfrak{c}$ is very large, and much larger than $\mathfrak{b}$. The reason is that by forcing, we can undertake a very long forcing iteration of length $\kappa$ to add a dominating real at each stage, and thereby get a model with continuum $\kappa$, such that $\kappa$ embeds into the order (and so the smallest ordinal not embedding into the order is $\kappa^+$). Now, the point is that with further ccc forcing, we can make $\mathfrak{b}$ small or whatever we like, but meanwhile, we still have our old functions showing that $\kappa$ maps into the order.

How do the compact Hausdorff topologies sit in the lattice of all topologies on a set?

2010-02-19T21:09:20Z

This question is about the space of all topologies on a fixed set X. We may order the topologies by refinement, so that τ ≤ σ just in case every τ open set is open in σ. Equivalently, we say in this case that τ is coarser than σ, that σ is finer than τ or that σ refines τ. (See wikipedia on comparison of topologies.) The least element in this order is the indiscrete topology and the largest topology is the discrete topology.

One can show that the collection of all topologies on a fixed set is a complete lattice. In the downward direction, for example, the intersection of any collection of topologies on X remains a topology on X, and this intersection is the largest topology contained in them all. Similarly, the union of any number of topologies generates a smallest topology containing all of them (by closing under finite intersections and arbitrary unions). Thus, the collection of all topologies on X is a complete lattice.

Note that the compact topologies are closed downward in this lattice, since if a topology τ has fewer open sets than σ and σ is compact, then τ is compact. Similarly, the Hausdorff topologies are closed upward, since if τ is Hausdorff and contained in σ, then σ is Hausdorff. Thus, the compact topologies inhabit the bottom of the lattice and the Hausdorff topologies the top.

These two collections kiss each other in the compact Hausdorff topologies. Furthermore, these kissing points, the compact Hausdorff topologies, form an antichain in the lattice: no two of them are comparable. To see this, suppose that τ subset σ are both compact Hausdorff. If U is open with respect to σ, then the complement C = X - U is closed with respect to σ and hence compact with respect to σ in the subspace topology. Thus C is also compact with respect to τ in the subspace topology. Since τ is Hausdorff, this implies (an elementary exercise) that C is closed with respect to τ, and so U is in τ. So τ = σ. Thus, no two distinct compact Hausdorff topologies are comparable, and so these topologies are spread out sideways, forming an antichain of the lattice.

My first question is, do the compact Hausdorff topologies form a maximal antichain? Equivalently, is every topology comparable with a compact Hausdorff topology? [Edit: François points out an easy counterexample in the comments below.]

A weaker version of the question asks merely whether every compact topology is refined by a compact Hausdorff topology, and similarly, whether every Hausdorff topology refines a compact Hausdorff topology. Under what circumstances is a compact topology refined by a unique compact Hausdorff topology? Under what circumstances does a Hausdorff topology refine a unique compact Hausdorff topology?

What other topological features besides compactness and Hausdorffness have illuminating interaction with this lattice?

Finally, what kind of lattice properties does the lattice of topologies exhibit? For example, the lattice has atoms, since we can form the almost-indiscrete topology having just one nontrivial open set (and any nontrivial subset will do). It follows that every topology is the least upper bound of the atoms below it. The lattice of topologies is complemented. But the lattice is not distributive (when X has at least two points), since it embeds N₅ by the topologies involving {x}, {y} and the topology generated by {{x},{x,y}}.

Answer by Joel David Hamkins for Order type of the smallest set containing the identity function and closed under exponentiation

2013-05-22T23:31:20Z

This is a partial answer, and I am unsure about part of it.

I claim that these functions are well-ordered by eventual domination, and the order type is at most the ordinal $\epsilon_0$.

First, your collection of functions can be identified with the unary terms that give rise to them, the unary terms in the term algebra in the language you have presented, terms with one free variable $n$ in the language with only the binary exponentiation function symbol. Examples of such terms are the expressions that appear in your question.

$$(n^n)^n\ \ \ \ \ (n^{n^n})^{n^n}\ \ \ \ \ n^{n^n}\ \ \ \ \ (n^{n^n})^{n^{n^n}}$$

To any such expression $f(n)$, we may associate to it the ordinal $f(\omega)$, obtained by replacing the variable $n$ with the ordinal $\omega$ and interpreting the resulting expression using the natural arithmetic on ordinals, rather than the usual arithmetic. That is, we resolve $(a^b)^c$ as $a^{b\mathop{\sharp}c}$ using the natural product $b\mathop{\sharp} c$, which is a commutative version of ordinal multiplication.

$$(\omega^\omega)^\omega\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^\omega}\ \ \ \ \ \omega^{\omega^\omega}\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^{\omega^\omega}}$$

All these resulting ordinals have a finitary exponential representation using $\omega$, and therefore are less than epsilon naught $\epsilon_0$.

I claim that this correspondence respects eventual domination; in other words, the function given by term $f(n)$ is eventually dominated by the function given by term $g(n)$ if and only if $f(\omega)\lt g(\omega)$ as interpreted in natural ordinal arithmetic. (Note: the reason to use the symmetric multiplication arises from the fact that $(\omega^{\omega})^{\omega^\omega}=\omega^{\omega^{1+\omega}}=\omega^{\omega^\omega}$ with usual ordinal arithmetic, even though $(n^n)^{n^n}$ dominates $n^{n^n}$; but the natural ordinal arithmetic gives the right answer here.) This claim has an affinity with the usual analysis of the representation of ordinals below $\epsilon_0$ in terms of complete (hereditary) base $n$, as used in Goodstein's theorem. Basically, the eventual domination order is determined by what might be called the stack height of the term expression, and one reduces inductively to comparing the terms that arise as coefficients of that tallest stack. The value of an ordinal exponential expression of $\omega$ is determined in exactly the same way, and so these two orders agree.

If this is right, then the eventual domination order is indeed a well-order, and the order-type is at most $\epsilon_0$, as I claimed.

As to whether the order-type reaches $\epsilon_0$ or not, I'm unsure, but I suspect it is strictly less than $\epsilon_0$. The reason is that the ordinals $f(\omega)$ face a severe restriction in their representation in complete base $\omega$. The complication is that not every ordinal arises as $f(\omega)$ for a term in your algebra. For example, the ordinal $\omega^2\cdot 4+\omega^3\cdot99$ is less than $\epsilon_0$, but it does not arise as an ordinal $f(\omega)$ for any term in your algebra. The ordinals $f(\omega)$ seem to be restricted in their complexity, and so it is conceivable that the total order type might be less than $\epsilon_0$. Nevertheless, it is possible to get some natural number coefficients appearing, as with

$$(\omega^\omega)^\omega=\omega^{\omega^2}\ \ \ \text{ and }\ \ (\omega^{\omega^2})^\omega=\omega^{\omega^3},$$

which arise as the ordinals of the corresponding terms. Perhaps if one can percolate this phenomenon upward to get arbitrary hereditary base $n$ expressions eventually high up in the exponents, then the order type will be $\epsilon_0$.

Meanwhile, let me mention that if one had a slightly more generous algebra, allowing addition and the natural number constants (which would arise from the zero function via $1=\omega^0$), then the order type would be fully $\epsilon_0$, since every ordinal less than $\epsilon_0$ would arise as $f(\omega)$ for a corresponding term in the algebra in a completely natural way.

Answer by Joel David Hamkins for Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?

2013-05-22T03:16:06Z

The first thing to notice is that if ZF is consistent, then it is consistent with ZFC that what you call ProveLoop is actually decidable. The reason is that if ZF is consistent, then by the incompleteness theorem, it is consistent with ZFC that $\neg$Con(ZF), in which case everything is provable in ZF, in which case every program is in ProveLoop.

So in the proof that ProveLoop is undecidable, one needs to make an additional assumption about the reliability of the proofs in ZF to avoid this issue with the incompleteness theorem.

Meanwhile, under such a consistency assumption, ProveLoop is indeed equivalent to the halting problem.

Theorem. Assume Con(ZF). Then ProveLoop is Turing equivalent to the Halting problem.

Proof. Under the Con(ZF) assumption, it follows that whenever ZF proves that a program doesn't halt, then it really doesn't halt, since if it did halt, then this fact would also be provable, contrary to consistency.

Clearly ProveLoop is c.e. and hence reducible to the halting problem, as you pointed out. Conversely, let's reduce the halting problem to ProveLoop. Given any program $p$, we want to decide whether $p$ halts on a blank tape, using an oracle for ProveLoop.

Define a computable function $f$, so that $f(q)$ is the program such that, on trivial input, if $p$ halts on the blank tape, then $f(q)$ jumps into an immediate infinite loop, and otherwise, while waiting for $p$ to halt, the program $f(q)$ halts just in case it finds a proof that $q$ does not halt. By the recursion theorem, there is a program $r$ such that $r$ and $f(r)$ compute the same function, and we can find this $r$ effectively. Furthermore, by using the $r$ from the proof of the recursion theorem, we may also assume that ZF proves that $r$ and $f(r)$ compute the same function. Notice that it can't ever be that $r$ halts on account of finding a proof that $r$ does not halt, by our assumption which ensures the accuracy of proofs of non-halting, and so definitely $r$ does not halt in any case. Meanwhile, if $p$ halts, then $r$ does not halt, but for a trivial reason that will be provable in ZF, namely, the fact that $p$ halted; and otherwise, when $p$ does not halt, then $r$ will run forever, but this fact will not be provable (for if it were provable, then $r$ would halt, contrary to consequence of our assumption that such proofs are reliable). So what we have is exactly a reduction of the halting problem to ProveLoop, as desired. QED

Answer by Joel David Hamkins for Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

2013-05-19T10:20:13Z

No, in general, a true $\Delta^0_1$ assertion may not necessarily be provably $\Delta^0_1$ in a given theory. For example, assume $\text{Con}(\text{PA})$ is true, and consider the formula $\phi(a)$ asserting that $a=a$ and the formula $\psi(a)$ asserting that "$a$ is not the code of a proof of a contradiction in $\text{PA}$," which is expressible as saying that $a$ does not solve a certain specific diophantine equation.

Since we assumed there is no such proof, we have that $\exists a\ \psi(a)$ is equivalent to $\forall a\ \psi(a)$, since these are both true sentences. But there can be no proof of this equivalence in $\text{PA}$, if it is consistent, since $\text{PA}$ proves the former sentence, but if it were to prove the latter sentence, it would be proving its own consistency.

Answer by Joel David Hamkins for A question about large real closed fields

2013-05-18T19:13:40Z

If $\delta$ is the cofinality of an ordered field $F$, that is, the size of the smallest unbounded subset of $F$, then every point of $F$ fills a cut of type $(\delta,\delta)$. In other words, every point in $F$ is the limit of an increasing $\delta$ sequence from below and a decreasing $\delta$ sequence from above. One can see that this is true of $0$ by inverting the elements of a strictly increasing positive unbounded $\delta$ sequence; and then one can translate this sequence from $0$ to any other point for the general conclusion.

It follows that any set with a limit point must have size at least $\delta$, and consequently any set of size less than $\delta$ has no limit points in $F$.

It is easy to make fields of any desired cofinality, just by forming a chain of elementary extensions of that length, adding new points above at each step.

Answer by Joel David Hamkins for Does the generalized $\Delta$-system lemma imply some weak version of the GCH?

2013-05-17T00:23:55Z

It is a very nice question! The answer is yes, natural instances of the $\Delta$ system property, which hold under GCH, are in fact equivalent to the GCH.

Theorem. $\Delta(\omega_2,\omega_1)$ is equivalent to CH.

Proof: You've pointed out that CH implies the principle, since the hypothesis you mention for this case amounts to $\omega_1^{\lt\omega_1}<\omega_2$, which amounts to CH. So let us consider what happens when CH fails. Let $T=2^{\lt\omega}$ be the tree of all finite binary sequences, and label the nodes of $T$ with distinct natural numbers. Let $F$ be the subsets of $\omega$ arising as the sets of labels occuring on any of $\omega_2$ many branches through $T$. Thus, $F$ has size $\omega_2$, and any two elements of $F$ have finite intersection. I claim that this family of sets can have no $\Delta$-system of size $\omega_2$, and indeed, it can have no $\Delta$-system even with three elements. If $r$ is the root of $a$, $b$ and $c$ in $F$, then $r=a\cap b=a\cap c$, and so $a$ and $b$ branch out at the same node that $a$ and $c$ do, in which case $b$ and $c$ must agree one step longer, so $b\cap c\neq r$. QED

The same idea works for higher cardinals as follows:

Theorem. For any infinite cardinal $\delta$, we have $\Delta(\delta^{++},\delta^+)$ is equivalent to $2^\delta=\delta^+$.

Proof. If $2^\delta=\delta^+$, then your criterion, which amounts to $(\delta^+)^{\lt\delta^+}<\delta^{++}$, is fulfilled, and so the $\Delta$ property holds. Conversely, consider the tree $T=2^{\lt\delta}$, the binary sequences of length less than $\delta$. Let $F$ be a family of $\delta^{++}$ many branches through $T$, regarding each branch $b$ as a subset of $T$, the set of its initial segments. Each such branch has size $\delta$, since the tree has height $\delta$. But for the same reason as before, there can be no $\Delta$ system with even three elements, since the tree is merely binary branching, and so three distinct branches cannot have a common root. This contradicts $\Delta(\delta^{++},\delta^+)$, as desired. QED

Corollary. The full GCH is equivalent to the assertion that $\Delta(\delta^{++},\delta^+)$ for every infinite cardinal $\delta$.

Update. The same idea shows that the hypothesis you mention is optimal: one can reverse the lemma from the conclusion to the hypothesis.

Theorem. The following are equivalent, for regular $\kappa$ and $\mu\lt\kappa$:

$\Delta(\kappa,\mu)$
$\lambda^{\lt\mu}\lt\kappa$ for every $\lambda\lt\kappa$.

Proof. You mentioned that 2 implies 1, and this is how one usually sees the $\Delta$ system lemma stated. For the converse, suppose that $\lambda^{\lt\mu}\geq\kappa$ for some $\lambda\lt\kappa$. Since $\kappa$ is regular and $\mu\lt\kappa$, this implies $\lambda^\eta\geq\kappa$ for some $\eta\lt\mu$. Let $T$ be the $\lambda$-branching tree $\lambda^{\lt\eta}$, which has height $\eta$. Let $F$ be a family of $\kappa$ many branches through this tree, where we think of a branch as the set of nodes in the tree that lie on it, a maximal linearly ordered subset of the tree $T$. Each such branch is a set of size $\eta$. I claim that this family has no subfamily that is $\Delta$ system of size $\lambda^+$. The reason is that because the tree is $\lambda$-branching, if we have $\lambda^+$ many branches with a common root, then at least two of them must extend that root to the next level in the same way, a contradiction to it being a root. Thus, the failure of 2 implies the failure of 1, as desired. QED

Answer by Joel David Hamkins for Are the two meanings of "undecidable" related?

2013-05-16T10:44:22Z

To my way of thinking, the two notions of undecidability are closely related, and the associated undecidability phenomenon and independence phenomenon, which are both pervasive in mathematics, are deeply inter-twined.

The reason is that every Turing undecidable set is saturated with logical undecidability. If we describe a certain undecidable property of finite graphs, say, then there will be infinitely many specific finite graphs for which it will be logically undecidable, even with respect to very strong theories such as ZFC+large cardinals, whether that finite graph has the property or not. And similarly with any undecidable set $A$ and consistent c.e. theory $T$. This is because if almost all instances of "$n\in A$?'' were settled by $T$, then we would have a decision procedure for $A$, namely, on input $n$, search for a proof from $T$ whether $n\in A$ or not (and hard-code the finitely many exceptions).

So every Turing undecidable property is accompanied by a huge assortment of logically undecidable statements, assertions about whether particular objects have the property or not, which are independent of whichever fixed consistent background theory you care to adopt.

So although the two undecidability phenomenon are distinct, I find them to be deeply connected.

Answer by Joel David Hamkins for Validity in Kripke frames whose points are finite or infinite sequences

2013-05-11T11:05:21Z

It is an attractive idea, but unfortunately, it seems not to be true.

The reason is that we can have that every $R_n$ is nontrivial, in the sense that the relation sometimes holds between different two different sequences, but there is no path through these relations so that $R^\omega$ never holds between two different sequences. For example, let $D=\{0,1\}$, and when $n$ is even, let $R_n$ be the reflexive lexical order on binary sequences, but when $n$ is odd, let it be the reverse lexical order. Thus, $R_\omega$ will never hold except reflexively, since the initial segments of a two infinite sequence can't be related lexically in both directions unless they are equal.

In this case, the formula $\Box p\leftrightarrow p$ will be valid in $R_\omega$, but not in any $R_n$.

Another simple counterexample would occur where one $R_n$, say $R_{17}$, never holds, but all the other $R_n$'s always hold. In this case, $R_\omega$ will never hold, and so it's validities will agree with the validities of $R_{17}$, but not with any other $R_n$.

Answer by Joel David Hamkins for Forcing mildly over a worldly cardinal.

2013-05-07T22:18:16Z

I've got it! We can kill the worldliness of a singular worldly cardinals as softly as we like.

Theorem. If $\theta$ is any singular worldly cardinal, then for any natural number $n$ there is a forcing extension $V[G]$ in which $\theta$ remains $\Sigma_n$ worldly, but not worldly, meaning that $V_\theta^{V[G]}$ satisfies the $\Sigma_n$ fragment of ZFC, but not ZFC itself.

Thus, such worldly cardinals can be killed as softly as desired.

Proof. First, we may assume without loss that the GCH holds, by forcing it if necessary. Also, by forcing to collapse the cofinality of $\theta$ to $\omega$, which is small forcing with respect to $\theta$ and therefore preserves the worldliness of $\theta$, we may assume that $\theta$ has cofinality $\omega$.

I claim that in $V$, we may find a set $A\subset\theta$ that is $V_\theta$-generic for the class forcing $\text{Add}(\text{Ord},1)$ to add a Cohen subset of the ordinals over $V_\theta$. To see this, one simply finds ordinals $\theta_n$ with supremum $\theta$ such that $V_{\theta_n}\prec_{\Sigma_n} V_\theta$, and then diagonalizes with respect to the $\Sigma_n$-definable dense classes having parameters in $V_{\theta_n}$ when extending $A$ up to $\theta_{n+1}$. Even though the forcing is not even countably closed (since $\theta$ has cofinality $\omega$), nevertheless we can meet the dense class before the next higher reflecting cardinal since we've limited the complexity of the dense class. It follows that $\langle V_\theta,A,{\in}\rangle$ satisfies $\text{ZFC}(A)$, the theory of ZFC in which the class $A$ is allowed to appear as a predicate the in the replacement scheme.

Now let $\mathbb{Q}$ be the class forcing over $V_\theta$ to code $A$ into the GCH pattern. If $G\subset\mathbb{Q}$ is $V$-generic, then it follows that $V_\theta^{V[G]}=V_\theta[G]$ is a model of ZFC, and so $\theta$ is still worldly in $V[G]$.

But let me now modify the argument slightly, so as to preserve only some amount of worldliness, while killing the rest. The idea is to find a set $A$ in $V$ that is $\Sigma_k$-generic over $V_\theta$, but not fully generic for the definable dense classes in the first step, where $k$ is much larger than $n$. We can ensure that $\langle V_\theta,A,{\in}\rangle$ satisfies the $\Sigma_k$ fragment of $\text{ZFC}(A)$, but not all of $\text{ZFC}(A)$. This can be done by inserting coding information to reveal an unbounded $\omega$-sequence when restricted to the $\Sigma_{k+1}$ reflecting cardinals. In essence, one hides away the cofinal $\omega$-sequence within the complex set of $\Sigma_{k+1}$-reflecting cardinals. A very similar idea is used in the the final section of our paper J. D. Hamkins, D. Linetsky, J. Reitz, Pointwise definable models of set theory.

The point now is that if $k$ is sufficiently larger than $n$, then the $\Sigma_k$ genericity of $A$ will ensure that after one codes $A$ into the GCH pattern of $V[G]$, one still gets that $V_\theta^{V[G]}=V_\theta[G]$ will satisfy at least the $\Sigma_n$ fragment of ZFC. But it will not satisfy all of ZFC, because $A$ is definable in this model and $A$ reveals the unbounded $\omega$-sequence of ordinals. So in $V[G]$, the ordinal $\theta$ is $\Sigma_n$-worldly, but not worldly. QED

As observed earlier, we can extend this result to regular $\theta$ in the case that $\theta$ is measurable, simply by first performing Prikry forcing to singularie $\theta$ while preserving its worldliness, thereby reducing to the singular case above.

Update. But in general, we cannot get the result for all regular worldly cardinals, because if the result holds for a regular worldly cardinal $\theta$, then in fact $\theta$ must be measurable in an inner model. To see this, suppose that $\theta$ is a regular worldly cardinal, which is another way of saying that $\theta$ is inaccessible, and suppose that the conclusion of the result is true for $\theta$. It follows that there is a forcing extension in which $\theta$ is a strong limit cardinal but not worldly, and so in particular $\theta$ is not inaccessible, and thus it is singular in $V[G]$. In other words, we have a forcing extension $V[G]$ in which $\theta$ is a singular cardinal. But this implies by a covering lemma argument with the Dodd-Jensen core model (recently explained to me by Gunter Fuchs) that $\theta$ is measurable in an inner model. So we cannot expect to kill inaccessibility softly down to worldly non-inaccessbility for all inaccessible cardinals.

Answer by Joel David Hamkins for The Kunen inconsistency and definable classes

2013-05-03T16:53:24Z

My perspective on this issue is that there are a variety of ways to take the claim of the Kunen inconsistency, and we needn't pick a particular one as the only right one. Rather, we gain a fuller perspective of the result by understanding the full robust context including all of the interpretations.

Kunen proved his result in Kelly-Morse set theory, in large part in order that he could formalize what it means for a class function $j:V\to V$ to be (fully) elementary. In KM, we can prove that that there is a satisfaction class, a truth predicate for first-order truth, and with this class (which is definable) one can express the elementarity of $j$ as a single second-order assertion.
Meanwhile, using the observation (Gaifman) that any cofinal $\Sigma_1$-elementary embedding is $\Sigma_n$-elementary for any meta-theoretic natural number $n$, we can formalize the result in GBC as the claim that no class $j$ is a nontrivial cofinal $\Sigma_1$-elementary embedding. Thus, this kind of elementarity of $j$ becomes expressible as a first-order assertion about $j$.
We don't actually need full GBC, since for example global choice is not used, but only the usual AC for sets, and so this argument can be formalized in GB+AC.
But actually, we don't need the full second-order part of GB, but only the ability to refer to the class $j$. So we can formalize the argument in $\text{ZFC}(j)$, the theory using ZFC where the axioms of replacement is allowed to use formulas in which the class $j$ appears. (But we only insist on elementarity of $j$ in the language without $j$.) This theory is used and suffices to show, for example, that the supremum of the critical sequence $\lambda=\sup_n\kappa_n$ exists.
If one intends to rule out only definable class embeddings $j$, that is, ones which are classes in the ZFC sense of being first-order definable from set parameters, then as you mentioned, there is an easy argument ruling them out, and this argument does not use AC. I do not know any set theorist, however, who takes this result as an answer to the question of whether one can prove the Kunen inconsistency in ZF. Rather, this example reveals the issues of formalization, and shows us that it may be important to take more care in our formal treatment of the result.
Meanwhile, a purely first-order version of the Kunen inconsistency is formalizable in ZFC, with no talk of classes of any kind, as the claim that there is no nontrivial $j:V_{\lambda+2}\to V_{\lambda+2}$ for any $\lambda$. This version still uses AC, and it is open in ZF. It avoids the set/class issues underlying your question by noting that the Kunen inconsistency proof establishes more by restricting to $V_{\lambda+2}$. This set version of the result implies the full result in any set theory capable of showing that a purported class $j$ must have a closure point $\lambda$.
The wholeness axiom gets around the issue of the previous point by stating the theory ZFC + "$j:V\to V$ is nontrivial and elementary in the language with a function symbol for $j$. Elementarity is expressed by the scheme $\forall x[\varphi(x)\iff \varphi(j(x))]$.
Various weakenings and strengthenings of the wholeness axiom are realized by making further claims about $j$, such as whether it has a critical point, whether it moves an ordinal, etc. Also, one can make claims about the extent to which $j$ may appear in the ZFC axioms. Officially, $j$ is allowed in the separation axiom but not in replacement, and so models of WA are not able to prove the supremum of the critical sequence exists.
If one uses merely the model-theoretic concept of embedding, one would be considering $j:V\to V$ for which $x\in y\iff j(x)\in j(y)$. But now the point is that ZFC proves that there are nontrivial embeddings. For example, we can inductively define $j(y)=\{j(x)\mid x\in y\}\cup\{\{\emptyset,y\}\}$, and prove that this is a nontrivial embedding $j:V\to V$. (See my paper Every countable model of set theory embeds into its own constructible universe, to appear in the JML, for more information.)

I prefer to understand the Kunen inconsistency in the rich context of all these results, rather than pick just one perspective and say that that perspective is the right one.

Answer by Joel David Hamkins for Which $\omega_1$-trees are proper?

2013-05-02T23:40:52Z

Concerning your final question, it is consistent that there is a proper normal $\omega_1$-tree that is not Suslin. If $T$ is a Suslin tree, then we may build a new tree $T^+$, consisting of the all-zero branch, together with nodes branching off (at the first one), followed by a copy of $T$. This is proper as a notion of forcing, since it is locally c.c.c., which means that it is dense to move to a condition (off the all-zero branch), below which the forcing is c.c.c. So every generic extension via $T^+$ is actually a c.c.c. extension by $T$. The forcing $T^+$ is essentially $\omega_1$ many side-by-side copies of $T$, but organized into an $\omega_1$-tree. But $T^+$ is not Suslin, since it isn't even Aronzsajn.

If one doesn't insist on normality in the tree, then one can prove outright that there is a proper $\omega_1$ tree that is not Suslin as follows: consider the tree $S$ consisting of countable ordinal length binary sequences that never have a $0$ after a $1$. Thus, either they are identically $0$, or they are $0$ for some length, followed by some number of $1$s. This tree consists of the all-zero branch, with all-one branches branching off from it, like a comb with $\omega_1$ many prongs, each of length $\omega_1$. It is technically an $\omega_1$-tree, though not normal, and it is proper since it is trivial as a notion of forcing, but it is not Suslin, since it has many uncountable branches and uncountable antichains.

Update. In answer to your revised question, let me say that Martin's axiom rules out not only the existence of Suslin trees, but also rules out the existence of trees of your type.

Theorem. If $\text{MA}_{\omega_1}$ holds, then then there are no Aronszajn proper $\omega_1$-trees.

Proof. Suppose that $\text{MA}_{\omega_1}$ holds and suppose that $T$ is an Aronszajn $\omega_1$-tree. Consider the forcing $\mathbb{P}$ to specialize $T$. This forcing is c.c.c., consisting of finite partial specializing functions. Now, it follows by our MA assumption that there is a specializing function defined on the entire tree. Thus, the tree $T$ is actually special already. (I guess I am just arguing that under this MA assumption, every Aronszajn tree is special.) Now, the point is that no special Aronszajn tree can be proper, since forcing with the tree will collapse $\omega_1$. QED

Thus, it is consistent with ZFC that there are no trees of the type you seek. In contrast, let me observe one way that positive instances can occur.

Theorem. If there is a Suslin tree, then there is an Aronszajn proper normal tree that is not Suslin, just as you seek.

Proof: Let $T$ be a Suslin tree, and let $S$ be an Aronszajn tree. Let $A$ be a maximal uncountable antichain in $S$. Let us make a new tree $U$ by performing surgery on $S$, replacing the part of the tree beyond any node in $A$ with a copy of $T$. That is, if the trees grow downward, then above the antichain $A$, the tree $U$ looks like $S$, but below $A$, the tree $U$ consists of copies of $T$ rooted at each node of $A$. Thus, $U$ is not Suslin, since it still has $A$ as an antichain. It is normal, since any node in $U$ below an element of $A$ can be extended to an element of $A$ and then to any level in $T$ beyond that; and any node not below an element of $A$ is in a copy of $T$ above an element of $A$, and hence can be further extended. It is proper, since forcing with $U$ amounts to forcing with $T$, as $U$ is locally like $T$, since any condition can be refined to a condition below which the forcing looks just like something in $T$. In particular, the forcing again is locally c.c.c., and hence proper. Finally, $U$ is Aronszajn, since any branch in $U$ would either get into the $T$ part, and hence be a branch in $T$, which is impossible, or else stays below $A$, in which case it would be a branch in $S$, which is also impossible. So $U$ is Aronszajn proper normal tree that is not Suslin, making for a positive instance of the kind of tree you seek. QED

Answer by Joel David Hamkins for $n$-in-a-row game on $\mathbb{R}^2$

2013-05-01T20:01:47Z

I'll start things off by observing that this is what is known as an open game, since if player 1 wins, then the winning condition is satisfied after finitely many moves. It follows by the Gale-Stewart theorem that this game is determined: one of the players must have a winning strategy. In particular, the theory of transfinite ordinal game values is applicable, and so player 1's winning strategy, if it exists, will be the value-reducing strategy; and player 2's strategy, if it exists, will be the value-maintaining strategy.

But in truth, I expect that we'll be able to describe the strategy directly in detail...

Although you insisted that $n\gt 3$, the game of course makes sense for smaller values of $n$. When $n=1$, the first player wins on the first move. When $n=2$, the first player clearly can win on the second move. When $n=3$, the first player wins on or before his fourth move, as follows: player 1 plays his second move at the midpoint of the first two points, so that we have $A_1$ $A_2$ $B_1$ collinear. Player 2 must block by playing in between, to give $A_1$ $B_2$ $A_2$ $B_1$ on a line, and now player 1 plays off this line to make a triangle of possibilities, with two ways to win, but player 2 can only block one of them.

See ARupinski's comment for a solution in the case $n=4$.

Answer by Joel David Hamkins for Cohen algebra (generalization)

2013-04-27T21:16:35Z

Regarding question $1$, it seems that you want to know whether you've got the unique complete c.c.c. Boolean algebra with density $\kappa$. The answer is no.

On the one hand, the forcing notion $\text{Add}(\omega,\omega_1)$ to add $\omega_1$ many Cohen reals is c.c.c. and has density $\omega_1$. This is another way to describe your algebra in the case $\kappa=\omega_1$.

But meanwhile, forcing with a Suslin tree is also c.c.c. and has density $\omega_1$. But these two complete Boolean algebras are not isomorphic, since forcing with the Suslin tree adds no reals and in fact is $\leq\omega$-distributive, whereas clearly $\text{Add}(\omega,\omega_1)$ adds reals.

Of course, there may not be a Suslin tree, but consider the forcing to add a single Cohen real (which creates a Suslin tree), followed by the forcing to force with that Suslin tree. This is the iteration of two c.c.c. forcing notions, and is hence c.c.c., but under CH has density $\omega_1$. But this forcing is not isomorphic to $\text{Add}(\omega,\omega_1)$, since the latter forcing is absolutely c.c.c., but the former is not, as the branch through the Suslin tree creates an uncountable antichain in the extension.

One may omit the CH assumption by taking the case $\kappa=\mathfrak{c}$. That is, compare the forcing to add continuum many Cohen reals, versus the forcing to add this many Cohen reals, and afterwards also to force with the Suslin tree created by the first one. Both of these are c.c.c. and have density $\mathfrak{c}$, but they are not isomorphic since the former remains c.c.c. in the forcing extension and the latter does not.

Answer by Joel David Hamkins for L-systems and Sierpinski Triangle

2013-04-27T14:48:41Z

The $L$-system described in the Wikipedia page to which you link is:

variables : A B

constants : + −

start : A

rules : (A → B−A−B), (B → A+B+A)

angle : 60°

Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (otherwise the bases would alternate between top and bottom).

The way I think about this is that these rules express the fundamental fractal symmetry of the Sierpinski triangle, namely, the symmetry of the whole triangle with each of the three next-smaller triangles. If one images a "basic traverse" of the full main triangle to be traveling on a line segment from the bottom left to the bottom right, let us call this an A-move, for the fractal sits to our left as we make this move.

Thus, I would put two additional pictures before your four pictures, one consisting of a line segment at the bottom, and the next consisting of three movements, like half a hexagon, traversing one side each of the three next-smaller triangles.

If we consider replacing the basic A move with the moves arising from one level deeper in the fractal symmetry, then what we would do is follow that half hexagon, one edge each of the three next-smaller triangles: first going up on the left, then across to the right, then down at the right. Note that when we go up the (bottom half) of the left side of the big triangle, the corresponding triangle is on our right now, so this is a B move. But when we go across to the right, at the bottom of the top subtriangle, it is on our left, and then coming back down to the bottom right point, the third (lower-right) triangle is on our right. So we have replaced the basic A move (moving across the bottom of the full big triangle), with the moves B-A-B. Similarly, a B move would be replaced with A+B+A, with the corresponding interpretation of angle rotation (I believe it also makes sense to add an extra reorientation rotation at the start of this, but evidently this just gets canceled out.)

One could easily find other ways to make the traverse that would also express these fundamental symmetries, and arrive at different systems generating the Sierpinski triangle.

Answer by Joel David Hamkins for A question on cofinite topology.

2013-04-23T13:04:24Z

You should mean $\{x\}=\bigcap\xi$, and the answer is clearly yes, since we can take $\xi$ equal to the set of all open sets containing $x$. Any point $y$ other than $x$ is excluded in this intersection by the open set $X-\{y\}$. The cardinality of this $\xi$ is the same as the number of finite subsets of $X$, which is equinumerous with $X$. And the same will be true of any $\xi$ having your property, since the points other than $x$ must get excluded by elements of $\xi$, but only finitely many at a time, and so the cardinality of $\xi$ must be the same as $X$.

(This argument uses the axiom of choice, in order to know that the collection of finite subsets of an infinite set is equinumerous with that set. In $\neg$AC worlds, the situation is more complicated.)

Comment by Joel David Hamkins

2013-06-19T05:09:35Z

Small observation: if we perform an additional small forcing $\mathbb{R}$, then we can find such a $\mathbb{Q}$ inside $\mathbb{P}\ast\mathbb{R}$. The reason is that we can let $\mathbb{R}$ collapse $|\delta|^{V^{\mathbb{P}}}$ to $\omega$, which is small relative to $\delta$ in the ground model, and so the composition will collapse $\delta$ to $\omega$, placing it into the case you mention at the end of the question.

Comment by Joel David Hamkins

2013-06-19T02:24:51Z

Do you have a counterexample when you drop the $\mathbb{P}\subset V_\delta$ restriction?

Comment by Joel David Hamkins

2013-06-19T02:17:57Z

My point was that you were assuming a particular notation in the Turing machines, since in unary notation (where we represent $n$ by $n$ many $1$s), you can't just add a $0$ to the end as you said; instead, you have to double the number of $1$s appearing on the tape, which takes about the same time as doing the primitive recursive recursion.

Comment by Joel David Hamkins

2013-06-19T02:03:08Z

You seem to be using binary notation in your Turing computation, and the phenomenon of your example arises purely in the Turing context, when one compares Turing-machines with unary notation versus Turing machines with binary notation. The Turing time to compute $2x$ in unary notation is about the same as what you are calling the Goedel time for computing $2x$. Could you clarify your set-up more precisely? After all, Turing machines operate with finite strings, and primitive recursive functions (ordinarily) operate with natural numbers.

Comment by Joel David Hamkins

2013-06-18T23:49:11Z

Isn't this problem essentially equivalent to testing for linear independence? (That is, determining if a new binary vector is in the span of a collection of presumed-independent binary vectors.) That is, if we could do your problem quickly, then we could also test for dependence quickly, and vice versa, presumably exploiting the binary nature of the vectors in both cases.

Comment by Joel David Hamkins

2013-06-18T14:11:58Z

I think he means "accepted".

Comment by Joel David Hamkins

2013-06-16T04:11:02Z

And I guess (please excuse this trivial remark) one needs to say "nonempty" as well, since the empty graph is directed and acyclic, but has no sources or sinks.

Comment by Joel David Hamkins

2013-06-16T03:51:36Z

Aeryk, you can edit to change your first sentence to add the finiteness hypothesis, since it isn't true for all directed acyclic graphs. For example, the integers under the successor relation is a DAG with no sources or sinks.

Comment by Joel David Hamkins

2013-06-16T03:31:24Z

I guess you're talking only about finite directed acyclic graphs?

Comment by Joel David Hamkins

2013-06-15T00:54:31Z

Oh, I'm very sorry to hear that you aren't interested in logical proof or logical conclusions. I'll leave you alone, then, to undertake your own kind of proof activity.

Comment by Joel David Hamkins

2013-06-15T00:31:08Z

I think Mirac may be referring to the fact that the collection of standard numbers inside a nonstandad model, in the sense of nonstandard analysis, is not a set in the nonstandard world. The reason is that if the standard cut $\mathbb{N}$ of $\mathbb{N}^\ast$ existed in the nonstandard world, then it would reveal an inductive subset of $\mathbb{N}^\ast$, containing $0$ and closed under successor, which was not the whole of $\mathbb{N}^\ast$, which would contradict the fact that $\mathbb{N}^\ast$ satisfies induction in the nonstandard realm.

Comment by Joel David Hamkins

2013-06-14T03:02:51Z

Waldemar, I guess your estimates assume that we do no pruning at all, but of course, we can substantially prune the game tree, while remaining certain of our analysis, and this might considerably cut down on the complexity. (Also, could you explain the $10^123$ estimate?)

Comment by Joel David Hamkins

2013-06-14T02:57:44Z

My understanding of the noisy rules is that, with small probability, a cell can turn on or off regardless of its surroundings. So any finite position has some small chance of appearing, regardless of what else is there, and so this will happen infinitely many times.

Comment by Joel David Hamkins

2013-06-14T00:40:27Z

How does the Takeuti theory compare with the theory SO, the theory of sets of ordinals, introduced by Koepke and Koerwien, as in section 5 of this paper: math.uni-bonn.de/people/koepke/Preprints/…?

Comment by Joel David Hamkins

2013-06-13T23:19:42Z

And let me add that it is usually the weakest students who want only to write up an account of some Big Theorem, since what I am asking for otherwise is difficult. Sometimes it happens that a student doesn't pre-approve their topic with me, and submits a paper presenting a standard theorem written in their own way, but I'm usually disappointed.

User joel david hamkins - MathOverflow

Answer by Joel David Hamkins for What new primitive recursive functions are needed to reconcile Turing time complexity with Godel time complexity?

Answer by Joel David Hamkins for Nearly all math classes are lecture+problem set based; this seems particularly true at the graduate level. What are some concrete examples of techniques other than the "standard math class" used at the *Graduate* level?

Answer by Joel David Hamkins for What would remain of current mathematics without axiom of power set?

Answer by Joel David Hamkins for Game of Chess and axiomatic systems

Is there any superstable configuration in the game of life?

Answer by Joel David Hamkins for Trivial forcings which are not very trivial

Answer by Joel David Hamkins for Research topics restricted to students at top universities?

Answer by Joel David Hamkins for A Question Regarding the Relation Between 0-sharp and Koepke's Bounded Truth Predicate.

Answer by Joel David Hamkins for Class forcing: Pelletier vs Friedman

Answer by Joel David Hamkins for Ontological status of some "sets" in ZFC

Answer by Joel David Hamkins for $L_{\omega_1,\omega}$ sentence with many automorphism in $\aleph_0$ and few automorphism in $\aleph_\omega$

Answer by Joel David Hamkins for Pointwise algebraic models of set theory

Answer by Joel David Hamkins for Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

Answer by Joel David Hamkins for Closure of one relation w.r.t other

Answer by Joel David Hamkins for What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

How do the compact Hausdorff topologies sit in the lattice of all topologies on a set?

Answer by Joel David Hamkins for Order type of the smallest set containing the identity function and closed under exponentiation

Answer by Joel David Hamkins for Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Answer by Joel David Hamkins for Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Answer by Joel David Hamkins for A question about large real closed fields

Answer by Joel David Hamkins for Does the generalized $\Delta$-system lemma imply some weak version of the GCH?

Answer by Joel David Hamkins for Are the two meanings of "undecidable" related?

Answer by Joel David Hamkins for Validity in Kripke frames whose points are finite or infinite sequences

Answer by Joel David Hamkins for Forcing mildly over a worldly cardinal.

Answer by Joel David Hamkins for The Kunen inconsistency and definable classes

Answer by Joel David Hamkins for Which $\omega_1$-trees are proper?

Answer by Joel David Hamkins for $n$-in-a-row game on $\mathbb{R}^2$

Answer by Joel David Hamkins for Cohen algebra (generalization)

Answer by Joel David Hamkins for L-systems and Sierpinski Triangle

Answer by Joel David Hamkins for A question on cofinite topology.

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Comment by Joel David Hamkins

Answer by Joel David Hamkins for Nearly all math classes are lecture+problem set based; this seems particularly true at the graduate level. What are some concrete examples of techniques other than the "standard math class" used at the Graduate level?

Answer by Joel David Hamkins for Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?