Reflexivität, Symmetrie, Transitivität zeigen/widerlegen

Neue Frage »

19.04.2005, 12:56	bartleby81	Auf diesen Beitrag antworten »
Reflexivität, Symmetrie, Transitivität von binären Relationen Hallo ich habe da mal eine Frage: Ich soll für folgende binäre Relation beweisen, dass Reflexivität, Symmetrie und Transitivität gilt, bzw. nicht gilt. In $\begin{eqnarray} \mathbb N \end{eqnarray}$ sei die binäre Relation $\begin{eqnarray} R = {(a,b)\|\exists k,l \in \mathbb N : a=2^{k} \wedge b=2^{l}} \end{eqnarray}$ erklärt. Für die Reflexivität habe ich folgendes: Um reflexiv zu sein müssen alle (a,a) Teil der Relation sein. Ein Gegenbeispiel dafür, dass die Reflexivität nicht gilt ist z.B. (3,3), da kein $\begin{eqnarray} k \in \mathbb N \end{eqnarray}$ mit $\begin{eqnarray} 2^{k}=3 \end{eqnarray}$ . Etwas was nicht gilt an einem Gegenbeispiel zu erklären leuchtet mir ja ein. Nur wie sieht man sowas oder wie kommt man auf solch ein Gegenbeispiel? Und noch wichtiger wäre die Frage, wie schreibe, beweise ich etwas was für alle gilt? Gibts da bestimmte Vorgaben wie sowas auszusehen hat? Zum Beispiel würde es mich mal für die Symmetrie und Transitivität interessieren, da die beiden ja für die Relation gelten. Würde mich über eine Antwort freuen.
19.04.2005, 14:28	Mathespezialschüler	Auf diesen Beitrag antworten »
Geteilt Bitte für ein neues Thema auch einen neuen Thread aufmachen! Siehe Userguide.
19.04.2005, 16:52	flixgott	Auf diesen Beitrag antworten »
deine vermutung mit dem gegenbeispiel zur widerlegung der reflexivität ist richtig. schau dir einfach die relation an und stell vermutungen auf. wenn es gegenbeispiele gibt sind die meist schnell zu finden. ansonsten mußt du ganz formal die definitionen überprüfen: symmetrie: $\begin{eqnarray} \forall (a,b) \in R ( (b,a) \in R) \end{eqnarray}$ deine relation mal ganz formal betrachtet: $\begin{eqnarray} (a,b) \in R \leftrightarrow \exists k,l \in \mathbb N (a= 2^{k} \wedge b=2^{l}) \leftrightarrow \exists k,l \in \mathbb N (b= 2^{k} \wedge a=2^{l}) \leftrightarrow (b,a) \in R \end{eqnarray}$ somit ist bewiesen, dass symmetrie gilt (was ja intuitiv auch klar war) genauso mußt du jetzt mit der transitivität vorgehen...
19.04.2005, 17:11	bartleby81	Auf diesen Beitrag antworten »
Danke schön für die Hilfe. Aber reicht das denn nur a und b zu vertauschen? Ist das denn dann damit bewiesen für alle a,b?
19.04.2005, 17:14	flixgott	Auf diesen Beitrag antworten »
ja, a und b waren doch ganz beliebig, das einzige was vorrausgesetzt war, ist, dass sie in relation zu einander stehen! der trick hier bei ist eigentlich, dass immer folgendes gilt: $\begin{eqnarray} a \wedge b \leftrightarrow b \wedge a \end{eqnarray}$ wobei a und b beliebige aussagen sind. ähnlich ansatz für die transitivität: $\begin{eqnarray} (a \wedge b ) \wedge (b \wedge c) \rightarrow a \wedge c \end{eqnarray}$
19.04.2005, 17:21	bartleby81	Auf diesen Beitrag antworten »
Ja die Ansätze waren mir bekannt. Wusste nur nicht das man das "für alle" so einfach beweisen kann. Da werde ich gleich mal die Transitivität versuchen.
Anzeige

