matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikRelationen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Diskrete Mathematik" - Relationen
Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Relationen: Äquivalenzrelation
Status: (Frage) beantwortet Status 
Datum: 15:16 Fr 19.05.2006
Autor: Frankster

Aufgabe
Auf der Menge A={0....9}x{0....9} ist folgende Äquivalenzrelation R definiert:
[mm] ((n_{1},m_{1}),(n_{2},m_{2})\in [/mm] R genau dann, wenn [mm] n_{1} \equiv n_{2}(mod3) [/mm] und [mm] m_{1} \equiv m_{2}(mod3) [/mm]

a)
n = 7
m = 8

Aus wie vielen Elementen besteht die Äquivalenzklasse bezüglich R, in der (n,m) liegt ?

b)
Für welchen Wert k ist R auch eine Halbordnung ?

Hallo!

Ich habe riesen Probleme beim Verständnis dieser Zeile
[mm] ((n_{1},m_{1}),(n_{2},m_{2})\in [/mm] R

A={0....9}x{0....9}
bedeutet ich verknüpfe jedes Element mit sich selbst
(0 0) (0 1) ....... (0 9)
(1 0) (1 1).........(1 9)
(2 0) (2 1).........(2 9)
usw.........................

[mm] n_{1} \equiv n_{2}(mod3) [/mm]
bedeutet die Differenz zwischen [mm] n_{1} [/mm] und [mm] n_{2} [/mm] und diesen Wert mod3

0 - 0 mod 3 = 0
1 - 0 mod 3 = 1
2 - 0 mod 3 = 2
3 - 0 mod 3 = 3
usw.......

Für n = 7
Würde ich sagen gibt es folgende Mengen:
(0 0) (0 3) (0 6)
(1 1) (1 4) (1 7)
(2 2) (2 5)
(3 0) (3 3) (3 6)
(4 1) (4 4) (4 7)
(5 2) (5 5)
(6 0) (6 3) (6 6)
(7 1) (7 4) (7 7)

Für m = 8
(0 0) (0 3) (0 6)
(1 1) (1 4) (1 7)
(2 2) (2 5) (2 8)
(3 0) (3 3) (3 6)
(4 1) (4 4) (4 7)
(5 2) (5 5) (5 8)
(6 0) (6 3) (6 6)
(7 1) (7 4) (7 7)
(8 2) (8 5) (8 8)

Stimmt das soweit ?

Mfg
Frankster

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Relationen: Lösung ?
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:58 Fr 19.05.2006
Autor: Frankster

Könnte es vielleicht 3 Äquivalenzklassen geben ?

(0,3,6)
(1 4 7)
(2 5 8)

Oder gehört der 9er auch noch rein ?
(0 3 6 9)????

Bezug
        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:16 Fr 19.05.2006
Autor: piet.t

Hallo Frankster,


>  
> A={0....9}x{0....9}
>  bedeutet ich verknüpfe jedes Element mit sich selbst

An dieser Stelle wird ja eigentlich nichts "verknüpft", es werden einfach Paare gebildet, wo das erste Element aus {0...9} und auch das zweite Element aus {0...9} stammt.

>  (0 0) (0 1) ....... (0 9)
>  (1 0) (1 1).........(1 9)
>  (2 0) (2 1).........(2 9)
>  usw.........................

>

Aber das ist wieder richtig, oben wahr vielleicht nur die Formulierung etwas unglücklich.
  

> [mm]n_{1} \equiv n_{2}(mod3)[/mm]
>  bedeutet die Differenz zwischen
> [mm]n_{1}[/mm] und [mm]n_{2}[/mm] und diesen Wert mod3
>

Von einer Differenz sehe ich hier erst mal nichts - [mm] n_1 [/mm] und [mm] n_2 [/mm] sind einfach mod3 zu vergleichen, d.h. es ist zu prüfen, ob sie bei Division durch 3 den gleichen Rest ergeben.

Bezüglich der gegebenen Relation wird es dann etwas unübersichtlich, ich versuche daher mal ein paar Sätze darüber zu verlieren:

Die Relation R "vergleicht" zwei Zahlenpaare aus A miteinander. Wenn [mm] ((n_1,m_1) ,(n_2,m_2)) [/mm] (hier haben wir also in "Paar von Paaren"...) in R liegt schreibt man oft auch (etwas) kürzer [mm] (n_1,m_1)R(n_2,m_2). [/mm] Ist R eine Äquivalenzrelation sagt man auch  [mm] (n_1,m_1) [/mm] und [mm] (n_2,m_2) [/mm]  sind äquivalent bezüglich R.

Die Definition der Relation liefert dann die Verfahrensvorschrift wie man prüfen kann, ob [mm] (n_1,m_1)R(n_2,m_2). [/mm]
Beispiel: Prüfe die Äquivalenz von (1,3) und (4,7) bezüglich R.
Laut Vorschrift muss man jetzt jeweils die ersten und die zweiten Elemente mod3 vergleichen. Wir haben also:
[mm]1 \equiv 4 \mod 3[/mm] -> O.K.
[mm]3 \not\equiv 7 \mod 3[/mm] -> nicht O.K.
Also [mm](1,3)\neg R (4,7)[/mm], d.h. die beiden Paare sind nicht äquivalent bezüglich R.

Vielleicht ist damit etwas klarer, wie die Relation eigentlich anzuwenden ist.

Bezüglich des zweiten Artikels: gesucht sind in der Aufgabe ja nicht die Zahl der verscheidenen Äquivalenzklassen, sondern nur die größe einer bestimmten, nämlich der, in der (7,8) liegt. Anders formuliert: Wie viele Elemente (n,m) gibt es in A, so dass (n,m)R(7,8) gilt?
Zusatzaufgabe: welche sind das?

Bezüglich b) kann ich erst mal gar nichts sagen, denn da taucht auf einmal ein k auf, das nirgends definiert wurde [verwirrt]

