¿

¿Es posible que y la cardinalidad de sea ​​la misma que la cardinalidad de ? ¿O significa que y deben tener diferentes cardinalidades?$\mathsf{P} \not = \mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \not = \mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$

Se sabe que P NP ⊂ R, donde R es el conjunto de lenguajes recursivos. Como R es contable y P es infinito (por ejemplo, los idiomas { n } para n ∈ N están en P), obtenemos que P y NP son contables.$\subseteq$$\subset$$\{n\}$$n \in \mathbb{N}$

Si le preocupa el tamaño de dos conjuntos P y NP, el tamaño de ambos conjuntos es infinito e igual.

Si estos dos conjuntos son iguales, entonces su tamaño también es igual. Si no son iguales, dado que son contables, entonces su cardinalidad es igual a la cardinalidad de los números naturales e igual.

Entonces, en cualquier caso, su cardinalidad es igual.

Principalmente trabajo en matemáticas y solo estoy un poco familiarizado con este tipo de problema. Sin embargo, la teoría de conjuntos es una de mis áreas de estudio favoritas, y esta parece ser una pregunta de teoría de conjuntos.

Entonces, para comenzar, tanto P como NP son infinitamente contables como otros han señalado antes. Por lo tanto, no tiene sentido discutir más la cardinalidad de P y NP.

Sin embargo, en general:

La desigualdad de conjunto no le informa a uno sobre el tamaño de un conjunto. Tomemos, por ejemplo, y B = { 4 , 5 , 6 } . A ≠ B , pero | A | = | B | . Considere también, C = { 1 , 2 , 3 } y D = { 4 , 5 } . C $A=\{1,2,3\}$$B=\{4,5,6\}$$A\neq B$$|A|=|B|$$C=\{1,2,3\}$$D=\{4,5\}$ y | C | ≠ | D | .$C\neq D$$|C|\neq|D|$

Sin embargo, por definición, la igualdad establecida nos informa sobre la cardinalidad. Si , entonces | A | = | B | . Considere el caso de A = { 1 , 2 , 3 } y B = { 1 , 2 , 3 } . A = B y | A | = | B | .$A=B$$|A|=|B|$$A=\{1,2,3\}$$B=\{1,2,3\}$$A=B$$|A|=|B|$

Si dos conjuntos son infinitamente contables, entonces comparten la misma cardinalidad. P y NP son ambos infinitamente contables, de modo que eso lo resume todo.