matematikk.net

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.

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]

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.

EulersPath skrev: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?