PM addressed complexity classes?
— TonesInDeepFreeze

That's my estimate. — Shawn

Estimate based on what?

I don't see it in the table of contents given in the article on PM in the SEP.

Set-theory can't do this — Shawn

What does "this" refer to there? Set theory can't do a lot of things, but what is it in particular are you saying set theory can't do?

I don't know. And I'm very much informed on complexity classes.
— TonesInDeepFreeze

There was an attempt at doing this by Russell and Whitehead in the Principia, where they utilized type theory extensively, to no avail. — Shawn

PM addressed complexity classes?

If my attempt was correct, and there are only finitely many symbols in the signature, then, if I'm not mistaken, there is an algorithm to list the theorems in order of proof length (and, say, lexicographically within length).

I don't see how this sort of knowledge would help prove a theorem — jgill

I find it interesting as a mathematical question onto itself.

If my previous post is correct, then I take it that your full question is:

What is the complexity class of such an algorithm?

I don't know. And I'm not very much informed on complexity classes.

I find it interesting whether there is an algorithm to compute the least length.

I take it we are talking about proofs in the first-order predicate calculus.

Not sure, but I think this is right: Any theorem has only finitely many symbols from the language signature, so a shortest proof would use only (1) connectives (of which there are only finitely many) and quantifiers (of which there are only finitely many), (2) signature symbols in the the theorem itself, and (3) finitely many variables. Then, modulo the variables used (since swapping variables wouldn't change length), for any n, there are only finitely many sequences of formulas whose sum of formula lengths is n. So, successively, for each n, look for proofs of the theorem. The answer is the first n that has a proof.

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?
— TonesInDeepFreeze

Well, yes. I'm concerned with complexity of a theorems proof — Shawn

And by 'complexity' do you mean 'the sum of the lengths of the formulas in the proof'?

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?

(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?

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.

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?

Since the U.S. Constitution has been mentioned, it helps to mention what it says:

"to form a more perfect union, establish justice, insure domestic tranquility, provide for the common defense, promote the general welfare, and secure the blessings of liberty to ourselves and our posterity"

There's nothing more deceptive than an obvious fact — Arthur Conan Doyle

"There is nothing as mysterious as a fact clearly described."
— Garry Winogrand

You are very welcome. I fixed some typos (including fatal ones) and added details and more explanation after you replied.

If you would like to have background to understand the details, then I can recommend a couple of books.

For any relation R, it is a theorem of first order logic that:

There does not exist an x such that, for all y, Ryx if and only if ~Ryy.

In symbols:

~ExAy(Ryx <-> ~Ryy)

In set theory (with 'e' for 'member of' and taking R to be the membership relation):

~ExAy(yex <-> ~yey)

That is, there does not exist a set x such that, for all y, y is a member of x if and only if y is not a member of itself.

That is a theorem of set theory, as it is a theorem of first order logic for any R.

But how does set theory ensure that that theorem is not contradicted by having its negation also a theorem of set theory?

That is accomplished by not having axioms that would allow it.

In particular, set theory does not have the axiom schema of unrestricted comprehension (aka 'the axiom schema of comprehension' or 'the axiom schema of naive comprehension'), which is:

If P is a formula in which x does not occur free, then ExAy(yex <-> P).

If we have that schema, then we could take P to be ~yey, and derive Russell's paradox from:

ExAy(yex <-> ~yey).

Instead, Z set theory has the axiom schema of separation (aka 'the axiom schema of specification'). (NBG class theory, has a different but similar approach), which is:

If P is a formula in which x does not occur free, then AzExAy(yex <-> (yez & P)).

That says: If you have a set z, then you can form the subset x of z such that the members of x are all and only those members of z that have property P.

In other words, to use a property to define a set, you can only do it by using that property to make a subset of an already given set.

With P being ~yey, with the axiom schema of separation, we have:

AzExAy(yex <-> (yez & ~yey)).

And that doesn't yield a contradiction.

So set theory does not block Russell's paradox by adopting an axiom to block it. (In general, since the logic is monotonic, one cannot add axioms to block inconsistency.) Instead, set theory avoids Russell's paradox by refraining from having axioms that would allow it.

Note: Pedantically, instead of saying 'set theory ensures', we would say 'as far as we know, set theory ensures', since, as far as we know, set theory is consistent.

I know I'm conscious,
because I am conscious.
Because I am conscious,
I know I'm conscious. — forrest-sounds

That only switches the order of the clauses 'I know I'm conscious' and 'because I'm conscious'.

That just redundancy, not circularity.

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?

if you go back and reread TIDF's discussion of counting a quantity, you'll see the equivocation with order — Metaphysician Undercover

That is the second time you've made that false claim. Moreover, I did not couch anything as "counting a quantity".

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.

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?

TonesInDeepFreeze was equivocating, or at best, creating ambiguity between quantity and order, using "2" to mean "second", when counting a quantity of two. — Metaphysician Undercover

There is no equivocation or ambiguity in what I said, Your confusions and implacable dedication to remaining ignorant of mathematics and dreadfully misunderstanding it are your own.

You said the discussion between us reached an end.

You were doing better with emoticons.

As if 'obtuse' is seriously "mudslinging".

But my remark does bear amendment. It's not that you're obtuse, it's that you are willfully so.

Now you are reaching your true level: emoticons.

Then why did you say "You're utterly obtuse" as if it mattered to you? :chin:
seconds ago — TheMadFool

Because it's worth pointing out the reason you can't understand the most basic things.

So, I'm utterly obtuse? — TheMadFool

Yes.

You are utterly obtuse
— TonesInDeepFreeze

Are you a genius then? — TheMadFool

Not in logic. And probably not in anything. So what?

Show me a reference that claims that "not all statements can be negated" and that "either this statement can't be negated or this statement can't be negated can't be negated". — TheMadFool

There's no reason for me to do that.

Yes, contextual but that's exactly the point! — TheMadFool

Then I don't need your exercise.

I've tried explaining to you that "this" is, as you said, is ambiguous but the point is precisely that. — TheMadFool

Then the moral of your exercise is trivial. It merely highlights what we already know: English pronouns and demonstrative pronouns are contextual and if used carelessly can cause ambiguity.

You've missed the point of the numbering. — TheMadFool

You are utterly obtuse. I miss the point of the numbering because your use of it is not grammatical. Make it grammatical if you would like me to understand whatever point you have.

Suppose we consider the statement "god exists". What is its negation? "god doesn't exist. In other words, the negation of "god exists" is "god doesn't exist". — TheMadFool

Yes, but that fails with 'this statement' in the mix because 'this' is contextual.

Also, you misuse the concept of 'implies'.

Each of your posts express even more of your confusions. It's exponential.

I answered your post about the liar. Now you're just flat out ignoring that answer.

And, still you are not facing that putting '(1)' between 'this' and 'statement' makes no sense.

the negation of "this statement can be negated" is "this statement can't be negates". — TheMadFool

Again, you miss the point:

In "This statement can be negated", 'this statement' denotes "This statement can be negated".

but

In "This statement can't be negated", 'this statement' denotes "This statement can't be negated".

So 'this statement' is used to denote two different things.

As I mentioned, that ambiguity comes from the fact that 'this' is contextual.

You have to set up your presentation so that it stays clear of those kinds of natural language foibles.

Nothing to fix, — TheMadFool

There is no apparent meaning in placing '(1)' between the adjective 'this' and the noun 'statement'.

Now I've said that three times.

That's good. Though, it's logically true anyway.

Next is to fix line 3 of Argument A.

Liar paradox:

If "This sentence is false" is true, then "This sentence is false" is false.

and

If "This sentence is false" is false, then "This sentence is false" is true.

Whatever you mean to say, if you want me to understand it (especially to understand it exactly) then you need to rewrite it without a number between an adjective and what the adjective modifies.

"IF this (1) statement can be negated THEN this (2) statement can't be negated" — TheMadFool

I can't make sense of that with the numbers interposed as written. I don't know what is meant by interposing a number between an adjective and what it modifies.