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

Ich weiß, dass diese Frage hier oft gestellt wurde, einige davon sind doppelt vorhanden. Ich habe sie alle gelesen, aber mein Problem wurde nicht gelöst. Ich kann mir nur merken, dass Axiom of Choice (AC) benötigt wird, aber ich möchte dies logischerweise klarstellen.

Hinweis: „Zählbar“ bedeutet hier unendlich zählbar.

Erinnere dich an den Beweis, er geht so:

Erstens habe ich abzählbar viele abzählbare Mengen. Lassen Sie mich sie aufzählen ⟨ A ich ⟩ ich ∈ N . Für jede ich , A ich ist zählbar. Seit A ich ist jeweils zählbar ich , gibt es eine Bijektion H ich : N → A ich für jede ich . Dann kommt hier Axiom of Choice (AC) ins Spiel. Es gibt zählbar viele A ich , also muss ich 'zählbar viele' Male wählen. Dann habe ich H ich : N → A ich für jede ich Ich will.

Aber warum wird AC benötigt?

Was ich über AC verstehe, ist, wenn ich eine Sammlung nicht leerer Mengen habe und eine neue Menge konstruieren möchte, indem ich ein Element aus jeder Menge in der Sammlung auswähle, dann erlaubt mir AC, sie auszuwählen, um meine neue zu „konstruieren“. Satz. Dies wird ausdrücklich in seiner logischen Formel angegeben. Zum Beispiel, wenn ich eine Sammlung habe A = { A ich } ich ∈ N Wo A ich ist für jeden nicht leer ich und ich möchte ein neues Set konstruieren { A ich } ich ∈ N so dass A ich ∈ A ich für jede ich , dann brauche ich AC, um sicherzustellen, dass ein solches Set hergestellt werden kann. Allerdings, wenn meine Sammlung A = { A ich } ich = 0 N endlich ist, dann kann ich die neue Menge ohne AC konstruieren, dh es kann bewiesen werden, dass solche { A ich } kann ohne die Notwendigkeit von AC konstruiert werden.

Aber was ich nicht verstehe ist, warum darf ich nicht einmal ein Element auswählen und es manipulieren? Kehren Sie zum gleichen Beispiel zurück, wenn ich eine Sammlung habe A = { A ich } ich ∈ N Wo A ich ist für jeden nicht leer ich , dann weiß ich, dass es existiert A ich ∈ A ich für jede ich . Darf ich manipulieren? A ich für jede ich ?, wie Bauen { A ich } nach dem Paaraxiom? Kann ich ein Set konstruieren A ich ' := A ich − { A ich } für jede ich ? Jede A ich existiert logisch, und ich möchte sie so in Klammern setzen { A ich } . Dies wird durch das Paaraxiom erlaubt. Kann ich natürlich nicht machen { A ich } ich ∈ N da dies durch kein Axiom (selbst durch das Axiom der Vereinigung oder das Axiom der Unendlichkeit) außer AC impliziert wird.

Die meiste Antwort, die ich hier gefunden habe, ist, dass ich ohne AC nicht einmal ein Element aus jeder Menge unendlich oft „aussuchen“ kann (ganz zu schweigen davon, eine neue Menge daraus zu konstruieren). Einige Leute sagten sogar, dass jeder A ich im Beweis zählbar zu sein bedeutet nicht, dass seine Aufzählung gegeben ist. Nun, kann ich in diesem Fall nicht einfach sagen, dass es, da es keine Aufzählung gibt, nicht zählbar ist und daher ein Widerspruch zur Annahme ist? Eine Aufzählung muss vorhanden sein. Einige mögen sagen, dass es existiert, aber nicht gegeben ist. Was bedeutet dann „gegeben“ in der Logik? Sogar in dem Beweis, der AC verwendet, behaupten wir, dass eine Auswahlfunktion existiert, aber es wird nicht klar angegeben, „welche“ Auswahlfunktion. Wir wissen nur, dass es existiert und verwenden es, um den Beweis zu vollenden. Warum unterscheidet sich diese Situation von dem Wissen, dass jede Bijektion H ich existiert für jeden ich . Warum dürfen wir bestehende Auswahlfunktionen manipulieren, aber nicht bestehende Bijektionen? Hängt das damit zusammen, dass es in der Logik erster Stufe formuliert ist?

Danke schön!

