Skip to main content
addendum strengthened
Source Link

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: there is athey are $\Delta^1_2$ reduction-bireducible, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: there is a $\Delta^1_2$ reduction, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: they are $\Delta^1_2$-bireducible, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Added addendum
Source Link

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: there is a $\Delta^1_2$ reduction, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely.

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: there is a $\Delta^1_2$ reduction, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)

Source Link

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely.

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)