15
$\begingroup$

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I was unable to find such a formulation anywhere so I'd be grateful to be pointed out where I can find it?

$\endgroup$
9
  • 5
    $\begingroup$ I hope you don't expect us to write down a expression of P vs NP problem in the language of ZFC, since that would be one long beast... $\endgroup$
    – Wojowu
    Apr 30, 2016 at 18:04
  • 2
    $\begingroup$ I wonder whether it matters? ZFC seems like a tentative temporary understanding of something mysterious, probably to be superseded entirely within two or three centuries. $\qquad$ $\endgroup$ Apr 30, 2016 at 18:05
  • 1
    $\begingroup$ Can you express this problem in the language of arithmetic? $\endgroup$
    – Asaf Karagila
    Apr 30, 2016 at 18:05
  • 1
    $\begingroup$ @AsafKaragila, I see what you are meaning. We can encode TM's and the operations inside arithmetic and hence inside set theory? $\endgroup$
    – FNH
    Apr 30, 2016 at 18:10
  • 1
    $\begingroup$ Exactly. It's not going to be much different. The point of encoding is that they exist, and behave faithfully to what we expect them to. We don't require them to be necessarily short, understandable, or even at a length which is less than a few googolplex symbols. We just want them to exist. (Which is a very Ingmar Bergman-esque thing to say, I think.) $\endgroup$
    – Asaf Karagila
    Apr 30, 2016 at 18:18

1 Answer 1

16
$\begingroup$

In fact, $\mathbf{P}=\mathbf{NP}$ is an arithmetical statement. What logicians mean by that is that it can be expressed (or, more precisely, a statement "fairly trivially" equivalent to it can be expressed) using only the language of first-order arithmetic, that is, as a formal statement built from {atoms of the form $s=t$ where $s$ and $t$ are expressions built from variables (intended to range over the natural numbers) and the constant $0$ using the binary operations $+$ and $\times$} using boolean connectors and quantifiers over the natural numbers.

For example, $$ \forall p\, \forall q\, ((p\times p = 2\times q\times q) \;\Rightarrow\; (q = 0)) $$ is an arithmetical statement (expressing, essentially, the irrationality of $\sqrt{2}$).

So now there are two distinct questions:

  • Why is $\mathbf{P}=\mathbf{NP}$ (easily equivalent to) an arithmetical statement?

  • Why is every arithmetical statement formally expressible in the language of set theory?

Concerning the first, the key fact is that natural numbers can be used to encode finite sequences of natural numbers (there are various ways to do this, e.g. using the Chinese remainder theorem), so we can encode as arithmetical statements those that speak about (and quantify over) not only natural numbers but also finite sequences thereof. Then we can use this to encode the behavior of Turing machines (e.g., encode a Turing machine, or a partial state or partial execution trace of a Turing machine, as finite sequences of integers), polynomials over the integers, and so on: essentially anything which is "finistic", i.e., encodable using finite data, can be translated using natural numbers using enough coding.

Then we can express the statement: "for any nondeterministic Turing machine $T$ and any polynomial $f$ such that: {for any finite input $x$, either (a) there exists a valid execution trace of $T$ starting on $x$ with time length than $f(|x|)$ (where $|x|$ is the length of $x$) terminating in the result value $1$, or else (b) all execution traces of $T$ starting on $x$ have time length than $f(|x|)$ and terminate in the result value $0$}, there exists a deterministic Turing machine $T'$ and a polynomial $f'$ such that: {for any finite input $x$, the execution trace of $T$ starting on $x$ has time length less than $f'(|x|)$ and terminates in the result value $1$ in case (a) and $0$ in case (b)}". Everything in there is finistic, therefore arithmetical.

(Of course, we can simplify the above statement once we know that there exists an $\mathbf{NP}$-complete problem. But that would beg the question of why this quetion is, itself, arithmetical.)

Concerning the question of why every arithmetical statement is expressible in the language of set theory, the thing is that the set $\omega$ of natural numbers (which is identified with the smallest infinite ordinal in the orthodox view of mathematics) can be defined inside $\mathsf{ZFC}$, and so can addition and multiplication over the integers. So any arithmetical statement can be rewritten as a statement about those sets definable within $\mathsf{ZFC}$. Again, it's a matter of coding.

Of course, I'm making matters harder by going through the "arithmetical" route: you can encode Turing machines (and their execution traces, and so on) and polynomials and everything of the sort, within set theory. In fact, the orthodoxy of mathematics is that (barring exotic things from set theory itself) every mathematical object whatsoever can be "encoded" as a set, and therefore, any formalizable statement made by mathematicians, can be translated into a statement of set theory (or, for the ultra-orthodox, that it "is" a statement of set theory in the first place, and that all of mathematics is done within $\mathsf{ZFC}$).

