Bedeutet

Ist es möglich, dass und die Kardinalität von der Kardinalität von ? Oder bedeutet , dass und unterschiedliche Kardinalitäten haben müssen?$\mathsf{P} \not = \mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \not = \mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$

Es ist bekannt, dass P NP ⊂ R ist, wobei R die Menge der rekursiven Sprachen ist. Da R zählbar ist und P unendlich ist (zB sind die Sprachen { n } für n ∈ N in P), erhalten wir, dass P und NP beide zählbar sind.$\subseteq$$\subset$$\{n\}$$n \in \mathbb{N}$

Wenn Sie sich Gedanken über die Größe von zwei Mengen P und NP machen, ist die Größe dieser beiden Mengen unendlich und gleich.

Wenn diese beiden Mengen gleich sind, ist auch ihre Größe gleich. Wenn sie nicht gleich sind, da sie zählbar sind, dann ist ihre Kardinalität gleich der Kardinalität natürlicher Zahlen und gleich.

In beiden Fällen ist ihre Kardinalität also gleich.

Ich arbeite hauptsächlich in der Mathematik und kenne mich mit dieser Art von Problem nur wenig aus. Die Mengenlehre ist jedoch eines meiner Lieblingsfächer, und dies scheint eine Mengenlehrefrage zu sein.

Zunächst sind also sowohl P als auch NP zählbar unendlich, wie andere bereits betont haben. Daher ist es nicht sinnvoll, die Kardinalität von P und NP weiter zu diskutieren.

Im Allgemeinen gilt jedoch:

Mengenungleichheit gibt keinen Aufschluss über die Größe einer Menge. Nehmen wir zum Beispiel und B = { 4 , 5 , 6 } . A ≠ B , aber | A | = | B | . Man betrachte auch C = { 1 , 2 , 3 } und D = { 4 , 5 } . C $A=\{1,2,3\}$$B=\{4,5,6\}$$A\neq B$$|A|=|B|$$C=\{1,2,3\}$$D=\{4,5\}$ und | C | ≠ | D | .$C\neq D$$|C|\neq|D|$

Definitionsgemäß gibt die Mengengleichheit jedoch Aufschluss über die Kardinalität. Wenn , dann | A | = | B | . Betrachten Sie den Fall von A = { 1 , 2 , 3 } und B = { 1 , 2 , 3 } . A = B und | A | = | B | .$A=B$$|A|=|B|$$A=\{1,2,3\}$$B=\{1,2,3\}$$A=B$$|A|=|B|$

Wenn zwei Mengen unendlich sind, haben sie dieselbe Kardinalität. P und NP sind beide zählbar unendlich, so dass das ziemlich gut zusammenfasst.