Isomorphe Äquivalenzbeziehungen und Partitionen

Lassen R 1 , R 2 R ( X ) Äquivalenzbeziehungen auf sein X . Definieren R 1 Und R 2 isomorph, wenn es eine Bijektion gibt F : X X so dass gilt:

Für alle j , z X : ( j , z ) R 1 dann und nur dann, wenn ( F ( j ) , F ( z ) ) R 2 .

( A ) Definieren Sie, was es für zwei Partitionen bedeutet P 1 , P 2 P ( X ) isomorph sein. (Eine Antwort darauf ist richtig, wenn Sie damit den nächsten Teil beweisen können.)

( B ) Beweisen Sie zwei Äquivalenzrelationen R 1 A N D R 2 genau dann isomorph sind, wenn die Partitionen φ ( R 1 ) Und φ ( R 2 ) sind isomorph. (Hier φ ist die Bijektion aus dem vorherigen Problem.)

(c) Let X = { 1 , 2 , 3 , 4 , 5 } . Bis auf Isomorphie, wie viele Äquivalenzrelationen gibt es noch X ?

Mein Versuch: So wie ich es verstehe, können Äquivalenzbeziehungen in eine Bijektion mit Partitionen gebracht werden, und wenn es also eine Bijektion zwischen Elementen einer Beziehung zu einer anderen gibt, dann gibt es eine Bijektion zwischen Elementen einer Partition mit einer anderen. Dies würde dazu führen, dass die Partitionen der in der Frage erwähnten Definition von Isomorphie entsprechen und somit bewiesen werden ( B ) . Ich verstehe nicht was ( C ) fragt überhaupt, und ich suche nach einem formalen Beweis / Weg, um zu schreiben, was ich denke, wenn das, was ich denke, überhaupt richtig ist.

Antworten (2)

Hinweis: In c) muss man alle Partitionen der Menge aufzählen X (bis auf Isomorphie). Berechnen Sie zuerst die Anzahl der Partitionen von X . Dies ist die Bell-Nummer B ( 5 ) , Wo B ( N ) = k = 1 N S ( N , k ) Und S ( N , k ) ist die Anzahl der Partitionen von N hinein k Teile (Stirling-Zahl 2. Art).

Wir haben B ( 1 ) = 1 , mit Teilung { { 1 } } ,

B ( 2 ) = 2 mit Trennwänden { { 1 , 2 } } , { { 1 } , { 2 } } ,

B ( 3 ) = 5 mit Trennwänden { { 1 } , { { 2 } , { 3 } } , { { 1 , 2 } , { 3 } } , { { 1 , 3 } , { 2 } } , { { 2 , 3 } , { 1 } } , { { 1 , 2 , 3 } } , usw.

In Anbetracht der Isomorphieklassen müssen Sie nur die Arten der Partitionen berücksichtigen (siehe Kommentar unten).

BY REQUEST: Nehmen Sie zum Beispiel die Bijektion F = ( 1 2 3 2 3 1 ) . Dann die Teilung { { 1 , 2 } , { 3 } } wird der Partition zugeordnet { { F ( 1 ) , F ( 2 ) } , { F ( 3 ) } } = { { 2 , 3 } , { 1 } } .

Beachten Sie, dass c) nach allen isomorphen Partitionen fragt. Das bedeutet, dass das zweite, dritte und vierte Beispiel in B ( 3 ) sind gleich
Stimmt, aber ich würde damit anfangen B ( N ) .
Können Sie bitte erklären, was es bedeutet, wenn Partitionen isomorph sind?
Siehe Beispiel am Ende.

Hinweis: Beachten Sie, dass mit Ihrer Definition zwei Partitionen in Sätzen vorhanden sind A 1 , . . , A N Und B 1 , . . , B N sind isomorph genau dann, wenn sie nach der Anzahl ihrer Elemente aufsteigend geordnet dieselbe Folge ergeben