Ihre Bedenken sind genau die Dinge, über die ich mich viele Jahre lang (seit ungefähr 40 Jahren) gewundert habe, und obwohl ich jetzt mehr über die damit verbundenen Probleme weiß als vor 40 Jahren, ist mir am meisten klar geworden (dies vielleicht durch die Anfang der 1990er für diejenigen, die Punkte sammeln) ist, dass es wahrscheinlich sinnlos ist, sich ohne den richtigen Hintergrund Gedanken über die Verwendung von Wechselstrom zu machen. Es ist, als würde man versuchen, die Topologie zu verstehen, indem man Beschreibungen auf der Ebene der "Gummiplattengeometrie" liest - es gibt zu viele Wörter mit spezifischen, präzisen Bedeutungen, die von Nichtexperten auf diesem Gebiet nicht auf die gleiche Weise verwendet werden.
In dem Ausdruck "nur die Mitglieder der Funktionsfolge auswählen" ist eine Annahme verborgen. Wenn es in logischer Syntax geschrieben ist, läuft es auf die Anwendung von Countable Choice hinaus, wie es im A von Rene Schipperus angegeben ist.
Ich glaube nicht, dass ich das wirklich verstanden habe, bis ich dachte, skeptisch zu sein, nur ein einzelnes Element „herauszupicken“ und herauszufinden, was dort vor sich geht.
Mein Verständnis ist, dass das Axiom der Wahl nur in Fällen "umstritten" ist, in denen eine unabzählbar unendliche Anzahl von Entscheidungen zu treffen sind. Das sind die Fälle, in denen "seltsame" Dinge wie das Banach-Tarski-Paradoxon und das Gefangenenhut-Paradoxon passieren können. Hier sieht es so aus, als gäbe es nicht unendlich viele Entscheidungen zu treffen. Einige Leute würden "das Axiom der zählbaren Auswahl" von "dem Axiom der Auswahl" unterscheiden, und es sieht so aus, als würde höchstens ersteres verwendet, um festzustellen, dass die Vereinigung einer zählbaren Anzahl zählbarer Mengen zählbar ist.
Für das Gefangenenhut-Paradoxon siehe "abzählbar unendliche Hutvariante" hier: en.wikipedia.org/wiki/Prisoners_and_hats_puzzle
Um Michaels Punkt zu verdeutlichen, hängt die Lösung des zählbar unendlichen Huträtsels vom (unzählbaren) Wahlaxiom ab.

Antworten (3)

Eine schwache Form von AC wird für while jede zählbare Menge verwendet A ich hat eine Bijektion F ich : A ich → N Diese Bijektion ist nicht eindeutig und AC muss die Sequenz auswählen ⟨ F ich : ich ∈ N ⟩ .

Das weiß ich, wenn ich die Sequenz konstruieren will ⟨ F ich : ich ∈ N ⟩ , dann wird AC (oder seine schwache Form) benötigt. Aber eine solche Folge wird im Beweis nicht benötigt. F ich (oder H ich in der Post) ist nur ein Symbol für jede Bijektion. Es kann durch andere Symbole ausgedrückt werden. Ich möchte nur verwenden H ich um eine neue Funktion zu konstruieren, nicht um eine Menge oder Folge zu bilden.
Der Punkt ist nicht so sehr, dass Sie eine Sequenz brauchen, sondern dass Sie wählen müssen F 3 , sagen wir, von den vielen Möglichkeiten für G : A 3 → N , Und F 4 Und F 5 usw. Um Ihre Karte zu definieren, müssen Sie all diese unendlich vielen Entscheidungen auf einmal treffen, hier kommt AC zur Rettung.
Neben der Frage, wo das (abzählbare) Auswahlaxiom verwendet wird, sollte erwähnt werden, dass der Grund für seine Verwendung darin besteht, dass einigen (z. B. Jech) bekannt ist, dass das Ergebnis ohne es nicht gilt. Tatsächlich ist für Ungläubige die reelle Linie die zählbare Vereinigung von zählbaren Mengen. (Ich weiß nichts davon, ich weiß nur, dass andere es tun.)
Eine Sequenz ⟨ F ich : ich ∈ N ⟩ wird später im Beweis benötigt. Eins F ich ist nicht genug. Der Beweis geht weiter, indem man alle unendlich vielen der Auserwählten zusammensetzt F ich 's in eine Aufzählung der Union ⋃ ich ∈ N A ich .
@AndreasBlass Das wollte ich ausdrücken, ich glaube, ich habe keine sehr gute Arbeit geleistet. Naja, jetzt ist es dein Problem.
Vielen Dank an alle. Ich glaube, ich habe es jetzt verstanden. Ja, eine solche Sequenz wird tatsächlich benötigt. Ich habe nachgedacht, seit ich die Frage gestellt habe. Ich musste den Beweis formal (mit logischen Symbolen) aufschreiben. Der Grund dafür ist, dass ich formal keine unendlich langen logischen Quantoren aufschreiben darf (jeden Quantor für jede Bijektion zu wählen). Aber mit AC machen Sie nur einen Quantor für die gesamte Folge von Bijektionen. So ein praktisches Axiom.
@ReneSchipperus Mein vorheriger Kommentar richtete sich an das OP, dessen erster Kommentar lautete: "Aber eine solche Sequenz wird im Beweis nicht benötigt." Und sein letzter Kommentar lässt mich denken, dass das Problem jetzt gelöst ist.
@ReneSchipperus Es ist nicht klar, was Sie mit einer "schwachen" Form von AC meinen. Vielleicht meinen Sie ähnlich wie mein Kommentar zur obigen Frage.

