Arbeitsgruppe Rechnergestützte Programmentwicklung

OVSS16-Serie04-Lsg.tex

\documentclass[12pt]{article} \include{macros} \newcommand{\Hom}{\mathrm{Hom}} \begin{document} \header{L\"osungen zu Serie 4} {Ordnungen und Verb\"ande} {Sommersemester 2016} \begin{exercise} Sei $(V, \sqcup_V, \sqcap_V)$ ein Verband. \begin{claim} Die folgenden Aussagen sind äquivalent: \begin{enumerate} \item $V$ ist Kette. \item Es gilt die Formel $\forall\, a, b, c \in V : a = b \sqcap c \Rightarrow (a = b \vee a = c)$. \item Jeder Ordnungshomomorphismus von $V$ ist ein Verbandshomomorphismus. \end{enumerate} \end{claim} \end{exercise} \begin{proof} ``(a) $\Rightarrow$ (b)'' Es gelte, dass $V$ eine Kette ist. Seien $a, b, c \in V$ mit $a = b \sqcap c$. Da $V$ Kette ist, gilt $b \sqsubseteq c$ oder $c \sqsubseteq b$, also nach Definition der Verbandsordnung $b \sqcap c = b$ oder $c \sqcap b = c$. Wegen der Kommutativit\"at von $\sqcap$ gilt damit $a = b$ oder $a = c$. \hfill\smallskip\\ ``(b) $\Rightarrow$ (a)'': Es gelte $\forall a,b,c \in V: a = b \sqcap c \Rightarrow (a = b \vee a = c)$. Seien $b,c \in V$ und setze $a \defeq b \sqcap c$. Dann gilt: \begin{align*} & \mathbf{wahr}\\ \iff & a = b \vee a = c & \text{Voraussetzung}\\ \iff & (b \sqcap c = b) \vee (b \sqcap c = c) & \text{Setzung von $a$}\\ \iff & b \sqsubseteq c \vee c \sqsubseteq b\ . \end{align*} Also sind $b, c$ vergleichbar und damit $V$ eine Kette. \hfill\smallskip\\ ``(a) $\Rightarrow$ (c)'': Es gelte, dass $V$ eine Kette ist. Sei $V$ eine Kette und $a,b \in V$. Wir k\"onnen ohne Beschr\"ankung der Allgemeinheit annehmen, dass $a \sqsubseteq b$ gilt. Damit gilt $a \sqcap b = a$. Wegen der Monotonie von $f$ erhalten wir $f(a) \sqsubseteq f(b)$, was $f(a) \sqcap f(b) = f(a)$ bedeutet. Also gilt \begin{align*} f(a \sqcap b) = f(a) = f(a) \sqcap f(b)\ . \end{align*} Analog gilt $a \sqcup b = b$ und wegen $f(a) \sqsubseteq f(b)$ auch $f(a) \sqcup f(b) = f(b)$, also \[ f(a \sqcup b) = f(b) = f(a) \sqcup f(b)\ . \] Somit ist $f$ ein Verbandshomomorphismus. \hfill\smallskip\\ ``(c) $\Leftarrow$ (a)'': Verwendet wird eine Kontraposition: $\neg$(a)$\Rightarrow \neg$(c). Sei $V$ keine Kette. Dann existieren $a, b \in V$ für die gilt, dass sie unvergleichbar sind. Zu zeigen ist, dass ein Ordnungshomomorphismus existiert, der aber kein Verbandshomomorphismus ist. Setze \[ f: V \to V\ , \quad x \mapsto \begin{cases} a \sqcup b & : a \sqcup b \sqsubseteq x \\ a & : \text{sonst}. \end{cases} \] Seien $x,y \in V$ mit $x \sqsubseteq y$.\\ \emph{1.Fall:} Es gilt $a \sqcup b \sqsubseteq x$.\\ Dann folgt auch $a \sqcup b \sqsubseteq y$, also gilt $f(x) = a \sqcup b = f(y)$ und somit insbesondere $f(x) \sqsubseteq f(y)$.\hfill\smallskip\\ \emph{2.Fall} Es gilt $\neg (a \sqcup b \sqsubseteq x)$.\\ Dann gilt $f(x) = a$. Wegen $a \sqsubseteq a$, $a \sqsubseteq a \sqcup b$ und $f(y) \in \set{a, a \sqcup b}$ gilt dann $f(x) = a \sqsubseteq f(y)$.\hfill\smallskip\\ Somit ist $f$ monoton. Es gilt $f(a \sqcup b) = a \sqcup b$. Weiterhin gilt $a \sqcup b \not \sqsubseteq a$, denn g\"alte $a \sqcup b \sqsubseteq a$, so h\"atten wir $a \sqcup b \sqsubseteq a \sqsubseteq a\sqcup b$, also $a = a \sqsubseteq b$ und damit $b \sqsubseteq a$, was nicht sein kann, weil $a, b$ unvergleichbar sind. Analog gilt auch $a \sqcup b \not \sqsubseteq b$. Also gilt $a \sqsubset a \sqcup b$ und wir erhalten: \[ f(a) \sqcup f(b) = a \sqcup a = a \sqsubset a \sqcup b = f(a \sqcup b)\ . \] Damit ist $f$ kein Verbandshomomorphismus. \end{proof} \begin{exercise} Seien $(V, \sqcup, \sqcap)$ ein modularer Verband und $a, b \in V$ mit $a \sqsubseteq b$. Wir definieren \[f_{a, b} : [a, b] \to V\ , \quad v \mapsto v \sqcap b \ .\] Zeigen Sie: \begin{enumerate} \item Es gilt $f_{a, b}([a, b]) \subseteq [a, b]$. \item $f_{a, b}$ aufgefasst als eine Funktion von $[a, b]$ nach $f_{a, b}([a, b])$ ist ein Verbandsisomorphismus. \end{enumerate} Geben Sie au\ss{}erdem die Inverse von $f_{a, b}$ an. \end{exercise} \begin{proof} Die L\"osung dieser Aufgabe ist trivial. F\"ur alle $v \in [a, b]$ gilt $v \sqsubseteq b$, also $f(v) = v \sqcap b = v$. Damit gilt $f = \id_{[a, b]}$. Insbesondere folgt damit (a) und $f$ ist nat\"urlich auch ein Verbandsisomorphismus, dessen Inverse wieder $f$ selbst ist. \end{proof} \begin{exercise} \noline1 \begin{enumerate} \item \begin{claim} F\"ur jede Menge $M$ ist $\left(2^M, \cup, \cap\right)$ ein distributiver Verband. \end{claim} \begin{proof} Seien $A, B, C \in 2^M$ und es gelte $A \subseteq C$. Dann gilt: \[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) = (A \cup B) \cap C\ , \] weil der Verband sogar distributiv ist. \end{proof} \item \begin{claim} Der Verband $(\bbn, \max, \min)$ ist ebenfalls distributiv. \end{claim} \begin{proof} Wir wissen, dass jeder nichtmodulare Verband einen zu $V_{\neg M}$ isomorphen Unterverband enth\"alt. Insbesondere gibt es in einen nichtmodularen Verband also unvergleichbare Elemente. Allerdings bildet $(\bbn, \max, \min)$ eine Kette, sodass alle Elemente paarweise vergleichbar sind. Damit gibt es darin keinen zu $V_{\neg M}$ isomorphen Unterverband. \end{proof} \item Seien $V$ ein Verband und $M$ eine nichtleere Menge. \begin{claim} $V^M$ ist genau dann modular, wenn $V$ modular ist. \end{claim} \begin{proof} ``$\Longleftarrow$'': Es gelte, dass $V$ modular ist. Seien $f, g, h \in V^M$ mit $f \sqsubseteq h$. Dann gilt f\"ur alle $x \in V$ auch $f(x) \sqsubseteq h(x)$ und damit \begin{align*} (f \sqcup (g \sqcap h)) (x) & = f(x) \sqcup (g \sqcap h)(x) & \text{Def. $\sqcup$ in $V^M$}\\ & = f(x) \sqcup (g(x) \sqcap h(x)) & \text{Def. $\sqcap$ in $V^M$}\\ & = (f(x) \sqcup g(x)) \sqcap h(x) & \text{$f(x) \sqsubseteq h(x)$ und $V$ modular}\\ & = (f \sqcup g)(x) \sqcap h(x) & \text{Def. $\sqcup$ in $V^M$}\\ & = ((f \sqcup g) \sqcap h)(x) \ . & \text{Def. $\sqcap$ in $V^M$} \end{align*} ``$\Longrightarrow$'': Es gelte, dass $V^M$ modular ist. Seien $a, b, c \in V$ mit $a \sqsubseteq c$. Definiere f\"ur alle $x \in \set{a, b, c}$ \[ f_x : M \to V\ , \quad m \mapsto x\ . \] Dann gilt $f_a, f_b, f_c \in V^M$ und $f_a \sqsubseteq f_c$. Da $M$ nichtleer ist, existiert ein $m$ in $M$. also gilt: \begin{align*} a \sqcup (b \sqcap c) & = f_a(m) \sqcup (f_b(m) \sqcap f_c(m)) & \text{Def. $f_a, f_b, f_c$}\\ & = (f_a \sqcup (f_b \sqcap f_c))(m) & \text{Def. $\sqcup, \sqcap$ in $V^M$}\\ & = ((f_a \sqcup f_b) \sqcap f_c)(m) & \text{$f_a \sqsubseteq f_c$ und $V^M$ modular}\\ & = (f_a(m) \sqcup f_b(m)) \sqcap f_c(m) & \text{Def. $\sqcup, \sqcap$ in $V^M$}\\ & = (a \sqcup b) \sqcap c \ . & \text{Def. $f_a, f_b, f_c$} \tag*{\qedhere} \end{align*} \end{proof} \end{enumerate} Es gibt f\"ur alle $n \in \bbn_{\ge 5}$ nichtmodulare Verb\"ande mit $n$ Elementen. Dazu f\"uge man unterhalb des kleinsten Elements von $V_{\neg M}$ eine Kette aus $n - 5$ weiteren Gliedern hinzu. \end{exercise} \begin{exercise} Sei $(V, \sqcup_V, \sqcap_V)$ und $(W, \sqcup_W, \sqcap_W)$ Verb\"ande. \hfill\\ \begin{claim} Genau dann ist $V\times W$ modular, wenn $V$ und $W$ modular sind. \end{claim} \begin{proof} Wir benutzen die Charakterisierung 3.1.3 der Modularit\"at: Genau dann ist ein Verband $A$ modular, wenn f\"ur alle $a, b, c \in A$ gilt: \begin{equation} \qquad a\sqcap((a\sqcap b)\sqcup c) = (a\sqcap b) \sqcup (a\sqcap c)\ . \tag{$\ast$} \label{aux} \end{equation} Wir zeigen zun\"achst: Sind $V$ und $W$ modular, so ist auch $V\times W$ modular. Seien also $V$ und $W$ modular. Seien $(u, v), (w, x), (y, z)\in V\times W$. Dann folgt \begin{align*} & (u, v) \sqcap (((u, v)\sqcap(w, x))\sqcup(y, z)) \\ ={} & (u, v)\sqcap((u\sqcap w, v\sqcap x) \sqcup (y, z)) & \text{Def. $\sqcap$ auf $V\times W$}\\ ={} & (u, v)\sqcap((u\sqcap w)\sqcup y, (v\sqcap x)\sqcup z) & \text{Def. $\sqcup$ auf $V\times W$}\\ ={} & (u\sqcap((u\sqcap w)\sqcup y), v\sqcap((v\sqcap x)\sqcup z)) & \text{Def. $\sqcap$ auf $V\times W$}\\ ={} & ((u\sqcap w)\sqcup(u\sqcap y), (v\sqcap x)\sqcup(v\sqcap z)) & \text{Satz 3.1.3}\\ ={} & (u\sqcap w, v\sqcap x) \sqcup (u \sqcap y, v\sqcap z) &\text{Def. $\sqcup$ auf $V\times W$}\\ ={} & (u\sqcap w, v\sqcap x)\sqcup((u, v)\sqcap(y, z)) &\text{Def. $\sqcap$ auf $V\times W$}\\ ={} & ((u, v)\sqcap(w, x)) \sqcup ((u, v)\sqcap(y, z)) &\text{Def. $\sqcup$ auf $V\times W$}\ , \end{align*} also gilt \eqref{aux} in $V \times W$. Somit ist $V\times W$ modular. Wir zeigen nun: Ist $V\times W$ modular, so sind $V$ und $W$ modular. Aus Symmetriegr\"unden beschr\"anken wir uns dabei darauf, die Modularit\"at von $V$ nachzuweisen. Es gelte, dass $V \times W$ modular ist. Seien $a, c, e\in V$. Wir fixieren ein beliebiges $w \in W$ ($W$ ist nichtleer). Dann gilt: \begin{align*} (a \sqcap ((a \sqcap b) \sqcup c), w) &= (a \sqcap ((a \sqcap b) \sqcup c), w \sqcap ((w \sqcap w) \sqcup w)) & \text{Idempotenz von $\sqcup$, $\sqcap$}\\ &= (a, w) \sqcap (((a, w) \sqcap (b, w))\sqcup (c, w)) & \text{wie oben}\\ &= ((a, w) \sqcap (b, w)) \sqcup ((a, w) \sqcap (c, w)) & \text{wegen \eqref{aux}}\\ &= ( (a \sqcap b) \sqcup (a \sqcap c), (w \sqcap w) \sqcup (w \sqcap w)) & \text{wie oben}\\ &= ( (a \sqcap b) \sqcup (a \sqcap c), w) & \text{Idempotenz von $\sqcup$, $\sqcap$}\ . \end{align*} Insbesondere gilt also $a \sqcap ((a \sqcap b) \sqcup c) = (a \sqcap b) \sqcup (a \sqcap c)$. Damit ist $V$ modular. \end{proof} \end{exercise} \end{document}