Surjektionen und Äquivalenzrelationen

(a) Let F : A → B sei eine surjektive Funktion. Wir definieren A 1 ∼ A 2 Wenn F ( A 1 ) = F ( A 2 ) . Beweise das ∼ ist eine Äquivalenzrelation.

  • Reflexivität: Dies ist kostenlos. Wenn A 1 ∼ A 1 , Dann F ( A 1 ) = F ( A 1 ) .

  • Symmetrie: Angenommen A ∼ B . Dann F ( A ) = F ( B ) . Aber das ist dasselbe wie zu sagen F ( B ) = F ( A ) . Daher B ∼ A .

  • Transitivität: Angenommen A ∼ B Und B ∼ C . Dann F ( A ) = F ( B ) Und F ( B ) = F ( C ) . Dann F ( A ) = F ( C ) . Daher A ∼ C .

(b) Angenommen A ist eine Menge und ∼ ist eine Äquivalenzrelation auf A . Finden Sie einen Satz B und eine Funktion F : A → B so dass F ( A 1 ) = F ( A 2 ) Genau wann A 1 ∼ A 2 .

Bei diesem bin ich mir nicht sicher, wie ich überhaupt anfangen soll. Es scheint, als würde ich versuchen, die Umkehrung von Teil (a) zu beweisen, aber ich bin mir nicht sicher.

Ihre freie Reflexivität ist nicht ganz richtig. In der Tat ist es ein bisschen rückwärts. Können Sie sehen, warum?
Dafür habe ich den Beweis stark gekürzt. Meine Überlegung ist, dass Wenn A ∼ A , Dann F ( A ) = F ( A ) . Aber Funktionsgleichheit ist bereits reflexiv, also folgt daraus ∼ ist reflexiv.
Eugene Tooms, Sie haben gerade den Trugschluss begangen, die Konsequenz zu bestätigen .
Oh Gott. Wie mache ich das rückgängig? Ich habe auch Probleme mit der Reflexivität, da es immer so aussieht, als ob es umsonst wäre.
Diesmal ist es einfach. Alles, was Sie tun müssen, ist stattdessen die andere Seite der doppelten Implikation zu verwenden.

Antworten (1)

Tipp : Lass B = { [ A ] : A ∈ A } , Wo [ A ] ist die Äquivalenzklasse von A . Genauer,

[ A ] = { X ∈ A : X ∼ A }

Versuchen Sie nun, zu definieren F ( A ) = [ A ] .

Um zu beweisen, dass F die gewünschten Eigenschaften hat, nehmen wir an, dass A 1 ∼ A 2 ; dann per Definition einer Äquivalenzklasse, A 1 Und A 2 in derselben Äquivalenzklasse liegen; das ist, [ A 1 ] = [ A 2 ] . Somit,

F ( A 1 ) = [ A 1 ] = [ A 2 ] = F ( A 2 )

wie gewünscht. Nun auf der anderen Seite nehmen wir das an F ( A 1 ) = F ( A 2 ) . Dann [ A 1 ] = [ A 2 ] , und besonders, A 1 ∈ [ A 2 ] ; somit, A 1 ∼ A 2 . Damit ist der Beweis abgeschlossen.

Meinst du das: F ( A ) = { X ∈ A : X ∼ A } ?
@EugeneTooms Ja, genau.
Es scheint, als würde diese Definition das nur für jeden sagen X ∈ [ A ] Da ist ein A ∈ A so dass F ( A ) = X . Vielleicht habe ich einfach die Waffe übersprungen ...
@EugeneTooms Nicht ganz. Die gewünschte Funktion muss nur für jedes Element derselben Äquivalenzklasse dieselbe Ausgabe liefern.
@EugeneTooms Ich habe den Beweis dafür beigefügt F hat die gewünschten Eigenschaften in meiner Antwort.
Die Funktion ist also nur eine Funktion, die ein Element in seine Äquivalenzklasse abbildet?
@EugeneTooms Ja, genau.
Ich denke, das a in Ihrer Definition der Äquivalenzklasse sollte groß geschrieben werden.
Surjektionen und Äquivalenzrelationen
AntwortenHierDatenschutz-Bestimmungen1y, 0v