Thursday, April 29, 2010

Ostra 2-tranzytywność grupy afinicznej ciała uogólnionego

Wstęp

Niniejsza nota dopełnia (jak druga strona medalu) wyniki not poprzednich, patrz

Przestrzenie ostro 2-przechodnie (spis rzeczy).

Chociaż dowody poniżej nie zależą od poprzednich not (poza podsumowaniem), to jednak notacja i terminologia pochodzi w dużej mnierze z wcześniejszych, więc warto rzucić na nie okiem. W sumie, scharakteryzowałem skończone ostro 2-przechodnie przestrzenie jako 1-wymiarowe przestrzenie afiniczne nad _ciałami uogólnionymi_ w sensie poniżej; nazywam takie uogólnione ciała _gildami_ (bo alfabetycznie po angielsku jesrt naturalnym mieć _gild_ po _field_ ). Pokazałem też, że dodawanie w gildach skończonych jest przemienne.

Definicja ciała uogólnionego, gild.

Niech

K := (K + * Sub Div 0 1)

będzie uporządkowaną siódemką, złożoną ze zbioru K, operacji 2-argumentowej + w zbiorze K, operacji 2-argumentowej * w zbiorze K# := K\{0}, operacji 1-argumentowej Sub w zbiorze K, 1-argumentowej Div w zbiorze K#, oraz dwóch różnych elementów 0 1 zbioru K, gdzie:

