Difference between revisions of "Hereditary Cardinality"

From Cantor's Attic
Jump to: navigation, search
m (Hereditarily Countable Sets)
m
 
(4 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
==Definition and Basic Absoluteness Properties==
 
==Definition and Basic Absoluteness Properties==
 
 
The set $H_\lambda$ is informally defined as the collection of all sets $x$ such that
 
The set $H_\lambda$ is informally defined as the collection of all sets $x$ such that
the cardinality of $x$ is less than $\lambda$, the cardinalities of the members of $x$ are less than $\lambda$, the cardinalities of the members of the members of $x$ are less than $\lambda$, <i>etc.</i>  Formally, $H_\lambda = \{x: \forall y \in \operatorname{trcl}(\{x\})\,(|y|<\lambda)\}$ where for any set $A$ the <i>transitive closure of $A$</i>, denoted $\operatorname{trcl}(A)$, is defined as follows.
+
the cardinality of $x$ is less than $\lambda$, the cardinalities of the members of $x$ are less than $\lambda$, the cardinalities of the members of the members of $x$ are less than $\lambda$, <i>etc.</i>  Formally, $H_\lambda=\{x: \forall y \in \operatorname{trcl}(\{x\})\,(|y|<\lambda)\}$ where for any set $A$ the <i>transitive closure of $A$</i>, denoted $\operatorname{trcl}(A)$, is defined as follows.
 
\begin{align*}
 
\begin{align*}
 
\operatorname{cl}(A,0)&=A \\
 
\operatorname{cl}(A,0)&=A \\
Line 14: Line 13:
 
The notion of transitive closure of a set is important and interesting in its own right.  
 
The notion of transitive closure of a set is important and interesting in its own right.  
  
The set $H_\lambda$ is usually only considered in the case that $\lambda$ is a regular cardinal.  In this case $H_\lambda = \{x: |\operatorname{trcl}(x)|<\lambda\}$, and this formula is often used as an alternative definition for regular $\lambda$.
+
The set $H_\lambda$ is usually only considered in the case that $\lambda$ is a regular cardinal.  In this case $H_\lambda = \{x: |\operatorname{trcl}(x)|<\lambda\}$, and assuming the axiom of choice $X\in H_\lambda\leftrightarrow X\subseteq H_\lambda\land |X|<\lambda$, and $H_\lambda = \{x: |\operatorname{trcl}(x)|<\lambda\}$ is often used as an alternative definition for regular $\lambda$.
Moreover if $\lambda$ is a regular cardinal then the inclusion $H_\lambda\subseteq V_\lambda$ holds, and if $\lambda$ is a regular strong limit cardinal (that is, $\lambda$ is inaccessible or $\lambda = \omega$) we have $H_\lambda=V_\lambda$.
+
Moreover if $\lambda$ is a regular cardinal then the inclusion $H_\lambda\subseteq V_\lambda$ holds, and if $\lambda$ is a regular strong limit cardinal (That is, $\lambda$ is inaccessible or $\lambda = \omega$) we have $H_\lambda=V_\lambda$.
  
For large regular $\lambda$, the set $H_\lambda$ exhibits many absoluteness properties for formulas that aren't typically absolute for transitive models. For example, $H_\lambda$ correctly interprets or computes various facts about its members: "$B$ is the powerset of $A$", "$B$ is an ultrafilter over $A$", "$A$ is the collection of functions from $B$ to $C$", "$\kappa$ is cardinal", "$\kappa$ is regular cardinal" and "$\kappa$ is the successor of $\gamma$", etc. Because these properties are absolute for $H_\lambda$ when $\lambda$ is large, much of Shelah's pcf theory can be implemented inside these models.
+
'''Theorem:''' If $\lambda$ is regular uncountable, $H_\lambda\prec_{\Sigma_1} V$.
  
 +
To see to  see this theorem, let $\phi$ be $\Delta_0$ with free variables among $y$,$x$. Suppose $\exists y(\phi)$. Now let $M\prec_{\Sigma_1} V$ with $TC(\{x\})\subseteq M$ and $|M|<\lambda$. By the Mostowski collapsing lemma, there is an isomorphism $\pi:M \to M'$ for some transitive $M'$. Since $TC(\{x\})\subseteq M$, $\pi(x)=x$ and thus $M'\vDash \exists y(\phi)$. Finally, we note that because $M'$ is transitive and has cardinality less than $\lambda$, $M'\in H_\lambda$ and so $H_\lambda\vDash \exists y(\phi)$.
 +
 +
As such, for uncountableregular $\lambda$, the set $H_\lambda$ exhibits many absoluteness properties for formulas that aren't typically absolute for transitive models.  For example, $H_\lambda$ correctly interprets or computes various facts about its members such as "$X$ is the powerset of $Y$", "$X$ is an ultrafilter over $Y$", "$X$ is the collection of functions from $Y$ to $Z$", "$\kappa$ is cardinal", "$\kappa$ is regular cardinal." etc. Because these properties are absolute for $H_\lambda$ when $\lambda$ is large, much of Shelah's pcf theory can be implemented inside these models.
 +
 +
If $\lambda$ is regular, and $x\in H_\lambda$, then $L_\lambda(x)\subseteq H_\lambda$. In addition, if $ZFC^-$ denote the theory $ZFC$ without the powerset axiom, and $\lambda$ is regular uncountable, then $(H_\lambda,\in)\vDash ZFC^-$, and so $(H_{\aleph_1},\in)\vDash KP$. In fact, this model also satisfies the negation of the powerset axiom.
 
==Hereditarily Finite Sets==
 
==Hereditarily Finite Sets==
 
 
The collection $H_{\aleph_0}$ of hereditarily finite sets is equal to the collection $V_\omega$ of sets of finite rank.
 
The collection $H_{\aleph_0}$ of hereditarily finite sets is equal to the collection $V_\omega$ of sets of finite rank.
The model $\langle H_{\aleph_0}, \in\rangle$ satisfies ZFC without the axiom of infinity (in fact, it satisfies the negation of the axiom of infinity) and in particular witnesses that the axiom of infinity is proof-theoretically independent of the other axioms of ZFC.
+
The model $\langle H_{\aleph_0}, \in\rangle$ satisfies $ZFC$ without the axiom of infinity (In fact, it satisfies the negation of the axiom of infinity) and in particular witnesses that the axiom of infinity is proof-theoretically independent of the other axioms of ZFC.
 
+
==Hereditarily Countable Sets==
+
 
+
Let $ZF^-$ denote the theory ZFC without the powerset axiom. Then $\langle H_{\aleph_1}, \in\rangle \models ZF^-$ (in fact, this model also satisfies the formal negation of the powerset axiom). In particular, this set witnesses that the powerset axiom is proof-theoretically independent of the other axioms of ZFC. In general, $\langle V_\alpha, \in\rangle\not\models ZF^-$. More generally, if $\lambda$ is regular and uncountable then $\langle H_\lambda, \in\rangle \models ZF^-$.
+
  
 
==Role in Elementary Embeddings==
 
==Role in Elementary Embeddings==
 
+
If $\kappa$ is $\lambda$-[[supercompact]] then there is some elementary embedding $j:V\to M$ with $M$ a transitive class and closed under arbitrary $\lambda$-sequences from $M$ and this implies that $M$ contains the model $H_{\lambda^+}$. This is also true of stronger large cardinals which are [[rank into rank]] types of embeddings. This latter fact plays a role in Woodin's proofs related to the [[HOD Conjecture]]. A cardinal $\kappa$ is strongly unfoldable with degree $\alpha$ if and only if for every $S\in H_{\kappa^+}$ and cardinal $\lambda$ there is a $\kappa-$model $S\in M$ non-trivial elementary embedding $j: M\rightarrow N$ with $N$ transitive and critical point $\kappa$ such that $j(\kappa)>max\{\alpha,\lambda\}$, such that $V_\alpha\subset N$ and $N\vDash (\kappa\,is\,strongly\,unfoldable\,of\,degree\,\beta)$ for every $\beta<\alpha$.
If $\kappa$ is $\lambda$-[[supercompact]] then there is some elementary embedding $j:V\to M$ with $M$ a transitive class and closed under arbitrary $\lambda$-sequences from $M$ and this implies that $M$ contains the model $H_{\lambda^+}$. This is also true of stronger large cardinals which are [[rank into rank]] types of embeddings. This latter fact plays a role in Woodin's proofs related to the [[HOD Conjecture]].  
+
 
   
 
   
 
{{References}}
 
{{References}}
 
{{stub}}
 

Latest revision as of 10:29, 8 June 2019


The collection of sets of hereditary cardinality $<\lambda$, usually denoted $H_\lambda$, play a fundamental role in many set-theoretic constructions. Because of their strong closure properties (and the fact that they are transitive), they are typically used in model-theoretic arguments, various forcing constructions and even Shelah's pcf theory to carry out various computations in the cardinal arithmetic of singular cardinals. Their importance stems from the fact that they are natural models for strong fragments of ZFC and even theories extending ZFC.

Definition and Basic Absoluteness Properties

The set $H_\lambda$ is informally defined as the collection of all sets $x$ such that the cardinality of $x$ is less than $\lambda$, the cardinalities of the members of $x$ are less than $\lambda$, the cardinalities of the members of the members of $x$ are less than $\lambda$, etc. Formally, $H_\lambda=\{x: \forall y \in \operatorname{trcl}(\{x\})\,(|y|<\lambda)\}$ where for any set $A$ the transitive closure of $A$, denoted $\operatorname{trcl}(A)$, is defined as follows. \begin{align*} \operatorname{cl}(A,0)&=A \\ \operatorname{cl}(A,n+1)&=\operatorname{cl}(A,n)\cup\bigcup \operatorname{cl}(A,n)\\ \operatorname{trcl}(A)&=\bigcup_{n<\omega} \operatorname{cl}(A,n). \end{align*} The notion of transitive closure of a set is important and interesting in its own right.

The set $H_\lambda$ is usually only considered in the case that $\lambda$ is a regular cardinal. In this case $H_\lambda = \{x: |\operatorname{trcl}(x)|<\lambda\}$, and assuming the axiom of choice $X\in H_\lambda\leftrightarrow X\subseteq H_\lambda\land |X|<\lambda$, and $H_\lambda = \{x: |\operatorname{trcl}(x)|<\lambda\}$ is often used as an alternative definition for regular $\lambda$. Moreover if $\lambda$ is a regular cardinal then the inclusion $H_\lambda\subseteq V_\lambda$ holds, and if $\lambda$ is a regular strong limit cardinal (That is, $\lambda$ is inaccessible or $\lambda = \omega$) we have $H_\lambda=V_\lambda$.

Theorem: If $\lambda$ is regular uncountable, $H_\lambda\prec_{\Sigma_1} V$.

To see to see this theorem, let $\phi$ be $\Delta_0$ with free variables among $y$,$x$. Suppose $\exists y(\phi)$. Now let $M\prec_{\Sigma_1} V$ with $TC(\{x\})\subseteq M$ and $|M|<\lambda$. By the Mostowski collapsing lemma, there is an isomorphism $\pi:M \to M'$ for some transitive $M'$. Since $TC(\{x\})\subseteq M$, $\pi(x)=x$ and thus $M'\vDash \exists y(\phi)$. Finally, we note that because $M'$ is transitive and has cardinality less than $\lambda$, $M'\in H_\lambda$ and so $H_\lambda\vDash \exists y(\phi)$.

As such, for uncountableregular $\lambda$, the set $H_\lambda$ exhibits many absoluteness properties for formulas that aren't typically absolute for transitive models. For example, $H_\lambda$ correctly interprets or computes various facts about its members such as "$X$ is the powerset of $Y$", "$X$ is an ultrafilter over $Y$", "$X$ is the collection of functions from $Y$ to $Z$", "$\kappa$ is cardinal", "$\kappa$ is regular cardinal." etc. Because these properties are absolute for $H_\lambda$ when $\lambda$ is large, much of Shelah's pcf theory can be implemented inside these models.

If $\lambda$ is regular, and $x\in H_\lambda$, then $L_\lambda(x)\subseteq H_\lambda$. In addition, if $ZFC^-$ denote the theory $ZFC$ without the powerset axiom, and $\lambda$ is regular uncountable, then $(H_\lambda,\in)\vDash ZFC^-$, and so $(H_{\aleph_1},\in)\vDash KP$. In fact, this model also satisfies the negation of the powerset axiom.

Hereditarily Finite Sets

The collection $H_{\aleph_0}$ of hereditarily finite sets is equal to the collection $V_\omega$ of sets of finite rank. The model $\langle H_{\aleph_0}, \in\rangle$ satisfies $ZFC$ without the axiom of infinity (In fact, it satisfies the negation of the axiom of infinity) and in particular witnesses that the axiom of infinity is proof-theoretically independent of the other axioms of ZFC.

Role in Elementary Embeddings

If $\kappa$ is $\lambda$-supercompact then there is some elementary embedding $j:V\to M$ with $M$ a transitive class and closed under arbitrary $\lambda$-sequences from $M$ and this implies that $M$ contains the model $H_{\lambda^+}$. This is also true of stronger large cardinals which are rank into rank types of embeddings. This latter fact plays a role in Woodin's proofs related to the HOD Conjecture. A cardinal $\kappa$ is strongly unfoldable with degree $\alpha$ if and only if for every $S\in H_{\kappa^+}$ and cardinal $\lambda$ there is a $\kappa-$model $S\in M$ non-trivial elementary embedding $j: M\rightarrow N$ with $N$ transitive and critical point $\kappa$ such that $j(\kappa)>max\{\alpha,\lambda\}$, such that $V_\alpha\subset N$ and $N\vDash (\kappa\,is\,strongly\,unfoldable\,of\,degree\,\beta)$ for every $\beta<\alpha$.

References

    Main library