Festsetzung a : N → N × N eine Bijektion, die Funktion, die Sie (vermutlich) konstruieren möchten, ist

N ↦ H a ( N ) 1 ( a ( N ) 2 ) .
Damit die Bijektion, die Sie machen/haben möchten, diese Definition sinnvoll macht, benötigen Sie die Funktion ich ↦ H ich , da es Teil der Komposition ist. Dies ist die gleiche wie die Sequenz ⟨ H ich ⟩ ich ∈ N .

Wenn es für Sie offensichtlich klingt, dass diese Funktion verfügbar sein sollte, ist das gut, denn wir verwenden AC als Axiom in den meisten Alltagsmathematik.

Einige mögen sagen, dass es existiert, aber nicht gegeben ist. Was bedeutet dann „gegeben“ in der Logik?

Normalerweise bedeutet gegeben, dass es eine Funktion gibt, die es gibt. In diesem Fall wäre das eine Funktion ich ↦ H ich .

Ich bin mir nicht sicher, ob dies eine vollständige Antwort darstellt, aber ich hoffe, ich kann einige Ihrer Verwirrungen beseitigen. Es mag an einigen Stellen technisch nicht korrekt sein (korrigieren Sie mich, wenn dies tatsächlich der Fall ist), aber so sehe ich die Situation intuitiv. Ich hoffe auch auf eine bessere Erklärung!

Jedes der Sets A ich sind abzählbar, also gibt es eine Bijektion H ich : N → A ich . Aber es gibt viele solcher Bijektionen, unendlich viele sogar, und es gibt keine "bevorzugte Bijektion". Was ich mit dem Fehlen einer bevorzugten Bijektion meine, ist, dass Sie ohne zusätzliche Struktur die Funktion nicht "auswählen" oder "ausschreiben" können H ich . Das bedeutet, dass die Bijektion existiert, aber nicht gegeben ist.

Angenommen, Sie können beweisen, dass die Gewerkschaft A = ⋃ ich ∈ N A ich ist zählbar. Das bedeutet, dass es eine Bijektion gibt H : N → A . Auch hier existiert es nur, anstatt gegeben zu sein, aber Sie müssen nur einmal eine Bijektion auswählen. Aus dieser Bijektion lassen sich Funktionen konstruieren F ich : H − 1 ( A ich ) → A ich , und es ist leicht zu überprüfen, ob es sich tatsächlich um Bijektionen handelt.

Jedes Set H − 1 ( A ich ) kann natürlich bijeziert werden N . Identifizieren Sie einfach das kleinste Element mit 0 , die zweitkleinste mit 1 , usw. Diese Bijektion ist "gegeben", da Sie sie explizit für alle angeben können ich gleichzeitig. Wenn Sie mit diesen Bijektionen komponieren, produzieren Sie Bijektionen G ich : N → A ich .

Daher aus der Einzelaufzählung von A Sie erzeugen gleichzeitig eine Aufzählung für jeden A ich . Aber das läuft darauf hinaus, unendlich viele Entscheidungen gleichzeitig zu treffen, indem man Bijektionen wählt N → A ich für alle ich auf einmal. Dies sollte nicht möglich sein, wenn Sie keine Form von AC zur Verfügung haben. Das heißt, Zählbarkeit von A beweist mehr als ohne AC möglich sein sollte. Daher ist es ohne AC nicht beweisbar.

Randbemerkung: Die Bijektionen N → H − 1 ( A ich ) ⊂ N oben erzeugt, führen ebenfalls zu einer Bijektion N → N 2 . Wenn Sie argumentieren können, dass dies ohne Wahl unmöglich ist (was der Fall ist), haben Sie dies gezeigt A ist nicht ohne Wahl abzählbar.

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