Korrektheit von Relationseigenschaften (reflexiv, symmetrisch, transitiv…) begründen auf einer Menge A mit |A|=n?

Question

Seien A eine Menge mit |A| = n und R, R₁ und R₂ Relationen auf A.

Jetzt soll ich die Korrektheit von den folgenden Aussagen bestimmen/begründen und eventuelle Gegenbeispiele angeben. Aber ich kann mit der Aufgabe nichts anfangen.

a) Wenn |R| ≥ n, dann ist R reflexiv.
b) Wenn R₁ ⊆ R₂, gilt:
i) R₁ reflexiv => R₂ reflexiv
ii) R₁ symmetrisch => R₂ symmetrisch
iii) R₁ antisymmetrisch=> R₂ antisymmetrisch
iv) R₁ transitiv => R₂ transitiv
c) Wenn R eine Äquivalenzrelation ist, dann gilt n ≤ |R| ≤ n².

Ich bin am verzweifeln :-(

Answer 1

 

Beachte die Definitionen hier: https://de.wikipedia.org/wiki/Äquivalenzrelation#Definition_einer_.C3.84quivalenzrelation

https://de.wikipedia.org/wiki/Antisymmetrische_Relation

Seien A eine Menge mit |A| = n und R, R₁ und R₂ Relationen 
auf A. Annahme 'auf' bedeutet surjektiv.

Jetzt soll ich die Korrektheit von den folgenden Aussagen bestimmen/begründen und eventuelle Gegenbeispiele angeben. Aber ich kann mit der Aufgabe nichts anfangen.

a) Wenn |R| ≥ n, dann ist R reflexiv. 

Falsch.

Sei A:={1,2} und R := {(1-->2), (2-->1)} nun ist |R| = 2≥2 aber 1R1 gilt nicht.

b) Wenn R₁ ⊆ R₂, gilt: 
i) R₁ reflexiv => R₂ reflexiv 

Richtig.

Sei m in A. Da R1 reflexiv gilt mR1m. Da R1 ⊂ R2. Gilt auch mR2m qed reflexiv in R2
ii) R₁ symmetrisch => R₂ symmetrisch 

Falsch.

Sei A:={1,2} und R1 := {(1-->1), (2-->2)}  und R2 := {(1-->2), (2-->2),(1-->1)}. R1 ⊂ R2 aber 2R₂1 ist falsch obschon 1R₂2 stimmt.

Vielleicht kannst du's ab hier ja nun selbst. Es kann sein, dass du A noch etwas vergrössern musst.

iii) R₁ antisymmetrisch=> R₂ antisymmetrisch 

Keine Vermutung.
iv) R₁ transitiv => R₂ transitiv 

Vermutung: Falsch. Man kann durchaus eine Zuordnung ergänzen, die dann die Transitivität zerstört.
c) Wenn R eine Äquivalenzrelation ist, dann gilt n ≤ |R| ≤ n².

Wenn das Wort 'auf' surjektiv impliziert, ist n ≤ |R| trivial. Da jedes Element der Zielmenge A mindestens zu einem Element von A zugeordnet sein muss. Zwischen 2 Elementen von A kann es höchstens einen Zuordnungspfeil geben. Deshalb ist n*n eine obere Grenze für |R|