Is Complexity in Mathematics Determinate?

[TimeSkip]

Slightly related to the OP, and what @fresh_42 has said, and I want to quote it again, is what Gödel said in "On the Length of Proofs":

"The transition to the logic of the next higher type not only results in certain previously unprovable propositions becoming provable, but also in it becoming possible to shorten extraordinarily infinitely many of the proofs already available."

How is that possible? I understand that the alphabet mustn't be growing anymore (or does it?), but, more axioms in the metalogical proof being available to entertain?

 

[suremarc]

I do not think that this specific statement (taken exactly as it is) is true. That $BB:\mathbb{N} \rightarrow \mathbb{N}$ is a total function would be a theorem of set theory [as a corollary to every statement of $PA$ being either true or false due to LEM].

I don’t understand what you mean in this last statement, but yes, I realize now I was mistaken. I was looking for an analog of Goodstein’s theorem for ZFC.

 

[SSequence]

I don’t understand what you mean in this last statement, but yes, I realize now I was mistaken. I was looking for an analog of Goodstein’s theorem for ZFC.

Yeah, you are right in that a statement (about $BB$ numbers) very similar to it will indeed be independent of set theory.

Nevermind about the sentence in brackets (I think the discussion would drift from the main topic).

 

[stevendaryl]

Slightly related to the OP, and what @fresh_42 has said, and I want to quote it again, is what Gödel said in "On the Length of Proofs":

"The transition to the logic of the next higher type not only results in certain previously unprovable propositions becoming provable, but also in it becoming possible to shorten extraordinarily infinitely many of the proofs already available."

How is that possible? I understand that the alphabet mustn't be growing anymore (or does it?), but, more axioms in the metalogical proof being available to entertain?

A lot of proofs in mathematics are proofs by induction. The simplest type of induction axiom is this:

$(\Phi(0) \wedge (\forall n \Phi(n) \Rightarrow \Phi(n+1))) \Rightarrow \forall n \Phi(n)$

So suppose that you want to prove $\Phi(100)$. Then you can do it in four steps:

1. Prove $\Phi(0)$
2. Prove $\forall n \Phi(n) \Rightarrow \Phi(n+1)$
3. Conclude from the induction axiom $\forall n \Phi(n)$
4. Take the special case $n = 100$ to get $\Phi(100)$

Now, if you didn't have an induction axiom, you could still prove $\Phi(100)$ in the following way:

1. Prove $\Phi(0)$
2. Prove $\forall n \Phi(n) \Rightarrow \Phi(n+1)$
3. Take the special case of 2 in which $n=0$ to conclude $\Phi(0) \Rightarrow \Phi(1)$
4. Using 1 and 3, conclude $\Phi(1)$
5. Take the special case of 2 in which $n=1$ to conclude $\Phi(1) \Rightarrow \Phi(2)$
6. Using 4 and 5, conclude $\Phi(2)$
7. etc.

So you could eventually prove $\Phi(100)$, but it would take you something like 202 steps, compared to a single step with the induction axiom.

The same thing is true with more powerful induction axioms. They allow you to prove more general statements and then get the specific statement you are interested in as a special case.

Higher-order systems of mathematics allow for more powerful induction axioms. So that's one reason why proofs can be made shorter in these systems.

 

[TimeSkip]

A lot of proofs in mathematics are proofs by induction. The simplest type of induction axiom is this:

$(\Phi(0) \wedge (\forall n \Phi(n) \Rightarrow \Phi(n+1))) \Rightarrow \forall n \Phi(n)$

So suppose that you want to prove $\Phi(100)$. Then you can do it in four steps:

1. Prove $\Phi(0)$
2. Prove $\forall n \Phi(n) \Rightarrow \Phi(n+1)$
3. Conclude from the induction axiom $\forall n \Phi(n)$
4. Take the special case $n = 100$ to get $\Phi(100)$

Now, if you didn't have an induction axiom, you could still prove $\Phi(100)$ in the following way:

1. Prove $\Phi(0)$
2. Prove $\forall n \Phi(n) \Rightarrow \Phi(n+1)$
3. Take the special case of 2 in which $n=0$ to conclude $\Phi(0) \Rightarrow \Phi(1)$
4. Using 1 and 3, conclude $\Phi(1)$
5. Take the special case of 2 in which $n=1$ to conclude $\Phi(1) \Rightarrow \Phi(2)$
6. Using 4 and 5, conclude $\Phi(2)$
7. etc.

