Skip to main content
deleted 206 characters in body
Source Link
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the successor of the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only values $\le\omega_1$ or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.

  • EDIT: Let $\mathcal{A}=\{S: \forall \alpha<\omega_1\exists x\in S(\omega_1^x\ge\alpha)\}$. Then $Spread(\mathcal{A})=\omega_2$: there is an obvious surjection onto $\omega_1$ (hence any $\alpha<\omega_2$). Conversely, for $f:\mathbb{R}\rightarrow\omega_2$ and $\alpha<\omega_1$ let $S_\alpha$ be the set of reals $x$ with $\omega_1^{CK}\ge\alpha$ which have minimal $f$-value among all such reals; by the regularity of $\omega_2$, $\bigcup_{\alpha<\omega_1} S_\alpha$ is not mapped onto $\omega_2$ by $f$. I suspect that we can get all successor ordinals below $\Theta$ in a similar way, using the Coding Lemma.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values ofis $Spread(\mathcal{F})$$Spread(\{$dominating sets$\})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the successor of the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only values $\le\omega_1$ or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values of $Spread(\mathcal{F})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the successor of the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only values $\le\omega_1$ or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.

  • EDIT: Let $\mathcal{A}=\{S: \forall \alpha<\omega_1\exists x\in S(\omega_1^x\ge\alpha)\}$. Then $Spread(\mathcal{A})=\omega_2$: there is an obvious surjection onto $\omega_1$ (hence any $\alpha<\omega_2$). Conversely, for $f:\mathbb{R}\rightarrow\omega_2$ and $\alpha<\omega_1$ let $S_\alpha$ be the set of reals $x$ with $\omega_1^{CK}\ge\alpha$ which have minimal $f$-value among all such reals; by the regularity of $\omega_2$, $\bigcup_{\alpha<\omega_1} S_\alpha$ is not mapped onto $\omega_2$ by $f$. I suspect that we can get all successor ordinals below $\Theta$ in a similar way, using the Coding Lemma.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

What is $Spread(\{$dominating sets$\})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

added 17 characters in body
Source Link
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the successor of the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only countable values $\le\omega_1$ or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values of $Spread(\mathcal{F})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only countable values or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values of $Spread(\mathcal{F})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the successor of the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only values $\le\omega_1$ or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values of $Spread(\mathcal{F})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.

Source Link
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

Spreading sets - especially without choice

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system.

Suppose I have a set $X\subseteq \mathbb{R}$. Let $\Theta(X)$ be the supremum of the ordinals onto which $X$ surjects. In the presence of choice, this is of course just the cardinality of $X$; in the presence of determinacy, the $\Theta$ function takes on only countable values or $\Theta=\Theta(\mathbb{R})$.

However, things get much weirder when we try to cover an ordinal by many sets simultaneously. For $\mathcal{F}$ a family of sets, let $$Spread(\mathcal{F})=\sup\{\alpha: \exists f:\mathbb{R}\rightarrow ON: \forall X\in\mathcal{F}(f(X)=\alpha)\},$$ that is, the sup of all ordinals onto which the elements of $\mathcal{F}$ simultaneously surject. Note that already this is complicated because the set of such ordinals need not be closed downwards!

My questions are below. Some initial observations (again, this is in ZF+AD+DC):

  • $Spread(\{$perfect sets$\})$ is $1$. For $\alpha>1$ countable, if $f:\mathbb{R}\rightarrow \alpha$ then some $\eta\in\alpha$ has uncountable preimage; this preimage contains a perfect set, by AD. For $\alpha$ uncountable, let $S\subset \alpha$ be an uncountable proper subset of $\alpha$; then the $f$-preimage of $S$ again contains a perfect subset, for any $f: \mathbb{R}\rightarrow\alpha$.

  • For $n\in\omega$, let $\mathbb{R}=\bigsqcup_{i\in n} P_i$ and let $\mathcal{F}=\{S: \forall i<n(S\cap P_i\not=\emptyset)\}$. Then it's easy to see that $Spread(\mathcal{F})=n$.

  • Similarly, let $\mathbb{R}=\bigsqcup_{i\in\omega}P_i$ and let $\mathcal{F}=\{S: \exists j\in\omega\forall i\in\omega(i>j\rightarrow S\cap P_i\not=\emptyset)\}$. Then $Spread(\mathcal{F})=\omega_1$: consider the map $f(r)=k$ iff $r\in P_{\langle k, m\rangle}$ for some $m$.


OK, so onto the question. First, a couple minor preliminary questions:

  • Has this notion been studied before? I have a strong sensation that I'm (yet again) reinventing the wheel; however, googling around hasn't been helpful here.

  • Can we have $Spread(\mathcal{F})=\omega$ for $\mathcal{F}\subseteq\mathcal{P}(\mathbb{R})$? This is a very minor question, I'm just curious.

My main question is:

Suppose $\mathcal{F}$ is a dominating family (that is, $\mathcal{F}\subseteq\omega^\omega$ is such that for all $g\in\omega^\omega$, there is some $f\in\mathcal{F}$ with $f(n)>g(n)$ for all $n$). What are the possible values of $Spread(\mathcal{F})$?

More generally, I'm interested in how $Spread$ interacts with cardinal characteristics of the continuum - e.g. it's easy to see that $Spread(\{$unbounding sets$\})\le Spread(\{$dominating sets$\})$ - but this seems a good test case.