Aber vielleicht kommst Du damit ja schon mal ein kleines Stückchen weiter!

Gruß

piet

Bezug
                
Bezug
Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:38 Fr 19.05.2006
Autor: Frankster

Das k bedeutet
A= {0...k}

ad Bsp1)

Das bedeutet
(1 2) (1 5) (1 8)
(4 2) (4 5) (4 8)
(7 2) (7 5) (7 8)
Sind meine Lösung ?

Bezug
                        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:32 Fr 19.05.2006
Autor: piet.t

Hallo,

> Das k bedeutet
>  A= {0...k}

Also wahrscheinlich A= [mm] \{0...k\}\times\{0...k\} [/mm]

>  
> ad Bsp1)
>  
> Das bedeutet
>  (1 2) (1 5) (1 8)
>  (4 2) (4 5) (4 8)
>  (7 2) (7 5) (7 8)
>  Sind meine Lösung ?

...das hätte ich zumindest auch raus.

Zu b) erstmal nur ein paar Gedanken:
R ist ja schon eine Äquivalenzrelation und soll nun gleichzeitig noch eine Halbordnung sein. Das bedeutet also
- R ist symmetrisch: aRb [mm] \gdw [/mm] bRa
und gleichzeitig
- R ist antisymmetrisch: aRb [mm] \wedge [/mm] bRa [mm] \Rightarrow [/mm] a=b

Was folgt daraus für die Größe der Äquivalenzklassen bezüglich R?
Für welche k kann das nur der Fall sein?

Gruß

piet

Bezug
                                
Bezug
Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:15 Fr 19.05.2006
Autor: Frankster

Sagen wir ich hätte jetzt ein Menge A mit
A={0 1} x {0 1}

Eigentlich bei jeder Zahl so lange sie gleich sind ?
(0 0) passt
(1 0) passt nicht
(0 1) passt nicht
(1 1) passt

Nur da könnte ja k unendlich sein ?

PS: das ist ja IMMER symmetrisch, wie kann das anti symm werden ?

PPS: Meine obige Darstellung der Lösung -> sind das meine Äquivalenzklassen ?

Bezug
                                        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 09:51 Sa 20.05.2006
Autor: piet.t


> Sagen wir ich hätte jetzt ein Menge A mit
> A={0 1} x {0 1}
>  
> Eigentlich bei jeder Zahl so lange sie gleich sind ?
>  (0 0) passt
>  (1 0) passt nicht
>  (0 1) passt nicht
>  (1 1) passt

Was bedeutet jezt hier "passt"? Wenn Du damit "liegt in R" meinst, dann Vorsicht: R bezieht sich immer auf 2 Zahlenpaare, also z.B. (0 0)R(0 0).

>  
> Nur da könnte ja k unendlich sein ?

...siehe später

>  
> PS: das ist ja IMMER symmetrisch, wie kann das anti symm
> werden ?
>  

