Skip to main content
added 186 characters in body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

I definitely don't think this is a good "first example" of an analytic non-Borel set. It does, however, make more sense when put in comparison with the standard example of a co-analytic, non-Borel set:

Given a binary relation $R$ on $\mathbb{N}$, we can code $R$ by a set $X_R\subseteq\mathbb{N}$: let $\langle \cdot,\cdot\rangle$ be a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ (e.g. the Cantor pairing function), and let $$X_R=\{\langle m, n\rangle: mRn\}.$$ Now for a property $\mathfrak{P}$ of relations, let $S_\mathfrak{P}$ be the family of sets coding relations with that property. E.g. $S_{\mbox{linear}}$ is the family of sets which code linear orders of $\mathbb{N}$, and so forth.

It's not hard to see that $S_{\mbox{linear}}$ is Borel, indeed closed. It turns out that a good way to get Borel sets of high complexity, and non-Borel sets, is to look at sets of the form $S_\mathfrak{P}$ for more complicated properties $\mathfrak{P}$.

One important property of relations is well-foundedness: call a relation $R$ well-founded if there is no infinite sequence $a_0R a_1R a_2R...$. And the associated family of sets is $S_{WF}$.

It's not hard to show that $S_{WF}$ is analyticco-analytic. (Strictly speaking, I've described $S_{WF}$ as a subset of $2^\omega$, not $\mathbb{R}$; but it's easy to switch it over, e.g. via the standard bijection between $2^\omega$ and the middle-thirds Cantor set.) But it turns out that $S_{WF}$ is not Borel!

Why? Well, remember that the Borel sets are arranged in a hierarchy, indexed by countable ordinals (the $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ sets, as $\alpha\in\omega_1$). Now, a well-founded relation has a rank - a countable ordinal that measures how complicated it is. Bigger ranks mean, intuitively, that the relation is "closer to being ill-founded". The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations. And this means that the set $S_{WF}$ is not, in fact, Borel.

This is of course not a proof - the details are much more complicated. But this is the idea: there's a connection between the complexity of a Borel set, and its ability to distinguish well-founded relations from ill-founded ones.

This motivates the following general intuition:

If I have a set defined in terms of quantification over infinite sequences, rather than only over natural numbers, then that set probably isn't Borel.

There are of course counterexamples, but this is a good rule of thumb. And the example you mention, of course, is of this kind. SoIt's kind of the natural thing to do toopposite of $S_{WF}$: $S_{WF}$ was defined by saying that there is proveno that thatsequence of a certain form, whereas your set is not Borel,defined by saying that there is a sequence of a certain form. So a natural thing to do is try to constructfind a Borel bijectionisomorphism between ityour set and the complement of $S_{WF}$.

I definitely don't think this is a good "first example" of an analytic non-Borel set. It does, however, make more sense when put in comparison with the standard example:

Given a binary relation $R$ on $\mathbb{N}$, we can code $R$ by a set $X_R\subseteq\mathbb{N}$: let $\langle \cdot,\cdot\rangle$ be a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ (e.g. the Cantor pairing function), and let $$X_R=\{\langle m, n\rangle: mRn\}.$$ Now for a property $\mathfrak{P}$ of relations, let $S_\mathfrak{P}$ be the family of sets coding relations with that property. E.g. $S_{\mbox{linear}}$ is the family of sets which code linear orders of $\mathbb{N}$, and so forth.

It's not hard to see that $S_{\mbox{linear}}$ is Borel, indeed closed. It turns out that a good way to get Borel sets of high complexity, and non-Borel sets, is to look at sets of the form $S_\mathfrak{P}$ for more complicated properties $\mathfrak{P}$.

One important property of relations is well-foundedness: call a relation $R$ well-founded if there is no infinite sequence $a_0R a_1R a_2R...$. And the associated family of sets is $S_{WF}$.

It's not hard to show that $S_{WF}$ is analytic. (Strictly speaking, I've described $S_{WF}$ as a subset of $2^\omega$, not $\mathbb{R}$; but it's easy to switch it over, e.g. via the standard bijection between $2^\omega$ and the middle-thirds Cantor set.) But it turns out that $S_{WF}$ is not Borel!

Why? Well, remember that the Borel sets are arranged in a hierarchy, indexed by countable ordinals (the $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ sets, as $\alpha\in\omega_1$). Now, a well-founded relation has a rank - a countable ordinal that measures how complicated it is. Bigger ranks mean, intuitively, that the relation is "closer to being ill-founded". The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations. And this means that the set $S_{WF}$ is not, in fact, Borel.

This is of course not a proof - the details are much more complicated. But this is the idea: there's a connection between the complexity of a Borel set, and its ability to distinguish well-founded relations from ill-founded ones.

This motivates the following general intuition:

If I have a set defined in terms of quantification over infinite sequences, rather than only over natural numbers, then that set probably isn't Borel.

There are of course counterexamples, but this is a good rule of thumb. And the example you mention, of course, is of this kind. So the natural thing to do to prove that that set is not Borel, is to construct a Borel bijection between it and $S_{WF}$.

