Difference between revisions of "TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 441"

From VoWi
Jump to navigation Jump to search
 
Line 51: Line 51:
 
Da <math> m \in \R </math> ist auch <math> (m+1) \in \R </math>. Daraus ergibt sich der Widerspruch <math> \mathrm{min}(m + 1, m) = m</math>
 
Da <math> m \in \R </math> ist auch <math> (m+1) \in \R </math>. Daraus ergibt sich der Widerspruch <math> \mathrm{min}(m + 1, m) = m</math>
  
Also handelt es sich um keine Boolesche Algebra!
+
Also handelt es sich um keine Boolesche Algebra!<br><br>
 +
 
 +
== Lösungsvorschlag für b) von neo ==
 +
Dass <math>(\mathbb{N}\setminus\{0\},ggT,kgV\})</math> ein Verband ist, beweist man genauso wie oben mit der Idee von Leibniz.<br><br>
 +
<math>aRb\Leftrightarrow a \leq b</math>...Totalordnung auf <math>\mathbb{R}</math>, also auch auf <math>\mathbb{N}\setminus\{0\}</math>, da <math>\mathbb{N}\setminus\{0\} \subseteq \mathbb{R}</math><br>
 +
<math>\forall a,b \in \mathbb{N}\setminus\{0\}: ggT(a,b) \leq kgV(a,b)</math><br>
 +
<math>a \land b = ggT(a,b) = inf(a,b)</math><br>
 +
<math>a \lor b = kgV(a,b) = sup(a,b)</math><br>
 +
<math>\Rightarrow (\mathbb{N}\{0\},ggT,kgV)\,\,\widehat{=}\,\,Verband</math><br><br>
 +
 
 +
Nun folgt der Beweis der Distributivität, welcher ein wenig Hintergrundinfo bedarf (genaueres im orangen Buch 4.Auflage Seite 19):<br>
 +
Wenn für eine Primzahl <math>p \in \mathbb{P}</math> gilt <math>p^k|a</math>, so schreibt man:<math>k=v_p(a)</math><br>
 +
Des Weiteren lassen sich ggT bzw. kgV folgendermaßen darstellen:<br><br>
 +
<math>ggT(a,b)=\prod_{p\in\mathbb{P}}{p^{min\{v_p(a),v_p(b)\}}}</math><br>
 +
<math>kgV(a,b)=\prod_{p\in\mathbb{P}}{p^{max\{v_p(a),v_p(b)\}}}</math><br><br>
 +
Wir müssen beweisen:<br>
 +
<math>a \land (b \lor c) = (a \land b) \lor (a \land c)</math><br>
 +
<math>ggT(a,kgV(b,c) = kgV(ggT(a,b),ggT(a,c))</math><br><br>
 +
Da sich ggT bzw. kgV nur bei den Potenzen von <math>p</math> unterscheiden (<math>p^a*p^b=p^{a+b}</math>), kann man schreiben:<br>
 +
<math>x=v_p(a),y=v_p(b),z=v_p(c)</math> und es gelte: <math>x\leq y\leq z</math><br>
 +
<math>min(x,max(y,z)) = max(min(x,y),min(x,z))</math><br>
 +
<math>min(x,z)=max(x,x)</math><br>
 +
<math>x=x \,\,\Rightarrow distributiv</math><br>
 +
Da weder ggT noch kgV ein neutrales Element besitzen, ist <math>(\mathbb{N}\setminus\{0\},ggT,kgV)</math> ein distributiver Verband.
  
 
== Links ==
 
== Links ==

Latest revision as of 21:07, 31 July 2020

Nur teilweise gelöst: b) ist ungelöst.

Man zeige, dass die folgenden algebraischen Strukturen Verbände sind. Welche sind außerdem distributiv, und welche sind Boolesche Algebren

a)  (\R, \mathrm{min}, \mathrm{max})

b)  (\N \setminus \{0\}, \mathrm{ggT}, \mathrm{kgV})

Hilfreiches[edit]

Verband äquivalent Halbordnung
Verband äquivalent Halbordnung[edit]

Satz (Idee von Leibniz):

Nach einer Idee von Leibniz kann man einen Verband  (M,\wedge, \vee) auch als eine Halbordnung darstellen (und umgekehrt). Zwischen dem Verband und der Halbordnung muss dann folgende Beziehung bestehen:

 a \leq b \quad \iff \quad a = a \wedge b \quad \iff \quad b = a \vee b \quad

Anders ausgedrückt:

 \mathrm{inf}(a,b) \iff a \wedge b \qquad \mathrm{sup}(a,b) \iff a \vee b

