# Maths question: what is the difference between a set and a class? **URL:** \ **Category:** Factual Questions\ **Created:** [March 6, 2006, 9:47pm UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301 "2006-03-06T21:47:44Z")\ **Posts on this page:** 9\ **Page:** 2
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 8, 2006, 12:10am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/21 "2006-03-08T00:10:22Z")
> [@jawdirk](#): > > P and NP are sets of decision problems, not languages. (Cite: [http://en.wikipedia.org/wiki/NP\_(complexity)](http://en.wikipedia.org/wiki/NP_%28complexity%29) ). > > 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. ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [March 8, 2006, 12:10am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/22 "2006-03-08T00:10:50Z")
But _Theoretical_ CS _is_ the study of the model. ---
**Author:** ![jawdirk](https://avatars.discourse-cdn.com/v4/letter/j/df705f/32.png) [@jawdirk](https://boards.straightdope.com/u/jawdirk)\ **Post date:** [March 8, 2006, 12:15am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/23 "2006-03-08T00:15:44Z")
> [@ultrafilter](#): > > Not that it’s a particularly troublesome disagreement, as the two definitions are equivalent. Right. 🙂 ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [March 8, 2006, 12:17am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/24 "2006-03-08T00:17:42Z")
> [@jawdirk](#): > > P and NP are sets of decision problems, not languages. (Cite: [http://en.wikipedia.org/wiki/NP\_(complexity)](http://en.wikipedia.org/wiki/NP_%28complexity%29) ). [Decision problems are equivalent to languages.](http://en.wikipedia.org/wiki/Computational_complexity_theory) > [@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. ---
**Author:** ![Jamaika\_a\_jamaikaiake](https://avatars.discourse-cdn.com/v4/letter/j/7993a0/32.png) [@Jamaika\_a\_jamaikaiake](https://boards.straightdope.com/u/Jamaika_a_jamaikaiake)\ **Post date:** [March 8, 2006, 1:42am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/25 "2006-03-08T01:42:01Z")
> [@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](http://en.wikipedia.org/wiki/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](http://mathworld.wolfram.com/Zermelo-FraenkelAxioms.html) ). 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. ---
**Author:** ![Captain\_Carrot](https://avatars.discourse-cdn.com/v4/letter/c/f0a364/32.png) [@Captain\_Carrot](https://boards.straightdope.com/u/Captain_Carrot)\ **Post date:** [March 8, 2006, 3:53am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/26 "2006-03-08T03:53:58Z")
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. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [March 8, 2006, 9:37am UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/27 "2006-03-08T09:37:38Z")
> [@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. ---
**Author:** ![CJJ](https://avatars.discourse-cdn.com/v4/letter/c/ecc23a/32.png) [@CJJ](https://boards.straightdope.com/u/CJJ)\ **Post date:** [March 8, 2006, 4:56pm UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/28 "2006-03-08T16:56:08Z")
> [@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. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 8, 2006, 5:24pm UTC](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301/29 "2006-03-08T17:24:02Z")
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. [Previous page](https://boards.straightdope.com/t/maths-question-what-is-the-difference-between-a-set-and-a-class/347301.md?page=1)