I definitely don't think this is a good "first example" of an analytic non-Borel set. It does, however, make more sense when put in comparison with the standard example of a co-analytic, non-Borel set:

Given a binary relation $R$ on $\mathbb{N}$, we can code $R$ by a set $X_R\subseteq\mathbb{N}$: let $\langle \cdot,\cdot\rangle$ be a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ (e.g. the Cantor pairing function), and let $$X_R=\{\langle m, n\rangle: mRn\}.$$ Now for a property $\mathfrak{P}$ of relations, let $S_\mathfrak{P}$ be the family of sets coding relations with that property. E.g. $S_{\mbox{linear}}$ is the family of sets which code linear orders of $\mathbb{N}$, and so forth.

It's not hard to see that $S_{\mbox{linear}}$ is Borel, indeed closed. It turns out that a good way to get Borel sets of high complexity, and non-Borel sets, is to look at sets of the form $S_\mathfrak{P}$ for more complicated properties $\mathfrak{P}$.

One important property of relations is well-foundedness: call a relation $R$ well-founded if there is no infinite sequence $a_0R a_1R a_2R...$. And the associated family of sets is $S_{WF}$.

It's not hard to show that $S_{WF}$ is co-analytic. (Strictly speaking, I've described $S_{WF}$ as a subset of $2^\omega$, not $\mathbb{R}$; but it's easy to switch it over, e.g. via the standard bijection between $2^\omega$ and the middle-thirds Cantor set.) But it turns out that $S_{WF}$ is not Borel!

Why? Well, remember that the Borel sets are arranged in a hierarchy, indexed by countable ordinals (the $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ sets, as $\alpha\in\omega_1$). Now, a well-founded relation has a rank - a countable ordinal that measures how complicated it is. Bigger ranks mean, intuitively, that the relation is "closer to being ill-founded". The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations. And this means that the set $S_{WF}$ is not, in fact, Borel.

This is of course not a proof - the details are much more complicated. But this is the idea: there's a connection between the complexity of a Borel set, and its ability to distinguish well-founded relations from ill-founded ones.

This motivates the following general intuition:

If I have a set defined in terms of quantification over infinite sequences, rather than only over natural numbers, then that set probably isn't Borel.

There are of course counterexamples, but this is a good rule of thumb. And the example you mention, of course, is of this kind. It's kind of the opposite of $S_{WF}$: $S_{WF}$ was defined by saying that there is no sequence of a certain form, whereas your set is defined by saying that there is a sequence of a certain form. So a natural thing to do is try to find a Borel isomorphism between your set and the complement of $S_{WF}$.

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

I definitely don't think this is a good "first example" of an analytic non-Borel set. It does, however, make more sense when put in comparison with the standard example:

Given a binary relation $R$ on $\mathbb{N}$, we can code $R$ by a set $X_R\subseteq\mathbb{N}$: let $\langle \cdot,\cdot\rangle$ be a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ (e.g. the Cantor pairing function), and let $$X_R=\{\langle m, n\rangle: mRn\}.$$ Now for a property $\mathfrak{P}$ of relations, let $S_\mathfrak{P}$ be the family of sets coding relations with that property. E.g. $S_{\mbox{linear}}$ is the family of sets which code linear orders of $\mathbb{N}$, and so forth.

It's not hard to see that $S_{\mbox{linear}}$ is Borel, indeed closed. It turns out that a good way to get Borel sets of high complexity, and non-Borel sets, is to look at sets of the form $S_\mathfrak{P}$ for more complicated properties $\mathfrak{P}$.

One important property of relations is well-foundedness: call a relation $R$ well-founded if there is no infinite sequence $a_0R a_1R a_2R...$. And the associated family of sets is $S_{WF}$.

It's not hard to show that $S_{WF}$ is analytic. (Strictly speaking, I've described $S_{WF}$ as a subset of $2^\omega$, not $\mathbb{R}$; but it's easy to switch it over, e.g. via the standard bijection between $2^\omega$ and the middle-thirds Cantor set.) But it turns out that $S_{WF}$ is not Borel!

Why? Well, remember that the Borel sets are arranged in a hierarchy, indexed by countable ordinals (the $\Sigma^0_\alpha$ and $\Pi^0_\alpha$ sets, as $\alpha\in\omega_1$). Now, a well-founded relation has a rank - a countable ordinal that measures how complicated it is. Bigger ranks mean, intuitively, that the relation is "closer to being ill-founded". The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations. And this means that the set $S_{WF}$ is not, in fact, Borel.

This is of course not a proof - the details are much more complicated. But this is the idea: there's a connection between the complexity of a Borel set, and its ability to distinguish well-founded relations from ill-founded ones.

This motivates the following general intuition:

If I have a set defined in terms of quantification over infinite sequences, rather than only over natural numbers, then that set probably isn't Borel.

There are of course counterexamples, but this is a good rule of thumb. And the example you mention, of course, is of this kind. So the natural thing to do to prove that that set is not Borel, is to construct a Borel bijection between it and $S_{WF}$.