Beweis von R*

Aufrufe: 992     Aktiv: 27.06.2019 um 19:40

0

Hallo,

anbei eine neue Uni-Aufgabe. 

Beweisen Sie: ist R ⊆ A×A eine endliche Relation mit genau n geordneten Paaren, so ist auch R+ endlich und hat höchstens n hoch 2 geordnete Paare. Ist mit R auch stets R∗ endlich?

Meine Überlegung ist, dass R auch stets R* endlich ist, weil ich die reflexive Hülle dazu kommt und, wenn die Relation endlich ist, dass ist R* endlich. Wie kann ich es aber am Besten beweisen? Ich habe mir gedacht, ein Beispiel mit Zahlen zu geben, zB A :={1,2,3,4} und daraus die geordneten Paare zunächst zu bilden, danach die transitive Hülle und anschließend die R*.

Danke für Eure Hinweise.

Beste Grüße

Eva

Diese Frage melden
gefragt

Student, Punkte: 50

 

Hallo,

ich entnehme deiner andere Frage das R+ die transitive und R* die reflexiv-transitive Hülle ist ?

Grüße Christian
  ─   christian_strack 25.06.2019 um 02:54

Ja, genau!
Ich habe als Menge A = {1,2,3,4} genommen und geordnete Paare (1,2), (2,3), (3,4)
Ich würde sagen, dass R+ = (1,2), (2,3), (3,4), (1,3), (1,4), (2,4) endlich
R* = (1,2), (2,3), (3,4), (1,3), (1,4), (2,4), (1,1), (2,2), (3,3), (4,4) auch endlich
Oder sind meine Überlegungen total daneben?
Danke und beste Grüße
Eva
  ─   evatsigkana 25.06.2019 um 09:14
Kommentar schreiben
1 Antwort
0

Hallo,

in deinem Beispiel stimmt das natürlich, aber du sollst es ja allgemein zeigen. Wenn du als \(A\) einfach die gesamten natürlichen Zahlen \(\mathbb{N}\) nimmst, kriegst du größte Probleme beim Bilden der reflexiven Hülle bezüglich Endlichkeit! ;)

Dass die transitive Hülle trotzdem endlich ist, ist relativ klar, denn wenn \(R\) endlich ist, also \(|R|=n\) für ein beliebiges \(n\in\mathbb{N}\) gilt, dann können sowieso nur \(2n\) "Zahlen" (wir nehmen hier mal Zahlen als Elemente von \(A\) an) in deiner Relation enthalten sein, jeweils eine vorne und eine hinten in insgesamt \(n\) Paaren der Form \((a,b)\). Wenn du aber \(2n\) verschiedene Zahlen nimmst, dann kommt nix neues dazu, weil du nirgends "kleben" kannst, du hast ja keine gleichen Zahlen. 

"Schlimmer" wird es, wenn du viel kleben kannst, aber eben auch viel fehlt, zum Beispiel:
$$R=\{(1,2),(2,3),(3,4),(4,5),...(n,n+1)\}$$

In diesem Fall bekommst du \(n\) Paare, in denen die \(1\) vorne steht, \(n-1\) viele, in denen die \(2\) vorne steht und so weiter bis \(n\) vorne steht, da hast du nach wie vor nur \(1\). Das macht also insgesamt:

$$\sum_{k=1}^{n}k=\frac{n(n+1)}{2}=\frac{n^2+n}{2}$$

Für diesen Fall bleibst du also immer unterhalb von \(n^2\), weil \(n^2\geq n\) gilt, wenn \(n\geq1\) ist. 

Genau kannst du es wahrscheinlich mit Induktion über die Anzahl der Elemente machen! :)

Diese Antwort melden
geantwortet

Student, Punkte: 2.6K

 

Hallo endlich verstanden,

super, tolle Antwort! Danke sehr! Wenn so was in Klausur kommt, werde ich versuchen, mit einem konkreten Beispiel es zu lösen und hoffen, dass es reicht.. Ich bin noch Anfängerin und mir fehlt die Übung.
DANKE vielmals für die großartige Hilfe.
Eva
  ─   evatsigkana 25.06.2019 um 19:48

Kommentar schreiben