Return to Answer

• the set of all true statements in the language of arithmetic. This has comlexity $\Sigma_\omega$, just beyond the the arithmetic hierarchy.

• the set of all Turing machine programs that compute a well-ordered relation on $\mathbb{N}$. This set has complexity complete $\Pi^1_1$ in the projective hiearchy, well beyond what can be computed by Turing machines.

• the set of all statements true in the realm of the hereditarily countable sets $\text{HC}=\langle H_{\omega_1},{\in}\rangle$. This is the complexity of projective truth, outside and above the projective hierarchy.

• the set of natural numbers $n$ such that $2^{\aleph_n}=\aleph_{n+1}$. This set of natural numbers is defined by a $\Sigma_2$ assertion of set theory (not in the arithmetic hierarchy, but the Levy hierarchy). It cannot be expressed as a statement about computation, since the particular contents of the set can be changed by forcing, and forcing does not affect the nature of any computation. Perhaps you will object that it is like your CH example, but it isn't of that binary form, and it would seem hard to say that this isn't a legitimate definition of a set of natural numbers that could be defined in some other way.

• there are many others...

I notice in your question that you mention the arithmetic and hyperarithmetic hierarchies, but I disagree with your characterization of them as being statements concerning properties of computation. Although it is true that one can iterate a $\Sigma_1$ process through the ordinals to arrive at the hyperarithmetic sets, it is the complexity of the ordinals that drives this hierarchy, rather than the comparatively trivial use of computation at each step. Similarly, although one could say that projective statements are statements about Turing machines, provided that one is allowed to quantify over integers and reals (one just writes the quantifier-free part of the assertion in terms of computation), this would seem to me to miss the point, for it is the quantification over reals that matters, and not the fact that one writes the quatifier-free part in a way involving computation. Ultimately, therefore, it seems to me that the answer to the ideas in your question consists of a careful appreciation of the nature of the various definability hierarchies.

Allow me to give a little more information by mentioning that there are several very large, intensely studied hierarchies of complexity for reals numbers. After the initial familiar notions come several others...

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

• the set of all true statements in the language of arithmetic. This has complexity $\Sigma_\omega$, just beyond the arithmetic hierarchy.

• the set of all Turing machine programs that compute a well-ordered relation on $\mathbb{N}$. This set has complexity complete $\Pi^1_1$ in the projective hiearchy, well beyond what can be computed by Turing machines.

• the set of all statements true in the realm of the hereditarily countable sets $\text{HC}=\langle H_{\omega_1},{\in}\rangle$. This is the complexity of projective truth, outside and above the projective hierarchy.

• the set of natural numbers $n$ such that $2^{\aleph_n}=\aleph_{n+1}$. This set of natural numbers is defined by a $\Sigma_2$ assertion of set theory (not in the arithmetic hierarchy, but the Levy hierarchy). It cannot be expressed as a statement about computation, since the particular contents of the set can be changed by forcing, and forcing does not affect the nature of any computation. Perhaps you will object that it is like your CH example, but it isn't of that binary form, and it would seem hard to say that this isn't a legitimate definition of a set of natural numbers that could be defined in some other way.

• there are many others...

I notice in your question that you mention the arithmetic and hyperarithmetic hierarchies, but I disagree with your characterization of them as being statements concerning properties of computation. Although it is true that one can iterate a $\Sigma_1$ process through the ordinals to arrive at the hyperarithmetic sets, it is the complexity of the ordinals that drives this hierarchy, rather than the comparatively trivial use of computation at each step. Similarly, although one could say that projective statements are statements about Turing machines, provided that one is allowed to quantify over integers and reals (one just writes the quantifier-free part of the assertion in terms of computation), this would seem to me to miss the point, for it is the quantification over reals that matters, and not the fact that one writes the quantifier-free part in a way involving computation. Ultimately, therefore, it seems to me that the answer to the ideas in your question consists of a careful appreciation of the nature of the various definability hierarchies.

Allow me to give a little more information by mentioning that there are several very large, intensely studied hierarchies of complexity for real numbers. After the initial familiar notions come several others...

A real $x$ is arithmetic if its digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in computable analysis.) The computable subsets of $\mathbb{N}$ are those for which we can compute yes/no answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.

The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the yes answers for membership in finite time. The concept of relative (oracle) computability leads to the hierarchy of Turing degrees, which measures the comparative computable complexity of a real.

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

A real is hyperarithmetic if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The hyperarithmetic hierarchy is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.

A real is projective if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The projective hierarchy is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.

A real is constructible if it exists in Gödel's constructible universe $L$. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.

A real (or set) is ordinal-definable if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.

The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in computable analysis.) The computable subsets of $\mathbb{N}$ are those for which we can compute yes/no answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.