Lösungsvorschlag für a) von Piri[edit]

Verband?

Bekanntlicher Weise bildet \R mit der Relation  aRb \Longleftrightarrow a \leq b eine Totalordnung. Da

\mathrm{inf}(a,b) \iff \mathrm{min}(a,b) \qquad  \mathrm{sup}(a,b) \iff \mathrm{max}(a,b)

gilt folgt daraus, dass es sich um einen Verband handelt.

Distributiver Verband?

Damit der Verband distributiv ist müssen

1.  \mathrm{min}(a, \mathrm{max}(b,c)) = \mathrm{max}(\mathrm{min}(a,b), \mathrm{min}(a,c))

2.  \mathrm{max}(a, \mathrm{min}(b,c)) = \mathrm{min}(\mathrm{max}(a,b), \mathrm{max}(a,c))

gezeigt werden. Um das zu zeigen können wir einfach naiv für alle Permutationen von  a \leq b \leq c in die Formeln einsetzen. Da aber die Rollen von b und c vertauschbar sind kann man es von 6 auf 3 Permutationen reduzieren:

1.  a \leq b \leq c

2.  b \leq a \leq c

3.  b \leq c \leq a

Nun setzt man für die 3 Permutationen in die Formeln ein und sieht, dass die Distributivgesetze für alle Permutationen gelten. Daraus folgt, dass es sich um einen distributiven Verband handelt.

Anmerkung 1: Es reicht eigentlich nur 1. Distributivgesetz zu zeigen, das andere folgt daraus. Wir haben den Beweis meines Wissens nach nicht in der Vorlesung geführt, er findet sich aber auf Wikipedia wieder.

Anmerkung 2: Laut Wikipedia ist jede total geordnete Menge ein distributiver Verband, mir fehlt jedoch der Beweis deswegen habe ich das in meiner Lösung nicht verwendet.

Boolesche Algebra?

Damit es sich um eine Boolesche Algebra handelt muss es ein 1-Element bzgl. \mathrm{min} geben. Das es kein 1-Element geben kann lässt sich schnell zeigen:

Nehmen wir an es gibt ein 1-Element m \in \R. D.h. es muss  \mathrm{min}(a,m) = a gelten.

Da  m \in \R ist auch  (m+1) \in \R . Daraus ergibt sich der Widerspruch  \mathrm{min}(m + 1, m) = m

Also handelt es sich um keine Boolesche Algebra!

Lösungsvorschlag für b) von neo[edit]

Dass (\mathbb{N}\setminus\{0\},ggT,kgV\}) ein Verband ist, beweist man genauso wie oben mit der Idee von Leibniz.

aRb\Leftrightarrow a \leq b...Totalordnung auf \mathbb{R}, also auch auf \mathbb{N}\setminus\{0\}, da \mathbb{N}\setminus\{0\} \subseteq \mathbb{R}
\forall a,b \in \mathbb{N}\setminus\{0\}: ggT(a,b) \leq kgV(a,b)
a \land b = ggT(a,b) = inf(a,b)
a \lor b = kgV(a,b) = sup(a,b)
\Rightarrow (\mathbb{N}\{0\},ggT,kgV)\,\,\widehat{=}\,\,Verband

Nun folgt der Beweis der Distributivität, welcher ein wenig Hintergrundinfo bedarf (genaueres im orangen Buch 4.Auflage Seite 19):
Wenn für eine Primzahl p \in \mathbb{P} gilt p^k|a, so schreibt man:k=v_p(a)
Des Weiteren lassen sich ggT bzw. kgV folgendermaßen darstellen:

ggT(a,b)=\prod_{p\in\mathbb{P}}{p^{min\{v_p(a),v_p(b)\}}}
kgV(a,b)=\prod_{p\in\mathbb{P}}{p^{max\{v_p(a),v_p(b)\}}}

Wir müssen beweisen:
a \land (b \lor c) = (a \land b) \lor (a \land c)
ggT(a,kgV(b,c) = kgV(ggT(a,b),ggT(a,c))

Da sich ggT bzw. kgV nur bei den Potenzen von p unterscheiden (p^a*p^b=p^{a+b}), kann man schreiben:
x=v_p(a),y=v_p(b),z=v_p(c) und es gelte: x\leq y\leq z
min(x,max(y,z)) = max(min(x,y),min(x,z))
min(x,z)=max(x,x)
x=x \,\,\Rightarrow distributiv
Da weder ggT noch kgV ein neutrales Element besitzen, ist (\mathbb{N}\setminus\{0\},ggT,kgV) ein distributiver Verband.

Links[edit]

Verband