2
$\begingroup$

The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of them). So why is it not $\Delta_1^0$ ? Something very basic is wrong in my reasoning, but I fail to see what. Thanks

$\endgroup$
0

2 Answers 2

5
$\begingroup$

There are essentially two different heirarchies that are related. There is the arithmetic hierarchy on formulas, which is just a formal statement about the logical formula as written.

Then there is the arithmetical hierarchy on subsets of $\mathbb N$ (or more generally, on subsets of $\mathbb N^k$ for some $k$.)

A subset $S\subset\mathbb N$ is in $\Pi_k^0$ if and only if there is a formula $\phi(n)$ which is a $\Pi_k^0$ formula with only one unbound variable, $n$, such that $n\in S\iff \phi(n)$.

So the statement $\phi(n)$ defined as "$n-1$ is prime and $n+1$ is prime" can be written, as a formula, so that it is $\Pi_0^0$. Therefore the set, $$\{n:n-1 \text{ and } n+1 \text{ are prime}\}$$ is,as a set, $\Pi_0^0$.

The twin prime conjecture is that there are infinitely many twin prime pairs, which can be written as:$$\forall k:\exists n: n>k \land \phi(n)$$ Since $\phi(n)$ is $\Pi_0^0$, this expression is $\Pi_2^0$.

In general, if an expression $\rho(n)$ is in $\Pi_k^0$, then whether $\{n:\rho(n)\}$ is infinite can be expressed by a formula in $\Pi_{k+2}^0$. That doesn't mean that the formula is not provably equivalent to some simpler formula lower in the hierarchy, however.

This doesn't say anything about whether the twin prime conjecture is decidable or not - the twin prime conjecture is not a function, it is just a true/false statement, so it doesn't fall under the domain of "computable functions."

For example, the formula for stating that there are infinitely many primes is minimally represented as $\Pi_2^0$, but that doesn't mean that we can't prove that there are infinitely many primes - the infinitude of the prime numbers is decidable.

The Wikipedia article on the arithmetic hierarchy might help make the distinction between the hierarchy on formulas and the hierarchy on sets a little clearer.

$\endgroup$
5
  • $\begingroup$ Thanks! I am still confused. By definition, a set X of natural numbers is defined by formula φ in the language of Peano arithmetic if the elements of X are exactly the numbers that satisfy φ. What would be that set if φ is the twin primes conjecture (the $\Pi_2^0$)? and what will be that set X for ¬φ? $\endgroup$ Nov 28, 2012 at 14:59
  • 1
    $\begingroup$ The twin prime conjecture is a sentence, so it's not the sort of formula that can define a set: such a formula needs a free variable. In other words, $X = \left\{ n : \varphi(n) \right\}$ for some $\varphi$. If you put in a sentence you'll just end up with $X = \emptyset$ or $X = \mathbb{N}$, depending on whether the sentence is false or true. $\endgroup$ Nov 28, 2012 at 15:04
  • $\begingroup$ There is no set. $\Pi^0$ is not about sets, it is about true-false expressions. $\endgroup$ Nov 28, 2012 at 15:04
  • $\begingroup$ The arithmetical hierarchy is about the complexity of sets definable by certain sorts of formulae. The $\Delta_1$ sets are those sets $X$ such that $n \in X \Leftrightarrow \varphi(n)$ where $\varphi$ is $\Sigma_1$, and there is a $\Sigma_1$ formula $\psi$ defining the complement of $X$. @julianfernandez isn't wrong to link these things, he just hasn't fully grasped the nature of the relationship yet. $\endgroup$ Nov 28, 2012 at 15:07
  • $\begingroup$ @BenedictEastaugh Thanks, yes, that clarifies it better. I'll try to update my answer to make that clearer. $\endgroup$ Nov 28, 2012 at 18:26
4
$\begingroup$

There's a terminological ambiguity here that I think may be the source of your confusion. A formula in the language of arithmetic, $\varphi$, can be more or less complex, depending on how many alternating unrestricted quantifiers appear at the front of the formula (we assume all formulae appear in prenex normal form). So given a formula $\psi$ containing no quantifiers, $\exists{n}\;\psi$ is a $\Sigma_1$ formula while $\forall{n}\;\psi$ is a $\Pi_1$ formula. $\exists{n}\forall{m}\;\psi$ is a $\Sigma_2$ formula, $\forall{n}\exists{m}\;\psi$ is a $\Pi_2$ formula, and so on.

That's formulae. But another common locution is "This set is $\Sigma_1$." So what is it for a set to be $\Sigma_1$ (or $\Pi_1$, etc.)? Well, it's just for it to be definable by a $\Sigma_1$ formula $\varphi$, so that

$$n \in X \Leftrightarrow \varphi(n).$$

So on the one hand we have formulae, like the twin prime conjecture. This is a $\Pi_2$ statement: a sentence in the language of arithmetic, saying that some particular property of the natural numbers holds. And on the other hand, we have sets, like the set of twin primes. How complex is this set? Well, we have an effective method for finding twin primes. In fact, we can do better than that: given a pair of numbers, we can always determine in a finite amount of time whether they are twin primes, and if they aren't, we can determine that too. So the set of twin primes is recursive (regardless of whether or not the twin prime conjecture holds).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .