Difference between revisions of "Erdos"
BartekChom (Talk | contribs) (sorting) |
BartekChom (Talk | contribs) m (→Facts: Baumgartner definition) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 9: | Line 9: | ||
A cardinal $\kappa$ is called Erdős if and only if it is $\alpha$-Erdős for some infinite limit ordinal $\alpha$. Because there exists at most one $\alpha$-Erdős cardinal, the notations $\eta_\alpha$ and $\kappa(\alpha)$ are sometimes used to denote the $\alpha$-Erdős cardinal. | A cardinal $\kappa$ is called Erdős if and only if it is $\alpha$-Erdős for some infinite limit ordinal $\alpha$. Because there exists at most one $\alpha$-Erdős cardinal, the notations $\eta_\alpha$ and $\kappa(\alpha)$ are sometimes used to denote the $\alpha$-Erdős cardinal. | ||
+ | |||
+ | Different terminology (Baumgartner, 1977): an infinite cardinal $κ$ is $ω$-Erdős if for every club $C$ in $κ$ and every function $f : [C]^{<ω} → κ$ that is regressive (i.e. $f(a) < \min(a)$ for | ||
+ | all $a$ in the domain of $f$) there is a subset $X ⊂ C$ of order type $ω$ that is homogeneous for $f$ (i.e. $f ↾ [X]^n$ is constant for all $n < ω$). Schmerl, 1976 (theorem 6.1) showed that the least cardinal $κ$ such that $κ → (ω)_2^{<ω}$ has this property, if it exists.<cite>Wilson2018:WeaklyRemarkableCardinals</cite> | ||
==Facts== | ==Facts== | ||
* $\eta_\alpha<\eta_\beta$ whenever $\alpha<\beta$ and $\eta_\alpha\geq\alpha$. <cite>Kanamori2009:HigherInfinite</cite> | * $\eta_\alpha<\eta_\beta$ whenever $\alpha<\beta$ and $\eta_\alpha\geq\alpha$. <cite>Kanamori2009:HigherInfinite</cite> | ||
+ | |||
+ | With Baumgartner definition:<cite>Wilson2018:WeaklyRemarkableCardinals</cite> | ||
+ | * Every $ω$-Erdős cardinal is inaccessible. | ||
+ | * If $η$ is an $ω$-Erdős cardinal then $η → (ω)_α^{<ω}$ for every cardinal $α < η$. | ||
+ | * If $α ≥ 2$ is a cardinal and there is a cardinal $η$ such that $η → (ω)_α^{<ω}$, then the least such cardinal $η$ is an $ω$-Erdős cardinal (and is greater than α.) | ||
+ | * Simple conclusions from the last two facts: | ||
+ | ** The statement “there is an $ω$-Erdős cardinal” is equivalent to the statement $∃_η η → (ω)_2^{<ω}$. | ||
+ | ** The statement “there is a proper class of $ω$-Erdős cardinals” is equivalent to the statement $∀_α ∃_η η → (ω)_α^{<ω}$. | ||
Erdős cardinals and the constructible universe: | Erdős cardinals and the constructible universe: | ||
Line 28: | Line 39: | ||
* The existence of an almost Ramsey cardinal is stronger than the existence of an $\omega_1$-Erdős cardinal. <cite>SharpeWelch2011:GreatlyErdosChang</cite> | * The existence of an almost Ramsey cardinal is stronger than the existence of an $\omega_1$-Erdős cardinal. <cite>SharpeWelch2011:GreatlyErdosChang</cite> | ||
* A cardinal $\kappa$ is [[Ramsey]] precisely when it is $\kappa$-Erdős. | * A cardinal $\kappa$ is [[Ramsey]] precisely when it is $\kappa$-Erdős. | ||
+ | * (Baumgartner definition) The existence of non-[[remarkable]] weakly remarkable cardinals is equiconsistent to the existence of $ω$-Erdős cardinal (equivalent assuming $V=L$):<cite>Wilson2018:WeaklyRemarkableCardinals</cite> | ||
+ | ** Every $ω$-Erdős cardinal is a limit of non-remarkable weakly remarkable cardinals. | ||
+ | ** If $κ$ is a non-remarkable weakly remarkable cardinal, then some ordinal greater than $κ$ is an $ω$-Erdős cardinal in $L$. | ||
== Weakly Erdős and greatly Erdős == | == Weakly Erdős and greatly Erdős == |
Latest revision as of 12:34, 11 September 2019
The $\alpha$-Erdős cardinals were introduced by Erdős and Hajnal in [1] and arose out of their study of partition relations. A cardinal $\kappa$ is $\alpha$-Erdős for an infinite limit ordinal $\alpha$ if it is the least cardinal $\kappa$ such that $\kappa\rightarrow (\alpha)^{\lt\omega}_2$ (if any such cardinal exists).
For infinite cardinals $\kappa$ and $\lambda$, the partition property $\kappa\to(\lambda)^n_\gamma$ asserts that for every function $F:[\kappa]^n\to\gamma$ there is $H\subseteq\kappa$ with $|H|=\lambda$ such that $F\upharpoonright[H]^n$ is constant. Here $[X]^n$ is the set of all $n$-elements subsets of $X$. The more general partition property $\kappa\to(\lambda)^{\lt\omega}_\gamma$ asserts that for every function $F:[\kappa]^{\lt\omega}\to\gamma$ there is $H\subseteq\kappa$ with $|H|=\lambda$ such that $F\upharpoonright[H]^n$ is constant for every $n$, although the value of $F$ on $[H]^n$ may be different for different $n$. Indeed, if $\kappa$ is $\alpha$-Erdős for some infinite ordinal $\alpha$, then $\kappa\rightarrow (\alpha)^{\lt\omega}_\lambda$ for all $\lambda<\kappa$ (Silver's PhD thesis).
The $\alpha$-Erdős cardinal is precisely the least cardinal $\kappa$ such that for any language $\mathcal{L}$ of size less than $\kappa$ and any structure $\mathcal{M}$ with language $\mathcal{L}$ and domain $\kappa$, there is a set of indescernibles for $\mathcal{M}$ of order-type $\alpha$.
A cardinal $\kappa$ is called Erdős if and only if it is $\alpha$-Erdős for some infinite limit ordinal $\alpha$. Because there exists at most one $\alpha$-Erdős cardinal, the notations $\eta_\alpha$ and $\kappa(\alpha)$ are sometimes used to denote the $\alpha$-Erdős cardinal.
Different terminology (Baumgartner, 1977): an infinite cardinal $κ$ is $ω$-Erdős if for every club $C$ in $κ$ and every function $f : [C]^{<ω} → κ$ that is regressive (i.e. $f(a) < \min(a)$ for all $a$ in the domain of $f$) there is a subset $X ⊂ C$ of order type $ω$ that is homogeneous for $f$ (i.e. $f ↾ [X]^n$ is constant for all $n < ω$). Schmerl, 1976 (theorem 6.1) showed that the least cardinal $κ$ such that $κ → (ω)_2^{<ω}$ has this property, if it exists.[2]
Facts
- $\eta_\alpha<\eta_\beta$ whenever $\alpha<\beta$ and $\eta_\alpha\geq\alpha$. [3]
With Baumgartner definition:[2]
- Every $ω$-Erdős cardinal is inaccessible.
- If $η$ is an $ω$-Erdős cardinal then $η → (ω)_α^{<ω}$ for every cardinal $α < η$.
- If $α ≥ 2$ is a cardinal and there is a cardinal $η$ such that $η → (ω)_α^{<ω}$, then the least such cardinal $η$ is an $ω$-Erdős cardinal (and is greater than α.)
- Simple conclusions from the last two facts:
- The statement “there is an $ω$-Erdős cardinal” is equivalent to the statement $∃_η η → (ω)_2^{<ω}$.
- The statement “there is a proper class of $ω$-Erdős cardinals” is equivalent to the statement $∀_α ∃_η η → (ω)_α^{<ω}$.
Erdős cardinals and the constructible universe:
- $\omega_1$-Erdős cardinals imply that $0^\sharp$ exists and hence there cannot be $\omega_1$-Erdős cardinals in $L$. [4]
- $\alpha$-Erdős cardinals are downward absolute to $L$ for $L$-countable $\alpha$. More generally, $\alpha$-Erdős cardinals are downward absolute to any transitive model of ZFC for $M$-countable $\alpha$. [5]
Relations with other large cardinals:
- Every Erdős cardinal is inaccessible. (Silver's PhD thesis)
- Every Erdős cardinal is subtle. [6]
- $\eta_\omega$ is a stationary limit of ineffable cardinals. [7]
- $η_ω$ is a limit of virtually rank-into-rank cardinals. [8]
- The existence of $\eta_\omega$ implies the consistency of a proper class of $n$-iterable cardinals for every $1\leq n<\omega$.[9]
- For an additively indecomposable ordinal $λ ≤ ω_1$, $η_λ$ (the least $λ$-Erdős cardinal) is a limit of $λ$-iterable cardinals and if there is a $λ + 1$-iterable cardinal, then there is a $λ$-Erdős cardinal below it.[8]
- The consistency strength of the existence of an Erdős cardinal is stronger than that of the existence of an $n$-iterable cardinal for every $n<\omega$ and weaker than that of the existence of $0^{\#}$.
- The existence of a proper class of Erdős cardinals is equivalent to the existence of a proper class of almost Ramsey cardinals. The consistency strength of this is weaker than a worldly almost Ramsey cardinal, but stronger than an almost Ramsey cardinal.
- The existence of an almost Ramsey cardinal is stronger than the existence of an $\omega_1$-Erdős cardinal. [10]
- A cardinal $\kappa$ is Ramsey precisely when it is $\kappa$-Erdős.
- (Baumgartner definition) The existence of non-remarkable weakly remarkable cardinals is equiconsistent to the existence of $ω$-Erdős cardinal (equivalent assuming $V=L$):[2]
- Every $ω$-Erdős cardinal is a limit of non-remarkable weakly remarkable cardinals.
- If $κ$ is a non-remarkable weakly remarkable cardinal, then some ordinal greater than $κ$ is an $ω$-Erdős cardinal in $L$.
Weakly Erdős and greatly Erdős
(Information in this section from [10])
Suppose that $κ$ has uncountable cofinality, $\mathcal{A}$ is $κ$-structure, with $X ⊆ κ$, and $t_\mathcal{A} ( X ) = \{ α ∈ κ \text{ — limit ordinal} : \text{there exists a set $I ⊆ α ∩ X$ of good indiscernibles for $\mathcal{A}$ cofinal in $α$} \}$. Using this one can define a hierarchy of normal filters $\mathcal{F}_\alpha$ potentially for all $α < κ^+$ ; these are generated by suprema of sets of nested indiscernibles for structures $\mathcal{A}$ on $κ$ using the above basic $t_\mathcal{A} (X)$ operation. A cardinal $κ$ is weakly $α$-Erdős when $\mathcal{F}_\alpha$ is non-trivial.
$κ$ is greatly Erdős iff there is a non-trivial normal filter $\mathcal{F}$ on $\mathcal{F}$ such that $F$ is closed under $t_\mathcal{A} (X)$ for every $κ$-structure $\mathcal{A}$. Equivalently (for uncountable cofinality of cardinal $κ$):
- $\mathcal{G} = \bigcup_{\alpha < \kappa^+} \mathcal{F}_\alpha \not\ni \varnothing$
- $κ$ is $α$-weakly Erdős for all $α < κ^+$
and (for inaccessible $κ$ and any choice $⟨ f_β : β < κ^+ ⟩$ of canonical functions for $κ$):
- $\{γ < κ : f_β (γ) ⩽ o_\mathcal{A} (γ)\} \neq \varnothing$ for all $β < κ^+$ and $κ$-structures $\mathcal{A}$ such that $\mathcal{A} \models ZFC$
Relations:
- If $κ$ is a $2$-weakly Erdős cardinal then $κ$ is almost Ramsey.
- If $κ$ is virtually Ramsey then $κ$ is greatly Erdős.
- There are stationarily many completely ineffable, greatly Erdős cardinals below any Ramsey cardinal.
References
- Erdős, Paul and Hajnal, Andras. On the structure of set-mappings. Acta Math Acad Sci Hungar 9:111--131, 1958. MR bibtex
- Wilson, Trevor M. Weakly remarkable cardinals, Erdős cardinals, and the generic Vopěnka principle. , 2018. arχiv bibtex
- Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www bibtex
- Silver, Jack. Some applications of model theory in set theory. Ann Math Logic 3(1):45--110, 1971. MR bibtex
- Silver, Jack. A large cardinal in the constructible universe. Fund Math 69:93--100, 1970. MR bibtex
- Jensen, Ronald and Kunen, Kenneth. Some combinatorial properties of $L$ and $V$. Unpublished, 1969. www bibtex
- Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www bibtex
- Gitman, Victoria and Shindler, Ralf. Virtual large cardinals. www bibtex
- Gitman, Victoria. Ramsey-like cardinals. The Journal of Symbolic Logic 76(2):519-540, 2011. www arχiv MR bibtex
- Sharpe, Ian and Welch, Philip. Greatly Erdős cardinals with some generalizations to the Chang and Ramsey properties. Ann Pure Appl Logic 162(11):863--902, 2011. www DOI MR bibtex