19.04.2005, 17:38	bartleby81	Auf diesen Beitrag antworten »
So hier wäre mein Ansatz für die Transitivität: $\begin{eqnarray} (a,b,c) \in R\leftrightarrow \exists k,l \in \mathbb N (a=2^{k} \wedge b= 2^{l})\leftrightarrow \exists l,m \in \mathbb N (b=2^{l} \wedge c=2^{m})\leftrightarrow \exists k,m \in \mathbb N (a=2^{k} \wedge c=2^{m}) \end{eqnarray}$ Ist das richtig?
19.04.2005, 17:44	flixgott	Auf diesen Beitrag antworten »
nee, leider nicht, denn deine relation ist nur zweistellig! $\begin{eqnarray} (a,b) \in R \wedge (b,c) \in R \leftrightarrow \exists k,l \in N (a= 2^{k} \wedge b=2^{l}) \leftrightarrow \exists l,m \in N (b= 2^{l} \wedge c=2^{m}) \end{eqnarray}$ $\begin{eqnarray} \rightarrow \exists k,m \in N (a= 2^{k} \wedge c=2^{m}) \leftrightarrow (a,c) \in R \end{eqnarray}$ also dein grundgedanke war schon richtig!!
19.04.2005, 17:52	bartleby81	Auf diesen Beitrag antworten »
Verstehe, macht auch irgendwie mehr Sinn. Und ich kann wirklich so einfach da ein c und ein m hinzufügen, je nachdem wie ich es brauche? Na da sieht das ganze ja gar nicht so schwierig aus. Hoffe ich finde noch ein paar Beispiele wo ich das üben kann. Und für einen Gegenbeweis gibt es ja leider kein Patentrezept. Ich hoffe ich sehe es in Zukunft, wenn es eins gibt. Vielen Dank nochmal. Hat mir wirklich sehr geholfen.
19.04.2005, 17:55	flixgott	Auf diesen Beitrag antworten »
naja entweder gegenbespiel finden oder bei einer dieser assoziationsketten einen widerspruch finden.. untersuch mal folgendes für die ganzen zahlen: $\begin{eqnarray} (a,b) \in R \leftrightarrow a \leq b \end{eqnarray}$
19.04.2005, 18:16	bartleby81	Auf diesen Beitrag antworten »
So dafür habe ich folgende Vorschläge: Die Relation ist erstmal reflexiv und transitiv, jedoch nicht symmetrisch. Reflexivität: $\begin{eqnarray} (a,a) \in R (a=a) \end{eqnarray}$ (Jede Zahl ist gleich sich selbst) Symmetrie: $\begin{eqnarray} (a,b) \in R (a\leq b \neq b\leq a) \end{eqnarray}$ Bsp.: $\begin{eqnarray} (1,2) \in R (1\leq 2 \neq 2\leq 1) \end{eqnarray}$ Transitivität: $\begin{eqnarray} (a,b) \in R (a\leq b) \leftrightarrow (b\leq c) \leftrightarrow (a\leq c) \leftrightarrow (a,c) \in R \end{eqnarray}$ Ich hoffe doch ich liege so ungefähr richtig.
19.04.2005, 18:19	flixgott	Auf diesen Beitrag antworten »
eigentlich schon, nur es hapert wieder ein bischen an der notation: bei der symmetrie ist das ungleich zeichen nicht so günstig, ehr besser währe ein durchgestrichener doppelpfeil. bei der transitivität mußt du davon ausgehen: $\begin{eqnarray} (a,b) \in R \wedge (b,c) \in R \leftrightarrow ... \end{eqnarray}$ (deine aussage ist einfach logisch nicht ganz korrekt nur weil a<b ist muß noch lange nicht für ein beliebiges, nicht näher bestimmtes c gelten, dass auch a<c ist.. du mußt auch für c entsprechende vorraussetzungen mit festhalten!)
19.04.2005, 18:30	bartleby81	Auf diesen Beitrag antworten »
Ja die Notation muss ich mir noch ein wenig aneignen. Sorry. Also bei der Symmetrie nur das $\begin{eqnarray} \neq \end{eqnarray}$ durch einen durchgestrichenen Doppelpfeil austauschen? Für die Transitivität: $\begin{eqnarray} (a,b) \in R \wedge (b,c) \in R \leftrightarrow (a\leq b \wedge b\leq c) \leftrightarrow (b\leq c \wedge a\leq c) \leftrightarrow (b,c)\in R \wedge (a,c)\in R \end{eqnarray}$
19.04.2005, 18:46	flixgott	Auf diesen Beitrag antworten »
es reicht schon: $\begin{eqnarray} (a,b) \in R \wedge (b,c) \in R \leftrightarrow (a\leq b \wedge b\leq c) \rightarrow (a \leq c) \leftrightarrow (a,c)\in R \end{eqnarray}$ denn du sollst ja nur zeigen, dass das paar (a,c) dann auch zur relation gehört! ach ja, vor das 'leftrightarrow' einfach ein n : 'nleftrightarrow'!
19.04.2005, 18:50	bartleby81	Auf diesen Beitrag antworten »
Muss das c nicht in die Klammer oder ist das so gewollt? Aha, da weiss ich ja jetzt Bescheid. Ist gar nicht so einfach mit der Notation. Naja muss ich noch bissl üben. Ich danke Dir trotzdem vielmals, hast mir sehr geholfen. Vielen Dank.
19.04.2005, 20:19	flixgott	Auf diesen Beitrag antworten »
tippfehler! schon berichtigt!

Neue Frage »

Antworten »

Reflexivität, Symmetrie, Transitivität zeigen/widerlegen

Verwandte Themen