A simple maximality principle

Posted on by
4

[bibtex key=Hamkins2003:MaximalityPrinciple]

In this paper, following an idea of Christophe Chalons, I propose a new kind of forcing axiom, the Maximality Principle, which asserts that any sentence$\varphi$ holding in some forcing extension $V^{\mathbb{P}}$ and all subsequent extensions $V^{\mathbb{P}*\mathbb{Q}}$ holds already in $V$. It follows, in fact, that such sentences must also hold in all forcing extensions of $V$. In modal terms, therefore, the Maximality Principle is expressed by the scheme $(\Diamond\Box\varphi)\to\Box\varphi$, and is equivalent to the modal theory S5. In this article, I prove that the Maximality Principle is relatively consistent with ZFC. A boldface version of the Maximality Principle, obtained by allowing real parameters to appear in $\varphi$, is equiconsistent with the scheme asserting that $V_\delta$ is an elementary substructure of $V$ for an inaccessible cardinal $\delta$, which in turn is equiconsistent with the scheme asserting that ORD is Mahlo. The strongest principle along these lines is the Necessary Maximality Principle, which asserts that the boldface MP holds in V and all forcing extensions. From this, it follows that $0^\sharp$ exists, that $x^\sharp$ exists for every set $x$, that projective truth is invariant by forcing, that Woodin cardinals are consistent and much more. Many open questions remain.

How tall is the automorphism tower of a group?

Posted on by
1

[bibtex key=Hamkins2001:HowTall?]

The automorphism tower of a group is obtained by computing its automorphism group, the automorphism group of that group, and so on, iterating transfinitely by taking the natural direct limit at limit stages. The question, known as the automorphism tower problem, is whether the tower ever terminates, whether there is eventually a fixed point, a group that is isomorphic to its automorphism group by the natural map. Wielandt (1939) proved the classical result that the automorphism tower of any finite centerless group terminates in finitely many steps. This was generalized to successively larger collections of groups until Thomas (1985) proved that every centerless group has a terminating automorphism tower. Here, it is proved that every group has a terminating automorphism tower. After this, an overview is given of the author’s (1997) result with Thomas revealing the set-theoretic essence of the automorphism tower of a group: the very same group can have wildly different towers in different models of set theory.

Indestructibility and the level-by-level agreement between strong compactness and supercompactness

Posted on by
Reply

[bibtex key=ApterHamkins2002:LevelByLevel]

Can a supercompact cardinal $\kappa$ be Laver indestructible when there is a level-by-level agreement between strong compactness and supercompactness? In this article, we show that if there is a sufficiently large cardinal above $\kappa$, then no, it cannot. Conversely, if one weakens the requirement either by demanding less indestructibility, such as requiring only indestructibility by stratified posets, or less level-by-level agreement, such as requiring it only on measure one sets, then yes, it can.

Post's problem for supertasks has both positive and negative solutions

Posted on by
Reply

[bibtex key=HamkinsLewis2002:PostProblem]

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post’s problem, the question whether there are supertask degrees between $0$ and the supertask jump $0^\triangledown$, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^\triangledown$, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.

Infinite time Turing machines

Posted on by
Reply

[bibtex key=Hamkins2002:Turing]

This is a survey of the theory of infinite time Turing machines.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

 

New inconsistencies in infinite utilitarianism

Posted on by
Reply

[bibtex key=FishkindHamkinsMontero2002:NewInconsistencies]

In the context of worlds with infinitely many bearers of utility, we argue that several collections of natural Utilitarian principles–principles which are certainly true in the classical finite Utilitarian context and which any Utilitarian would find appealing–are inconsistent.

Barbara Gail Montero

Indestructible weakly compact cardinals and the necessity of supercompactness for certain proof schemata

Posted on by
Reply

[bibtex key=ApterHamkins2001:IndestructibleWC]

We show that if the weak compactness of a cardinal is made indestructible by means of any preparatory forcing of a certain general type, including any forcing naively resembling the Laver preparation, then the cardinal was originally supercompact. We then apply this theorem to show that the hypothesis of supercompactness is necessary for certain proof schemata.

Unfoldable cardinals and the GCH

Posted on by
Reply

[bibtex key=Hamkins2001:UnfoldableCardinals]

Introducing unfoldable cardinals last year, Andres Villaveces ingeniously extended the notion of weak compactness to a larger context, thereby producing a large cardinal notion, unfoldability, with some of the feel and flavor of weak compactness but with a greater consistency strength. Specifically, $\kappa$ is $\theta$-unfoldable when for any transitive structure $M$ of size $\kappa$ that contains $\kappa$ as an element, there is an elementary embedding $j:M\to N$ with critical point $\kappa$ for which $j(\kappa)$ is at least $\theta$. Define that $\kappa$ is fully unfoldable, then, when it is $\theta$-unfoldable for every $\theta$. In this paper I show that the embeddings associated with these unfoldable cardinals are amenable to some of the same lifting techniques that apply to weakly compact embeddings, augmented with methods from the strong cardinal context. Using these techniques, I show by set-forcing over any model of ZFC that any given unfoldable cardinal $\kappa$ can be made indestructible by the forcing to add any number of Cohen subsets to $\kappa$. This result contradicts expectations to the contrary that class forcing would be required.