(K + 0) jest grupą,
(K# * 1) jest grupą,

oraz zakładając (dodefiniowując):

a*0 = 0*a = 0 dla każdego a ∈ K

niech zachodzi własność lewej rozdzielności:

a*(b+c) = a*b + a*c

(jak zwykle zakładamy, że * wiąże mocniej niż +). Wtedy uporządkowaną siódemkę K nazywamy ciałem uogólnionym lub krótko gild.

UWAGA 0: Nie zakładamy przemienności ani dodawania +, ani mnożenia *.

TWIERDZENIE 0 x * Sub(y) = Sub(x * y)

DOWÓD

x*y + x*Sub(y) = x*(y + Sub(y)) = x*0 = 0

KONIEC DOWODU

Przekształcenia afiniczne

Dla dowolnych a b ∈ K definiujemy przekształcenie afiniczne

f := fa b : K → K

jak następuje:

f(x) := a*x + b dla dowolnego x ∈ K

Gdy a=0, to f jest funkcją stałą, równą b. Dla niezerowych a, przekształcenia afiniczne jest surjekcją, t.zn. dla dowolnego X ∈ K istnieje x ∈ K takie, że f(x) = X - rzeczywiście, jest tak dla:

x := Div(a)*(X + Sub(b))

Co więcej, jest tak tylko dla tego jednego x, co wynika z procesu rozwiązywania równania f(x) = X. Można też sprawdzić jednoznaczność bez rozwiązywania równania tak -

gdy f(x') = f(x), to f(x') + Sub(f(x)) = 0,

czyli:

a*(x' + Sub(x)) = a*x' + a*Sub(x)

= a*x' + Sub(a*x)

= a*x' + b + Sub(b) + Sub(a*x)

= f(x') + Sub(f(x)) = 0

więc x' +Sub(x) = 0, skąd x'=x.

Pokazaliśmy, że dla niezerowego współczynnika a przekształcenie afiniczne f jest bijekcją.

W szczególności bijekcją afiniczną jest IdK:

IdK(x) := 1*x + 0

Przekształcenie odwrotne

Widzieliśmy, że dla 0 ≠ a ∈ K, afiniczna równość daje się odwrócić:

X = a*x + b ⇔ x = A*X + B

gdzie A := Div(a) oraz B := Div(a) + Sub(b)

Oznacza to, że bijekcja g odwrotna do bijekcji afinicznej f jest afiniczna, gdzie

g(x) := A*x + B
g o f = f o g = IdK

Kompozycja przekształceń afinicznych

Niech dwa przekształcenia afiniczne będą dane wzorami:

f(x) := a*x + b oraz F(x) := A*x + B

gdzie a b A B ∈ K są dowolne. Wtedy:

(F o f)(x) = F(a*x + b) = (A*a)*x + (A*b + B)

czyli kompozycja F o f też jest afiniczna. W szczególności dla bijekcji, w świetle ostatniego i poprzednich wyników, otrzymujemy:

TWIERDZENIE 1: Bijekcje afiniczne gildu K tworzą grupę względem operacji 2-argumentowej kompozycji przekształceń.

Ostra 2-przechodniość grupy afinicznej

Dla dowolnie ustalonych x y X Y ∈ K takich, że x ≠ y, znajdźmy wszystkie (o ile jakiekolwiek) pary a b ∈ K dla których zachodzą równości:

X = a*x + b
Y = a*y + b

czyli chodzi o rozwiązanie układu 2 równań z niewiadomymi a b. Wartości a b muszą spełniać:

Y + Sub(X) = a*y + b + Sub(b) + Sub(a*x)

= a*y + Sub(a*x) = a*y + a*Sub(x)

= a*(y + Sub(x))

czyli

a := (Y + Sub(X))*Div(y + Sub(x))

jest jedyną możliwą wartością a (t.zn. każda inna jest zła). Skoro tak, to

b := Sub(a*x) + X

dla a zdefiniowanego jak przed chwilą, jest jedyną możliwą wartością b. To dowodzi 2-ostrości grupy afinicznej. Pozostała 2-przechodniość. Wystarczy sprawdzić, że podane wartości a b są poprawne:

a*x + b = a*x + Sub(a*x) + X = X

- działa. Teraz:

a*y + b = a*y + Sub(a*x) + X = a*(y + Sub(x)) + X

= (Y + Sub(X)) + X = Y

- działa. Udowodniliśmy:

TWIERDZENIE 2: Grupa bijekcji afinicznych gildu K jest ostro 2-przechodnia.

Saturday, April 17, 2010

Charakteryzacja skończonych przestrzeni ostro 2-przechodnich (cz. II)

W poprzedniej notce:

Charakteryzacja skończonych przestrzeni ostro 2-przechodnich (cz. I)

zacząłem, a w niniejszej kontynuuję dowód afiniczności 1-wymiarowej dowolnej, skończonej przestrzeni ostro 2-przechodniej (X G).

Niniejsza notka jest kontynuacją poprzednich, z cyklu:

    Przestrzenie ostro 2-przechodnie (spis rzeczy)

W szczególności zakładamy, że (X G) jest skończoną, n-punktową, ostro 2-przechodnią przestrzenią, oraz V(G) - zbiorem wszystkich permutacji z G, niemających punktu stałego; ponadto

        A(G) := V(G) ∪ {IdX};
        Xif(a) := { g ∈ G : g(a) = a }   dla każdego  a ∈ X;
        O E ∈ X,   przy czym  O ≠ E.

=================================================
Lewostronna rozdzielność względem mnożenia przez 2
=================================================

W notce:

    Przestrzenie ostro 2-przechodnie. Cykle. Inwolucje. Przemienność wektorów (grupy A(G)).

rozpatrywałem dwa podejścia do dodawania dwóch różnych wektorów  v w, gdyż chodziło o dowod przemienności. Tym razem popatrzmy na przypadek  v=w  czyli  a=b,  gdzie  a=v(O)  oraz  b:=w(O);  ale tym razem mniejsza o obiekty  w b.  Rozważania o podwojeniu są nietrywialne tylko dla nieparzystego  n := |X|,  co odtąd w tym semencie tekstu o rozłączności względem mnożenia przez 2, zakładamy: niech  n  będzie nieparzyste.

Z jednej strony podwojony punkt  a+a  definiujemy jako  v(a),  gdzie  v  jest wektorem, spełniającym  v(O) = a.  Z drugiej strony chcielibyśmy, żeby podwojone  a  było punktem  ja(O),  gdzie  ja  jest nietrywialną inwolucją, spełniającą  ja(a) = a.  Pokażę, że te dwie definicje podwojonego punktu dają ten sam wynik - udowodnię:

        ja(O)  =  v(a)

Dowód:  Najpierw rozpatrzmy nietrywialną inwolucję  jO, dla której punktem stałym jest punkt  O.  Wtedy:

        ja  =  v o jO o v-1

jest nietrywialną inwolucją, której punktem stałym jest punkt  a := v(O).  Także inwolucją jest  v o jO. Ponieważ:

        (v o jO)(O)  =  a

to

        (v o jO)(a)  =  O

Zatem:

    ja(v(a))  =  (v o jO o v-1)(v(a)))  =  (v o jO)(a)  =  O

więc

    ja(O)  =  v(a)

KONIEC dowodu

Przejdźmy wreszcie do rozdzielności. Niech  r ∈ Xif(O)  oraz  a ∈ X.  Chcemy pokazać, że

        r(a + a)  =  r(a) + r(a)

DOWÓD:  Niech  ja  będzie nietrywialną inwolucją, o punkcie stałym  a,  tak że

        a+a = ja(O)

Wtedy


        jr(a)  =  r o ja o r-1

jest nietrywialną inwolucją, o punkcie stałym  r(a).  Zatem


        jr(a)(O)  =  r(a) + r(a)

Stąd:

    r(a) + r(a)  =  jr(a)(O)  =  (r o ja o r-1)(O)  =  (r o ja)(O)  =  r(a+a)

KONIEC dowodu

=================================================
Mnożenie  ⋅  w  X\{O}  jako operacja grupowa
=================================================

Wiemy z wcześniejszych rozważań ogólnych, że:

        M(G)  :=  { g|X\{O} : g ∈ Xif(O) }

jest ostro 1-przechodnią grupą permutacji zbioru  X\{O}.  Grupa ta jest izomorficzna z algebraiczną strukturą  (X\{O} ⋅),  zdefiniowaną w poprzedniej notce. Zatem grupą jest także struktura algebraiczna  (X\{O} ⋅).

=================================================
Rozdzielność dodawania względem mnożenia w X
=================================================

Niech  a b c ∈ X. Chcemy najpierw dowieść lewego prawa rozdzielności:

        a⋅(b + c)  =  a⋅b + a⋅c

Równość zachodzi dla  a=O. Załóżmy, że odtąd  a ≠ O,  oraz niech  ra ∈ Xif(O)  spełnia 

        ra(E)  =  a

Chcemy udowodnić równość:

        ra(b+c)  =  ra(b) + ra(c)

Dla  b=c  uczyniliśmy to powyżej, w odcinku tekstu o rozdzielności względem mnożenia przez 2. Dla różnych  b c  dowiedliśmy tej rozdzielności w cz. I.

KONIEC dowodu


UWAGA 0  Przypominam, że rozdzielność dla b=c, przy parzystym  n, jest trywialna,  0=0.

(Będę kontynuować)

Wednesday, April 14, 2010

Charakteryzacja skończonych przestrzeni ostro 2-przechodnich (cz. I)

Pokażę (w tej i następnej notce), że każda skończona, n-punktowa przestrzeń ostro 2-przechodnia  (X G)  jest zbiorem elementów pewnego ciała skończonego, wraz z jego grupą przekształceń afinicznych (traktujemy ciało jako 1-wymiarową przestrzeń afiniczną).

Niniejsza notka jest kontynuacją poprzednich, z cyklu:

Przestrzenie ostro 2-przechodnie (spis rzeczy)

W szczególności zakładamy, że (X G) jest skończoną, n-punktową, ostro 2-przechodnią przestrzenią, oraz V(G) - zbiorem wszystkich permutacji z G, niemających punktu stałego; ponadto

        A(G)  :=  V(G) ∪ {IdX}
        Xif(a)  :=  { g ∈ G : g(a) = a }   dla każdego  a ∈ X

==========================================
Lewostronna rozdzielność
==========================================

Niech  O ∈ X,  r ∈ Xif(O),  oraz niech  v w ∈ A(G)  będą dwoma różnymi wektorami. Ponadto wprowadźmy punkty  a b A B  oraz involucje  s S ∈ Inv(G),  takie że:

        a := v(O)
        b := w(O)
        s(a) := b   (zatem także  s(b) := a)

        A := r(a)
        B := r(b)   (punkty  A B  są różne)
        S(A) := B   (zatem także  S(B) := A)

Zachodzi wtedy, jak pokażę poniżej, następująca rozdzielność:

        S(O) = (r o s)(O)

Jest to rozdzielność, gdyż lewa strona  S(O)  gra rolę  A+B = r(a)+r(b),  oraz prawa strona  (r o s)(O)  gra rolę  r(a+b).  Otrzymujemy zatem równość:  r(a+b) = r(a) + r(b).  Więcej o tym napiszę w dalszej części niniejszej notki.

DOWÓD (powyższej rozdzielności)  Oczywiście:

        (r o s o r-1)(A) = B  oraz  (r o s o r-1)(B) = A

Zatem:

        S  =  r o s o r-1

Ponadto:

        A = V(O)   dla wektora  V := r o v o r-1
        B = W(O)   dla wektora  W := r o w o r-1

Zgodnie z wynikiem z poprzedniej notki (o przemienności wektorów):

    S(O)  =  (V o W)(O)  =  ((r o v o r-1) o (r o w o r-1))(O)

        =  (r o v o w o r-1)(O)  =  (r o v o w)(O)  =  (r o s)(O)

KONIEC dowodu (powyższej rozdzielności)

=========================================================
Definicja struktury ciała w przestrzeni ostro 2-przechodniej
=========================================================

Niech  O E ∈ X  będą dwoma różnymi punktami. Zdefinijmy, dla dowolnych  a b ∈ X,  gdzie  a ≠ O,  permutacje  adb ∈ A(G)  oraz  mpa ∈ Xif(a)  jako (jedyne!) spełniające równości:

        adb(O) := b
        mpa(E) := a

oraz dodatkowo definiujemy  mpO  jako funkcję  X  w siebie, tożsamościowo równą O:

        mpO(x) := O   dla każdego  x ∈ X

W szczególności:

        adO  =  IdX  =  mpE

Z pomocą dwóch właśnie wprowadzonych funkcji dodawania stałej oraz mnożenia przez stałą, pełne 2-argumentowe dodawanie i mnożenie definiujemy następująco:

        x + y  :=  adx(y)
        x ⋅ y  :=  mpx(y)

dla dowolnych  x y ∈ X.

Struktura ostro 1-przechodniej grupy  A(G)  przenosi się izomorficznie na  X  poprzez bijekcję zbiorów  X A(G),  daną przez:

        x adx     dla x ∈ X

Jest to szczególny przypadek ogólnego twierdzenia (obserwacji) o grupach ostro 1-przechodnich (zachodzi zarówno w przypadku skończonym jak i nieskończonym), ale dla spokoju ducha podam dowód. Wystarczy pokazać, że podana bijekcja jest izomorfizmem struktur algebraicznych (A(G) o)  oraz (X +). W tym celu porównajmy wektor ada+b z wektorem ada o adb. Oba odwzorowują (jako wektory-permutacje) element  O  w element  a+b. Jest to więc ten sam wektor. Ponieważ struktura algebraiczna  (A(G) o)  jest grupą, a struktura algebraiczna  (X +)  jest z nią izomorficzna, to grupą jest także struktura algebraiczna  (X +).

Sunday, April 11, 2010

Przestrzenie ostro 2-przechodnie. Cykle. Inwolucje. Przemienność wektorów (grupy A(G)).

Niniejsza notka jest kontynuacją poprzednich, z cyklu:

    Przestrzenie ostro 2-przechodnie (spis rzeczy)

W szczególności zakładamy, że (X G) jest skończoną, n-punktową, ostro 2-przechodnią przestrzenią, oraz V(G) - zbiorem wszystkich permutacji z G, niemających punktu stałego; ponadto

        A(G)  =  V(G) ∪ {IdX}


============================
Cykle
============================


Niech  g ∈ G  będzie dowolne. Gdy gt = IdX, to długość cyklu każdego x ∈ X:

        (x g(x) ... gs-1)

gdzie s jest najmniejszą liczbą naturalna (1 2 ...), dla której gs(x) = x, jest podzielnikiem liczby t: zachodzi s|t.

Niech teraz  g ∈ G \ {IdX}.  Wtedy istnieje najmniejsza liczba naturalna  t > 1,  i taka, że istnieje  a ∈ X,  spełniające:

        gt(a)  =  a

Zatem Fix(gt(a)) zawiera zbiór t-elementowy (cykl)

        { a g(a) ... gt-1(a) }

Na mocy ostrości oznacza to, że  gt = IdX. Zatem, na mocy minimalności t,

długość każdego niejednopunktowego cyklu permutacji g jest równa t; gdy g nie jest identycznością, to co najwyżej jeden cykl może mieć długość różną od t - równą 1.

================================
Inwolucje
================================


Permutację g ∈ G nazywamy inwolucją ⇐:⇒ g o g = IdX. Gdy g ≠ IdX, to, na mocy ostatniego stwierdzenia powyżej, wszystkie cykle permutacji g są 2-puntowe, co najwyżej poza jednym. Oznacza to, że dla n parzystego każda inwolucja należy do A(G). Co więcej, dla n parzystego istnieje co najmniej n różnych inwolucji - rzeczywiście, ustalmy O ∈ X. Wtedy dla każdego  x ∈ X\{O}  dostajemy inwolucję  g  taką, że  g(O) = x  oraz  g(x) = O.  Jest ich n-1.  Ponadto dochodzi identyczność. Skoro tak, to dla parzystego n zachodzi równość

        Inv(G) = A(G)    (dla parzystego n)

Dla n nieparzystego rozpatrzmy dowolną nieidentycznościową inwolucję. Oznaczmy ją przez jO, gdzie O jest jej jedynym punktem stałym, JO(O) = O. Dla dowolnego a ∈ X wybierzmy dowolną permutację f ∈ G, spełniającą f(O) = a. Wtedy

        ja  :=  f o jO o f-1

jest inwolucją, ktorej punktem stałym jest a. Otrzymaliśmy w ten sposób n różnych inwolucji nieidentycznościowych. Łącznie z IdX jest ich n+1. Więcej ich nie ma. Rzeczywiście, dla każdej pary różnych punktów istnieje dokładnie jedna (nieidentycznościowa) inwolucja, która ją transponuje. Par istnieje dokładnie

        (n ## 2)  =  n ⋅ (n-1)/2

Przy tym każda nieidentycznościowa inwolucja, dla nieparzystego n, transponuje (n-1)/2 różnych par. Zatem takich inwolucji jest

        (n ## 2) / ((n-1)/2) = n

co łącznie z identycznością daje:

        |Inv(G)|  =  n+1

Z powyższego wynika, że w powyższym rozumowaniu różne dozwolone wybory  f  dawały tę samą inwolucje  ja;  także dla  a = O.  Otrzymaliśmy też informację o strukturze zbioru  Inv(G),  w szczególności:

        f o ja o f-1 = ja  dla każdego  f ∈ Xif(a)

Bowiem mamy po jednej involucji  ja  w każdej podgrupie  Xif(a),  a ∈ X.

====================================================
Kompozycje inwolucji i wektorów
====================================================


Dla parzystego  n  dowiedziona wcześniej równość

        Inv(G) = A(G)    (dla parzystego n)

daje nam całą podstawową wiedzę na temat wektorów i inwolucji. Niech więc odtąd, w niniejszej części notki, liczba  n  bedzie nieparzysta.

Niech  s ∈ Inv(G) \ {IdX}  będzie nietrywialną inwolucją; niech  a ∈ X,  oraz  b := s(a) ≠ a.  Istnieje wtedy (dokładnie jeden) wektor  v ∈ V(G),nbsp taki że  v(a) = b.  Oczywiście:

        (s o v)(a) = a

więc:

        ((s o v) o (s o v))(a) = a

Ale  s o v o s  jest wektorem (bo  s  jest swoją własną odwrotnością); więc także:

        (s o v) o (s o v) = (s o v o s) o v

jest wektorem (jako kompozycja dwóch wektorów). Jest to wektor tożsamościowy, bo ma punkt stały  a.  Zatem:

        (s o v) o (s o v) = IdX

Innymi słowy,  kompozycja  s o v  jest inwolucją, s o v ∈ Inv(G).  Co więcej, znamy jej punkt stały:

        s o v = ja  ∈  Xif(a) ∩ Inv(G)

lub pełniej:

        Xif(a) ∩ Inv(G)  =  {s o v}

Oznacza to, że z każdym punktem  a ∈ X\{O}  związany jest inny wektor  v ∈ V(G). Ponieważ  |X\{O}| = |V(G)| = n-1,  to w grę wchodzi każdy nietrywialny wektor. Otrzymaliśmy zatem już 99% natępującego twierdzenia:

TWIERDZENIE 0  Kompozycja  s o v,  oraz  v o s,  dowolnego wektora z dowolną inwolucją, jest inwolucją.

Jest tak oczywiście także dla wektora trywialnego  IdX.  Czyli wiemy, że twierdzenie zachodzi dla wszystkich kompozycji  s o v.  Ale kompozycja  v o s  jest odwrotnością komppozycji  s o v-1 czyli inwolucji (bo  v-1  jest wektorem), a więc sama też jest inwolucją.  KONIEC dowodu

==================================
Przemienność wektorów
==================================

Następujące twierdzenie dowiedliśmy wcześniej dla parzystych  n:

TWIERDZENIE 1  w o v = v o w  dla dowolnych wektorów  v w ∈ A(G) - czyli grupa  A(G)  jest abelowa (dla skończonego  n := |X| = A(G) > 1;  nie wiem jak jest w przypadku nieskończonym).

DOWÓD  Skoro dla parzystych  n  twierdzenie zachodzi, to załóżmy, że  n  jest nieparzyste.

Niech  v w ∈ A(G)  będą dwoma różnymi wektorami. Niech  O ∈ X  będzie dowolne; oraz zdefiniujmy  a := v(O)  oraz  b := w(O). Więc  a b  są różne, i istnieje (dokładnie jedna) inwolucja  s,  transponująca  a b.  Zatem dla inwolucji  s o v  dostajemy:

        (s o v)(O) = b
        (s o v)(b) = O
        s((v o w)(O)) = O       (bo  b = w(O))
        s(O) = (v o w)(O)

Podobnie dowodzi się:

        s(O) = (w o v)(O)

Zatem dla wektorów  w o v  oraz  v o w  zachodzi równość:

        (v o w)(O)  =  (w o v)(O)

Skoro tak, to wektory te są równe:

        v o w  =  w o v

========================
UWAGI
========================


Twierdzenia 0 1  zachodzą dla dowolnych liczb naturalnych  n > 1,  zarówno dla parzystych, jak i dla nieparzystych. Przy tym dla parzystych, odkąd wiemy, że  Inv(G) = A(G)  (dla n - parzystych), twierdzenia te zachodzą trywialnie.

Także równość:

        s(O) = (v o w)(O)

gdzie  v w  są dwoma różnymi wektorami, oraz  punkt  wraz z inwolucją  s  mają własność:

        s(v(O)) = w(O)   (wię  s(w(O)) = v(O)) )

zachodzi zarówno dla nieparzystych  n (co dowiodłem), jak i dla parzystych  n (co jest trywialne, gdyż po prostu, i jednoznacznie:

        s = w o v = v o w

gdy  Inv(G) = A(G)).

Przestrzenie ostro 2-przechodnie (spis rzeczy)

Pierwsze dwie pozycje dotyczą sytuacji ogólniejszych, niż tytułowe.


Friday, April 9, 2010

Przestrzenie ostro 2-przechodnie. Wektory.

Opieram niniejszą notkę na poprzedniej: Przestrzenie ostro k-przechodnie (patrz też Homomorfizm indukowany przez zbiór niezmienniczy (...)). Będę opuszczał indeks dolny w XifG, na przykład pisząc po prostu Xif(O) zamiast XifG(O).

Niech (X G) będzie skończoną, n-elementową, ostro 2-przejściową przestrzenią, gdzie n ≥ 2. Wtedy grupa G jest następującą unią mnogościową:

        G = {IdX} ∪ ({ Xif_O \ {IdX}} : O ∈ X } ∪ V(G)

gdzie V(G) jest zbiorem wszystkich permutacji g ∈ G, które nie mają punktu stałego; będziemy te permutacje g ∈ V(G) nazywali (niezerowymi) wektorami.

Ponieważ zbiory Xif_O \ {IdX} są parami rozłączne, oraz jest ich n, to ich unia liczy sobie n ⋅ (n-2) elementów. Zatem

        |V(G)| = n-1

oraz dla zbioru wszystkich wektorów, łącznie z zerowym IdX, t.j. dla

        A(G) := V(G) ∪ {IdX}

otrzymujemy:

        |A(G)| = n

Pokażę teraz, że dla dowolnych O E ∈ X istnieje (dokładnie jeden) wektor w ∈ A(G) taki, że w(O) = E. Rzeczywiście, gdy O = E, to twierdzenie jest trywialne (wektor jest zerowy, IdX). Niech więc O ≠ E. Istnieje v ∈ V(G), gdyż n > 1. Niech P := v(O), więc P ≠ O. Istnieje więc (dokładnie jedna) permutacja g ∈ Xif(O) taka, że g(P) = E. Zdefiniujmy:

        w = g o v o g-1.

Wtedy w jest wektorem (nietrywialnym, gdy v jest nietrywialnym), w ∈ V(G), oraz:

        w(O) = (g o v)(g-1(O)) = (g o v)(O) = g(E) = p

Widzimy, że rzeczywiście dla dowolnych O E ∈ X istnieje wektor w ∈ A(G) taki, że w(O) = E. Przy tym dla ustalonego O istnieje takich wektorów co najmniej n (po jednym dla każdego E ∈ X). Ponieważ jest wszystkich wektorów dokładnie n, to dla każdego E ∈ X może istnieć co najwyżej jeden wektor w, spełniający w(O) = E. Zatem dla każdego E ∈ X istnieje dokładnie jeden wektor w ∈ A(G), taki że w(O) = E. Koniec dowodu.

Kulminacją powyższych rozważań jest następujący wynik (stosujemy wcześniejsze założenia i notację dotyczącą X G V(G) A(G)):

TWIERDZENIE 0 (X A(G)) jest ostro 1-przechodnią przestrzenią.

DOWÓD
Wiemy, że |A(G)| = |X| = n, oraz że zbiór A(G) jest ostro 1-przechodni, w sensie:

        ∀ x y ∈ X ∃! v ∈ A(G) v(x) = y

gdzie symbol ∃! oznacza "istnieje dokładnie jeden". Pozostało dowieść, że A(G) jest podgrupą permutacji (grupy G).

(i) IdX ∈ A(G) jest elementem neutralnym względem kompozycji (działania grupowego) - czyli jest tym co zwykle nazywa się jednością (lub zerem przy notacji addytywnej).

(ii) Niech v ∈ A(G). Wtedy permutacja odwrotna, v-1, jest równa IdX lub nie ma punktów stałych, tak jak v. W obu przypadkach v-1 ∈ A(G).

(iii) Niech v w ∈ A(G). Jeżeli (w o v)(x) ≠ x dla każdego x ∈ X, to w o v ∈ A(G). W przeciwnym wypadku istnieje a ∈ X, spełniające (w o v)(a) = a. Oznacza to, że:

        w(v(a)) = a = v-1(v(a)), gdzie v-1 ∈ A(G).

Na mocy ostrości A(G): w = v-1 czyli w o v = IdX ∈ A(G). Koniec DOWODU

Sunday, April 4, 2010

Przestrzenie ostro k-przechodnie

Grupę wszystkich bijekcji zbioru X na siebie oznaczamy przez Sym(X).

Niech X będzie dowolnym zbiorem oraz k liczbą naturalną (1 2 ...). Podgrupę G grupy Sym(X) nazywamy ostro k-przechodnią (lub ostro k-tranzytywną), gdy dla każdych dwóch ciągów uporządkowanych (x1 ... xk) i (y1 ... yk), złożonych z różnych k elementów zbioru X -- t.zn.

    |{x1 ... xk}| = |{y1 ... yk}| = k

-- istnieje dokładnie jedno g ∈ G, takie że g(xj) = yj dla każdego j = 1 ... k. Przestrzenią ostro k-przechodnią nazywamy parę uporządkowaną (X G), złożoną ze zbioru X, o co najmniej k elementach, |X| ≥ k, i z ostro k-przechodniej grupy G w X.

Gdy zbiór X jest skończony, to dla n := |X| ≥ k rząd grupy G dany jest wzorem:

    |G|  =  n ⋅ (n-1) ⋅ ... ⋅ (n-k+1)  =  (n ## k) ⋅ k!

gdzie (n ## k) jest dwumianowym współczynnikiem Newtona.

UWAGA 0 Dodatkowo ciekawe rzeczy dzieją się, gdy ze zbiorem X związana jest dodatkowa struktura, na przykład geometryczna.


Punkty stałe i przestrzenie indukowane
======================================


Niech g : X --> X będzie dowolną funkcją. Wprowadźmy oznaczenie:

        Fix(g) := { x ∈ X : g(x) = x }

czyli Fix(g) jest zbiorem punktów stałych przekształcenia g. Ogólniej, dla dowolnego zbioru H przekształceń g : X --> X rozpatruje się też zbiór ich wspólnych punktów stałych:


        Fix(H) := { x ∈ X : ∀ g ∈ H g(x) = x }

Niech teraz G będzie dowolną grupą bijekcji zbioru X na siebie. W duchu Galois, wprowadźmy pojęcia dualne:

        XifG(a) := { g ∈ G : g(a) = a }

oraz

        XifG(A) := { g ∈ G : ∀ a ∈ A g(a) = a }

dla dowolnych a ∈ X oraz A ⊆ X. Widzimy, że:

        Fix(H) = g ∈ H Fix(g)
        XifG(A) = a ∈ A XifG(a)

więc na przykład:

        XifG(A ∪ B) = XifG(A) ∩ XifG(B)

Oczywiście XifG(a) oraz XifG(A) są podgrupami grupy Sym(X). Jeżeli g ∈ Sym(X), to:

    g o XifG(a) o g-1 = XifG(g(a))
    g o XifG(A) o g-1 = XifG(g(A))

dla a ∈ X, A ⊆ X, gdzie z definicji:

        g o H o g' := { g o h o g' : h ∈ H } dla H ⊆ Sym(X);
        g(A) := { g(x) : x ∈ A }

Odwzorowanią Fix i XifG są antymonotoniczne względem inkluzji. Ponadto zachodzą inkluzje domykania:

        Fix(XifG(A)) ⊇ A   dla każdego A ⊆ X
        XifG(Fix(H)) ⊇ H   dla każdego H ⊆ G

Ogólnie, tego typu dwie odpowiedniości antymonotoniczne i domykające algebraik A.G.Kurosz nazywał odpowiedniościami Galois. Zachodzi dla nich twierdzenie (mood improver):

        XifGFix(XifG(A))) = XifG(A)   dla każdego A ⊆ X
        Fix(XifG(Fix(H))) = Fix(H)   dla każdego H ⊆ G

Zdefiniujmy domknięcia zbiorowe i grupowe:

        Cls(A) := Fix(XifG(A))   dla każdego A ⊆ X
        Clg(H) := XifG(Fix(H))   dla każdego H ⊆ G

Mówimy, że A ⊆ X jest domknięte, gdy Cls(A) = A; oraz że H ⊆ G jest domknięte, gdy Clg(H) = H. Zatem Fix(H) i Xif(A) są domknięte odpowiednio w X i G dla dowolnego H ⊆ G i A ⊆ X. Ponadto zachodzą własności (aksjomaty) Kuratowskiego:

        A ⊆ Cls(A)   dla każdego A ⊆ X
        H ⊆ Clg(H)   dla każdego H ⊆ G

oraz:

        Cls(Cls(A)) = Cls(A)   dla każdego A ⊆ X
        Clg(Clg(H)) = Clg(H)   dla każdego H ⊆ G

UWAGA 1 Na ogół nie zachodzi dla powyższych operacji domknięcia krytyczny aksjomat Kuratowskiego, typu: Cl(K ∪ L) = Cl(K) ∪ Cl(L). Wynika z niego natychmiast monotoniczność:

        K ⊆ L   ==>   Cl(K) ⊆ Cl(L)

Jednak monotoniczność Cls oraz Clg i tak zachodzi, gdyż operacje te są kompozycją dwóch antymonotonicznych przekształceń FiX i XifG.


UWAGA 2 Dla zbioru pustego ∅ zachodzi:

        Fix(∅) = X   oraz   XifG(∅) = G

zgodnie zresztą z antymonotonicznością.

UWAGA 3 Gdybyśmy zajmowali się podstawami matematyki (logiką, teorią mnogości, ...), to należałoby pisać raczej Fix({g}) oraz XifG({a}) dla pojedynczych g ∈ G oraz a ∈ X, bo notacja Fix(g) oraz Xif(a) byłaby niebezpieczna, czasem byłaby dwuznaczna. Bowiem ogólnie ten sam obiekt może być jednocześnie elementem i podzbiorem tego samego zbioru X lub G.




Niech (X G) będzie n-elementową ostro k-przechodnią przestrzenią. Niech A będzie α-elementowym podzbiorem zbioru X, przy czym niech 0 < α < k. Wtedy

        H  :=  { g|X\A : g ∈ XifG(A) }

jest ostro (k-α)-przechodnią grupą permutacji w X\A, czyli (X\A H) jest (n-α)-punktową, ostro (k-α)-przechodnią przestrzenią. Zatem

    |H| = (n-α) ⋅ ... ⋅ (n-k+1) = (n-α ## k-α) ⋅ (k-α)!

Saturday, April 3, 2010

Homomorfizm indukowany przez zbiór niezmienniczy (teoria grup)

Niech G = (G ⋅ -1 e) będzie dowolną grupą, gdzie e ∈ G jest jednością.

Zbiór T ⊆ G nazywamy niezmienniczym (w grupie G), gdy


    x ⋅ t ⋅ x-1 ∈ T dla dowolnego t ∈ T oraz x ∈ G.


Przykład 0 Każda podgrupa niezmiennicza grupy G jest zbiorem niezmienniczym.


Przykład 1 Niech

    Inv(G) := { x ∈ G : x2 = e } - jest to zbiór wszystkich elementów-inwolucji grupy G. Nietrudno sprawdzić, że inwolucje stanowią zbiór niezmienniczy. Ponadto iloczyn dwóch inwolucji, a ⋅ b, jest inwolucją ⇔ gdy te inwolucje są przemienne,  a ⋅ b = b ⋅ a.  Zatem, gdy każde dwie inwolucje są przemienne, i tylko wtedy, zbiór Inv(G) stanowi podgrupę - oczywiście normalną i przemienną.



Niech T będzie niepustym zbiorem niezmienniczym. Niech Sym(T) bedzie zbiorem wszystkich bijekcji zbioru T (czyli permutacji, gdy T jest skończone). Sym(T) jest grupą ze względu na działanie kompozycji funkcji, ο. Dla dowolnego g ∈ G otrzymujemy bijekcję

    Fg : T --> T

zadaną wzorem: Fg(t) := g ⋅ t ⋅ g-1, dla dowolnego t ∈ T (jest to obcięcie automorfizmu wewnętrznego grupy G do zbioru T). Zachodzą wzory:

(i) Fe  =  IdT
(ii) (Fg)-1 = Fg-1
(iii) Fh ο Fg = Fh ο g

(gdzie przez (Fg)-1 rozumie się tu odwrotność Fg w Sym(T), względem kompozycji funkcji). Własności (i) (ii) (iii) oznaczają, że przyporządkowanie F :G --> Sym(T), dane wzorem:

    F : g |--> Fg

jest homomorfizmem grupy G w grupę Sym(T).

Uwaga 0 Powyższa własność (ii) wynika z kombinacji własności (i) i (iii).

Gdy T jest podgrupą normalną i przemienną grupy G, to Ft = IdT dla dowolnego t ∈ T, czyli T jest zawarte w jądrze homomorfizmu F. Zatem F indukuje homomorfizm

    Φ : G/T --> Sym(T)

-- to znaczy, F = Φ ο π, gdzie π : G --> G/T jest homomorfizmem ilorazowym.

Dodatek: Grupy Inwolucji
===============================================


Grupa G, której każdy element jest inwolucją (jest rzędu 1 lub 2), jest abelowa. Nazwijmy więc jej element jednostkowy zerem, 0, a operację grupową dodawaniem, +. Jest jasnym, że G w sposób jednoznaczny dopuszcza strukturę przestrzeni wektorowej nad ciałem dwuelementowym. Taka grupa, czyli przestrzeń wektorowa nad ciałem 2-elementowym, ma bazę liniową B, co w przypadku skończonej grupy G oznacza, że jej rząd jest potęgą 2:

    |G| = 2|B|

Oczywiście każda podgrupa grupy inwolucji, jak i grupa ilorazowa, sama jest grupą inwolucji, więc ma podobne własności; w szczególności jej rząd jest potęgą 2.