Partielle Ordnung

30.10.2012, 23:13

chillerStudent

Partielle Ordnung

Hallo,

ich muss beweisen, dass T eine partielle Ordnung ist. T ist wie folgt definiert:

$\begin{eqnarray*} T\subset \mathbb N X \mathbb N \end{eqnarray*}$ auf $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ durch die Vorschrift:
Für x,y aus N gilt xTy gdw ein a aus N mit xa=y exis. Wenn xTy gilt, dann nennt man y ein Vielf. von x bzw. einen Teiler von y.

Meine Ideen:
Aso ich weiß, dass ein Relation nur dann eine part. Ordnung heißt, wenn sie reflexiv und transitiv ist aber nicht sysmmetrisch.

Wie finde ich heraus, T reflexiv und transitiv ist?

30.10.2012, 23:26

Leopold

Auf diesen Beitrag antworten »

In der Zahlentheorie schreibt man statt $\begin{eqnarray*} T \end{eqnarray*}$ einen senkrechten Schritt und liest ihn als "teilt":

$\begin{eqnarray*} 3 \, | \, 12 \end{eqnarray*}$ liest man so: "3 teilt 12" (oder "3 ist ein Teiler von 12" oder "12 ist ein Vielfaches von 3")

$\begin{eqnarray*} 3 \, | \, 12 \ \text{und} \ 12 \, | \, 48 \, , \ \text{also} \ 3 \, | \, 48 \end{eqnarray*}$

Das gilt immer. Also ist die Teilbarkeitsrelation transitiv. (Das mußt du natürlich abstrakt nachweisen, ein Beispiel genügt nicht.)

Daß sie nicht symmetrisch ist, ist offensichtlich: $\begin{eqnarray*} 15 \, | \, 45 \, , \ 45 \not | \, 15 \end{eqnarray*}$

30.10.2012, 23:37

chillerStudent

Auf diesen Beitrag antworten »

Das ist echt schwer. Ich glaub ich hab noch nie etwas ohne Zahlen bewiesen.
Kannst du mir ein Beispiel für einen Beweis geben?

30.10.2012, 23:45

Leopold

Auf diesen Beitrag antworten »

Transitivität:

Du mußt in

WENN
x Teiler von y ist und y Teiler von z ist

DANN
ist x Teiler von z

die Relationen nur durch Gleichungen zum Ausdruck bringen:

"x Teiler von y" heißt: y = ax mit einem geeigneten a
"y Teiler von z" heißt: ...

Und wie folgt nun der DANN-Teil?

30.10.2012, 23:50

chillerStudent

Auf diesen Beitrag antworten »

DannTeil:

z=ay ?

30.10.2012, 23:56

Leopold

Auf diesen Beitrag antworten »

Ja und nein. Es muß ja nicht das $\begin{eqnarray*} a \end{eqnarray*}$ von eben sein.

Beispiel:

$\begin{eqnarray*} 3 | 12 \end{eqnarray*}$ , denn $\begin{eqnarray*} 12 = 4 \cdot 3 \end{eqnarray*}$

Hier ist also $\begin{eqnarray*} a=4 \end{eqnarray*}$ .

$\begin{eqnarray*} 12 | 60 \end{eqnarray*}$ , denn $\begin{eqnarray*} 60 = 5 \cdot 12 \end{eqnarray*}$

Hier ist also - na, $\begin{eqnarray*} a \end{eqnarray*}$ darf man jetzt nicht sagen (wir sind in derselben Gültigkeitsumgebung), denn das war ja $\begin{eqnarray*} 4 \end{eqnarray*}$ , wir brauchen aber $\begin{eqnarray*} 5 \end{eqnarray*}$ , also einen neuen Buchstaben.

30.10.2012, 23:57

chillerStudent

Auf diesen Beitrag antworten »

z=ky?

Edit:

heißt das, dass x= nz ist ? n aus N

31.10.2012, 00:00

Leopold

Auf diesen Beitrag antworten »

Ich hätte $\begin{eqnarray*} b \end{eqnarray*}$ genommen. Aber (seufz!) wenn dir $\begin{eqnarray*} k \end{eqnarray*}$ lieber ist, soll's so sein ...

Wie folgt aus

$\begin{eqnarray*} y = a x \ \ \text{und} \ \ z = k y \end{eqnarray*}$

nun der gesuchte Zusammenhang zwischen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} z \end{eqnarray*}$ ?

31.10.2012, 00:03

chillerStudent

Auf diesen Beitrag antworten »

Zitat:

heißt das, dass x= nz ist ? n aus N

31.10.2012, 00:06

Leopold

Auf diesen Beitrag antworten »

Das paßt doch überhaupt nicht! Wer soll Teiler von wem sein? Schau dir nochmal das Beispiel an:

Aus $\begin{eqnarray*} 3 | 12 \end{eqnarray*}$ und $\begin{eqnarray*} 12 | 60 \end{eqnarray*}$ , folgt: ....

"Transitivität" heißt "Hinübergang". Eine Beziehung pflanzt sich über ein Zwischenglied fort.

Und dann mußt du das ja beweisen (!!!).

31.10.2012, 00:16

chillerStudent

Auf diesen Beitrag antworten »

Ich verliere langsam die Motivation. Zu spät? Sehr wahrscheinlich.

Mit dem Zahlen beispiel komme ich klar aber ich kanns nicht allgemein aufschreiben.

31.10.2012, 00:22

Leopold

Auf diesen Beitrag antworten »

Du hast zwei Voraussetzungen:

$\begin{eqnarray*} \text{(1)} \ x | y \, , \ \ \text{(2)} \ y | z \end{eqnarray*}$

und die bedeuten ausgeschrieben: $\begin{eqnarray*} y = ax \, , \ \ z = ky \end{eqnarray*}$

Und du hast eine Behauptung:

$\begin{eqnarray*} x | z \end{eqnarray*}$

Aber die mußt du jetzt beweisen. Du kannst also nicht einfach schreiben: $\begin{eqnarray*} z = nx \end{eqnarray*}$ (so herum wäre es richtig), sondern mußt hier zeigen, daß es so ein $\begin{eqnarray*} n \end{eqnarray*}$ gibt. Das mußtest du oben bei $\begin{eqnarray*} \text{(1),(2)} \end{eqnarray*}$ nicht beweisen, denn dort war es vorausgesetzt!

Am Zahlenbeispiel kannst du übrigens schön nachempfinden, wie man das gesuchte $\begin{eqnarray*} n \end{eqnarray*}$ aus den anderen Zahlen erhält.

31.10.2012, 00:28

chillerStudent

Auf diesen Beitrag antworten »

Danke dir bis hier hin. Kann nicht mehr. Bis morgen wenn noch Lust und Zeit mitspielen.

31.10.2012, 00:30

Leopold

Auf diesen Beitrag antworten »

Und hier der einzeilige Beweis:

Aus $\begin{eqnarray*} x|y \end{eqnarray*}$ , also $\begin{eqnarray*} y=ax \end{eqnarray*}$ , und $\begin{eqnarray*} y|z \end{eqnarray*}$ , also $\begin{eqnarray*} z=ky \end{eqnarray*}$ , folgt:

$\begin{eqnarray*} z=ky=k(ax)=\underbrace{(ka)}_n x \end{eqnarray*}$ , d.h. $\begin{eqnarray*} x|z \end{eqnarray*}$ .

Damit ist gezeigt: Die Teilbarkeitsrelation ist transitiv.

Neue Frage »

Antworten »

Partielle Ordnung

Verwandte Themen