Da R ja eine Äquivalenzrelation ist (und auch bleibt) gilt natürlich immer die Symmetrie, d.h. (n,m)R(n,m) gilt immer.
Wenn man sich aber die Definitionen von symmetrisch und antisymmetrisch anschaut stellt man fest, dass sie sich nicht unbedingt ausschließen.
Betrachten wir jetzt einmal den Fall, dass R gleichzeitig symmetrisch und antisymmetrisch ist. Seien dann [mm] (n_1,m_1) [/mm] und [mm] (n_2,m_2) [/mm] aus A mit [mm] (n_1,m_1)R(n_2,m_2). [/mm] Dann gilt ja:
[mm] (n_1,m_1)R(n_2,m_2) \Rightarrow (n_2,m_2)R(n_1,m_1) [/mm] (Symmetrie), also auch
[mm] (n_1,m_1)R(n_2,m_2) \wedge (n_2,m_2)R(n_1,m_1) [/mm]
und damit wegen der Antisymmetrie
[mm] (n_1,m_1) [/mm] = [mm] (n_2,m_2). [/mm]
Also kann jede Äquivalenzklasse nur genau ein Element enthalten. Für welche k-Werte ist das der Fall, wann finden wir Äquivalenzklassen mit 2 oder mehr Elementen?
  


> PPS: Meine obige Darstellung der Lösung -> sind das meine
> Äquivalenzklassen ?

Deine Aufzählung oben stellt ja alle Elemente aus A dar, und da da keine Äquivalenten dabei sind: ja!
Allgemein könnte man die Äquivalenzklassen so bilden:
Man schreibt sich alle Elemente der Grundmenge auf und verteilt sie dann so auf unterschiedliche "Töpfe", dass in einem Topf nur äquivalente Elemente liegen und zwei Elemente aus unterschiedlichen Töpfen nicht äquivalent sind.

Gruß

piet


Bezug
                                                
Bezug
Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:19 Sa 20.05.2006
Autor: Frankster

Irgendwie steh ich auf der Leitung

Wenn wir sagen
$ [mm] (n_1,m_1)R(n_2,m_2) \wedge (n_2,m_2)R(n_1,m_1) [/mm] $ genau dann wenn [mm] (n_1,m_1)=(n_2,m_2) [/mm]

Wir sollen prüfen ob [mm] (n_1,m_1)mod3 [/mm] das gleiche wie [mm] (n_2,m_2)mod3 [/mm] ist

Nur sobald unsere Menge A ={0,1}x{0,1} besteht
habe ich (0 0) (1 0) (0 1) (1 1)

(0 0)R(1 0) -> ist nicht erfüllt
usw....

Ich würde sagen das geht nur wenn k null ist ?
Weil sobald k > 0 ist kann ich paar bilden und somit ist die Relationsbedingung nicht mehr erfüllt ?


Bezug
                                                        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 10:29 Sa 20.05.2006
Autor: piet.t

Du hast doch vorhin schon die Äquivalenzklassen zu k = 1 gebildet. Wie groß waren die jeweils? Und wie schauen im Gegensatz dazu die Äquivalenzklassen zu k = 4 aus (insbesondere z.B. die mit (1,0))?


Bezug
                                                                
Bezug
Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:36 Sa 20.05.2006
Autor: Frankster

Kann es vielleicht so sein ?

Bei k = 1
gibt es keine Äquivalenzklassen

Bei k = 2
Gibts auch keine

Erst bei k =3
(1 0) == (1 3)
(0 1) == (3 1)
(0 2) == (3 2)
usw...

Bezug
                                                                        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
Datum: 13:10 Sa 20.05.2006
Autor: piet.t


> Kann es vielleicht so sein ?
>  
> Bei k = 1
>  gibt es keine Äquivalenzklassen

Doch, es gibt schon welche, allerdings enthält jede davon nur ein Element.
Damit ist in diesem Fall also R auch eine Halbordnung. Das musst Du allerdings noch zeigen, denn oben habe ich ja nur bewiesen, dass falls R eine Halbordnung ist alle Äquivalenzklassen nur ein Element haben können, d.h. die Rückrichtung fehlt noch.

>  
> Bei k = 2
>  Gibts auch keine
>  

Siehe oben....

> Erst bei k =3
>  (1 0) == (1 3)
>  (0 1) == (3 1)
>  (0 2) == (3 2)
>  usw...

Genau, d.h. hier kann R keine Halbordnung mehr sein!

Gruß

piet

Bezug
                                                                                
Bezug
Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:47 Sa 20.05.2006
Autor: Frankster

Danke :)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]