There is no set of all sets, I hope we're not going down this road. — fishfry

It's off topic; but, I recall reading that Russell solved this by class hierarchy in type theory. I'll search if I'm wrong on this.

You don't need to search. You are correct that PM is one approach to avoiding the paradox.

You don't need to search. You are correct that PM is one approach to avoiding the paradox. — TonesInDeepFreeze

I do not believe there is a set of all sets either in Russell's type theory or in any version of modern type theory. I'd be grateful if you could supply references and/or context to the contrary. At best I've read that type theory "avoids the paradox," but I've seen no claim that there is a set of all sets.

I do not believe there is a set of all sets either in Russell's type theory or in any version of modern type theory. I'd be grateful if you could supply references and/or context to the contrary. — fishfry

Why would I want to supply references to a claim that PM allows a set of all sets when I agree that PM does not allow a set of all sets?

Why would I want to supply references to a claim that PM allows a set of all sets when I agree that PM does not allow a set of all sets? — TonesInDeepFreeze

Do you have a cat? Perhaps your cat wrote this using your handle:

You are correct that PM is one approach to avoiding the paradox. — TonesInDeepFreeze

You seem to be confused.

It is correct that PM is one approach to avoiding the paradox. With PM there is no set of all sets.

So, within a formal system does anyone think that to determine complexity of a Turing computable proof of a theorem, that consistency is of greater importance, no?

It is correct that PM is one approach to avoiding the paradox. With PM there is no set of all sets. — TonesInDeepFreeze

That last sentence makes all the difference, especially in the context of @Shawn referencing the set of all sets, my telling him that there is no such thing, Shawn saying he'd look up PM, and you saying that he didn't need to, the implication being that PM confirmed his misunderstanding, when in fact it doesn't. You added to OP's confusion on this issue and I don't know why.

I was talking about type theory in general avoiding the issue of the set of all sets by assigning hierarchy classes as I last read about the issue.

He said that he thinks PM solves the problem with types but that he might have to look it up to be sure.

I said he doesn't have to look it; he is correct that PM avoids the paradox.

I was talking about type theory in general avoiding the issue of the set of all sets by assigning hierarchy types as I last read about the issue. — Shawn

In context, your remark served to amplify the OP's confusion rather than correct it. I straightened the situation out. You're welcome. I myself am singularly unconfused about this issue, which is why I challenged your technically correct but misleading-in-context claim.

I was talking about type theory in general avoiding the issue of the set of all sets by assigning hierarchy classes as I last read about the issue. — Shawn

You understand that there is no set of all sets, correct? Even in type theory. Yes?

Yes, sir.

I'm only pondering if class complexity can be ascertained at the moment for a proof of a theorem in a formal system, for Turing computability. That's where I left off with @TonesInDeepFreeze

No, I addressed exactly the sentence he wrote. What he wrote in that sentence was correct. I am not responsible for addressing other confusions he has that might conflict with the sentence he posted and to which I responded. He wrote something correct, and I affirmed it.

Yes, sir. — Shawn

No, I addressed exactly the sentence he wrote. What he wrote in that sentence was correct. I am not responsible for addressing other confusions he has that might conflict with the sentence he posted and to which I responded. He wrote something correct, and I affirmed it. — TonesInDeepFreeze

I think I'll go argue with the partisans on the Israel-Palestine war thread. It seems more peaceful.

class complexity — Shawn

Not 'class complexity'. The 'complexity class'.

Do you think complexity class can determine "complexity" quantifiably for a Turing computable algorithm?

OK

Do you think complexity class can determine "complexity" quantifiably for a Turing computable algorithm? — Shawn

Perhaps Turing degree is what you're looking for. I'm not sure what you mean by quantifiable. Complexity theory puts computational problems into equivalence classes, That's perhaps more qualitative than quantitative.

https://en.wikipedia.org/wiki/Turing_degree

OK, I sat down, read it, and read it more, and seemingly you would have the have a powerful oracle machine to make the decision to do this with least decidedly complexity.

Am I getting that much right?

I surmise that he's not asking about degree of unsolvability but about the complexity of the problem.

4.1 Significance of Complexity here: https://plato.stanford.edu/entries/computability/

If I'm not mistaken, this is not about unsolvable problems. Rather, it's about finding out the complexity of the algorithm for deciding this decidable problem.

Rather, it's about know the complexity of solving this particular solvable problem. — TonesInDeepFreeze

Assuming you have a metric to do this by, which is why I reference the need for a way to ascertain the computability beforehand, meaning some kind of robust oracle machine.

A machine for ascertaining the length of the shortest proof of a theorem doesn't involve anything like oracles.

A machine for ascertaining the length of the shortest proof of a theorem doesn't involve anything like oracles. — TonesInDeepFreeze

But, how does the machine do this without a brute force method?

OK, I sat down, read it, and read it more, and seemingly you would have the have a powerful oracle machine to make the decision to do this with least decidedly complexity.

Am I getting that much right? — Shawn

I'm not an authority on CS theory. The idea seems to be that we write A < B for sets of natural numbers if A can be decided with an oracle for B. What's interesting is that this is not a linear order. There are sets A and B such that neither A < B or B < A.

how does the machine do this without a brute force method? — Shawn

The method I mentioned is brute force. I don't know whether there's a better method.

What's interesting is that this is not a linear order. — fishfry

How would you define it? Is it even possible to define this? And, may I ask how is this distinct from estimating Kolmogorov complexity?

The method I mentioned is brute force. I don't know whether there's a better method. — TonesInDeepFreeze

I see, so that's where I kinda made the quip in the OP about stuff like quantum computing that take the route of least complexity eg. Shor's algorithm.

How would you define it? Is it even possible to define this? And, may I ask how is this distinct from estimating Kolmogorov complexity? — Shawn

It's defined in CS, you can Google around. It's a fairly technical subject, nothing I know much about.

Of course it's possible to define, the definition is in the Wiki article, although that article's not too informative. I don't know any more about it than you'd learn from Googling and reading some papers. None that I've seen are particularly accessible.