Ist das Auswahlaxiom notwendig, um R≈P(ω)R≈P(ω)\mathbb R \approx \mathcal P(\omega) zu beweisen?

Question

Ist das Auswahlaxiom notwendig, um R≈P(ω)R≈P(ω)\mathbb R \approx \mathcal P(\omega) zu beweisen?

Kardinäle
Mathematik
Axiom der Wahl
elementare Mengenlehre

aerdna91

Ich studiere Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876) im Selbststudium , und ich bin ziemlich verwirrt über Kardinalarithmetik ohne AC.

Hier ( Welche Sets sind ohne Axiom of Choice gut bestellbar? ) schreibt OP $\mathbb R$ ist bei ZF nicht unbedingt gut bestellbar. Gleichzeitig kommt es mir so vor $\mathcal P(\omega)$ ist in ZF gut bestellbar (Beweisversuch folgt). Daher ist entweder mein Beweis falsch, oder die Antwort auf die ursprüngliche Frage ist "Ja". Irgendeine Hilfe? Danke.

Anspruch auf ZF $\vdash$ " $\mathcal P(\omega)$ ist gut bestellbar"

Beweis Das wissen wir $2=\{0,1\}$ ist eine Kardinalzahl, also wohlgeordnet bzgl. $\in$ " (natürlich könnte dies auch manuell überprüft werden). Dasselbe gilt für $\omega$ . (Ich verwende " $<$ " anstatt " $\in$ "). Lassen Sie uns überlegen $2^\omega = \{f \mid f : \omega \to 2\}$ . Die Beziehung definiert durch
$F ≺ G ⟺ \exists N [F (N) < G (N) \land \forall ich < N F (ich) = G (ich)]$ $f \prec g \iff \exists n \, [f(n) < g(n) \wedge \forall i\!\!<\!\!n \;\; f(i)=g(i)]$ ist eine gut ordnung auf $2^\omega$ (und das gilt für ZF). Beachten Sie abschließend, dass ZF $\vdash 2^\omega \approx \mathcal P(\omega)$ .

Update: Der Beweis ist falsch, da die lexikographische Ordnung auf $2^\omega$ ist eindeutig keine gute Ordnung, wie in Asaf Karagilas Antwort betont. Asaf behauptet auch, dass ZF $\not\vdash$ " $2^\omega$ ist gut bestellbar". Aber dann habe ich noch eine Frage: In dem Buch, das ich oben zitiere, gibt es folgenden Beweis (Seite 51):

Geben Sie hier die Bildbeschreibung ein

Jetzt: Wenn $2^\omega$ ist nicht unbedingt gut bestellbar, weshalb darf der Autor verwenden $2^{\aleph_0}$ als Kardinalzahl? Oder ebenso, warum darf er über die Kardinalität von sprechen $\prod_{n \in \mathbb N} B_n$ ?

Lösung zum Update: Es war nur eine Frage der Definitionen. In dem Text, in dem ich diese Themen studiert habe, werden Kardinalzahlen als Ordnungszahlen definiert, für die es keine Bijektion mit kleineren Ordnungszahlen gibt. Dann wird ein Satz gegeben $A$ , $|A|$ ist eine Kardinalzahl, also ist sie definiert iff $A$ ist gut bestellbar. Im Gegenteil, in diesem Buch $|A|$ ist als Äquivalenzklasse von gedacht $A$ unter der Äquivalenzrelation $A \sim B \iff$ Es gibt eine Bijektion $A \to B$ . Hier entlang, $|A|$ ist immer wohldefiniert.

Zhen Lin

Die von Ihnen definierte Reihenfolge wird als lexikografische Reihenfolge bezeichnet. Es ist keine Wohlordnung. (Versuchen Sie, eine unendliche absteigende Kette zu finden!)

Asaf Karagila

Während Sie Recht haben, dass Ihre Frage eine positive Antwort hat und Ihr Beweis falsch ist, ist es durchaus möglich, dass die Antwort negativ ist und der Beweis ebenfalls falsch ist. Sie berücksichtigen nicht alle möglichen Ergebnisse! :-)

aerdna91

@AsafKaragila D'OH!

Antworten (2)

Ist das Auswahlaxiom notwendig, um R≈P(ω)R≈P(ω)\mathbb R \approx \mathcal P(\omega) zu beweisen?

Die von Ihnen definierte Reihenfolge wird als lexikografische Reihenfolge bezeichnet. Es ist keine Wohlordnung. (Versuchen Sie, eine unendliche absteigende Kette zu finden!)
Während Sie Recht haben, dass Ihre Frage eine positive Antwort hat und Ihr Beweis falsch ist, ist es durchaus möglich, dass die Antwort negativ ist und der Beweis ebenfalls falsch ist. Sie berücksichtigen nicht alle möglichen Ergebnisse! :-)

Asaf Karagila · Answer 1

