Maths question: what is the difference between a set and a class?

[ultrafilter]

@jawdirk

P and NP are sets of decision problems, not languages. (Cite: http://en.wikipedia.org/wiki/NP_(complexity) ).

A decision problem is a function over a set to {0,1} (yes/no), where the set is the input to a question and the function maps it to a yes/no answer.

P and NP arise because you want to know whether a given decision problem is decidable with a polynomial-time alogorithm (P), or decidable with a polynomial-time non-deterministic algorithm (NP).

Theoretically, they are related to languages only in that the specification of the decision problem frequently makes use of a language; the decision problem is often, “Does the string s belong to the language L?”

Alternatively, P and NP are the sets of languages whose decision problems are respectively decidable and verifiable in polynomial time. I’ll have to check my books when I get home, but I think this is the more usual definition. Not that it’s a particularly troublesome disagreement, as the two definitions are equivalent.

[Tyrrell_McAllister]

But Theoretical CS is the study of the model.

[jawdirk]

@ultrafilter

Not that it’s a particularly troublesome disagreement, as the two definitions are equivalent.

Right.

[Tyrrell_McAllister]

@jawdirk

P and NP are sets of decision problems, not languages. (Cite: http://en.wikipedia.org/wiki/NP_(complexity) ).

Decision problems are equivalent to languages.

@Wikipedia

A decision problem is a problem where the answer is always YES/NO. For example, the problem IS-PRIME is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a language, which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES.

[Jamaika_a_jamaikaiake]

@Tyrrell McAllister

For example, we would like to be able to refer to the collection V of all sets. But if we call V itself a set, this leads to a paradox. For then V would contain its own power set P(V) as a subset, because V contains all sets, including those in P(V). But then there would be an injection from P(V) into V, violating Cantor’s Theorem.

The quick and dirty solution is to refuse to call V a set, and instead call it a class. Now, magically, you don’t even have to deal with the existence of P(V) (since you may have only defined P(S) when S is a set, not a class). And even if you are working in a system where P(V) exists, it will now be full of things that are not sets (but rather classes) and therefore not in V. That prevents the paradox above from going through, and mathematics is saved.

As a set theorist, I agree.

A class is a collection of things which does not neccesarily follow the axioms of set theory (usually ZFC ). Thus, talking about V or NP or Ord or whatnot as a class won’t lead to any paradox because there are no assumed axioms to lead us anywhere.
The downside of this, of course, being that we can prove absolutely nothing about classes in general.

[Captain_Carrot]

I retract my previous statements. It is obvious to me, as ftg said, that I really don’t know enough about this to be posting in this thread. However, rest assured that I will be rectifying this ignorance in a few years, once I get to college/beyond.

[Capt.Ridley_s_Shooting_Party]

@ultrafilter

How confident are you?

This sort of thing is always glossed over in undergraduate algorithms classes, but all of your results are contingent on the accuracy of your model. When it comes to it, though, you’re not running mergesort on your model; you’re running it on a real computer. If your model accurately reflects a real computer, your predictions will bear out, and if not…well, you can always publish the data if it’s interesting enough.

What’s that got to do with theoretical CS? I know that algorithms are analysed with respect to a formal model. Theoretical CS is solely concerned with these models and analyses using them, though, isn’t it? These sorts of analyses existed before the computer as we know it today was even invented.

[CJJ]

@Dominic Mulligan

What’s that got to do with theoretical CS? I know that algorithms are analysed with respect to a formal model. Theoretical CS is solely concerned with these models and analyses using them, though, isn’t it? These sorts of analyses existed before the computer as we know it today was even invented.

This is swerving into GD territory, but I think the essential distinction is that science develops and test models based on their correspondence with reality, while mathematics is a tool for logically analyzing these theoretical models. One could glibly say that science deals with physical items, but math deals with the metaphysical. By definition, theoretical CS limits the discussion to models, but no computer scientist devoted him/herself exclusively to theory anymore (machines are a lot more fun:)).

The historic development of computer science is somewhat different than physics in that the theoretical models were developed before the machines they attempted to describe existed (by contrast, Newton’s laws described a physical reality that existed long before Newton). This perhaps is why some still consider CS a mathematical discipline.

[ftg]

This is just getting too weird of a thread but I still feel a need to mention two key points:

1. A lot of Scientists don’t deal with experiments. Theoretical Physicists for example. Some Physicists do experiments some don’t. The ones that don’t aren’t Mathematicians. Substitute “Computer Scientists” for “Physicists” in the last three sentences.

2. Mathematicians create Math. There are a lot of people who use Math. These include Scientists, Social Scientists, Engineers, etc. Sometimes in a given field, the Math isn’t there yet and people have to create their own Math. E.g., Theoretical Physicists and String Theory. But that isn’t terribly common and the people doing that usually don’t consider themselves Mathematicians.

Theoretical Computer Scientists use Math but don’t usually create Math. Ergo, not Mathematicians.

From our perspective, it’s like confusing a person who builds cars with a person who drives cars. It is that big of a distinction.