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

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$.," or more concretely that $\mathcal{O}^\mathcal{O}$ is not $\Pi^1_2$ complete. The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$." The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$," or more concretely that $\mathcal{O}^\mathcal{O}$ is not $\Pi^1_2$ complete. The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

Post Undeleted by Noah Schweber
Post Deleted by Noah Schweber
added 324 characters in body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. Deduction is onlyIn terms of Turing degree this means that we're not going to "add a $\Pi^1_1$" here, so we get that the special classes are exactlyescape the $\Sigma^m_n$s and $\Pi^m_n$s for $m\in\{0,1\}$ and$\omega$th hyperjump of $n\in\omega$; that is$\emptyset$, which is a tiny subclass of special = analytical$\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$." The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. Deduction is only going to "add a $\Pi^1_1$" here, so we get that the special classes are exactly the $\Sigma^m_n$s and $\Pi^m_n$s for $m\in\{0,1\}$ and $n\in\omega$; that is, special = analytical.

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.

(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$." The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)

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

Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:

Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).

Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. Deduction is only going to "add a $\Pi^1_1$" here, so we get that the special classes are exactly the $\Sigma^m_n$s and $\Pi^m_n$s for $m\in\{0,1\}$ and $n\in\omega$; that is, special = analytical.