Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Prüfung auf eine Äquivalenzrelation?

Prüfung auf eine Äquivalenzrelation?

Universität / Fachhochschule

Sonstiges

Tags: Äquivalenzrelation

tommy40629 aktiv_icon

11:59 Uhr, 09.10.2015

Hi,

ich habe heute mit den Äquivalenzrelationen angefangen und bei den Definitionen für
symmetrisch und transitiv auf ein "Problem gestoßen".

Man muss doch bei diesen Definitionen alle möglichen Kombination durchgehen, so wie in der Stochastik, oder????

Wenn wir die Geburtstage aller Menschen in der BDR nehmen, wobei uns nur Tag und Monat wichtig ist, dann ist das eine Äquivalenzrelation.

Sei M={alle Menschen in der BRD}
In der Menge N sind alle Menschen von 1 bis n durchnummeriert.
N={1,2,...,n} Gleichzeitig ist jeder Zahl aus N das Geburtsdatum zugeordnet.
Ich mache das jetzt nicht formal!!

Die Relation R ist dann R=

{(a, b) \in N \times N :

a hat am gleichen Tag wie b Geburtstag

}

R ist dann eine Äquivalenzrelation, weil

Weil R reflexiv

\forall a \in N (a R a)

ist.

Weil R symmetrisch

\forall a, b \in N (a R b \to b R a)

ist.

Weil R transitiv

\forall a, b, c \in N (a R b \land b R c \to a R c)

ist.

Ich habe dabei aber dieses Problem:
-------------------------------------

symmetrisch

\forall a, b \in N (a R b \to b R a)

Wir haben ja Paare (a,b) aus der Menge N haben und die Menge N hat n-Elemente,
da haben wir doch für das Paar (a,b)

n * n = n^{2}

viele Möglichkeiten

Klar ist, dass die Symmetrie für alle Paare gilt, wo

a = b

gilt.

Was ist aber mit den Paaren, für die gilt, dass "a nicht wie b Geburtstag hat"?

z.B. (1.1.,20.1.) das ist falsch die Implikation bei

\forall a, b \in N (a R b \to b R a)

ist dann aber wahr. Also gilt die Symmetrie.

Ähnlich bei der Transitivität:

\forall a, b, c \in N (a R b \land b R c \to a R c)

Hier haben wir Paare (a,b), (b,c) und (a,c)
Für jedes Paar gibt es

n^{2}

-viele Möglichkeiten

Betrachten wir hier auch einfach nur die Implikation zusammen mit diesen vielen Möglichkeiten???

a R b \land b R c \to a R c

Diese Implikation ist ja nur falsch, wenn die Situation:

"aus WAHR folgt FALSCH" eintritt.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

12:04 Uhr, 09.10.2015

Und wo siehst Du ein Problem? Es gibt

n^{2}

Paare, und? Gefällt Dir

n^{2}

rein ästhetisch nicht? :-)

tommy40629 aktiv_icon

12:08 Uhr, 09.10.2015

Liege ich richtig, wenn ich sage, dass ich alle diese n² Möglichkeiten prüfen muss?

DrBoogie aktiv_icon

12:13 Uhr, 09.10.2015

Wozu willst Du sie prüfen? Und was verstehst Du überhaupt unter "prüfen"?

Hier ein einfacheres Beispiel für Dich:

a = b

(gewöhnliche Gleichheit) ist eine Äquivalenzrelation auf natürlichen Zahlen. Es gibt hier nicht

n^{2}

Paare, sondern unendlich viele:

(n, m)

, wobei

n

und

m

beliebige natürlich Zahlen sein können.
Würdest Du hier auch für alle Paare

(n, m)

prüfen wollen, ob

n = m

gilt? :-)

tommy40629 aktiv_icon

12:18 Uhr, 09.10.2015

Nein, würde ich nicht prüfen wollen.

z.B. bei der Symmetrie:

\forall a, b \in N (a R b \to b R a)

Das gilt ja für Paare, wo a=b gilt und Paare, wo die Relationsbedingung erfüllt ist.
"a hat wie b Geburtstag, also am selben Datum."

Was ist aber mit Paaren, wo gilt "a hat nicht wie b Geburtstag"

Bei diesen Paaren ist doch der Vordersatz der Implikation

\forall a, b \in N (a R b \to b R a)

falsch, also die Implikation wahr.

Die Bedingung "symmetrisch" gilt dann ja auch für diese Paare.

Rein logisch gesehen ist es eine wahre Aussage.

Sehe ich das richtig??

DrBoogie aktiv_icon

12:30 Uhr, 09.10.2015

