Darmowa krata - Free lattice

W matematyce , w obszarze teorii porządku , wolna sieć jest swobodnym obiektem odpowiadającym kracie . Jako obiekty swobodne mają one właściwość uniwersalną .

Definicja formalna

Dowolny zestaw X może zostać użyty do wygenerowania wolnego efektu semilattice . Wolną semilattice określa się składać się ze wszystkich skończonych podzbiorów z X , z semilattice działania danego zwykłą zestaw jedności . Swobodna półlatka ma właściwość uniwersalną . Uniwersalny morfizmem jest ( FX , η) , gdzie η jest jednostką mapa η: X → FX która odbywa x ∈ X do jednoelementowy zbiór { x }. Właściwość uniwersalna jest zatem następująca: dana dowolna mapa f : X → L od X do pewnego dowolnego semilattice L istnieje unikalny semilattice homomorfizm tak, że . Mapa może być wyraźnie spisana; jest dany przez ${\ displaystyle {\ tilde {f}}: FX \ do L}$${\ displaystyle f = {\ tilde {f}} \ circ \ eta}$${\ displaystyle {\ tilde {f}}}$

${\ Displaystyle S \ w FX \ mapsto \ bigvee \ lewo \ {f (s) \ mid s \ in S \ prawo \}}$

gdzie oznacza operację semilattice w L . Ta konstrukcja może być promowana od półlatych do krat ; ze względu na konstrukcję mapa będzie miała takie same właściwości jak krata. ${\ displaystyle \ bigvee}$${\ displaystyle {\ tilde {f}}}$

Konstrukcja X ↦ FX jest więc funktorem z kategorii zbiorów do kategorii krat. Funktor F jest połączony z funktorem zapominalskim od krat do ich zbiorów bazowych. Wolna krata jest swobodnym przedmiotem .

Problem słowny

Przykładowe obliczenia x ∧ z ~ x ∧ z ∧ ( x ∨ y )

x ∧ z ∧ ( x ∨ y ) ≤ ~ x ∧ z przez 5. od x ∧ z ≤ ~ x ∧ z przez 1. od x ∧ z = x ∧ z

x ∧ z ≤ ~ x ∧ z ∧ ( x ∨ y ) przez 7. od x ∧ z ≤ ~ x ∧ z i x ∧ z ≤ ~ x ∨ y przez 1. od x ∧ z = x ∧ z przez 6. od x ∧ z ≤ ~ x przez 5. od x ≤ ~ x przez 1. od x = x

Zadanie tekstowe dla darmowych kratownic ma kilka interesujących aspektów. Rozważmy przypadek ograniczonych krat , czyli struktur algebraicznych z dwiema operacjami binarnymi ∨ i ∧ oraz dwiema stałymi ( operacje zerowe ) 0 i 1. Zbiór wszystkich dobrze sformułowanych wyrażeń, które można sformułować za pomocą tych operacji na elementach z podanej zestaw generatorów X będzie nazywany W ( X ). Ten zestaw słów zawiera wiele wyrażeń, które okazują się oznaczać równe wartości w każdej sieci. Na przykład, jeśli a jest jakimś elementem X , to a  ∨ 1 = 1 i a  ∧ 1 = a . Zadanie tekstowe dla sieci o swobodnym ograniczeniu polega na określeniu, które z tych elementów W ( X ) oznaczają ten sam element w FX sieci swobodnej , a zatem w każdej sieci ograniczonej.

Problem tekstowy można rozwiązać w następujący sposób. Relację ≤ _~ na W ( X ) można zdefiniować indukcyjnie , ustawiając w ≤ _~ v wtedy i tylko wtedy, gdy zachodzi jeden z poniższych warunków:

1.   w = v (można to ograniczyć do przypadku, gdy w i v są elementami X ),
2.   w = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ i oba w ₁ ≤ _~ v i w ₂ ≤ _~ v trzymaj,
5.   w = w ₁ ∧ w ₂ i albo w ₁ ≤ _~ v lub w ₂ ≤ _~ v trzyma się,
6.   v = v ₁ ∨ v ₂ i albo w ≤ _~ v ₁ lub w ≤ _~ v ₂ trzyma się,
7.   v = v ₁ ∧ v ₂ i oba w ≤ _~ v ₁ i w ≤ _~ v ₂ ładowni.

