2
$\begingroup$

We have two integers $i$ and $j$, and the difference between them is large enough such that $(i >j) \rightarrow (K(i) > K(j))$. $K$ is the Kolmogorov complexity function.

We have a set of axioms $\mathcal{A}$ that for sake of argument can prove $i > j$, which is formalized as $\mathcal{A}\vdash i >j$. If we add $(i >j) \rightarrow (K(i) > K(j))$ to $\mathcal{A}$ to make $\mathcal{A}^+$, then $(\mathcal{A} \vdash i > j) \rightarrow (\mathcal{A}^+\vdash K(i) > K(j))$.

By Chaitin's incompleteness theorem, for all finite sets of axioms $S$, there is a value $L_S$ based only on $S$ such that it is impossible to prove $K(b) > L_S$, where $b$ is a bitstring.

Consequently, there is also an $L_{\mathcal{A}^+}$ for $\mathcal{A}^+$. If we set $K(j) > L_{\mathcal{A}^+}$, then for all possible $\mathcal{A}^+$ there is a $j$ such that $\neg(\mathcal{A}^+\vdash K(i) > K(j)$. By modus tollens, this also means that $\neg(A\vdash i >j)$.

This is very strange, because it seems intuitive to me that proving one integer is always larger than smaller integers should always be trivial.

Is there an error in my reasoning?

Improve this question
$\endgroup$
  • $\begingroup$ The expectation that $K$ is an increasing function is totally misguided, and then of course the whole reasoning breaks down (even weak theories such as Robinson arithmetic will prove $i>j$ whenever this is correct). You can easily produce huge numbers that have relatively low complexity because they have compact descriptions (such as evaluate the Ackermann function $A(n)$ times). $\endgroup$ – user138530 Jul 3 '17 at 4:30
  • 1
    $\begingroup$ I'm confused by things like "If we set $K(j)>L_{\mathcal{A}^+}$, then for all possible $\mathcal{A}^+$ there is a $j$ such that ...". $\mathcal{A}^+$ depends on $i$ and $j$ and is a specific system, right? So this seems gibberish. Or when you wrote "$(i>j)\rightarrow (K(i)>K(j))$", did you mean "$\forall i, j[(i>j)\rightarrow (K(i)>K(j))]$"? If so, then that's extremely false - even very weak theories can prove that Kolmogorov complexity is not eventually increasing. $\endgroup$ – Noah Schweber Jul 3 '17 at 4:50
  • $\begingroup$ @ChristianRemling over a large enough interval K is increasing. E.g. once all the 2 bit programs have been taken only 3 bit programs are available. $\endgroup$ – yters Jul 3 '17 at 12:03
  • $\begingroup$ @NoahSchweber that's why I say the difference between $i$ and $j$ is large enough that the implication holds. $\endgroup$ – yters Jul 3 '17 at 12:04
  • $\begingroup$ @yters You're missing my point. Let's start with $\mathcal{A}^*$. Are $i, j$ fixed? If so, then $\mathcal{A}^*$'s Kolmogorov complexity depends on $i$ and $j$, and so the line "If we set $K(j)>L_{\mathcal{A}^*}$" is nonsense - and the difference between $i$ and $j$ is irrelevant. If $i,j$ aren't fixed, then the only interpretation for $\mathcal{A}^*$ I can see is that it is $\mathcal{A}$ together with the sentence "$\forall i, j(i>j\implies K(i)>K(j))$," but of course that (and all variants) leads to a contradictory system because of the non-eventually-increasing nature of $K$. So you need to $\endgroup$ – Noah Schweber Jul 3 '17 at 14:40
2
$\begingroup$

What you've written is pretty unclear, because the nature of $i$ and $j$ seems to be in flux. But there are basically two possibilities, each of which has a fundamental error.

The most natural interpretation of what you've written is that $i, j$ are chosen at the beginning. The choice of $i$ and $j$ determines $\mathcal{A}^*$ - pick different $i$ and $j$ and you get different systems. So for clarity let's write it "$\mathcal{A}[i,j]$" instead of "$\mathcal{A}^*$" so we can distinguish between systems coming from different $i$ and $j$.

Now the mistake reveals itself. You write "Pick $j$ such that $K(j)>L_{\mathcal{A}^*}$." This looks reasonable because the notation suggests that $\mathcal{A}^*$ is a system defined independently of $j$. But in our notation above, what you've written is $$\mbox{"Pick $j$ such that $K(j)>L_{\mathcal{A}[i, j]}$,"}$$ and now it's clear that the existence of such a $j$ needs to be proved. And, in fact, no such $j$ exists.

In fact, we can add a bit of clarity here. If we pick $i$ and $j$ such that $i>j$, then of course $\mathcal{A}$ proves $i>j$; so the system $\mathcal{A}[i,j]$ is equivalent to $\mathcal{A}\cup\{K(i)>K(j)\}$. And now it's even clearer that we can't in fact find a $j$ which works as desired.

The error above can be resolved if we interpret $\mathcal{A}^*$ as being variables which range over some set of values. One bad interpretation is as $$\mathcal{A}^*_1=\mathcal{A}\cup\{(i>j)\rightarrow (K(i)>K(j)): i,j\in\mathbb{N}\}.$$ This is silly, so let's ignore it.

We actually want $i$ and $j$ to range over reasonable values. This suggests a second interpretation: that we have $$\mathcal{A}^*_2=\mathcal{A}\cup\{(\mbox{$i-j$ is "large enough"})\rightarrow[(i>j)\rightarrow (K(i)>K(j))]: i, j\in\mathbb{N}\}.$$ This is a perfectly reasonable system; indeed, the new sentence is provable in $\mathcal{A}$ itself (as long as $\mathcal{A}$ is reasonably strong)! But this system can't actually prove any new values of $K$, since there will be a limit to the pairs $i, j$ for which $\mathcal{A}^*$ proves the appropriate largeness condition, corresponding to $L_\mathcal{A}=L_{\mathcal{A}^*}$.

Finally, we might consider the system $$\mathcal{A}^*_3=\mathcal{A}\cup\{(i>j)\rightarrow (K(i)>K(j)): \mbox{$i-j$ is "large enough"}\}.$$ This system certainly computes lots of new values of $K$; however, it's not recursively axiomatized! So Chaitin's incompleteness theorem doesn't apply.

So the problem with your argument is an ambiguity around what $\mathcal{A}^*$ is. Once we resolve this ambiguity by picking a precise definition, regardless of how we do this, a clear error emerges - either the nonexistence of the desired $j$, or the weakness/incomputability of the theory.

Improve this answer
$\endgroup$
  • $\begingroup$ Your argument shows that any proof of $i > j$ cannot always imply $K(i) > K(j)$. Yet if the definition of $i > j$ does always require the implication, then my larger claim is correct. I can make that a separate question. $\endgroup$ – yters Jul 3 '17 at 18:33
  • 1
    $\begingroup$ @yters What "larger claim"? If $i$ is sufficiently greater than $j$ that $K(i)>K(j)$, then $\mathcal{A}$ can still prove "$i>j$" since $\mathcal{A}$ will not prove "$i$ is sufficiently greater than $j$ that $K(i)>K(j)$." There is absolutely no Kolmogorov complexity barrier to comparing large numbers. $\endgroup$ – Noah Schweber Jul 3 '17 at 19:34
  • $\begingroup$ @yters Also, I'm hoping this is a typo: "if the definition of $i>j$ does always require the implication." You don't get to redefine "$i>j$." If you want to add a new symbol, say "$\succ$," to denote "$i$ is sufficiently greater than $j$ that $K(i)$ is forced to be $>K(j)$," then great - and your argument indeed shows that for sufficiently large $i$ and $j$, $\mathcal{A}$ can't prove $i\succ j$. But that's a very different thing from what you've claimed. $\endgroup$ – Noah Schweber Jul 3 '17 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.