"Die Bedingung "symmetrisch" gilt dann ja auch für diese Paare."

Es gibt keine Bedingung "symmetrisch" für einzelne Paare. Symmetrisch kann nur Relation an sich sein, für Paare ist dieser Begriff nicht definiert.

"Rein logisch gesehen ist es eine wahre Aussage."

Ja, das ist eine wahre Aussage. Und?

tommy40629 aktiv_icon

12:34 Uhr, 09.10.2015

Hier ist ein Beispiel, wegen dem bin ich auch auf meine Frage gekommen:

P={1,2,3,4,5,6,7}
Wer hat wann Geburtstag:
1=1.1.
2=10.2.
3=4.5.
4=1.1.
5=10.2.
6=1.1.
7=4.5.

Relation B
B={(p,q)∈ P×P: p und q haben an gleichen Tag Geburtstag}.

\forall x \in P (x B x)

ja ist reflexiv

\forall x, y \in P (x B y \Rightarrow y B x)

(1,4)=>(4,1)
(2,5)=>(5,2)
(3,7)=>(7,3)
Beim Rest ist der Vordersatz falsch, aber die Implikation wahr.
Also auch symmetrisch.

\forall x, y, z \in P (x B y \land y B z \Rightarrow x B z)

Gilt für alle gleichen Paare.
Wir betrachten nun: x≠y,x≠z
(1,4)&(4,6)=>(1,6)

Was ist aber z.B. mit (1,2) & (2,5)=>(1,5) Der Vordersatz ist falsch, also können wir wieder alles folgern, die Implikation ist wahr.

Die Möglichkeit "wahr folgt falsch" ist hier nicht möglich.
Also transitiv.

tommy40629 aktiv_icon

12:47 Uhr, 09.10.2015

Man kann die Frage auch anders stellen:

Eine Menge R auf einer Menge A, ist eine Äquivalenzrelation, wenn gilt:

\forall x \in A (x R x)

\forall x, y \in A (x R y \Rightarrow y R x)

\forall x, y, z \in A (x R y \land y R z \Rightarrow x R z)

Wenn wir diese 3 Bedingungen, was ja Allaussagen sind prüfen, dann darf deren Verneinung nicht wahr sein:

\exists x \in P (\neg (x B x))

\exists x, y \in P (x B y \land \neg (y B x))

\exists x, y, z \in P (x B y \land y B z \land \neg (x B z))

Das prüfen wir einfach nach den Regeln der Aussagen- und Prädikatenlogik.

Trifft eine der Existenzaussagen zu, dann war es das mit der Äquivalenzrelation.

Wenn jetzt hier kein Fehler zu sehen ist, dann bin ich zufrieden.

DrBoogie aktiv_icon

12:47 Uhr, 09.10.2015

Und ich verstehe die Frage immer noch nicht.
Du hast jetzt sehr streng die ziemlich offensichtliche Tatsache bewiesen, dass "gleichen Geburtstag zu haben" eine Äquivalenzrelation ist.
Gut, wo ist das Problem?

Kannst Du Dich immer noch nicht damit abfinden, dass (FALSCH => WAHR) eine wahre Implikation ist? ;-)
Genau an diesem Beispiel sieht man eigentlich, warum das so ist.
Denn ohne formale Logik ist die Symmetrie-Eigenschaft einer Äquivalenzrelation so formuliert: wenn "

a \sim b

WAHR" ist, dann ist auch "

b \sim

WAHR". Die Variante "

a \sim b

FALSCH" wird gar nicht betrachtet. Wenn wir aber diese Aussage in der formalen Logik schreiben, können wir einfach

a \sim b = > b \sim a

schreiben, was eine einfachere Aussage ist als "wenn "

a \sim b

WAHR" ist, dann ist auch "

b \sim

WAHR", aber zu ihr äquivalent, eben weil (FALSCH => WAHR) immer WAHR ist. Damit muss man die falschen Prämisse überhaupt nicht "prüfen", nur die wahren.

DrBoogie aktiv_icon

12:49 Uhr, 09.10.2015

"Das prüfen wir einfach nach den Regeln der Aussagen- und Prädikatenlogik.

Trifft eine der Existenzaussagen zu, dann war es das mit der Äquivalenzrelation."

Ja, das kann man so machen.

tommy40629 aktiv_icon

12:52 Uhr, 09.10.2015

Das hilft mir sehr.

Und es war wirklich gut, dass ich mit Dir darüber "sprechen" konnte.

Es war mir unklar, weil das Problem "Alltagslogik" und Logik vermengt habe.

Noch mal Danke!

1258005

1257991

	Status: nicht eingeloggt	Noch nicht registriert?