Difference between revisions of "Erdos"

From Cantor's Attic
Jump to: navigation, search
(sorting)
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&#337;s cardinals and the constructible universe:
 
Erd&#337;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&#337;s cardinal. <cite>SharpeWelch2011:GreatlyErdosChang</cite>
 
* The existence of an almost Ramsey cardinal is stronger than the existence of an $\omega_1$-Erd&#337;s cardinal. <cite>SharpeWelch2011:GreatlyErdosChang</cite>
 
* A cardinal $\kappa$ is [[Ramsey]] precisely when it is $\kappa$-Erd&#337;s.
 
* A cardinal $\kappa$ is [[Ramsey]] precisely when it is $\kappa$-Erd&#337;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

  1. Erdős, Paul and Hajnal, Andras. On the structure of set-mappings. Acta Math Acad Sci Hungar 9:111--131, 1958. MR   bibtex
  2. Wilson, Trevor M. Weakly remarkable cardinals, Erdős cardinals, and the generic Vopěnka principle. , 2018. arχiv   bibtex
  3. 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
  4. Silver, Jack. Some applications of model theory in set theory. Ann Math Logic 3(1):45--110, 1971. MR   bibtex
  5. Silver, Jack. A large cardinal in the constructible universe. Fund Math 69:93--100, 1970. MR   bibtex
  6. Jensen, Ronald and Kunen, Kenneth. Some combinatorial properties of $L$ and $V$. Unpublished, 1969. www   bibtex
  7. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
  8. Gitman, Victoria and Shindler, Ralf. Virtual large cardinals. www   bibtex
  9. Gitman, Victoria. Ramsey-like cardinals. The Journal of Symbolic Logic 76(2):519-540, 2011. www   arχiv   MR   bibtex
  10. 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
Main library