Or in other words how are mathematical theorems and proofs scrutinized in terms of complexity if completeness cannot be determined first.

And, another approach is to determine the amount of information a proof "contains" informationally and then be able to ascertain this with a metric of a quantum computer, I think?

What does it mean to say that a theorem is complete - or incomplete? What is a theorem's complexity?

The logic for determining this is that a Gödel alphabet can expand infinitely until it attains completeness — Shawn

Complete? At infinity? That means it never is, yes?

I think I know what a Godel alphabet is, another term for Godel numbering, a method for assigning a unique number to an expression. As such any such system maxes out at a countable length. No infinities. He did write an article titled, "On the Length of Proofs," the gist of which is that by adding axioms 1) unprovable theorems may become provable, and 2) many long proofs may be shortened.

What is a theorem's complexity? — tim wood

I think I can help with this question. It simply means the number of steps to determine a Q.E.D. result for a Turing machine. Of course there's no units to measure this by, which reverts us back to the original question.

Complete? At infinity? That means it never is, yes? — tim wood

Well, hypothetically, and I firmly believe that completeness isn't impossible to entertain, that by expanding the Gödel alphabet up to a certain integer, that we might arrive at a proof that is least complex for a theorem.

He did write an article titled, "On the Length of Proofs," the gist of which is that by adding axioms 1) unprovable theorems may become provable, and 2) many long proofs may be shortened. — tim wood

Yes, you did mention this previously, which is of interest to me. Yet, as mentioned that given the Second Incompleteness Theorem, you cannot have consistency, which aligns with no way of determining complexity, even without the previous issue with no unitary measure of determining it at all!

whether it is necessary for determining a theorems complexity, whether it would be needed it to be proven true that it is complete. — Shawn

What do you mean by a theorem being complete?

[the complexity of a theorem is] the number of steps to determine a Q.E.D. result for a Turing machine. — Shawn

What do you mean by "determine a QED result for a Turing machine"?

/

Have you read a book in mathematical logic?

What do you mean by a theorem being complete? — TonesInDeepFreeze

There aren't many to talk if any, and Godel's Incompleteness theorems apply retroactively, to all that have denumerable and countable alphabets. However, some uncountable alphabets exist, which leaves open the possibility that a theorem may be complete, yet possibly incomprehensible.

What do you mean by "determine a QED result for a Turing machine"? — TonesInDeepFreeze

That the Turing complexity is determinate or definite.

There aren't many to talk if any, and Godel's Incompleteness theorems apply retroactively, to all that have denumerable and countable alphabets. However, some uncountable alphabets exist, which leaves open the possibility that a theorem may be complete, yet possibly incomprehensible. — Shawn

That is not an answer to my question, and it's gibberish as is the rest of what you've posted in this thread.

You've brought this up before. Let me get it straight. You are not talking about deriving the proof of a math theorem, you are asking that if I were to conjecture a theorem, then prove it, and then put my proof into some sort of computer algorithm - which is just another way of writing it out - is there a way to determine the "complexity" of my proof by examining the algorithm? Is this what you mean?

which leaves open the possibility that a theorem may be complete, yet possibly incomprehensible. — Shawn

Are you saying a theorem is complete if it has been proven?

Then provide your reasoning. I don't see what your getting at. Everything written in the OP is just what it says.

You are not talking about deriving the proof of a math theorem, you are asking that if I were to conjecture a theorem, then prove it, and then put my proof into some sort of computer algorithm - which is just another way of writing it out - is there a way to determine the "complexity" of my proof by examining the algorithm? Is this what you mean? — jgill

Yes, jgill, that's what I mean. In simpler terms, I don't see how logically you can begin to ascertain "complexity" or Turing complexity of a theorem's proof by working at it in any way without knowing it being complete and/or consistent, which Gödel proved it being impossible to satisfy it being both complete and consistent.

Are you saying a theorem is complete if it has been proven? — jgill

No, I'm saying that to work on a theorem in terms of "complexity", which doesn't even have unitary measure or quantifiable methodology to start with, then how does one ascertain this with the proof being moot in terms of both completeness and consistency.

Hope that makes some sense.

Actually, in even more simpler terms to determine the complexity of theorems, supposedly, of greater importance would be a focus on completeness rather than consistency of a theorem, as the proof of a theorem is more concerned with maintaining consistency by all measures.

What do others think? Does this make things sounds somewhat disorganized in how proofs are written?

What do others think? Does this make things sounds somewhat disorganized in how proofs are written? — Shawn

