Does P != NP imply that | NP | > | P |?

Is it possible that P != NP and the cardinality of P is the same as the cardinality of NP? Or does P != NP mean that P and NP must have different cardinalities?

-

migrated from cstheory.stackexchange.comJan 1 at 2:19

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.

-

I work in mathematics mainly and have only a bit of familiarity with this type of problem. However, set theory is one of my favorite areas of study, and this seems to be a set theory question.

So, to begin with, both P and NP are countably infinite as others have pointed out before. So, it does not make sense to discuss the cardinality of P and NP any further.

However, in general:

Set inequality does not inform one about the size of a set. Take for instance, $A=\{1,2,3\}$ and $B=\{4,5,6\}$. $A\neq B$, but $|A|=|B|$. Consider also, $C=\{1,2,3\}$ and $D=\{4,5\}$. $C\neq D$, and $|C|\neq|D|$.

However, by definition, set equality does inform us about cardinality. If $A=B$, then $|A|=|B|$. Consider the case of $A=\{1,2,3\}$ and $B=\{1,2,3\}$. $A=B$, and $|A|=|B|$.

If two sets are countably infinite, then they share the same cardinality. P and NP are both countably infinite, so that pretty much sums that up.

-
Re "both P and NP are countably infinite as others have pointed out before. So, it does make sense to discuss the cardinality of P and NP.": I disagree. Because they are both countably infinite, there is nothing more to say about their cardinality. – David Eppstein Dec 31 '12 at 20:59
@DavidEppstein, upon thinking, you are correct. I will edit my answer to fix that. However, I will leave some discussion on cardinality in general (mentioning the cardinality of countably infinite sets). – Travis Fields Dec 31 '12 at 22:10
The relevant detail you're missing here, in terms of the example with $A$ and $B$ is that $P \subseteq NP$. – jmite Mar 21 at 5:02