Blattlar's Page


		<Paradoxien >Logistik Algebra Die moderne Algebra beschäftigt sich mit der Untersuchung von algebraischen Strukturen wie: Halbgruppe, Gruppe, Ring, Körper. Definition einer Halbgruppe: Es sei H ¹ Æ: Eine Funktion f::H x H ® H, mit a,b,c ÎH: (a,b) ® c (eindeutig) heißt innere binäre Operation. Eine Menge H ¹ Æ mit einer inneren binären Operation „.“ heißt Halbgruppe, wenn die Operation „.“ assoziativ ist. d.h. a(bc) = (ab)c " a,b,c ÎH Eine Halbgruppe H heißt kommutativ, wenn ab = ba " a,b Î H. Ein Element e Î H heißt Einselement der Halbgruppe (H, .), wenn ea = ae = a " a Î H. Rees - Matrix - Halbgruppen DEFINITION I.1.1. es sei G^o = G È 0 (G eine Gruppe mit adjungiertem Nullelement) seien I = (i,j,k,...) und L = (l,µ,n,...) Indexmengen. Es sei P: L x I -> G (l,i) -> p_li eine Lx I Matrix über G^o . Es sei S = (I x G x L) È (0). Definiere auf S eine Multiplikation durch: (i,a,l)(j,b,m) = (i,aplj b,m) für plj ¹ 0 und = 0 sonst 0(i,a,l)=(i,a,l) = 00 = 0 S = M (I,G,L,P) heißt die Rees Matrix Halbgruppe über der Gruppe G^o mit der Sandwich Matrix P. Bemerkung: M ^o = M^o (I,G,L,P) ist wirklich eine Halbgruppe, so dass M ^o abgeschlossen unter der definierten Multiplikation ist und diese Multiplikation assoziativ ist. DEFINITION I.1.2 Die Sandwich Matrix P Heißt regulär, falls: 1. " i Î I $ µ Î L sodass p_mi ¹ 0 2. " l Î L $ i Î I sodass p_li ¹ 0 Bemerkung: M ^o = M ^o (I,G,L,P) ist regulär <=> P regulär ist. Denn: M ^o regulär => " (i,a,l) Î M ^o $ (j,x,m) sodass (i,a,l) = (i,a,l)(j,x,m)(i,a,l) = (i,ap_lj xp_mia,l) => a = ap_lj xp_mi a => p_lj xp_mi = a^-1 => x = p_lj^-1 a^-1 p_mi ^-1 <=> p_lj ¹ 0 und p_mi ¹ 0 d.h. " i Î I $ µ Î L sodass p_µi ¹ 0 und " l ÎL $ j Î I , dass p_lj ¹ 0, d.h. insgesamt, dass P regulär ist. Ist umgekehrt P regulär, so ist (j,p_lj ^-1 a^-1 p_mi ^-1 ,m) das gesuchte Element. Definition I.1.3. Eine Halbgruppe S ohne 0 heißt einfach, wenn S keine eigentlichen Ideale enthält. Eine Halbgruppe S mit 0 heißt 0-einfach, wenn 1. {0} und S sind die einzigen Ideale von S 2. S² ¹ (0) Definition I.1.4. Ein idempotentes Element f einer Halbgruppe S mit 0 heißt primitiv, wenn 1. f ¹ 0 2. e £ f => e = 0 oder e = f Definition I.1.5. Eine Halbgruppe S mit 0 heißt vollständig 0-einfach, wenn: 1. S ist 0-einfach 2. es existiert ein primitives Idempotentes Lemma I.1.6. eine Halbgruppe S Ist 0-einfach <=> S = SaS " aÎS\{0)} <=> " a,bÎS\{0} $ x,yÎS sodass xay = b Beweis: 1. Þ) Angenommen S ist 0-einfach. Dann ist S² ein Ideal von S und daher Ist S² = S, da ja S² ¹ {0}ist. Also S³ = S²S = SS = S. Es sei aÎS\{0}. Dann ist SaS ein Ideal von S. Also muß SaS = {0} oder SaS = S sein. Angenommen SaS = {0}, dann enthält die Menge I = {x Î S: SxS = {0}] ein Element verschieden von 0. Nun ist I auch ein Ideal von S und daher ist I = S. D.h. SxS = {0} " xÎS => S³ = {0} Widerspruch. Daher ist SaS = S " aÎS\{0}. 2.Þ) Es gelte SaS = S " aÎS\{0}. Dann Ist S² ¹ {0}. Ebenso gilt, wenn A ein Ideal von S ist, welches a enthält und A ¹ {0}, dass A Ê SAS Ê SaS = S => A = S. Lemma I.1.7 M ^o= M ^o (I,G,L,P), mit P als regulärer Sandwich-Matrix, ist eine vollständig 0-einfache Halbgruppe. Beweis:1) Zu zeigen: " (i,a,l) ¹ 0, (j,b,m) ¹ 0 ÎM^o $ (l,x,n) und (k,y,k) so, dass (l,x,n)( i,a,l)(k,y,k) = (j,b,m) Aus der Regularität von P folgt, dass für ein i ÎI ein nÎL existiert, sodass p_ni ¹ 0 und, dass für lÎL ein kÎI existiert, sodass p_lk ¹ 0. Wir setzen (l,x,n) = (j,a^-1p_ni^-1,n) (k,y,k) = (k,p_lk^-1tb,m) Dann haben wir: (j,a^-1p_ni^-1,n)(i,a,l)(k,p_lk^-1b,m) d.h. M ^o ist 0-einfach nach Lemma 1.6. 2. Zu zeigen: $ ein primitives Idempotentes. Zeige: E_M^o= {(i,p_li^-1,l)/ iÎI, µÎL} È {0} Es sei e Ein Idempotentes von M ^o. e = (i,a,l), d.h. (i,a,l)(i,a,l) = (i,a,l) <=> ap_lia = a <=> p_li = a^-1aa^-1 <=> p_li^-1 = a und (i,p_li^-1,l)² = (i,p_li^-1,l) Zeige: Jedes Idempotente ist primitiv. Zu zeigen: " e,fÎE_M^o mit e £ f => e = f (e £ f <=> e = ef = fe) e = (i,p_li^-1,µ), f = (j,p_mj^-1,m) ef = (i,p_li^-1p_ljp_mj^-1,m), fe = (j,p_mj¹p_mip_li^-1,l) ef = fe => i = j, l = m und so p_li^-1p_ljp_{m j}^-1 = p_mj^-1p_mip_li^-1d.h.. insgesamt, dass M ^o vollständig 0-einfach ist. ist. Hiermit ist der "einfache" Teil des Satzes von Rees (1940) bewiesen. I.1.8. Satz(Rees) Es sei G^o eine Gruppe mit 0; es seien I,L ¹ 0 Mengen und P = (p_li) eine LxI - Matrix über G^o . Die Matrix P sei regulärer im Sinne von I.1.2. Es sei S = (IxGxL)È{0} mit der in I.1.1. definierten Multiplikation. Dann ist S eine vollständig 0-einfache Halbgruppe. Umgekehrt ist jede vollständig 0-einfache Halbgruppe isomorph zu einer so konstruierten Halbgruppe. Um die zweite Hälfte des Satzes beweisen zu können, brauchen wir noch folgende Vorbereitungen: I.1.9. Definition: Eine Halbgruppe heißt "bisimple", falls S nur auf einer D-Klasse besteht. Eine Halbgruppe S mit 0 heißt "0-bisimple", falls S nur die beiden D -Klassen {0} und S\{0} enthält. Nach J. Howie: Introduction to semigroups, Lemma 2.6. gilt: Wenn S vollständig 0-einfach ist, dann ist S regulär. I.1.10.Lemma: Jede vollständig 0-einfache Halbgruppe S ist 0-bisimple Beweis: Zu zeigen: " a,bÎS* gilt a D b [a D 0 => a = 0, 0 D 0 immer] es seien also a,bÎS* so, dass S vollständig 0-einfach ist, existieren für alle a,bÎS* x,y,r,sÎS mit xay = b, rbs = a. Die Vollständigkeit von S ist äquivalent zu der Bedingung min_L und min_R d.h. dass jede nichtleere Menge von L -Klassen bzw von R -Klassen ein minimales Element enthält, wobei L_a £ L_b <=> S¹a Í S¹b R_a £ L_b <=> aS¹ Í bS¹ Betrachte die Menge X = {x Î S/ $ y Î S mit xay = b}. Dann ist die Menge X ¹ Æ und ebenso gilt, dass L = {L_x/xÎX} ¹ Æ. Dass S min_L erfüllt können wir ein minimales Element L_u finden, wobei uav = b für ein gewisses vÎS. Nun ist uruavsv = b, => L_uru ÎL und L_uru £ L_u . Aus der Minimalität von L_u folgt, dass L_u = L_uru. Also L_u = L_uru £ L_ru £ L_u Þ ru L u = ruav L uav d.h. rb L b. Analog ergibt sich, dass bs R b => rbs R rb d.h. a R rb. Also a R rb und rb L b => a D b. Bemerkung: Das heißt also insgesamt, daß jede vollständig 0-einfache Halbgruppe S aus der regulären D-Klasse {0} und auf der regulären D- Klasse S* besteht. Die folgenden Aussagen übernehme ich ohne Beweis aus Clifford & Preston: I.1.11.Satz (Green) Es sei H eine H- Klasse einer Halbgruppe S. Wenn a,b abÎH, dann ist H eine Untergruppe von S. Speziell: Enthält H ein Idempotentes von S, so ist H eine Untergruppe von S. I.1.12.Lemma von Green: Es seien a,bÎS, S eine Halbgruppe. Es sei a R b, es seien s,s’ÎS¹so, dass as = b, bs’ = a. Dann sind die Rechtstranslationen r_s : L_a -> L_b beziehungsweise r_s’ : L_b ® L_a zueinander inverse R- Klassen erhaltende Bijektionen von L_a ® L_b bzw. L_b ® L_a. Dual erhält man die Aussage für Linkstranslationen. I.1.13.Lemma: In jeder regulären D- Klasse enthält jede R- KLasse und jede L- Klasse mindestens ein idempotentes Element. I.1.14.Lemma: Sind H,K zwei Gruppen - H - Klassen in eine regulären D- Klasse, dann sind H und K isomorph. I.1.15.Korollar: Es sei S eine vollständig 0-einfache Halbgruppe und H eine H -Klasse. Dann ist H entweder eine Gruppe oder H² = {0}. Beweis des Satzes von Rees: Es sei S eine vollständig 0-einfache Halbgruppe. S* besteht also aus eine regulären D- Klasse, nach oben. Wir indizieren nun alle R- Klassen von S* durch I und alle L- Klassen von S* durch L. [R_i\ iÎI], [L_m\ µÎL] Bezeichne die H- Klassen von S^durch H_i_l = R_i ÇL_l. Nach I.1.13. folgt nun, daß jedes R_i mindestens eine Gruppen - H - Klasse H_i_lund jedes L_l ebenso mindestens eine Gruppen - H - Klasse H_i_l enthält. Wir wählen also ein i und ein l (und halten diese fest) so, daß H_i_l eine Gruppe ist. O.B.d.A. können wir die gewählte H- Klasse mit H₁₁ bezeichnen (nach I.1.14.). Bezeichne das Einselement von H₁₁ mit e. Wir wählen für jedes i Î I ein Element r_i Î H_i1 und für jedes l Î L ein q_l Î H₁_l (dies ist möglich nach i.1.13). Da r_i L e Þ r_ie = r_i (Rechtseinheit). Also folgt aus I.1.12. daß die Abbildung H₁₁ -> H_i1 x -> r_ix bijektiv ist. Da q_l L e Þ eq_l = q_l (Linkseinheit) gilt, dass auf die Abbildung H_i1 -> H_i_l y ® yq_l bijektiv ist. D.h. also daß wir eine bijektive Abbildung von H₁₁ auf H_i_l haben. Daher läßt sich jedes Element aus H_i_l in eindeutiger Weise als ein r_iaq_l (a Î H₁₁) darstellen. Da S = È {H_i_l \ i Î I,l Î L} und diese Vereinigung disjunkt ist (H ist eine Äquivalenzrelation) können wir eine Abbildung f: (I x H₁₁ x L) È {0} -> S definieren durch: (i,a,µ)f = r_iaq_l 0f = 0 Diese Abbildung ist bijektiv. Damit f ein Isomorphismus wird, müssen wir auf (I x H₁₁ x L) È {0} eine Multiplikation einführen sodass (I x H₁₁ x L) È {0} eine Rees Matrix Halbgruppe wird. Dass (r_iaq_l)(r_jbq_m) = r_i(aq_lr_jb)q_m ist es naheliegend die Sandwich-Matrix P = (p_li ) zu definieren als p_li = q_lr_i (i Î I, l Î L). Wir zeigen daß p_li Î H₁₁: Ist H_i_l eine Gruppe mit Einheit f so haben wir fr_i = r_i und daher ist die Abbildung f: x ® xr_i eine R- Klassen erhaltende Abbildung L_l ® L₁ (nach I.1.12). Folglich ist p_li = q_lr_i Î H₁₁. Haben wir andererseits daß H_i_l² = {0} (und dies ist der einzige alternative Fall nach I.1.15) dann "c Î H_i_l $ u,v Î S¹ so, dass q_l = uc und r_i = cv => p_li= q_lr_i = uc²v = 0, d.h. p_li Î H₁₁^o . Da nun nach I.1.13. jede L- Klasse L_l und jede R- Klasse R_i der regulären D- Klasse S* ein Idempotentes enthält, existiert also für jedes i Î I ein l Î L so, daß H_i_l eine Gruppe ist und analog existiert für jedes l Î L ein i Î I so, daß H_i_l eine Gruppe ist. Hierauf folgt also die Regularität der Sandwich-Matrix P = (p_li). Es bleibt also zu zeigen, daß f: M^o(I,H₁₁,L,P) ® S ein Isomorphismus ist. Die Bijektivität diese Abbildung ist klar nach Konstruktion. Zu zeigen ist also: f ist ein Homomorphismus Es seien (i,a,l), (j,b,m) Î M^o(I,H₁₁,L,P): [(i,a,l)(j,b,m)]f = [(iap_ljb,m)]f = r_iap_ljbq_m = (r_iaq_m)(r_jbq_m) = (i,a,l)f (j,b,m)f w.z.z.w. Somit ist der Satz von Rees vollständig bewiesen. <Paradoxien >Logistik