Sie brauchen das Axiom der Wahl nicht, um das zu zeigen $|\Bbb R|=2^{\aleph_0}$ . Wenn Sie genau beobachten weder die Injektion aus $\Bbb R$ hinein $\mathcal P(\omega)$ Durch Aufzählen der Rationalen und Dedekind-Schnitte definiert sich noch die Injektion aus $\mathcal P(\omega)$ hinein $\Bbb R$ definiert durch die Erstellung der Cantor-Menge verwenden Sie das Axiom der Wahl.

Da auch der Beweis des Satzes von Cantor-Bernstein nicht auf dem Wahlaxiom beruht, zeigt dies dies $\sf ZF\vdash|\Bbb R|=|\mathcal P(\omega)|$ .

Was Ihren Beweis dafür angeht $2^\omega$ eine wohlgeordnete Menge ist, ist diese Relation nicht wohlbegründet (also kann sie keine wohlgeordnete Menge sein). Lassen $f_n$ Sei die Funktion, die konstant ist $0$ bis $n$ und dann $1$ aus $n$ weiter. Dann $f_n\prec f_k$ dann und nur dann, wenn $n>k$ was bedeutet, dass dies eine abnehmende Folge ist.

Beachten Sie bei Ihrer Bearbeitung, dass die Kardinalexponentiation immer noch gut definiert ist. So wie ein Produkt zweier Kardinalzahlen nicht gleich der unendlichen Summe der einen durch einen Index der anderen sein muss, muss die Potenzierung nicht das Produkt der einen für sich über den Index der anderen sein.

Dies verleiht dem alten Sprichwort, dass Multiplikation keine wiederholte Addition ist (und Potenzierung keine wiederholte Multiplikation), nur mehr Gewicht.

Wir definieren die Kardinalarithmetik direkt: $|A|+|B|$ ist die Kardinalität von $|A\cup B|$ Wo $A\cap B=\varnothing$ ; $|A|\cdot|B|=|A\times B|$ ; Und $|A|^{|B|}=|A^B|$ , nämlich die Mächtigkeit aller Funktionen aus $B$ hinein $A$ .

Und beachte das $\prod_{i\in I}X_i$ ist eine bestimmte Menge, hat also eine wohldefinierte Kardinalität. Ob es gleich ist oder nicht $\prod_{i\in I}Y_i$ unter der Annahme, dass $|X_i|=|Y_i|$ für alle $i\in I$ ist eine ganz andere Geschichte. Aber bestimmte Produkte haben bestimmte Kardinalitäten.

Oder alternativ das $\{f_n\mid n\in \mathbb N\}\subseteq 2^{\mathbb N}$ ist nicht leer und enthält kein Least-Element. (Ich bin mir nicht sicher, ob viele Anfänger den Begriff „fundiert“ kennen.)
@ThomasAndrews Ich bin kein Anfänger (trotz meines SE-Rufs), ich weiß genau, was Ordnung bedeutet, und ich habe Asafs Gegenbeispiel so oft gesehen, dass ich sie nicht einmal zählen kann (zumindest ohne AC :) . Was es noch schlimmer macht. Tatsache ist, dass ich dumm bin und mich manchmal, wenn ich müde bin, auf mein Gedächtnis statt auf Logik verlasse. Und jedes Mal scheitere ich kläglich. Diesmal dachte ich, dass ich mich daran erinnerte, dass die lexikografische Ordnung eine Brunnenordnung war $2^\omega$ , und ich habe es nicht einmal überprüft. Mein Fehler. Danke Asaf trotzdem ... immer das Beste (und das erste auch)! Wie auch immer, Sie sollten 1 und 0 in Ihrer Definition vertauschen.
@ aerdna91 "Gut begründet" ist nicht "wohlgeordnet". Fundiert ist eine Verallgemeinerung auf Nichtordnungsbeziehungen.
Ok, jetzt verstehe ich was du meinst. BTW, das wusste ich auch.
@AsafKaragila Es tut mir leid, aber ich kann es immer noch nicht ganz verstehen. Behaupten Sie, dass wenn $\lambda$ Und $\kappa$ Kardinalzahl sind, dann $^\lambda \kappa$ (die Menge aller Funktionen $\lambda \to \kappa$ ) ist gut bestellbar (und dann $|^\lambda \kappa|$ wohldefiniert ist)?
@ aerdna91: Nein, ich behaupte, dass Kardinalzahlen nicht unbedingt Ordnungszahlen sind. Und diese kardinale Potenzierung ist wohldefiniert (in dem Sinne, dass wenn $|A|=|A'|$ Und $|B|=|B'|$ Dann $|A^B|=|A'^{B'}|$ ). Es ist eine Übung auf Anfängerniveau in der schmerzhaften Zusammensetzung von Bijektionen, und ich überlasse es Ihnen, dies zu überprüfen.
Jetzt verstehe ich, warum ich total verwirrt war! Hier geht der Autor "naiv mengentheoretisch" mit Kardinalzahlen um! Nun, meiner Meinung nach wäre es in diesem Fall klarer gewesen zu schreiben $|2^\omega|$ anstatt $2^{\aleph_0}$ . Danke nochmal
@aerdna91: Aber $2^{\aleph_0}$ ist die richtige Schreibweise. Es ist ein gut definierter Kardinal. Vielleicht wäre es ein besserer Weg, in der Einleitung zu schreiben, dass die kardinale Potenzierung von zwei wohlgeordneten Kardinalzahlen selbst keine wohlgeordnete Kardinalzahl sein muss; aber hast du schon die einleitung gelesen? :-)
Ja, ich habe es getan, ich schwöre :) Ich hatte auch mit Strg+F nach "Kardinal" gesucht, weil ich langsam vermutete, dass mein Problem ein Missverständnis der Definitionen mit dem Autor sein könnte. Um ehrlich zu sein, scheint es mir, dass es keine klare Definition von Kardinaloperationen durch das Buch gibt. Trotzdem befasst sich das Buch mit Ordnungszahlen, daher dachte ich, dass dies der Ansatz war, den er verwendete (dh Kardinalzahlen sind Ordnungszahlen, und $|A|$ ist eine Kardinalzahl und daher definiert iff $A$ ist gut bestellbar).