The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the yes answers for membership in finite time. The concept of relative (oracle) computability leads to the hierarchy of Turing degrees, which measures the comparative computable complexity of a real.

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

A real is hyperarithmetic if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The hyperarithmetic hierarchy is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.

A real is projective if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The projective hierarchy is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.

A real is constructible if it exists in Gödel's constructible universe $L$. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.

A real (or set) is ordinal-definable if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.

I notice in your question that you mention the arithemtic and hyperarithmetic hierarchies, but I disagree with your characterization of them as being statements concerning properties of computation. Although it is true that one can iterate a $\Sigma_1$ process through the ordinals to arrive at the hyperarithmetic sets, it is the complexity of the ordinals that drives this hierarchy, rather than the comparatively trivial use of computation at each step. Similarly, although one could say that projective statements are statements about Turing machines, provided that one is allowed to quantify over integers and reals (one just writes the quantifier-free part of the assertion in terms of computation), this would seem to me to miss the point, for it is the quantification over reals that matters, and not the fact that one writes the quatifier-free part in a way involving computation. Ultimately, therefore, it seems to me that the answer to the ideas in your question consists of a careful appreciation of the nature of the various definability hierarchies.

Allow me to give a little more information by mentioning that there are several very large, intensely studied hierarchies of complexity for reals numbers. After the initial familiar notions come several others...

• rational

• algebraic

• computable

The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in computable analysis.) The computable subsets of $\mathbb{N}$ are those for which we can compute yes/no answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.

• computably enumerable

The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the yes answers for membership in finite time. The concept of relative (oracle) computability leads to the hierarchy of Turing degrees, which measures the comparative computable complexity of a real.

• arithmetic

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

• hyperarithmetic

A real is hyperarithmetic if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The hyperarithmetic hierarchy is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.

• projective

A real is projective if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The projective hierarchy is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.

• constructible

A real is constructible if it exists in Gödel's constructible universe $L$. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.

• ordinal-definable

A real (or set) is ordinal-definable if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.

• generic

A real is generic over $L$ (or some other fixed universe $V$) if it exists in a forcing extension of $L$ (or $V$) by set forcing. Of course, it is relatively consistent with ZFC that every real is generic over $L$, since this is true in $L$ itself, but under some large cardinal axioms, there are reals, such as $0^\sharp$, that cannot be added by forcing over $L$.

The higher levels of these latter hierarchies are further developed and stratified by the enormous variety of models of set theory arising from large cardinals, various inner model constructions, forcing extensions and so on, so that the hierarchy loses its linear nature, becoming instead a dense jungle of various interacting concepts of set theory.

I notice in your question that you mention the arithmetic and hyperarithmetic hierarchies, but I disagree with your characterization of them as being statements concerning properties of computation. Although it is true that one can iterate a $\Sigma_1$ process through the ordinals to arrive at the hyperarithmetic sets, it is the complexity of the ordinals that drives this hierarchy, rather than the comparatively trivial use of computation at each step. Similarly, although one could say that projective statements are statements about Turing machines, provided that one is allowed to quantify over integers and reals (one just writes the quantifier-free part of the assertion in terms of computation), this would seem to me to miss the point, for it is the quantification over reals that matters, and not the fact that one writes the quatifier-free part in a way involving computation. Ultimately, therefore, it seems to me that the answer to the ideas in your question consists of a careful appreciation of the nature of the various definability hierarchies.

Allow me to give a little more information by mentioning that there are several very large, intensely studied hierarchies of complexity for reals numbers. After the initial familiar notions come several others...

• rational

• algebraic

• computable

The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in computable analysis.) The computable subsets of $\mathbb{N}$ are those for which we can compute yes/no answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.

• computably enumerable

The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the yes answers for membership in finite time. The concept of relative (oracle) computability leads to the hierarchy of Turing degrees, which measures the comparative computable complexity of a real.

• arithmetic

A real $x$ is arithmetic if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The arithmetic hierarchy breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.

• hyperarithmetic

A real is hyperarithmetic if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The hyperarithmetic hierarchy is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.

• projective

A real is projective if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The projective hierarchy is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.

• constructible

A real is constructible if it exists in Gödel's constructible universe $L$. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.

• ordinal-definable

A real (or set) is ordinal-definable if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.

• generic

A real is generic over $L$ (or some other fixed universe $V$) if it exists in a forcing extension of $L$ (or $V$) by set forcing. Of course, it is relatively consistent with ZFC that every real is generic over $L$, since this is true in $L$ itself, but under some large cardinal axioms, there are reals, such as $0^\sharp$, that cannot be added by forcing over $L$.

The higher levels of these latter hierarchies are further developed and stratified by the enormous variety of models of set theory arising from large cardinals, various inner model constructions, forcing extensions and so on, so that the hierarchy loses its linear nature, becoming instead a dense jungle of various interacting concepts of set theory.