So you could eventually prove $\Phi(100)$, but it would take you something like 202 steps, compared to a single step with the induction axiom.

The same thing is true with more powerful induction axioms. They allow you to prove more general statements and then get the specific statement you are interested in as a special case.

Higher-order systems of mathematics allow for more powerful induction axioms. So that's one reason why proofs can be made shorter in these systems.

So, are induction axioms subject to complexity or is it purely intuitionistic?

 

[TimeSkip]

So, I don't think anyone has addressed the question posed in the title; but, is complexity in mathematics in your opinion determinate?

Thanks.

 

[stevendaryl]

So, I don't think anyone has addressed the question posed in the title; but, is complexity in mathematics in your opinion determinate?

Thanks.

I think you haven't made it clear, to me, anyway, what you mean by "complexity" and "determinate".

 

[TimeSkip]

I think you haven't made it clear, to me, anyway, what you mean by "complexity" and "determinate".

Namely a precise amount of steps to call a proof either least (qualitatively less 'complex') or where a necessarily least amount of steps has been made in the proof of the theorem.

Can you conceptualize 'complexity' if this is hard to still understand or at least quantify it in regards to proofs?

 

[Stephen Tashi]

The development of mathematics often involves inventing definitions and proving theorems using the new terminology. Using new terminology allows statements to be written in a shorter form. Is this phenomena represented when we compute "Turing Complexity"?

I don't think the use of definitions corresponds to the concept of using subprograms. For example (I think) that if a program running on a Turing Machine executed a subprogram that has 10 steps ten times then that would count as 100 steps of computation, not 10.

 

[Jarvis323]

Do mean that,

Namely a precise amount of steps to call a proof either least (qualitatively less 'complex') or where a necessarily least amount of steps has been made in the proof of the theorem.

Can you conceptualize 'complexity' if this is hard to still understand or at least quantify it in regards to proofs?

Maybe the question is the same as something like, is a function $f_L : T \longrightarrow \mathbb{N}$, defined as $f(t;L)=\min_{p\in P_{t,L}}|p|$ computable? Where $T$ is the set of all provable theorems, and $L$ is the formal language for the axiomatic system, over a given alphabet $A$, that the theorems and proofs are expressed in, and $P_{t ,L}$ is the set of proofs of theorem $t$ under language $L$.

I think that the answer is yes, granted that you have $T$, the set of provable theorems. Because you could compute this function by simply testing all possible proofs one by one from smallest to biggest, and checking if they prove the theorem or not, and then stop when they do. There is one catch, which is that we don't know what the domain is, because we don't know if some theorems are provable or not. But say you had a proof of a theorem and you wanted to know if it were the shortest possible one, just test every string in the language that is smaller and see if any of them are shorter proofs of the same theorem.

The other question you seem to be asking is whether the size of the alphabet matters. Say you had the provable theorems ordered according to the size of their minimal proofs in a given language. Would the order change if the language changes? It could change by having different syntax, and a larger or smaller alphabet. Yes, I think that a theorem may have a smaller or larger minimal proof relative to another theorem in the different language.

One thing that might be neglected, with a finite alphabet, is the need to encode each symbol. A Turing machine can only handle a finite number of symbols, and we pretend that we can write and read symbols with atomic operations. Maybe in a real physical system, that is not true, because we need to decipher each symbol, and if you have a lot of different ones, then there will be more work to be done deciphering and distinguishing them. With modern computers, the alphabet is actually 0s and 1s. And characters are represented as strings of 0s and 1s that encode them. We usually neglect the cost of encoding characters and such things, when they are finite in number, since it's only a constant amount of overhead, it's still $O(1)$ to read and write, say an ASCII character, in order to model a language with a larger alphabet than just 0s and 1s.

However, say we want to model a formal language with an infinite alphabet, I don't think you could make the simplifying assumption that each symbol is read or written with an atomic operation. At least not with a Turing machine. What you would have instead of an alphabet is something like the set of all natural numbers. And the complexity of reading or writing one of them would be a function of the length of it's encoding $n$. So reading and writing the symbols would be $O(n)$.

But suppose you did have a formal axiomatic system with a language over an infinite alphabet. Then to model it with a Turing machine, you would have to choose which symbols, with their particular meanings get to be represented by the smaller or larger natural numbers that encodes them. Supposing the language makes sense, still, the relative size of the minimal proof of one theorem compared to another could change simply by making one such different choice about encoding the symbols alone.

 

