Bedeutet

19

Ist es möglich, dass und die Kardinalität von der Kardinalität von ? Oder bedeutet , dass und unterschiedliche Kardinalitäten haben müssen?PNPPNPPNPPNP

Jason Baker
quelle
Es hat anscheinend einen Sinn, dass komplexere Sprachen zahlreicher sind als weniger komplexe, aber es scheint, dass nicht viel gelernt wird. Stattdessen gibt es zB die Raum und Zeit Hierarchie Theoreme ....
VZN

Antworten:

69

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.{n}nN

Yuval Filmus
quelle
Wie ist R definiert?
Saadtaame
Dies ist die Menge aller Sprachen, die von C-Programmen akzeptiert werden.
Yuval Filmus
7
Lassen Sie mich zunächst die Definition korrigieren: ist die Menge aller Sprachen, die von C-Programmen akzeptiert werden , die immer anhalten . Wir brauchen keine formellere Definition, da C-Programme Zeichenfolgen über einem endlichen Alphabet sind und es nur unzählige davon gibt. Die Rekursionstheorie basiert auf der Erkenntnis, dass Programme endlich (als Zahlen) spezifiziert und so als Eingabe für andere Programme verwendet werden können. R
Yuval Filmus
1
Ein abzählbares Produkt von abzählbaren Mengen ist nur dann abzählbar, wenn alle bis auf endlich viele Singletons sind oder wenn mindestens eine leer ist. Ich schlage vor, dass Sie weitere Fragen zur Kardinalität auf math.stackexchange stellen, wo sie hingehören.
Yuval Filmus
1
@ernab Eine Teilmenge einer zählbaren Teilmenge ist entweder endlich oder zählbar.
Yuval Filmus
1

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.

orezvani
quelle
3
Cantor hat sich bereits im 19. Jahrhundert eine Methode ausgedacht, um die Größen der unendlichen Mengen zu vergleichen.
Yuval Filmus
Ist die Kardinalität natürlicher Zahlen also größer als die Kardinalität gerader natürlicher Zahlen?
Orezvani
1
Nein, sie haben die gleiche Kardinalität. Sie können in jedem Buch über Mengenlehre (oder Wikipedia) nach den erforderlichen Definitionen suchen. Es wird gesagt, dass zwei Mengen die gleiche Kardinalität haben, wenn zwischen ihnen eine Bijektion besteht. Eine Menge soll höchstens die Kardinalität von B haben, wenn von A nach B gespritzt wird . Unter der Annahme des Axioms der Wahl hat entweder A für alle zwei Mengen A und B höchstens die Kardinalität von B oder umgekehrt. Wir sagen, dass A eine Kardinalität kleiner als B hat, wenn es höchstens die Kardinalität von B hatABABABABABBaber nicht die gleiche Mächtigkeit wie . B
Yuval Filmus
P und NP sind zählbar, also wurde jedes Element einer natürlichen Zahl zugeordnet. Ist das richtig?
Orezvani
Richtig, P und NP haben die gleiche Kardinalität wie die Menge der natürlichen Zahlen.
Yuval Filmus
0

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}AB|A|=|B|C={1,2,3}D={4,5} und | C | | D | .CD|C||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.

Yuval Filmus
quelle
7
Zu "sowohl P als auch NP sind zählbar unendlich, wie andere bereits dargelegt haben. Daher ist es sinnvoll, die Kardinalität von P und NP zu diskutieren.": Ich bin anderer Meinung. Weil sie beide unendlich sind, gibt es nichts mehr über ihre Kardinalität zu sagen.
@DavidEppstein, wenn du nachdenkst, hast du recht. Ich werde meine Antwort bearbeiten, um das zu korrigieren. Ich werde jedoch eine Diskussion über die Kardinalität im Allgemeinen hinterlassen (wobei die Kardinalität von abzählbar unendlichen Mengen erwähnt wird).
Die relevante Detail Sie fehlt hier, in Bezug auf das Beispiel mit und B ist , dass P N P . ABPNP
Jmite