Ekvivalens relasjoner

[fabster]

Hallo
Jeg har en oppgave i Mat1030 Diskret Matematikk og sliter med deler av oppgaven.
Lurer på om det er noen som kan hjelpe meg med å forstå og løse den.

La X være en endelig mengde og la P(X) være potensmengden til X. dvs mengden av alle delmengder av X. For en valgt delmengde Y (C med strek under) X definerer en relasjon Ry på P(X) ved

ARyB hvis A snitt B = B snitt A

a) Vis at Ry er en ekvivalensrelasjon.

Her har jeg kommet frem til at det er en ekvivalens relasjon siden den er
refleksiv: (A snitt Y) = (A snitt Y)
Symetrisk: Siden (A snitt Y) = (B snitt Y) må (B snitt Y = A snitt Y)
Transitiv: Siden vi vet at (A snitt Y) = (B snitt Y) og forutsetter at (B snitt Y) = (C snitt Y)
må (A snitt Y) = (C snitt Y)

b) La X = {1, 2, 3, 4} og Y = {1, 2}. Skriv ned alle ekvivalensklassene til Ry på P(X).

Det er her jeg ikke lengre er helt med.

[daofeishi]

Jeg er ikke helt sikker på om jeg forstår oppgaven din.

Du er altså gitt en mengde [tex]X = \{ a_1, \ a_2, \... \ a_n \}[/tex] og dens potensmengde [tex]P(X) = \left{ \empty, \ \{a_1\}, \ \{a_2\}, \ ..., \ \{a_1, a_2, \ ... \ a_n\} \right}[/tex]. Vi tar så en tilfeldig delmengde Y av X (som selvfølgelig er et element i P(X)), og definerer en relasjon [tex]{\rm Ry}[/tex] på [tex]P(X) \times P(X)[/tex] ved

[tex]Y_A {\rm Ry} Y_B[/tex] dersom [tex]Y_A \cap Y_B = Y_B \cap Y_A[/tex]

Isåfall har du en ekvivalensrelasjon, ja. "Problemet" er vel at du bare har én ekvivalensklasse, siden snitt-operasjonen er kommutativ. Ta en liten titt på transitivitetsbeviset ditt. Vi kan ikke kan forutsette at A snitt Y = B snitt Y. Vi kan ha A Ry Y og Y Ry B uten at A snitt Y = Y snitt B. Faktisk vil A snitt B = B snitt A for alle sett A og B. Relasjonen er transitiv, men under oppgaveteksten din, slik jeg har forstått den, stemmer ikke beviset.

Jeg lurer på om ikke relasjonen skal være definert slik?:

[tex]Y_A {\rm Ry} Y_B[/tex] dersom [tex]Y_A \cap Y_B = Y_A \cup Y_B[/tex]

[EulersPath]

At relasjonen er symmetrisk betyr ikke at A snitt Y = B snitt Y. Det betyr derimot at hvis A snitt Y = B snitt Y, så er B snitt Y = A snitt Y, noe som er ganske selvsagt og selvsagt lettere beviselig.

Transitiv er den også siden: Hvis A Ry B og B Ry C, så A Ry C. A og B gir samme resultatet snittet med Y, siden også C gir samme resultat som B snittet med Y, må nødvendigvis A snitt Y = C snitt Y. Hvis du skjønner hva jeg mener.

Jeg kan opplyse om at det eksisterer fire ekvivalensklasser for dette. E( [symbol:tom] ), E({1}), E({2}), E({1,2}). Merkelig nok, ser vi at dette er de fire delmengdene inneholdt i P(Y).

Beklager elendig bruk av forumets muligheter for matematiske symboler, men jeg er ny her og det er også sent.

[Orchin]

Jeg kan opplyse om at det eksisterer fire ekvivalensklasser for dette. E( [symbol:tom] ), E({1}), E({2}), E({1,2}). Merkelig nok, ser vi at dette er de fire delmengdene inneholdt i P(Y).

Hvordan finner man disse?