To definiuje zamówienie wstępne ≤ _~ na W ( X ), więc relację równoważności można zdefiniować przez w ~ v, gdy w ≤ _~ v i v ≤ _~ w . Można wtedy wykazać, że częściowo uporządkowana przestrzeń ilorazowa W ( X ) / ~ jest swobodną ograniczoną przestrzenią sieciową FX . Do klas równoważności z W ( X ) / ~ są zestawy wszystkich słów w i v o szer ≤ _~ v i v ≤ _~ wag . Dwa poprawnie sformułowane słowa v i w w W ( X ) oznaczają tę samą wartość w każdej ograniczonej sieci wtedy i tylko wtedy, gdy w ≤ _~ v i v ≤ _~ w ; te ostatnie warunki można skutecznie określić przy użyciu powyższej definicji indukcyjnej. W tabeli przedstawiono przykładowe obliczenia pokazujące, że słowa x ∧ z i x ∧ z ∧ ( x ∨ y ) oznaczają tę samą wartość w każdej ograniczonej sieci. Przypadek nieskrępowanych krat jest traktowany podobnie, pomijając reguły 2. i 3. w powyższej konstrukcji.

Rozwiązanie zadania tekstowego na swobodnych kratach ma kilka interesujących następstw. Jednym z nich jest to, że swobodna sieć trójelementowego zestawu generatorów jest nieskończona. W rzeczywistości można nawet wykazać, że każda wolna sieć na trzech generatorach zawiera podsieć, która jest wolna dla zestawu czterech generatorów. Dzięki indukcji ostatecznie uzyskuje się podwarstwę wolną od licznie wielu generatorów. Ta właściwość przypomina uniwersalność SQ w grupach .

Dowód na to, że wolna sieć w trzech generatorach jest nieskończony, wynika z definicji indukcyjnej

p _{n +1} = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p _n )))))

gdzie x , y i z to trzy generatory, a p ₀ = x . Następnie można pokazać, używając indukcyjnych relacji problemu tekstowego, że p _{n +1} jest ściśle większe niż p _n , a zatem wszystkie nieskończenie wiele słów p _{n jest} ocenianych do różnych wartości w swobodnej siatce FX .

Pełna darmowa krata

Innym następstwem jest to, że cała sieć swobodna (na trzech lub więcej generatorach) „nie istnieje” w tym sensie, że jest to właściwa klasa . Dowód na to wynika również z problemu tekstowego. Aby zdefiniować pełną siatkę w stosunkach, to nie wystarczy, aby skorzystać z finitary relacje z spotykają się i dołącz ; trzeba też mieć nieskończone relacje określające spotkanie i połączenie nieskończonych podzbiorów. Na przykład relacja nieskończona odpowiadająca „złączeniu” może być zdefiniowana jako

${\ displaystyle \ operatorname {sup} _ {N} :( f: N \ do FX)}$

Tutaj f jest mapą z elementów kardynała N do FX ; operator oznacza supremum, ponieważ przyjmuje obraz f do jego złączenia. Jest to oczywiście identyczne z „złączeniem”, gdy N jest liczbą skończoną; celem tej definicji jest zdefiniowanie sprzężenia jako relacji, nawet jeśli N jest nieskończonym kardynałem. ${\ displaystyle \ operatorname {sup} _ {N}}$

Do aksjomatów wstępnego uporządkowania zadania tekstowego mogą przylegać dwa nieskończone operatory odpowiadające spotkaniu i złączeniu. Po wykonaniu tej czynności rozszerza się definicję do normalnie indeksowanej przez ${\ displaystyle p_ {n}}$${\ displaystyle p _ {\ alpha}}$

${\ Displaystyle p _ {\ alpha} = \ operatorname {sup} \ {p _ {\ beta} \ mid \ beta <\ alpha \}}$

kiedy jest limitem porządkowym . Wtedy, jak poprzednio, można wykazać, że jest to ściśle większe niż . Tak więc w pełnej sieci swobodnej jest co najmniej tyle elementów, ile jest liczb porządkowych, a zatem cała sieć swobodna nie może istnieć jako zbiór i dlatego musi być odpowiednią klasą. ${\ displaystyle \ alpha}$${\ displaystyle p _ {\ alpha +1}}$${\ displaystyle p _ {\ alpha}}$

Bibliografia

• Peter T. Johnstone, Stone Spaces , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ( ISBN   0-521-23893-5 ) (patrz rozdział 1)