Äquivalenzr. a*b= gerade Z.? < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:35 Mo 14.07.2014 | | Autor: | MietzeK |
| Aufgabe | [mm] R=[(a,b)\in \IN [/mm] x [mm] \IN [/mm] : a*b ist eine gerade Zahl oder a=b]
Prüfen Sie ob R eine Äquivalenzrelation ist und geben Sie ggf. die Klasseneinteilung an. |
Hallo!
Bin in der Prüfungsvorbereitung und komme hier leider nicht weiter:
Eine ÄR liegt vor, wenn die Eigenschaften reflexiv, transitiv und symmetrisch vorliegen.
Meine Ideen:
reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm] a\in [/mm] A gilt: [mm] (a,a)\in [/mm] R
die Eigenschaft ist nicht erfüllt, denn ich habe ein Gegenbeispiel:
3*3 ist 9 und 9 ist keine gerade Zahl
transitiv: Eigenschaft erfüllt, wenn [mm] (a,b)\in [/mm] R und [mm] (b,c)\in [/mm] R [mm] ->(a,c)\in [/mm] R
da hätte ich auch ein Gegenbeispiel: a=3, b=4, c=5
a*b ist gerade, b*c ist gerade aber a*c nicht
symmetrisch: wenn aus [mm] (a,b)\in [/mm] R folgt dass [mm] (b,a)\in [/mm] R ist
Eigenschaft ist erfüllt, weil die Multiplikation kommutativ ist
Irgendwie kommen mir die ersten beiden Ansätze nicht richtig vor. Falls sie doch richtig ist, wie kann ich das ohne Beispiel, also als Beweis aufschreiben?
Danke schonmal! :)
|
|
| |
|
Hallo,
> [mm]R=[(a,b)\in \IN[/mm] x [mm]\IN[/mm] : a*b ist eine gerade Zahl oder a=b]
> Prüfen Sie ob R eine Äquivalenzrelation ist und geben
> Sie ggf. die Klasseneinteilung an.
> Hallo!
> Bin in der Prüfungsvorbereitung und komme hier leider
> nicht weiter:
>
> Eine ÄR liegt vor, wenn die Eigenschaften reflexiv,
> transitiv und symmetrisch vorliegen.
> Meine Ideen:
> reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm]a\in[/mm] A
> gilt: [mm](a,a)\in[/mm] R
> die Eigenschaft ist nicht erfüllt, denn ich
> habe ein Gegenbeispiel:
> 3*3 ist 9 und 9 ist keine gerade Zahl
Hier nochmal der Teil der Angabe den du offensichtlich überlesen hast:
oder a=b
> transitiv: Eigenschaft erfüllt, wenn [mm](a,b)\inR[/mm] und
> [mm](b,c)\inR ->(a,c)\inR[/mm]
> da hätte ich auch ein
> Gegenbeispiel: a=3, b=4, c=5
> a*b ist gerade, b*c ist gerade aber a*c
> nicht
Richtig.
> symmetrisch: wenn aus [mm](a,b)\inR[/mm] folgt dass [mm](b,a)\inR[/mm] ist
> Eigenschaft ist erfüllt, weil die
> Multiplikation kommutativ ist
>
> Irgendwie kommen mir die ersten beiden Ansätze nicht
> richtig vor. Falls sie doch richtig ist, wie kann ich das
> ohne Beispiel, also als Beweis aufschreiben?
> Danke schonmal! :)
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:10 Mo 14.07.2014 | | Autor: | MietzeK |
reflexiv: Eigenschaft ist erfüllt, wenn für alle $ [mm] a\in [/mm] $ A
> gilt: $ [mm] (a,a)\in [/mm] $ R
> die Eigenschaft ist nicht erfüllt, denn ich
> habe ein Gegenbeispiel:
> 3*3 ist 9 und 9 ist keine gerade Zahl
Hier nochmal der Teil der Angabe den du offensichtlich überlesen hast:
oder a=b
Danke schonmal!
Ich dachte, dass (a,a) etwas anderes ist als a=b. Aber wenn es die gleiche Zahl ist erscheint es mir logisch :)
Wie kann ich beweisen, dass es nicht transitiv ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:12 Mo 14.07.2014 | | Autor: | fred97 |
> reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm]a\in[/mm] A
> > gilt: [mm](a,a)\in[/mm] R
> > die Eigenschaft ist nicht erfüllt, denn ich
> > habe ein Gegenbeispiel:
> > 3*3 ist 9 und 9 ist keine gerade Zahl
>
> Hier nochmal der Teil der Angabe den du offensichtlich
> überlesen hast:
>
> oder a=b
>
>
> Danke schonmal!
> Ich dachte, dass (a,a) etwas anderes ist als a=b. Aber
> wenn es die gleiche Zahl ist erscheint es mir logisch :)
>
> Wie kann ich beweisen, dass es nicht transitiv ist?
Durch ein Gegenbeispiel. Aber das hast Du doch schon !
FRED
|
|
|
| |
|
> [mm]R=[(a,b)\in \IN[/mm] x [mm]\IN[/mm] : a*b ist eine gerade Zahl oder a=b]
> Prüfen Sie ob R eine Äquivalenzrelation ist und geben
> Sie ggf. die Klasseneinteilung an.
> Hallo!
> Bin in der Prüfungsvorbereitung und komme hier leider
> nicht weiter:
>
> Eine ÄR liegt vor, wenn die Eigenschaften reflexiv,
> transitiv und symmetrisch vorliegen.
> Meine Ideen:
>
> reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm]a\in[/mm] A
> gilt: [mm](a,a)\in[/mm] R
> die Eigenschaft ist nicht erfüllt, denn ich
> habe ein Gegenbeispiel:
> 3*3 ist 9 und 9 ist keine gerade Zahl
>
> transitiv: Eigenschaft erfüllt, wenn [mm](a,b)\inR[/mm] und
> [mm](b,c)\inR ->(a,c)\inR[/mm]
> da hätte ich auch ein
> Gegenbeispiel: a=3, b=4, c=5
> a*b ist gerade, b*c ist gerade aber a*c
> nicht
>
> symmetrisch: wenn aus [mm](a,b)\inR[/mm] folgt dass [mm](b,a)\inR[/mm] ist
> Eigenschaft ist erfüllt, weil die
> Multiplikation kommutativ ist
>
> Irgendwie kommen mir die ersten beiden Ansätze nicht
> richtig vor. Falls sie doch richtig ist, wie kann ich das
> ohne Beispiel, also als Beweis aufschreiben?
> Danke schonmal! :)
Hallo,
wie schon berichtet wurde, hast du bei der Eigenschaft "reflexiv"
nicht beachtet, dass nach Definition [mm] (a,a)\in [/mm] R für alle [mm] a\in\IN [/mm] ,
also insbesondere [mm] (3,3)\in [/mm] R . Also ist dies kein Gegenbeispiel.
Die Relation ist tatsächlich reflexiv, genau wegen diesem
Teil der Definition.
Dein Gegenbeispiel zur Transitivität ist OK. Um zu beweisen,
dass eine gewisse Eigenschaft nicht für alle Elemente der
Grundmenge (hier [mm] \IN\times\IN) [/mm] zutrifft, genügt es, ein einziges
Gegenbeispiel vorzuweisen. Dieser Nachweis, dass es wenigstens
ein konkretes Gegenbeispiel gibt, ist dann auch schon ein
vollwertiger Beweis.
Nur im umgekehrten Fall, wo es darum geht zu zeigen, dass
eine Eigenschaft allgemeingültig ist, ist der Nachweis eines
einzigen Beispiels dafür natürlich weit davon entfernt, schon
als Beweis brauchbar zu sein.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:52 Do 17.07.2014 | | Autor: | MietzeK |
Vielen Dank! :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:37 Do 17.07.2014 | | Autor: | Marcel |
Hallo,
> [mm]R=[(a,b)\in \IN[/mm] x [mm]\IN[/mm] : a*b ist eine gerade Zahl oder a=b]
> Prüfen Sie ob R eine Äquivalenzrelation ist und geben
> Sie ggf. die Klasseneinteilung an.
> Hallo!
> Bin in der Prüfungsvorbereitung und komme hier leider
> nicht weiter:
>
> Eine ÄR liegt vor, wenn die Eigenschaften reflexiv,
> transitiv und symmetrisch vorliegen.
> Meine Ideen:
>
> reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm]a\in[/mm] A
> gilt: [mm](a,a)\in[/mm] R
> die Eigenschaft ist nicht erfüllt, denn ich
> habe ein Gegenbeispiel:
> 3*3 ist 9 und 9 ist keine gerade Zahl
>
> transitiv: Eigenschaft erfüllt, wenn [mm](a,b)\inR[/mm] und
> [mm](b,c)\inR ->(a,c)\inR[/mm]
> da hätte ich auch ein
> Gegenbeispiel: a=3, b=4, c=5
> a*b ist gerade, b*c ist gerade aber a*c
> nicht
auch, wenn es offensichtlich ist: Du solltest auch noch $a [mm] \not=c$ [/mm] (wegen $3 [mm] \not=5$) [/mm] erwähnen.
Denn: Dass $a,b,c [mm] \in \IN$ [/mm] und daher $(a,b),(b,c),(a,c) [mm] \in \IN \times \IN,$ [/mm] ist klar.
Für
$(a,b),(b,c) [mm] \in [/mm] R$
hast Du daher dann Begründungen angegeben. Nun gilt aber
$(a,c)=(3,5) [mm] \in [/mm] R$
[mm] $\iff$ $a*c=3*5\,$ [/mm] ist gerade [mm] $\textbf{ oder }$ $a=c\,.$
[/mm]
Du hast oben aber nirgends erwähnt, dass die Aussage [mm] $a=c\,$ [/mm] in trivialer Weise
nicht(!!) erfüllt ist.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:55 Do 17.07.2014 | | Autor: | Marcel |
Hallo nochmal,
> [mm]R=[(a,b)\in \IN[/mm] x [mm]\IN[/mm] : a*b ist eine gerade Zahl oder a=b]
> Prüfen Sie ob R eine Äquivalenzrelation ist und geben
> Sie ggf. die Klasseneinteilung an.
>
> Hallo!
> Bin in der Prüfungsvorbereitung und komme hier leider
> nicht weiter:
>
> Eine ÄR liegt vor, wenn die Eigenschaften reflexiv,
> transitiv und symmetrisch vorliegen.
> Meine Ideen:
>
> reflexiv: Eigenschaft ist erfüllt, wenn für alle [mm]a\in[/mm] A
> gilt: [mm](a,a)\in[/mm] R
> die Eigenschaft ist nicht erfüllt, denn ich
> habe ein Gegenbeispiel:
> 3*3 ist 9 und 9 ist keine gerade Zahl
>
> transitiv: Eigenschaft erfüllt, wenn [mm](a,b)\in[/mm] R und
> [mm](b,c)\in[/mm] R [mm]->(a,c)\in[/mm] R
> da hätte ich auch ein Gegenbeispiel: a=3,
> b=4, c=5
> a*b ist gerade, b*c ist gerade aber a*c
> nicht
>
> symmetrisch: wenn aus [mm](a,b)\in[/mm] R folgt dass [mm](b,a)\in[/mm] R ist
> Eigenschaft ist erfüllt, weil die
> Multiplikation kommutativ ist
auch hier ist Deine Begründung nicht ganz korrekt: Du unterschlägst in der
Begründung den Fall
$(a,b) [mm] \in [/mm] R$ mit [mm] $a=b\,.$
[/mm]
(Nebenbei: Für [mm] ($\IN \times \IN$ $\ni$) [/mm] $(2,2) [mm] \in R\,$ [/mm] kann man zwei Begründungen angeben:
1. Es ist [mm] $2*2=4\,$ [/mm] gerade
oder
2. Es ist [mm] $2=2\,.$)
[/mm]
Natürlich kann man hier auch sagen, dass der Fall eigentlich mit der
Reflexivität abgehandelt worden ist. Aber aus dem von Dir geschriebenen
geht nicht hervor, dass Du Dir dazu überhaupt Gedanken gemacht hast.
Die genauere Begründung wäre also:
Die Multiplikation ist kommutativ und "=" ist symmetrisch (aus [mm] $a=b\,$ [/mm] folgt [mm] $b=a\,$).
[/mm]
Oder Du sagst:
Die Multiplikation ist kommutativ und [mm] $a=a\,$ [/mm] gilt in trivialer Weise immer.
Auf jeden Fall solltest Du halt aufpassen, dass Du die [mm] $R\,$ [/mm] charakterisierenden
Eigenschaften alle prüfst.
P.S. Ich hoffe, Dir passiert nun nicht folgender Fehler (eine typische Übungsaufgabe
ist es, diesen zu finden), dass Du denkst, dass jede symmetrische und
transitive Relation auch reflexiv ist.
Ein "falscher Beweis" davon geht so:
"Wenn [mm] $(a,b)\,$ [/mm] aus [mm] $R\,,$ [/mm] dann liefert ja die Symmetrie auch $(b,a) [mm] \in R\,.$
[/mm]
Mit
[mm] $(a,b),\,(b,a) \in [/mm] R$
folgt dann wegen Transitivität
$(a,a) [mm] \in R\,.$
[/mm]
Das zeigt die Reflexivität."
Frage an Dich: Wo ist der Fehler?
Hinweis: Reflexivität: Für alle $... [mm] \in [/mm] ...$ muss...
Was bedeutet aber oben:
"Wenn $(a,b) [mm] \in [/mm] R$..."
genauer?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:24 So 20.07.2014 | | Autor: | MietzeK |
Vielen Dank! Darauf habe ich gar nicht geachtet!
P.S. Ich hoffe, Dir passiert nun nicht folgender Fehler (eine typische Übungsaufgabe
ist es, diesen zu finden), dass Du denkst, dass jede symmetrische und
transitive Relation auch reflexiv ist.
Ein "falscher Beweis" davon geht so:
"Wenn $ [mm] (a,b)\, [/mm] $ aus $ [mm] R\,, [/mm] $ dann liefert ja die Symmetrie auch $ (b,a) [mm] \in R\,. [/mm] $
Mit
$ [mm] (a,b),\,(b,a) \in [/mm] R $
folgt dann wegen Transitivität
$ (a,a) [mm] \in R\,. [/mm] $
Das zeigt die Reflexivität."
Frage an Dich: Wo ist der Fehler?
Hinweis: Reflexivität: Für alle $ ... [mm] \in [/mm] ... $ muss...
Was bedeutet aber oben:
"Wenn $ (a,b) [mm] \in [/mm] R $..."
Ich verstehe leider gar nicht, warum aus $ [mm] (a,b),\,(b,a) \in [/mm] R $
die Transitivität $ (a,a) [mm] \in R\,. [/mm] $ folgen sollte? Für die Transititvität brauche ich doch zusätzlich ein c?
Zur Reflexivität habe ich noch eine Verständnisfrage:
z.B. R= (a,a), (a,b), (b,a)
->nicht reflexiv, weil (b,b) nicht drin ist aber auch nicht irreflexiv wegen (a,a) ?
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:11 So 20.07.2014 | | Autor: | fred97 |
> Vielen Dank! Darauf habe ich gar nicht geachtet!
>
> P.S. Ich hoffe, Dir passiert nun nicht folgender Fehler
> (eine typische Übungsaufgabe
> ist es, diesen zu finden), dass Du denkst, dass jede
> symmetrische und
> transitive Relation auch reflexiv ist.
> Ein "falscher Beweis" davon geht so:
>
> "Wenn [mm](a,b)\,[/mm] aus [mm]R\,,[/mm] dann liefert ja die Symmetrie auch
> [mm](b,a) \in R\,.[/mm]
> Mit
>
> [mm](a,b),\,(b,a) \in R[/mm]
>
> folgt dann wegen Transitivität
>
> [mm](a,a) \in R\,.[/mm]
>
> Das zeigt die Reflexivität."
>
> Frage an Dich: Wo ist der Fehler?
>
> Hinweis: Reflexivität: Für alle [mm]... \in ...[/mm] muss...
>
> Was bedeutet aber oben:
>
> "Wenn [mm](a,b) \in R [/mm]..."
>
>
> Ich verstehe leider gar nicht, warum aus [mm](a,b),\,(b,a) \in R[/mm]
>
> die Transitivität [mm](a,a) \in R\,.[/mm] folgen sollte? Für
> die Transititvität brauche ich doch zusätzlich ein c?
>
c=a
>
> Zur Reflexivität habe ich noch eine Verständnisfrage:
> z.B. R= (a,a), (a,b), (b,a)
Du meinst R= [mm] \{(a,a), (a,b), (b,a)\}
[/mm]
> ->nicht reflexiv, weil (b,b) nicht drin ist aber auch
> nicht irreflexiv wegen (a,a) ?
Ja
FRED
>
> Danke!
>
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 22:08 So 20.07.2014 | | Autor: | Marcel |
Hallo,
> > Vielen Dank! Darauf habe ich gar nicht geachtet!
> >
> > P.S. Ich hoffe, Dir passiert nun nicht folgender Fehler
> > (eine typische Übungsaufgabe
> > ist es, diesen zu finden), dass Du denkst, dass jede
> > symmetrische und
> > transitive Relation auch reflexiv ist.
> > Ein "falscher Beweis" davon geht so:
> >
> > "Wenn [mm](a,b)\,[/mm] aus [mm]R\,,[/mm] dann liefert ja die Symmetrie
> auch
> > [mm](b,a) \in R\,.[/mm]
> > Mit
> >
> > [mm](a,b),\,(b,a) \in R[/mm]
> >
> > folgt dann wegen Transitivität
> >
> > [mm](a,a) \in R\,.[/mm]
> >
> > Das zeigt die Reflexivität."
> >
> > Frage an Dich: Wo ist der Fehler?
> >
> > Hinweis: Reflexivität: Für alle [mm]... \in ...[/mm] muss...
> >
> > Was bedeutet aber oben:
> >
> > "Wenn [mm](a,b) \in R [/mm]..."
> >
> >
> > Ich verstehe leider gar nicht, warum aus [mm](a,b),\,(b,a) \in R[/mm]
> >
> > die Transitivität [mm](a,a) \in R\,.[/mm] folgen sollte? Für
> > die Transititvität brauche ich doch zusätzlich ein c?
> >
>
> c=a
Fred meinte [mm] $c=b\,,$ [/mm] sonst würden wir aus obigem $(b,b) [mm] \in [/mm] R$ einsehen (jedenfalls,
wenn er das so wie ich zu Ende denkt - und im Prinzip wäre das eigentlich
auch egal...).
Aber kurz: Namen sind doch nur Schall und Rauch.
Wenn Du bspw.
[mm] $(3,\red{4}) \in [/mm] R$ und [mm] $(\red{4},3) \in [/mm] R$
weißt, dann "klebt das [mm] $\red{4}$ [/mm] die beiden Paare zusammen und löst sich danach auf"
und das Ergebnis ist ein Element von [mm] $R\,$ [/mm] (wegen Transitivität):
"Zusammenkleben": [mm] $(3,\red{4},3)$ [/mm]
"Auflösen" (der roten Zahl): $(3,3)$ [mm] ($\in [/mm] R$).
(Allgemein: $(a, [mm] \red{b}) \in [/mm] R$ und [mm] $(\red{b},c) \in [/mm] R$:
"Zusammenkleben": [mm] $(a,\red{b},c)$ [/mm]
"Auflösen" (der roten Zahl): $(a,c)$ [mm] ($\in [/mm] R$).
Das ist der Inhalt von "Transitivität"!)
Also:
[mm] $(a,\red{b}) \in [/mm] R$ und [mm] $(\red{b},a) \in [/mm] R$:
"Zusammenkleben": [mm] $(a,\red{b},a)$ [/mm]
"Auflösen" (der roten Zahl): $(a,a)$ [mm] ($\in [/mm] R$).
"Zusammenkleben" bedeutet sowas wie: Lege die zwei 2-Tupel an ihrer
"Schnittstelle" übereinander und mache ein 3-Tupel draus.
"Auflösen" bedeutet dann: Entferne aus dem 3-Tupel die "Schnittstelle"
(also den mittleren Eintrag) und mache wieder ein 2-Tupel draus.
Gruß,
Marcel
|
|
|
|