Your OP and subsequent posts are a mishmash of several things and I can't figure out what you're saying. You could be talking about an extension of Turing machines that accept languages over an uncountable alphabet. You could be talking about Turing degree, the level of algorithmic unsolvability sets of natural numbers. Interestingly this is not a linear order, so that there are sets with incomparable Turing degree. You could be talking about extending an incomplete axiomatic system by adding either a proposition or its negation in order to form a larger system, which is still necessarily incomplete; and doing that over and over, hoping to eventually generate a complete system. That can't be done, and was in fact the subject of Turing's doctoral dissertation. You also tossed in Kolmogorov complexity and even everyone's favorite buzzphrase, quantum computing.

Is it possible for you to focus your subject? Can you perhaps give a specific example of what you're getting at?

Is it possible for you to focus your subject? Can you perhaps give a specific example of what you're getting at? — fishfry

The subject or point in question is whether one can determine a theorem's complexity from the fact that a theorem cannot both be consistent and complete, according to Gödel's Incompleteness Theorems?

a theorem cannot both be consistent and complete, according to Gödel's Incompleteness theorems? — Shawn

A theorem can neither be consistent nor complete not by virtue of Gödel, but rather by virtue of the fact that the terms consistency and completeness apply to axiomatic systems and NOT to theorems. You seem unclear on this point.

Let me elaborate in an effort to be useful. Standard set theory, ZF, is incomplete by Gödel's first incompleteness theorem. We can identify a particular proposition that can neither be proved nor disproved, say the axiom of choice, That's incompleteness. Consistency just says that there's no proposition P such that both P and not-P can be proven from ZF. So consistency and completeness are properties of axiomatic systems.

A particular theorem, like Fermat's last theorem, or the fundamental theorem of finitely generated Abelian groups, or the fundamental theorem of calculus, do not have the properties of consistency and completeness. Those properties don't apply to individual theorems.

A theorem can neither be consistent nor complete not by virtue of Gödel, but rather by virtue of the fact that the terms consistency and completeness apply to axiomatic systems and NOT to theorems. You seem unclear on this point. — fishfry

Please forgive my lack of knowledge on the matter; but, what I wanted to say that a theorems proof for an axiomatic system in math is unable to be ascertained in complexity with regards to being neither complete and consistent.

With this fact being true, then how does one ever hope to gauge a mathematical theorem's proof as measurably complex or less complex.

Please forgive my lack of knowledge on the matter; but, what I wanted to say that a theorems proof for an axiomatic system in math is unable to be ascertained in complexity with regards to being neither complete and consistent. — Shawn

This sentence repeats the same misunderstanding. Individual theorems do not have the consistency or completeness attributes, in the same sense that automobile tires don't have the horsepower attribute.

With this fact being true, — Shawn

As stated, what you said is not sufficiently clear to be true or false; but if I had to guess at your meaning, it's false because consistency and completeness don't apply to individual theorems.

then how does one ever hope to gauge a mathematical theorem's proof as measurably complex or less complex. — Shawn

For computational problems, computational complexity theory is the standard approach, as you already know. For theorems, I suppose if anyone cared, we can pick any one of the contemporary proof assistants like Coq or Agda, and define the complexity of a theorem as the shortest proof of that theorem in such a system.

But completeness and consistency of axiomatic systems seem to have little or nothing to do with your question. If a theorem has a proof and you want to find the simplest one, that has nothing to do with the axiomatic system being incomplete. The axiom of choice has no proof in ZF so it's meaningless to ask about the simplest proof. And if a system is inconsistent, then everything has a one-line proof following directly from the inconsistency. So completeness and consistency are irrelevant to your question.

provide your reasoning — Shawn

Reasoning requires definitions. You have not provided them.

I don't see what your getting at. — Shawn

What I'm getting at is exactly the question I already asked:

What is your definition of 'a theorem is complete'?

Do you know what a definition is?

This sentence repeats the same misunderstanding. Individual theorems do not have the consistency or completeness attributes, in the same sense that automobile tires don't have the horsepower attribute. — fishfry

So, when I say that a proof of a theorem is subject to not being able to determine its complexity does that mean anything?

But completeness and consistency of axiomatic systems seem to have little or nothing to do with your question. If a theorem has a proof and you want to find the simplest one, that has nothing to do with the axiomatic system being incomplete. The axiom of choice has no proof in ZF so it's meaningless to ask about the simplest proof. And if a system is inconsistent, then everything has a one-line proof following directly from the inconsistency. So completeness and consistency are irrelevant to your question. — fishfry