[TimeSkip]

The development of mathematics often involves inventing definitions and proving theorems using the new terminology. Using new terminology allows statements to be written in a shorter form. Is this phenomena represented when we compute "Turing Complexity"?

Well, yes. All I'm saying is there even any syntactical sense in talking about a "growing alphabet" even though we don't really know how complexity should be defined in we cannot begin to ascertain in any quantitative aspect the notion of a proofs complexity, instead resorting to something of the sort in talking about a proofs 'length', whatever that may or may not mean?

 

[TimeSkip]

I think that the answer is yes, granted that you have $T$, the set of provable theorems. Because you could compute this function by simply testing all possible proofs one by one from smallest to biggest, and checking if they prove the theorem or not, and then stop when they do. There is one catch, which is that we don't know what the domain is, because we don't know if some theorems are provable or not. But say you had a proof of a theorem and you wanted to know if it were the shortest possible one, just test every string in the language that is smaller and see if any of them are shorter proofs of the same theorem.

The other question you seem to be asking is whether the size of the alphabet matters. Say you had the provable theorems ordered according to the size of their minimal proofs in a given language. Would the order change if the language changes? It could change by having different syntax, and a larger or smaller alphabet. Yes, I think that a theorem may have a smaller or larger minimal proof relative to another theorem in the different language.

Yeah, syntax would be the question in point here. I know that Gödel pretty much disproved that there's any universal syntax to be applied in terms of formalism. Yet, still it seems important to say that the size of the alphabet matters, in terms of the provability or even decidability of algorithmic equations like God's algorithm.

 

[TimeSkip]

Instead of repeating the same, I suppose the follow up question would be:

If complexity in mathematics is not determinate or cannot be determined exactly or at least with a lower bound estimate, then what mathematical proof assertions are subject to it?

If none at all, then what can be said about the nature of proof's in mathematics, as purely intuitive or intuitionalist?

 

[TimeSkip]

I posted elsewhere about this, and at risk of spewing gobbledygook I would like to expand the scope a little, and say that it seems to mathematicians this isn't something they would call a discovery, much to the consensus of mathematicians it seem more like mathematics deals with inventions or the undetermined aspect of imagination being an inventive feature of human intuition that is mathematics.

Anyone want to comment on this broadening of scope of analysis about the nature of mathematical truths?

 

[nuuskur]

My brain is in knots, I can't follow anything at all, it should go like this
<br /> A_1\rightarrow A_2\rightarrow \ldots\rightarrow A_{n-1} \rightarrow A_n,<br />
but instead it's going more like this..
<br /> A_1 \rightarrow A_2 \overset{?!}\rightarrow A_3?, B_1? \rightarrow \ldots \rightarrow A_n (?) \rightarrow \ldots<br />
The more philosophy flavored forums might entertain the notion of arguing based on foggy intuition spawned semi-definitions, but you are constantly assuming we all know what (the hell) you mean by every single piece of terminology you put out here. This is not mathematics, not even on a meta level.

Worse still, you have the auauaudacity to point out that nobody has actually answered your question. Have you considered that your question is incomprehensible?

 

[TimeSkip]

My brain is in knots, I can't follow anything at all, it should go like this
<br /> A_1\rightarrow A_2\rightarrow \ldots\rightarrow A_{n-1} \rightarrow A_n,<br />
but instead it's going more like this..
<br /> A_1 \rightarrow A_2 \overset{?!}\rightarrow A_3?, B_1? \rightarrow \ldots \rightarrow A_n (?) \rightarrow \ldots<br />
The more philosophy flavored forums might entertain the notion of arguing based on foggy intuition spawned semi-definitions, but you are constantly assuming we all know what (the hell) you mean by every single piece of terminology you put out here. This is not mathematics, not even on a meta level.

Worse still, you have the auauaudacity to point out that nobody has actually answered your question. Have you considered that your question is incomprehensible?

I think fresh_42, already answered it here:

https://www.physicsforums.com/threads/is-complexity-in-mathematics-determinate.1000094/post-6462143

I'm not sure I can elaborate as I already tried.

 

[berkeman]

Thread closed temporarily for Moderation.

 

[Mark44]

And since the thread has run its course, it is now closed.