It should be viewed as a question of encoding: much like everything a computer handles is "encoded" as a finite binary string, everything a mathematician handles is "encoded" as a set. Some (but not all) of these things can, additionally, be "encoded" as a natural number, because they are finistic in nature. So many mathematical statements are arithmetical, but all are set-theoretic. (An example of a statement with is set-theoretic but not arithmetical is the continuum hypothesis: it is not equivalent to any arithmetical statement.)

Now decidability is something different. There is a formal system for dealing with arithmetical statements, namely $\mathsf{PA}$ (:= first-order Peano arithmetic), just like there is one for dealing with set-theoretic statements, namely $\mathsf{ZFC}$. The latter is stronger than the former, in two respects: first, it can talk about more things, because not all set-theoretic statements are arithmetical; second, even among the arithmetical statements, there are some that $\mathsf{ZFC}$ can prove and that $\mathsf{PA}$ cannot (the simplest example being "$\mathsf{PA}$ does not prove $0=1$", a statement that is arithmetical because it says essentially that a Turing machine that searches for a proof of $0=1$ within $\mathsf{PA}$ never terminates, and unprovable in $\mathsf{PA}$ whereas it is provable in $\mathsf{ZFC}$).

But in real life (i.e., outside of mathematical logic), arithmetical statements that are provable in $\mathsf{ZFC}$ but not in $\mathsf{PA}$ are rare (one example is Kruskal's tree theorem; there are occasional debates on whether, for example, Fermat's last theorem is provable within $\mathsf{PA}$, but I don't think anyone seriously doubts it, even if prima facie, Wiles's proof uses techniques that goes beyond $\mathsf{PA}$).

And arithmetical statement (as opposed to general set-theoretic statements) that are unprovable in $\mathsf{ZFC}$ but still known/believed to be true because they follow from stronger systems like the addition of large cardinals, are pretty much unheard-of (I mean, there's no doubt that they exist: "$\mathsf{ZFC}$ does not prove $0=1$" is an arithmetical statement that $\mathsf{ZFC}$ does not prove and which is still known/believed to be true because it follows from the existence of inaccessible cardinals; but it is often thought that such statements simply do not occur in ordinary mathematical work unless you actively look for them).

So it is logically conceivable that neither (the arithmetical statement) $\mathbf{P}=\mathbf{NP}$ nor its negation follow from $\mathsf{ZFC}$, but I don't think anyone really believes this seriously. (Even if it does happen, it could be because $\mathbf{P}=\mathbf{NP}$ is true, there exists an algorithm solving an $\mathbf{NP}$-complete problem but $\mathsf{ZFC}$ cannot prove that; or it could be because $\mathbf{P}\neq\mathbf{NP}$ is true and $\mathsf{ZFC}$ cannot prove that.)

$\endgroup$
12
  • $\begingroup$ any non-deterministic Turing machine ??? how would you define that in the language of arithmetic ? to me, it seems to be the key point. and the other point is : how do we define Turing machines in the language of arithmetic ? it seems obvious that we can, but detailing "the different ways for achieving it" seems interesting too. $\endgroup$
    – reuns
    Apr 30, 2016 at 22:38
  • 3
    $\begingroup$ @user1952009 A deterministic Turing machine is just a finite transition table {states}×{symbols}→{states}×{symbols}×{directions}, all these data are finistic, so can be coded using integers; a nondeterministic TM is a finite multimap instead of a map (a subset of {states}×...×{directions}), so it is again finistic. There is no particular difficulty there. $\endgroup$
    – Gro-Tsen
    Apr 30, 2016 at 22:45
  • $\begingroup$ As for executions of such machines, provided we start with a tape with only finitely many symbols on it initially, it is still a finite datum, and will remain such after finitely (but arbitrarily) many states: an "execution trace" is a finite list of finite tape + state, and checking whether an execution trace follows the program is still finistic, etc. The details are tedious, but there is no real difficulty. $\endgroup$
    – Gro-Tsen
    Apr 30, 2016 at 22:48
  • 1
    $\begingroup$ @user1952009 I think my definition of a nondeterministic TM is fairly standard (it seems to be that on Wikipedia). A "problem" doesn't have to be defined: P=NP just says that any set of integers that is accepted in polynomial time by some (any) nondeterministic TM is accepted in polynomial time by some deterministic TM, so that is what I state. Nor do we need a proof of the fact that they accept the same sets, merely that they do (of course, to prove P=NP, we would need something like that, but not to state it). $\endgroup$
    – Gro-Tsen
    Apr 30, 2016 at 23:21
  • 1
    $\begingroup$ Nice answer. I think it's rather strange to say that the claim "$\text{ZFC}$ does not prove $0=1$" is believed to be true because it follows from the existence of inaccessible cardinals. I expect that most people who believe the claim have no idea what an inaccessible cardinal is, and anyone who seriously doubts the claim would not be convinced by the proof in ZFC + there exists an inaccessible! $\endgroup$ May 1, 2016 at 5:18

You must log in to answer this question.

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