Gap forcing

Posted on by
1

[bibtex key=Hamkins2001:GapForcing]

Many of the most common reverse Easton iterations found in the large cardinal context, such as the Laver preparation, admit a gap at some small delta in the sense that they factor as $P*Q$, where $P$ has size less than $\delta$ and $Q$ is forced to be $\delta$-strategically closed. In this paper, generalizing the Levy-Solovay theorem, I show that after such forcing, every embedding $j:V[G]\to M[j(G)]$ in the extension which satisfies a mild closure condition is the lift of an embedding $j:V\to M$ in the ground model. In particular, every ultrapower embedding in the extension lifts an embedding from the ground model and every measure in the extension which concentrates on a set in the ground model extends a measure in the ground model. It follows that gap forcing cannot create new weakly compact cardinals, measurable cardinals, strong cardinals, Woodin cardinals, strongly compact cardinals, supercompact cardinals, almost huge cardinals, huge cardinals, and so on.

Infinite time Turing machines with only one tape

Posted on by
Reply

[bibtex key=HamkinsSeabold2001:OneTape]

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions $f:\mathbb{R}\to\mathbb{N}$, the same class of computable functions. Nevertheless, there are infinite time computable functions $f:\mathbb{R}\to\mathbb{R}$ that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal which is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.

The wholeness axioms and $V=\rm HOD$

Posted on by
Reply

[bibtex key=Hamkins2001:WholenessAxiom]

The Wholeness Axioms, proposed by Paul Corazza, axiomatize the existence of an elementary embedding $j:V\to V$. Formalized by augmenting the usual language of set theory with an additional unary function symbol j to represent the embedding, they avoid the Kunen inconsistency by restricting the base theory ZFC to the usual language of set theory. Thus, under the Wholeness Axioms one cannot appeal to the Replacement Axiom in the language with j as Kunen does in his famous inconsistency proof. Indeed, it is easy to see that the Wholeness Axioms have a consistency strength strictly below the existence of an $I_3$ cardinal. In this paper, I prove that if the Wholeness Axiom $WA_0$ is itself consistent, then it is consistent with $V=HOD$. A consequence of the proof is that the various Wholeness Axioms $WA_n$ are not all equivalent. Furthermore, the theory $ZFC+WA_0$ is finitely axiomatizable.

Infinite time Turing machines

Posted on by
1

[bibtex key=HamkinsLewis2000:InfiniteTimeTM]

This is the seminal paper introducing infinite time Turing machines.

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for reals and sets of reals and a rich degree structure, stratified by two natural jump operators.

The lottery preparation

Posted on by
Reply

[bibtex key=Hamkins2000:LotteryPreparation]

The lottery preparation, a new general kind of Laver preparation, works uniformly with supercompact cardinals, strongly compact cardinals, strong cardinals, measurable cardinals, or what have you. And like the Laver preparation, the lottery preparation makes these cardinals indestructible by various kinds of further forcing. A supercompact cardinal $\kappa$, for example, becomes fully indestructible by $\kappa$-directed closed forcing; a strong cardinal $\kappa$ becomes indestructible by less-than-or-equal-$\kappa$-strategically closed forcing; and a strongly compact cardinal $\kappa$ becomes indestructible by, among others, the forcing to add a Cohen subset to $\kappa$, the forcing to shoot a club $C$ in $\kappa$ which avoids the measurable cardinals and the forcing to add various long Prikry sequences. The lottery preparation works best when performed after fast function forcing, which adds a new completely general kind of Laver function for any large cardinal, thereby freeing the Laver function concept from the supercompact cardinal context.

Changing the heights of automorphism towers

Posted on by
2

[bibtex key=HamkinsThomas2000:ChangingHeights]

If $G$ is a centreless group, then $\tau(G)$ denotes the height of the automorphism tower of $G$. We prove that it is consistent that for every cardinal $\lambda$ and every ordinal $\alpha < \lambda$, there exists a centreless group $G$ such that (a) $\tau(G) = \alpha$; and (b) if $\beta$ is any ordinal such that $1 \leq \beta < \lambda$, then there exists a notion of forcing $P$, which preserves cofinalities and cardinalities, such that $\tau(G) = \beta$ in the corresponding generic extension $V^{P}$.

Small forcing creates neither strong nor Woodin cardinals

Posted on by
Reply

[bibtex key=HamkinsWoodin2000:SmallForcing]

After small forcing, almost every strongness embedding is the lift of a strongness embedding in the ground model. Consequently, small forcing creates neither strong nor Woodin cardinals.