Peter Franken · Answer 2

Peter Franken

Es scheint mir, dass Sie irgendwie Ordnungsfähigkeit mit Kardinalität vermischen. Zwei Sets $A$ Und $B$ haben genau dann dieselbe Kardinalität, wenn es eine Bijektion gibt $A\to B$ . Es sagt nicht aus, ob sie gut geordnet werden können oder nicht.

Laut Carl Mummerts Antwort hier stimmt es mit ZF überein, dass es keine gute Ordnung der Realzahlen gibt.

aerdna91

Falls es eine Bijektion gibt

f : λ \to A

$f: \lambda \to A$ , Wo

λ

$\lambda$ ist also wohlgeordnet

A

$A$ ist gut bestellbar. Es stimmt, dass ZF

⊬

$\not\vdash$ "

R

$\mathbb R$ ist gut bestellbar.“ Wenn es stimmen würde, dass ZF

⊢ " P (ω)

$\vdash \mathcal "P(\omega)$ ist gut bestellbar" und ZF

⊢ R \approx P (ω)

$\vdash \mathbb R \approx \mathcal P(\omega)$ , dann hatten wir ein ernstes Problem ;)

Peter Franken

R ≃ P (ω)

$\mathbb{R}\simeq\mathcal{P}(\omega)$ ist nachweisbar in

Z F

$ZF$ . Die gute Bestellbarkeit von

R

$\mathbb{R}$ (oder gleichwertig,

P (ω)

$\mathcal{P}(\omega)$ ) meines Wissens nach nicht. Aber selbst wenn es beweisbar wäre, sehe ich das ernsthafte Problem nicht.

Asaf Karagila

Peter, es scheint, dass das OP nicht sicher war, ob ihr "Beweis" falsch ist, und war sich daher nicht sicher, ob oder nicht

| R | = | P (ω) |

$|\Bbb R|=|\mathcal P(\omega)|$ ohne das Wahlaxiom beweisbar ist, und daher die Frage.

Ist das Auswahlaxiom notwendig, um R≈P(ω)R≈P(ω)\mathbb R \approx \mathcal P(\omega) zu beweisen?

aerdna91

Zhen Lin

Asaf Karagila

aerdna91

Antworten (2)

Asaf Karagila

Thomas Andreas

aerdna91

Thomas Andreas

aerdna91

Asaf Karagila

Asaf Karagila

aerdna91

Asaf Karagila

aerdna91

Asaf Karagila

aerdna91

Peter Franken

aerdna91

Peter Franken

Asaf Karagila

Bezüglich κ+κ=κκ+κ=κ\kappa+\kappa=\kappa für jede unendliche Kardinalzahl κκ\kappa

Zählen von Teilmengen unterschiedlicher Größe einer Menge

Wie man die Definition der Kardinalpotenzierung versteht

Kardinalität der Menge reeller stetiger Funktionen

Auswahlaxiom anhand von Beispielen verstehen

Zorns Lemma und Wahlaxiom

Gültigkeit des Auswahlaxioms unter verschiedenen Definitionen paarweise disjunkter Mengen

Warum wird für den Beweis, dass abzählbare Vereinigungen abzählbarer Mengen abzählbar sind, ein Axiom of Choice benötigt?

Zusammenhang zwischen den vielen verschiedenen Definitionen des Axiom of Choice

Verwendung des Auswahlaxioms in der Übung zur Kardinalmultiplikation