What I'm trying to determine is whether there is any possibility to determine the complexity of proofs by reasoning that a Q.E.D. would occur at the least exhaustive method of determining it. Does that make sense? Following with this logic, if you don't have a method of doing this, then how can you determine complexity in mathematical proofs?

What I'm trying to determine is whether there is any possibility to determine the complexity of proofs by reasoning that a Q.E.D. would occur at the least exhaustive method of determining it. Does that make sense? Following with this logic, if you don't have a method of doing this, then how can you determine complexity in mathematical proofs? — Shawn

May I try? Is it a fair translation to say that you're interested in the length of proofs and determining when a given proof is the shortest?

As to determining complexity itself, that measure is pre-given, yes? E.g., as the count of the symbols in the proof? In any case you cannot measure anything without first having established a method of measuring and quantifying it, yes?

As to shortest, that's becomes sensitive to definition, as well as "least exhaustive." Akin to the situation of the contractor who has a two-hour job. He has a marvelous tool that will do the job in two minutes, but that takes him six hours to set up. Not to mention acquisition, carrying, operating and incidental labor, maintenance, insurance, transport, licensing, and materials costs, to name a few.

So the question dissolves into consideration of practical constraints. Shortest depends strictly on definition and utility. So the only way to entertain your question is to first establish what it is, exactly, you're about, or are looking for. If in theory or seeming, sure. If in principle, what principles? if in fact, get out your slide rule.

May I try? Is it a fair translation to say that you're interested in the length of proofs and determining when a given proof is the shortest? — tim wood

Yes.

As to determining complexity itself, that measure is pre-given, yes? — tim wood

No, according to how I view complexity, it's ascertained or determined by the shortest Q.E.D.

E.g., as the count of the symbols in the proof? In any case you cannot measure anything without first having established a method of measuring and quantifying it, yes? — tim wood

Well, yes. Meaning that the amount of primitives and recursions leads to the least exhaustive outcome for a Turing machine.

It's interesting @tim wood and @fishfry, that Kolmogorov complexity is not computable, so not sure if this is moot.

it's ascertained or determined by the shortest Q.E.D. — Shawn

How long is this stick? Oh, by the way, no means or methods of measuring allowed.

How long is this stick? Oh, by the way, no means or methods of measuring allowed. — tim wood

Yeah, and that's not even counterintuitive, until I bring into the discussion completeness and consistency of a theorem, which seemingly, as I view it, are needed to determine the shortest length of a proof to determine the complexity of it. And, brute forcing the result of the shortest Q.E.D. is not really that interesting to talk about.

Kolmogorov complexity — Shawn

Subject to correction, this is a non-deterministic method. Which means that the "complexity" of the use of it itself becomes part of the problem. Akin to waiting for a bus that may never in this or any lifetime come.

Yeah, and that's not even counterintuitive, until I bring into the discussion completeness and consistency of a theorem, which seemingly, as I view it, are needed to determine the shortest length of a proof to determine the complexity of it. And, brute forcing the result of the shortest Q.E.D. is not really that interesting to talk about. — Shawn

Zero of which you can do at all without first determining a way to go about it

If P is a theorem, let L(P) be defined by:

L(P) = n iff (there is a proof of P in n number of symbols & for all m, if m<n, then there is no proof of P in m number of symbols)

That is, L(P) is the least length of a proof of P.

Are you asking whether L(P) is computable? That is, is your question this:? Is there an algorithm for the set of theorems that takes any theorem as input and outputs the least length from among its proofs?

completeness [,,,] of a theorem — Shawn

For about the fifth time, "completeness of a theorem" makes no sense unless you tell us what you meant by it.

Maybe you mean "completeness of a theory", which does make sense.

Are you asking whether L(P) is computable? — TonesInDeepFreeze

I'm asking if n or m<n is determine in shortest Turing Computable length given P, and L(P) being P's proof.

(1) You changed my definition of 'L(P)', setting up confusion now as to what is meant by it.

I'll stick with my definition. I would add another terminology with definition to accommodate your different notion, but it doesn't make sense: There is no such thing as P's proof, since P has many proofs, so there is no single proof to say is "P's proof".

(3)

I'm asking if n [...] is determine in length given P — Shawn

I guess you mean 'determinate' not 'determine'. What definition of 'determinate'? Do you mean 'decidable'? Something else?

I'm asking if n or m<n is determine in shortest Turing Computable length given P — Shawn

That's your edit now.

As far as I can guess, you are asking what I already mentioned:

Given P, is "What is the length of the shortest proof of P?" computable?