Is there one? For example, the classes P and NP. What is gained by referring to these two as classes as opposed to sets? Mathworld states that “class” has several specialised meanings in maths, but doesn’t mention what the difference between one and a set is.
I don’t know precisely why P and NP are not refered to as sets, but I can tell you the usual motivation for speaking of “classes” rather than “sets” in some circumstances: it is basically a linguistic trick to avoid certain well-known paradoxes.
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.
In Computer Science (not Math), there is a hierarchy for formal languages (from smallest to largest):
Symbols. E.g., “1”, “a”, etc.
Alphabets. Sets of symbols. E.g., the Roman alphabet, the ASCII characters, {0,1}, etc.
Strings. E.g., “a string of words”, “10001”, the empty string (usually denoted by a lambda or epsilon), etc.
Languages. Sets of strings. E.g., C++ programs with valid syntax. Strings of 1’s and 0’s with an even number of 1’s, etc.
Classes. Sets of languages. (Ergo, sets of sets of strings.) Context-free languages, regular languages, P, NP, etc.
So the latter are sets, but being sets of sets it is nice to use a slightly different term to avoid certain confusions. If you refer to the empty set in formal languages, people will know that it is a set of no strings rather than a set of no languages.
Unfortunately, many computer languages have their own definitions for classes and sets. Also, the empty set generally refers to a set that doesn’t have anything of any type, not just strings.
Unfortunately, it has the side effect of introducing certain other confusions. In set theory, not every collection of objects is a set. Rather, every collection is a class, and only those classes which are elements of another class are sets.
Mind you, the number of people working in both theoretical CS and set theory is small, and they’re most likely more than capable of keeping the terms straight, but it may be troubling to a student. Is there any rigor behind your distinctions, or are they just terms of convenience?
This isn’t difficult to get around. In order to disprove that the empty set is a set of sets, you would have to exhibit an element which is not a string. Similarly, to disprove that it’s a set of sets*, you would have to exhibit an element which is not a set. And so on and so forth.
*(Of course, the notion of a set that contains anything other than sets is purely a matter of convenience in the modern theory. But there’s no need to bring that up.)
The first part indicates a general misunderstanding of this thread. The OP clearly mentioned the use of “class” in the context of classes of languages. Obviously “class” has dozens of meanings depending on context. E.g., “I’m late for class.”
The second part is of course trivially true in Math. But CS people usually (but not always) like to keep things typed. I.e., an empty set of strings is a different thing from an empty set of languages. But since we are also terse people, we like to drop the “of …” part when the meaning is clear.
Now, you may know more about this than I do, but I don’t think that P and NP necessarily have anything to do with languages. Furthermore, as I read his OP, Dominic Mulligan isn’t talking about languages at all. There certainly isn’t a ‘clear mention’ of class relating to languages.
And just as obviously, there are only a few meanings of ‘class’ that have anything to do with ‘set’. However, that wasn’t what I was talking about at all.
I gladly yield to you in this, ultrafilter, since I know you know more about this than I do. I don’t quite understand your explanation, but I trust you.
P and NP are sets of languages. I’ll give ftg the first shot at posting a specific definition.
Look up the term “vacuous implication”. I think you’ll find a clear explanation out there.
Sorry, I should have been clear, I’m talking about classes as they apply to complexity theory.
OK, I’ve asked this before and there wasn’t a definitive answer last time, but you seem to know what you are talking about. What, exactly, is the difference between theoretical computer science and mathematics? A lot of computer science departments are within mathematics departments, a lot of computer science professors also belong to mathematics departments, most of the pioneers of computer science were mathematicians or logicians, Turing, for example. Indeed, this Wikipedia page on Discrete Mathematics lists algorithmics, complexity and computability theory as being subfields of discrete mathematics, which are all traditionally associated with theoretical computer science, so, how exactly is it wrong to refer to “classes” in this context as related to mathematics? If CS isn’t a branch of mathematics, what exactly is it?
What’s the difference between Math and Physics? CS, being new, developed out of existing fields. Where I got my PhD, the department was spread out among EE, Math and a non-departmental CS group. The AI people were in EE. One of the Numerical Analysts was in Math but the other wasn’t. The students were grouped in “Engineering” which benefitted the school’s AA numbers tremendously.
At two of the three places I have been on the faculty, the CS program wasn’t even in a college (as in “Arts and Sciences”), let alone affiliated with the Math dept. It is that interdisciplinary.
In my “advisor tree”, my great-great and great grandfather’s had PhDs in EE, my grandmother and father have PhDs in CS. Based on my knowledge of the history of CS, I doubt seriously that most founders of Theoretical CS, let alone CS, considered themselves “Mathematicians”.
So at any given university, historically, CS gets spawned off of somewhere. Some places still haven’t finished the separation process. At the last college I worked, the Physics program was for a while a part of the Math department! An organizational convenience or historical fluke does not imply a subfield relationship.
Politics plays a role. Math as a field is dying. Fewer and fewer US students want a PhD in Math and there are few jobs outside academia once you get a PhD. Some places have stopped awarding PhDs in Math. CS was growing very quickly. A lot more grant money is availbe in CS than in Math. A Math department can survive by claiming CS as a subfield. It’s just politics. Lots of jealousy, etc. Ergo, “P=NP?” appears on some lists of open problems in Math which really cheeses off a lot of CS people.
Theoretical Computer Science “looks like” Math to people. Very few researchers actually use any Math as advanced as most Physicists. (But more advanced stuff is being used all the time.) We are Just Another Field of Science That Uses Math.
Note that there is a range of how much Math a Theoretician gets involved with. So some people do straddle the boundary and consider themselves both. But the labelling they apply to themselves obviously does not apply to one and all.
dwalin: If you don’t know even the basic definitions of P and NP, then it is perhaps best for you to not post in this thread. Both are sets of languages by definition (as are all complexity classes).
Also, I wanted to make clear that “class” has a lot of meanings. Based on the OP, I was limiting my first response solely to what seemed to be the most relevant definition within CS. Obviously other definitions in CS and Math abound and are perfectly okay.
Some of my creds:
PhD in CS.
Faculty member in CS for over 20 years.
Published over 40 papers in Theoretical Computer Science.
One of my research results appears in standard undergrad textbooks.
I have taught various Theory courses dozens and dozens of times.
(I apologize for not answering each and every question posed in this thread. There’s just too much to explain to too many people.)
Is there any distinction between math and theoretical CS that doesn’t hinge on which academic department teaches it? That sort of thing is really only interesting to people in the academic departments in question.
Experimentation and empiricism. Where’s the empiricism in CS? I’ve showed that CLIQUE is NP-complete, LC commands are side-effect free and mergesort can be computed in polynomial time etc. in my lectures. Not once have I ever been asked to show this via experimentation, so how does CS qualify “as just another science that uses math”? I’m hard pressed to think of any experimentation in the CS we’ve been exposed to. Even physics, at its most theoretical, relies heavily on observed phenomena no matter what the maths says.
Not trying to be combatitive, I’m just interested in what exactly CS actually is.
That’s because all the problems you’ve been exposed to, including all the ones you listed, are very easy. I’ve seen papers that rely heavily on experimental data because no analytical solutions have been found yet.
But by the same token, the truth of the Goldbach conjecture is “known” experimentally, but not theoretically. Are you going to try to claim that the Goldbach conjecture belongs to some discipline other than math?
Theoretical computer science is a branch of mathematics. Much of computer science is not theoretical, of course, and much of applied computer science is not math. But the fact that there are theorems in computer science is enough to convince me that theoretical computer science is math.
I have to side with those who call CS a subdiscipline of mathematics. The situation seems analogous to that of statistics. Many universities find it convenient for administrative or political reasons to have separate math and stats departments. But as a category of human knowledge, statistics is a branch of mathematics.
Of course, by CS, I meant Theoretical CS.
Most probably 
But again, in what way is this analogous to any other branch of science? You state that we have to rely on empirical results because we haven’t found an analytical one yet. You can quite confidently state that mergesort runs in polynomial time without ever having to resort to empiricism. Is there anything similar in physics? What is an “analytical solution” in biology, for instance?
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?”
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.