Kafes (sıra teorisi)

Kafes veya örgü, matematikte özellikle sıra kuramı ve soyut cebir alanlarında incelenen temel yapılardan biridir. Kafes, her iki elemanının hem en büyük alt sınırını (meet, ∧) hem de en küçük üst sınırını (join, ∨) belirlemenin mümkün olduğu kısmi sıralı kümeler temelinde tanımlanır. Bu yönüyle kafesler, hem sıralı yapıların hem de cebirsel işlemlerin bir araya geldiği bir çerçeve sunar.

Kafes yapıları, küme kuramından sayı teorisine, mantıksal sistemlerden bilgisayar bilimine kadar birçok farklı disiplinde doğal olarak karşımıza çıkar. Örneğin bir kümenin kuvvet kümesi, alt küme ilişkisiyle kısmi sıralanmış bir kafes oluşturur; burada birleşim işlemi join, kesişim işlemi ise meet olarak işlev görür. Benzer şekilde, doğal sayılar kümesi de bölünebilme ilişkisiyle bir kafes oluşturur; burada en küçük ortak kat join’e, en büyük ortak bölen ise meet’e karşılık gelir.

Kafesler yalnızca sıralı yapılar olarak değil, aynı zamanda iki işlemi yani birleşim (join) ve kesişim (meet) taşıyan cebirsel sistemler olarak da tanımlanabilir. Bu iki yaklaşım birbirine denktir ve kafes kuramı her iki perspektifi de birleştirir. Kafeslerin daha genel hali olan yarı-kafesler, yalnızca tek bir birleşim ya da kesişim işlemini gerektirirken; tam kafesler, bu iki işlemi birden gerektirir. Öte yandan Heyting cebirleri ve Boole cebirleri, kafeslerin mantıksal yorumlara sahip özel türleridir.

Bu bağlamda kafes kuramı, soyut cebirin bir alt dalı olarak bu yapıların özelliklerini, örneklerini ve uygulamalarını sistematik biçimde inceler.

 Tanımı 
Bir kafes yapısı hem bir kısmi sıralı küme olarak sıra kuramı kapsamında hem de bir cebirsel yapı olarak tanımlanabilir.

 Kısmi sıralı küme olarak 
Teknik olarak, kısmi sıralı bir küme  (poset olarak kısaltılabilir) ele alındığında, eğer her iki eleman için hem en küçük ortak üst sınır (birleşim, ∨) hem de en büyük ortak alt sınır (kesişim, ∧) tanımlıysa, bu yapı bir kafes olarak adlandırılır. Yani, ’nin her iki elemanlı alt kümesi   için bir birleşim  (yani en küçük üst sınır,  ile gösterilir) ve buna karşılık gelen bir kesişim  (yani en büyük alt sınır,  ile gösterilir) tanımlıdır. Örneğin, bir kümenin tüm alt kümelerinden oluşan kuvvet kümesi, alt kümeler arasındaki kapsama (dahil olma) ilişkisiyle kısmi sıralanmıştır; burada birleşim işlemi küme birleşimine, kesişim ise küme kesişimine karşılık gelir. Bu tanım, ∧ ve ∨ işlemlerini dualite prensibine uygun ikili işlemler haline getirir. Bir kafesin birleşim ve kesişim işlemleri, sıralamaya uyumlu yani monotoniktir; bu, elemanlar sıralama içinde büyürken işlemlerin de aynı yönde "büyüdüğü" anlamına gelir: Eğer  ve ise, o zaman  ve  eşitsizlikleri sağlanır.

Bir tümevarım argümanıyla gösterilebilir ki, bir kafesin boş olmayan her sonlu alt kümesi, bir en küçük üst sınıra ve bir en büyük alt sınıra sahiptir. Ek varsayımlar altında daha ileri sonuçlara ulaşılabilir; bu konunun ayrıntıları için Tamlık başlığına bakılabilir. Aynı makalede, yukarıdaki tanımın, ilişkili kısmi sıralı kümeler arasında uygun Galois bağlantılarının varlığı üzerinden nasıl yeniden ifade edilebileceği de ele alınır. Bu yaklaşım, özellikle kategoriler kuramı bağlamında kafeslere yönelik çalışmalarda ve biçimsel kavram çözümlemesi alanında önem taşır.

Bir kafesin herhangi bir alt kümesi  üzerinde birleşim ve kesişim işlemleri her zaman tanımlı olmayabilir. Bu durumda, sadece bazı durumlarda bu işlemler yapılabiliyorsa, bu yapı kısmi kafes olarak adlandırılır. Yani kısmi kafeste birleşim ve kesişim işlemleri kısmi fonksiyonlardır; her zaman sonuç kümenin içinde olmayabilir. Eğer işlemin sonucu 'de değilse, tanımsız kabul edilir. Kısmi kafesler, ya bir kafesin alt kümeleri olarak tanımlanabilir, ya da doğrudan belirli aksiyomları sağlayan kısmi işlemler olarak içsel biçimde ele alınabilir.

 Cebirsel yapı olarak 
Kafes,  biçiminde tanımlanan bir cebirsel yapıdır; burada  bir küme,  ve  ise  üzerinde tanımlı iki değişmeli ve birleşmeli işlemlerdir. Bu işlemler, tüm elemanlar  için aşağıdaki aksiyomatik özdeşlikleri sağlar (bazen “absorpsiyon kanunu” olarak adlandırılır):

Her ne kadar aşağıdaki iki eşitlik de, iki absorbsiyon kanununun birlikte alınmasıyla türetilebilir olsa bile sıklıkla aksiyom olarak kabul edilir. Bu biçimdeki özdeşlikler "etkisizlik kanunları" olarak adlandırılır.  

Bu aksiyomlar,  ve  yapılarını yarı-kafesler haline getirir. Yukarıdaki aksiyomlar içinde hem kesişim hem birleşimin birlikte yer aldığı tek aksiyomlar olan absorpsiyon kanunları, kafesi rastgele iki yarı-kafes çiftinden ayırır ve bu iki yarı-kafesin uygun şekilde etkileşmesini sağlar. Özellikle, her yarı-kafes diğerinin dualidir. Absorpsiyon kanunu, kesişim ve birleşim yarı-kafeslerinin aynı kısmi sıralamayı tanımlaması gerektiği şartı olarak da görülebilir.

 İki tanım arasındaki bağlantı 
Sıralama kuramsal bir kafes,  ve  olmak üzere iki ikili işlem ortaya çıkarır. Bu işlemler için değişmeli, birleşmeli ve absorpsiyon kanunlarının kolayca doğrulanabilmesi nedeniyle,  cebirsel anlamda bir kafes oluşturur.

Tersi de doğrudur. Cebirsel olarak tanımlanmış bir kafes  verildiğinde,   üzerinde kısmi bir sıralama  'nin tüm elemanları için  şöyle tanımlanabilir: Absorpsiyon kanunları, bu iki tanımın birbirine eşdeğer olduğunu garanti eder:ve benzer biçimde diğer yönde de geçerlidir.

Böylece tanımlanan  ilişkisi, orijinal  and  işlemleriyle uyumlu olan bir kısmi sıralamayı ifade eder; yani bu sıralama altında ikili kesişim  ve birleşim işlemleri ilk verilen  and  işlemleriyle sağlanır.

Kafesin iki tanımı eşdeğer olduğundan, hangi tanımı kullanmak amaç açısından uygunsa serbestçe tercih edilebilir ve tanımların her iki yönü de kullanılabilir.

 Sınırlı kafes 
Bir sınırlı yani alt ve üst sınırı bulunan kafes aşağıdaki formülü sağlayan en küçük ve en büyük elemanı sırasıyla 0 (⊥) ve 1 veya (⊤) öğeleri olan bir kafes türüdür.

Bir sınırlı kafes tıpkı  kafesinde olduğu gibi  cebirsel form yapısında, kafesin en küçük elemanı olan  birleşim işlemi  için, en büyük elemanı olan  ise kesişim işlemi  için etkisiz elemandır.Kısmi sıralı kümenin bir sınırlı kafes oluşu eğer ve sadece her belirli elemanlar kümesinin (boş küme dahil) kesişim ve birleşim işlemine sahip olduğu gösterilebilir.

Her kafes, en büyük ve en küçük birer eleman eklenerek bir sınırlı kafes içine yerleştirilebilir. Ayrıca, boş olmayan her sonlu kafes zaten doğası gereği sınırlıdır; çünkü tüm elemanların birleşimi alınarak en büyük eleman  ve tüm elemanların kesişimi alınarak en küçük eleman   elde edilir. Burada  kafesteki tüm elemanları içeren kümedir.

 Diğer cebirsel yapılarla olan ilişkisi 
Kafeslerin, grup benzeri cebirsel yapılar ile bazı ilişkileri bulunmaktadır. Bunun nedeni birleşim ve kesişim işlemleri hem değişmeli hem de birleşmeli  olduğundan, bir kafes, aynı evrende tanımlı iki değişmeli yarıgruptan oluşan bir yapı olarak düşünülebilir. Eğer kafes sınırlıysa (yani 0 ve 1 elemanları varsa), bu yarıgruplar aslında değişmeli monoidlerdir.

Absorbsiyon yasası, yalnızca kafes teorisine özgü olan tek tanımlayıcı özelliktir. Ayrıca, bir sınırlı kafes, dağılım özelliği olmadan tanımlanmış bir değişmeli halka olarak da düşünülebilir.

Değişme, birleşme ve etkisizlik özellikleri sayesinde, birleşim ve kesişim işlemleri ikili elemanlar yerine boş olmayan sonlu kümeler üzerinde tanımlı işlemler olarak da görülebilir. Sınırlı kafeslerde boş kümenin birleşimi ve kesişimi de sırasıyla 0 ve 1 olarak tanımlıdır. Bu özellik, sınırlı kafesleri genel kafeslere kıyasla daha ‘doğal’ yapar ve bu nedenle birçok yazar, her kafesin sınırlı olmasını varsayar.

Kafeslerin cebirsel yorumu, evrensel cebir alanında temel bir rol oynar.

 Örnekler 

 Herhangi bir  kümesi için, 'nın tüm altkümelerinden oluşan koleksiyon (yani 'nın kuvvet kümesi), alt küme kapsaması ilişkisine göre sıralandığında, boş küme ve 'nın kendisi tarafından sınırlandırılmış bir kafes elde edilir. Bu kafeste küme birleşimi en küçük üst sınırı, küme kesişimi ise en büyük alt sınırı verir. (Bkz. Şekil 1) 
 Herhangi bir  kümesi için, 'nın tüm sonlu alt kümelerinden oluşan ve kapsama ilişkisine göre sıralanan küme de bir kafestir. Bu kafes,  yalnızca sonluysa sınırlıdır.
 Herhangi bir  kümesi için, 'nın tüm küme bölünmesi, inceltilme hali ilişkisine göre sıralandığında bir kafes oluşturur (Bkz. Şekil 3).
 Pozitif tamsayılar, klasik ≤ sıralaması altında "min" ve "max" işlemleriyle bir sınırsız kafes oluşturur. 1 en küçük elemandır; en büyük eleman yoktur (Bkz. Şekil 4).
 Doğal sayıların Kartezyen çarpımı,  olacak şekilde sıralanır; bu,  ve  anlamına gelir. Bu yapıda  en küçük elemandır; en büyük eleman yoktur (Bkz. Şekil 5).
 Doğal sayılar ayrıca bölenlik ilişkisi altında da bir kafes oluşturur:  yalnızca , 'yi bölüyorsa geçerlidir. Bu durumda en büyük ortak bölen (GCD) en küçük üst sınır, en küçük ortak kat (LCM) ise en büyük alt sınır olur. 1 en küçük, 0 ise en büyük elemandır. Şekil 2, bu yapının sonlu bir alt kafesini gösterir.
 Her tam kafes (bununla ilgili daha fazla bilgi için aşağıdaki Tamlık bölümüne bakınız), belirli bir türde sınırlı kafestir. Bu sınıf, birçok pratik örneğe kaynaklık eder.
 Bir aritmetik tam kafesin kompakt elemanları kümesi, kafes işlemleri aritmetik kafesin işlemleriyle sınırlanmış olacak şekilde, en küçük elemana sahip bir kafes oluşturur. Bu özellik, aritmetik kafesleri yalnızca birleşim yarı-kafesi oluşturan kompakt elemanlara sahip cebirsel kafeslerden ayıran temel farktır. Bu iki kafes türü de alan kuramı içinde incelenir.

 Kafes olmayan örnekler 
küçükresim|155x155pik|Şekil 8: Kafes olmayan bir kısmi sıralı küme:  ve  öğeleri için ortak alt sınırlar  ve 'dir; ancak bunlardan hiçbiri en büyük alt sınır  değildir.
küçükresim|177x177pik|Şekil 7: Kafes olmayan bir kısmi sıralı küme: ve  öğeleri için ortak üst sınırlar  ve 'tir; ancak bunlardan hiçbiri en küçük üst sınır değildir.
küçükresim|150x150pik|Şekil 6: Kafes olmayan bir kısmi sıralı küme: ve  öğelerinin hiç ortak üst sınırı yoktur.
Çoğu kısmi sıralı küme, bir kafes yapısına sahip değildir. Bunlara şu örnekler verilebilir:

 Ayrık (discrete) kısmi sıralı küme:  yalnızca  durumunda geçerliyse, bu kümeye ayrık poset denir. Böyle bir poset yalnızca bir ya da sıfır öğe içeriyorsa kafes olabilir. Örneğin, iki öğeli ayrık poset bir kafes değildir.
 Bölünebilirlik ile sıralanmış sayılar: Küme  bölünebilirlik ilişkisiyle sıralandığında bir kafestir. Ancak kümesi, aynı şekilde sıralandığında bir kafes değildir. Çünkü 2 ve 3'ün birleşimi yani en küçük ortak katları bu kümede yoktur.  Benzer şekilde,  kümesinde 2 ve 3'ün kesişimi yani en büyük ortak böleni bulunmamaktadır.
 Küme : Bu küme de bölünebilirlik sırasına göre bir kafes değildir. Örneğin, 2 ve 3'ün ortak üst sınırları 12, 18 ve 36'dır. Ancak bunların hiçbiri diğerlerini bölmediği için en küçük üst sınır olamaz. Aynı şekilde, 12 ve 18'in ortak alt sınırları 1, 2 ve 3'tür, ancak bunlardan hiçbiri diğerlerini bölmediği için en büyük alt sınır olamaz. 

 Kafes morfizmleri 
küçükresim|Şekil 9: Kafesler arasında tanımlanmış monoton bir fonksiyon , birleşim ve kesişim işlemlerini korumamaktadır. Örneğin:

   and   
Kafesler arasında bir morfizma (homomorfizma) tanımı, cebirsel tanımdan kolayca elde edilir.

İki kafes verildiğinde: ve  bir kafes homomorfizması olan  fonksiyonu,  için aşağıdaki koşulları sağlamalıdır:

Bu durumda , her iki alt-yarı-kafesin de homomorfizması olur. Kafesler ilave yapılara sahipse (örneğin sıfır ve bir öğeleri gibi), morfizmaların bu yapıları da koruması gerekir. Özellikle, sınırlı kafesler arasında tanımlanan homomorfizmalar (genellikle doğrudan "kafes homomorfizması" denir), iki sınırlı kafes olan ve  arasındaki  şu koşulları da sağlamalıdır:Kısmi sıralama bağlamında bu koşullar, fonksiyonun ikili birleşim ve kesişimi koruması anlamına gelir. Sınırlı kafesler için 0 ve 1'in korunması, boş kümenin birleşimi ve kesişiminin korunması ile eşdeğerdir. Her kafes homomorfizması, ilişkili sıralama (≤) ile uyumlu olacak şekilde monoton bir fonksiyondur. Ancak yalnızca monoton olmak yeterli değildir çünkü birleşim ve kesişimi korumayan monoton fonksiyonlar homomorfizma değildir (bkz. Şekil 9).

İzomorfizmler standart olarak tersinir morfizmalar olarak tanımlanır. Bu çerçevede bir kafes izomorfizması, sadece bire bir bir kafes homomorfizmasıdır.

Benzer şekilde:

 Bir kafes endomorfizması, bir kafesin kendisine tanımlanan bir kafes homomorfizmasıdır.
 Bir kafes otomorfizması ise, birebir örten bir kafes endomorfizmasıdır (yani, kafesin kendisine bire bir ve yapı koruyucu dönüşüm).

Kafesler ve bunların homomorfizmaları birlikte bir kategori oluşturur. Bu, kategori kuramında önemli bir yapıdır; nesneler kafeslerdir, morfizmalar ise bu kafesler arasındaki homomorfizmalardır.

Varsayalım ki:

  ve  iki 0 ve 1 öğelerine sahip kafeslerdir (yani sınırlı kafesler).

Bu iki kafes arasında tanımlanmış bir homomorfizma :→, “0,1-ayıran” olarak adlandırılır ancak ve ancak aşağıdaki koşullar sağlanır:

  (yani yalnızca 0 öğesi 0'a gider – , 0'ı ayırır)
  (yani yalnızca 1 öğesi 1'e gider – , 1'i ayırır)

Bu özellik, homomorfizmanın en küçük (0) ve en büyük (1) öğeleri bozmadan ve başka öğelerle karıştırmadan aktardığını ifade eder. Özellikle kafes izomorfizmalarında bu özellik otomatik olarak sağlanır çünkü izomorfizma hem yapıyı korur hem de bire birdir

 Alt kafesler 

Bir kafesin  altkafesi, o kafesin  bir altkümesidir ve bu altküme, aynı birleşim ∨ ve kesişim ∧ işlemleriyle bir kafes yapısı oluşturuyorsa, altkafes olarak adlandırılır.

Yani, eğer  bir kafes ve  bir altkümeyse ve her  için hem  hem de  olacak şekilde işlem sonuçları yine 'de kalıyorsa, o zaman , ’nin bir altkafesidir.Burris, Stanley N., and Sankappanavar, H. P., 1981. A Course in Universal Algebra.   Springer-Verlag. .

Bir altkafes , konveks bir altkafes olarak adlandırılır ancak ve ancak şu koşulu sağlıyorsa: Her  ve  için eğer  ise, bu durumda  de ’nin içinde olmak zorundadır. İki eleman arasındaki tüm ara değerler de alt kafeste bulunuyorsa, bu alt kafes konveks olarak adlandırılır.

 Kafeslerin özellikleri 
Kafeslerin ilginç özel türlerine ilişkin kimi önemli özellikler aşağıda yer almaktadır. Bunlarda ilki olan sınırlılık yukarıda izah edilmiştir.

 Tamlık 

Bir kısmi sıralı küme (poset), tüm alt kümeleri için hem birleşim ∨ hem de kesişim ∧ varsa, tam bir kafes olarak adlandırılır. Bu tanım gereği, her tam kafes aynı zamanda sınırlı bir kafestir (yani hem en küçük hem de en büyük elemana sahiptir). Sınırlı kafes homomorfizmaları, genelde yalnızca sonlu birleşimleri ve kesişimleri korur. Ancak, tam kafes homomorfizmaları ise herhangi bir (sonsuz dahil) birleşimi ve kesişimi korumak zorundadır.

Herhangi bir kısmi sıralı küme, tam yarı-kafes ise, tam kafes olmak zorundadır. Bu duruma bağlı olarak, bu tür yapılarda farklı homomorfizma tanımlarıyla karşılaşılır; çünkü kısmi sıralı kümenin yapısına şu dört farklı şekilde yaklaşılabilir: Tam kafes, Tam birleşim-yarı-kafesi, Tam kesişim-yarı-kafesi, Birleşimce-tam veya kesişimce-tam bir kafes. Her yaklaşım, homomorfizmanın hangi işlemleri koruması gerektiği açısından farklılık gösterebilir.

"Kısmi kafes" terimi, "tam kafes" kavramının karşıtı değildir. Yani her tam kafes bir kafestir; her kafes bir kısmi kafestir — ancak tersi doğru değildir.

 Koşullu tamlık 

Bir kafes, herhangi bir üst sınırı olan boş olmayan her altkümesinin birleşimi (en küçük üst sınırı) varsa, koşullu olarak tam (conditionally complete) kabul edilir. Bu tür kafesler, reel sayılar kümesindeki tamlık aksiyomunun doğrudan genellemesini oluşturur. Koşullu olarak tam bir kafes şu türlerden biri olabilir: Tam kafes, En büyük elemanı (1) olmayan tam kafes, En küçük elemanı (0) olmayan tam kafes ve Hem 0 hem 1 elemanından yoksun tam kafes.

 Dağılırlılık 
küçükresim|150x150pik|Şekil 11: En küçük modüler olmayan (dolayısıyla dağılırlık göstermeyen) kafes: N5Burada  olduğu halde:

 ,


olduğu için modüler yasa ihlal edilir.

Aynı zamanda bu şekilde etiketlenmiş elemanlar, aşağıdaki dağılırlık denklemini de ihlal eder:Ancak bunun dual (çift) versiyonu sağlanır:
küçükresim|150x150pik|Şekil 10: En küçük dağılırlık göstermeyen (ancak modüler olan) kafes M3.

Kafesler iki ikili işlem içerdiği için, bu işlemlerden birinin diğerine göre dağılıp dağılmadığı sorusu doğar. Yani, aşağıdaki ikili yasaların tüm  için geçerli olup olmadığı incelenir:

∨ işleminin ∧ işlemi üzerine dağılımı:∧ işleminin ∨ işlemi üzerine dağılımı:Bu iki eşitlik aslında birbirine denktir. Eğer bir kafes bu eşitliklerden birini sağlıyorsa, dağılırlık gösteren kafes olarak adlandırılır.6'dan az elemana sahip olan ve dağılırlık göstermeyen tek kafesler M3 ve N5 olarak bilinir., Exercise 4.1, p. 104. Bunlar yukarıdaki şekillerde gösterilmiştir. Bir kafes, yalnızca içinde M3 ya da N5’e izomorf bir alt kafes bulunmuyorsa dağılırlık gösterir., Theorem 4.10, p. 89. Her dağılırlık gösteren kafes, küme kafeslerine (birleşim ∨ ve kesişim ∧ işlemleriyle tanımlı) izomorftur., Theorem 10.21, pp. 238–239.

Tam kafesler için daha özel dağılırlık tanımları da vardır. Bunlar örneğin:

 Frame yapıları
 Tamamen dağılırlık gösteren kafesler

gibi daha gelişmiş yapılara temel oluşturur.

 Modülerlik 

Bazı uygulamalarda dağılırlık koşulu çok katıdır. Bunun yerine daha zayıf fakat faydalı bir koşul olan modülerlik tercih edilir. Bir kafes  aşağıdaki eşitlik tüm  için sağlanıyorsa modüler kabul edilir: Bu eşitlik, şu aksiyoma da denktir: ⇒

Bir kafes, yalnızca içinde N5’e izomorf bir alt kafes yoksa modülerdir. Modüler kafeslere örnekler: Bir modülün alt modül kafesi, Bir halkadaki iki taraflı idealler kafesi, Bir grubun normal alt grupları kafesi. Öte yandan, otomatik akıl yürütmede kullanılan “daha özel olma” sıralamasına dayalı terimler kümesi, modüler olmayan bir kafestir.

 Yarımodülerlik 

Bir sonlu kafes, ancak ve ancak hem üstten yarı-modüler hem de alttan yarı-modüler ise modülerdir. Sonlu uzunlukta bir kafes için üstten yarı-modülerlik, kafesin dereceli (graded) olması ve derece (rank) fonksiyonu ’nin şu koşulu sağlaması ile eşdeğerdir: 


Dereceli kafesler için eşdeğer başka bir koşul da Birkhoff koşuludur:

Kafesteki  her  ve  için, eğer her ikisi de 'yi kapsıyorsa, o zaman  hem ’i hem de ’yi kapsar.

Bir kafes alttan yarı-modüler olarak adlandırılırsa, bu onun dualinin yarı-modüler olması anlamına gelir.

Sonlu kafesler için bu, yukarıdaki koşulların;  ve  işlemlerinin yer değişmesiyle, "kapsar" işlemi yerine "tarafından kapsanır" işlemine dönüşmesiyle ve eşitsizliklerin yönünün ters çevrilmesiyle geçerli olması demektir.

 Süreklilik ve cebirsellik 
Alan kuramı bağlamında, bir kısmi sıralamanın öğelerini daha "basit" öğelerle yaklaşık olarak ifade etmek doğaldır. Bu durum, şu kavramları doğurur: Sürekli kısmi sıralı kümeler: Her öğe, kendisinden "çok daha küçük"  öğelerden oluşan yönlü bir kümenin üst sınırı olarak ifade edilebilir. Eğer bu yönlü kümeler sadece sıkı öğelerle sınırlanırsa, poset ayrıca cebirsel olur.

Bu iki kavram kafesler için şöyle tanımlanır:

 Sürekli kafes: Tam olan ve poset olarak süreklilik gösteren kafes.
 Cebirsel kafes: Tam olan ve poset olarak cebirsel özellik gösteren kafes.

Bu kafes sınıflarının ilginç özellikleri vardır. Örneğin:

 Sürekli kafesler, belirli sonsuz-yerine-geçebilen işlemlerle tanımlanan cebirsel yapılara karşılık gelir.
 Cebirsel kafesler için benzer bir yapı tanımı bilinmemekle birlikte, bunlar Scott bilgi sistemleri ile sentaktik olarak tanımlanabilir.

 Tümleyenler ve yarı tümeyenler 
Bir kafes , eğer en küçük eleman 0 ve en büyük eleman 1'e sahipse, yani sınırlı bir kafes  ise, şu tanımlar geçerlidir:

İki öğe  ve , ancak ve ancak:ise birbirinin tümleyeni olur.

Ancak, her sınırlı kafeste tüm öğelerin tümleyeni olmayabilir. Bazı öğelerin hiç tümleyicisi yoktur, bazılarının ise birden fazla olabilir. Örneğin:  kümesi (doğal sıralamasıyla) bir sınırlı kafestir, ancak 'nin tümleyicisi yoktur. N5 kafesinde (Şekil 11),  öğesinin iki tümleyeni vardır:  ve . Her öğesinin bir tümleyeni bulunan sınırlı kafeslere tümleyen kafes denir.

Hem tümleyenli hem de dağılırlık gösteren kafesler ise Boole cebiri olarak adlandırılır.

Dağılırlık gösteren bir kafeste, eğer bir öğenin  tümleyeni varsa, bu tümleyen tektir.

Bu durumda şu şekilde yazılır:

   ve denk olarak 

Bu tekil tümleyen, kafes  üzerinde mantıksal olumsuzlama gibi davranan bir birli işlem tanımlar. Bu işleme tümleme denir.

Heyting cebirleri, dağılırlık gösteren ancak her öğesi için mutlaka bir tümleyen içermeyen yapılar olarak öne çıkar. Ancak her öğe  için bir yarı-tümleyen vardır ve bu da  ile gösterilir. Yarı-tümleyici,  olacak şekilde, x'e göre bu koşulu sağlayan en büyük 'dir. Eğer bir Heyting cebirinde her yarı-tümleyici aynı zamanda gerçek bir tümleyiciyse, o cebir bir Boole cebiri olur.

 Jordan–Dedekind zincir koşulu 
Bir zincir, 'dan 'ye kadar olan bir öğe kümesidir:  burada  Bu zincirin uzunluğu, ndir; yani zincirdeki eleman sayısının bir eksiğidir.

Bir zincir, eğer her , 'i kapsıyorsa —yani:  arada başka hiçbir öğe yoksa her  için— o zaman bu zincir maksimal zincir olarak adlandırılır.

Eğer her  çifti için, 'ten 'ye kadar olan tüm maksimal zincirlerin uzunluğu aynıysa, o zaman kafes Jordan–Dedekind zincir koşulunu sağlar.

 Dereceli/dizili 
Bir kafes , eğer bir derece fonksiyonu ile donatılabiliyorsa dereceli, bazen de dizili olarak adlandırılır. (Ancak dizili poset teriminin farklı anlamları da olabilir.) Bu derece fonksiyonu:  (veya bazen ) şöyle bir uyumluluk göstermelidir: Eğer  ise, o zaman . Özellikle, eğer , 'i kapsıyorsa, yani arada başka bir öğe yoksa: 

Bu fonksiyona derece fonksiyonu, her öğeye atadığı değere de öğenin derecesi denir.

Bir öğe , bir başka öğe 'i kapsar, eğer: ise ve  olacak hiçbir başka  öğesi yoksa. Yani,  ve  olmakla birlikte, x ile y arasında başka hiçbir öğe bulunmuyorsa, y, x'i kapsıyordur .

 Serbest kafesler 

Herhangi bir  kümesi, serbest yarıkafes 'i oluşturmak için kullanılabilir. Serbest yarıkafes, 'in tüm sonlu altkümelerinden oluşur ve yarıkafes işlemi, sıradan küme birleşimi olarak tanımlanır. Bu yapı, evrensel özelliği taşır.

Bir  kümesi üzerinden tanımlı serbest kafes için, Whitman, 'in öğeleri üzerinden tanımlı polinomlara dayalı bir yapı önererek bir inşa yöntemi geliştirmiştir.

 Kafes kuramında önemli terimler 
Aşağıda, bazı önemli sıralama kuramı kavramları kafes kuramı bağlamında tanımlanmaktadır. Burada , bir kafes 'nin bir öğesi  olsun.

 Birleşime göre indirgenemez öğe (join-Irreducible); Bir öğe tüm  için  ve  koşullarının ikisini birden sağlıyorsa birleşime göre indirgenemez öğe olarak adlandırılır. Eğer 'de bir en küçük öğe  varsa, bazı kaynaklar ayrıca  koşulunu sağlaması gerektiğini varsayar, bu tanımın, keyfi birleşimler için genelleştirilmiş hali , tam birleşime göre indirgenemez ya da (-indirgenemez)  kavramını verir. Bu terimin duali ise, kesişime göre indirgenemez  (meet-irreducible) (-indirgenemez) öğelerdir. Örnek olarak, şekil 2'de yer alan öğeler 2, 3, 4 ve 5 toplama göre indirgenemez; 12, 15, 20 ve 30 ise kesişime göre indirgenemezdir. Kimi tanımlarda, en küçük öğe (örneğin 1) ve en büyük öğe (örneğin 60), indirgenemez kabul edilmeyebilir. Gerçek sayılar kümesi üzerinde tanımlı sıradan kafeslerde, her öğe toplama göre indirgenemezdir ancak hiçbiri tamamen toplama göre indirgenemez değildir.
 Birleşime göre asal öğe (Join-Prime); Bir öğe  ve  koşullarının ikisini birden sağlıyorsa birleşime göre asal öğe olarak adlandırılır. Yine, bazı kaynaklar  koşulunu da arar; ancak bu pek yaygın değildir. Bu da genelleştirilerek tamamen birleşime göre asal öğe kavramına ulaşılır. Bu terimin duali ise kesişime göre asal öğedir (meet-prime). Her birleşime göre asal öğe aynı zamanda birleşime göre indirgenemez öğedir. Benzer biçimde, her kesişime göre asal öğe de kesişime göre indirgenemezdir. Ancak tersine dönüş (her indirgenemez aynı zamanda asaldır) yalnızca kafes  dağılımlı ise geçerlidir.

Eğer kafes , bir en küçük öğe 0'a sahipse, bir öğe , aşağıdaki koşulları sağlıyorsa atom olarak adlandırılır:  ve  olacak herhangi bir  öğesi yoktur. Bu durumda eğer ’nin sıfırdan farklı her öğesi için,  olacak şekilde bir atom  varsa, kafes atomiktir. Eğer ’deki her öğe, kafesin atomlarının birleşimi olarak ifade edilebiliyorsa, kafes atomistiktir.İdeal ve onun duali olan filtre kavramları, kısmi sıralı kümelerin özel türde altkümeleri olup kafes kuramı için önemli yapılardır.

 Ayrıca bakınız 

 Birleşim ve kesişim (sıra teorisi) - Sıralı kümelerde birleşim (join, ∨) ve kesişim (meet, ∧) işlemleri.
 Kafesler haritası - Matematikte, farklı kafes türlerinin yapısal ilişkilerini gösteren diyagram veya şema.
 Ortokomplemanlı kafes - Her eleman için belirli kurallara uyan bir "tamamlayıcı" (kompleman) tanımlanmış olan kafes. 
 Tam sıralı düzen - Her iki elemanın karşılaştırılabildiği (ya x ≤ y ya da y ≤ x olduğu) sıralı yapı
 İdeal ve filtre (ikili kavramlar) - İdeal: Boş olmayan, yukarıdan sınırlı, aşağıya kapalı alt küme. Filtre:''' Bunun duali, yani aşağıdan sınırlı, yukarıya kapalı alt küme.
 Eğri kafes (veya yönsüz olmayan kafes) - Birleşim ve kesişim işlemlerinin değişmeli (komütatif) olmadığı cebirsel yapı.
 Euleryen kafes - Her kapalı zincirinin tek sayı uzunluğuna sahip olduğu, belirli topolojik özellikleri taşıyan kafes.
 Post kafesi - {0,1} kümesi üzerindeki tüm klonların (bileşime kapalı ve projeksiyonları içeren işlem kümeleri) birleşim altındaki sıralaması.
 Tamari kafesi - Parantezleme biçimlerine göre sıralanmış ifadelerden oluşan matematiksel yapı.
 Young–Fibonacci kafesi - Young diyagramları ve Fibonacci sayılarına dayanan özel bir kafes yapısı.
 0,1-basit kafes - Yalnızca en küçük (0) ve en büyük (1) elemanları olan ve belirli basitlik koşullarını sağlayan kafes.

 Kafes teorisinde kullanılan uygulamalar Birçok uygulamada kümelerin yalnızca kısmi kafesler olduğunu unutmayın: her eleman çiftinin birleşme veya birleşme noktası yoktur. Anlamsız topoloji
 Alt grupların kafesi
 Spektral uzay
 Değişmez alt uzay
 Kapatma operatörü
 Soyut yorumlama
 Alt tüketim kafesi
 Bulanık küme teorisi
 Birinci dereceden mantığın cebirselleştirilmesi
 Programlama dillerinin semantiği
 Alan teorisi
 Ontoloji (bilgisayar bilimi)
 Çoklu kalıtım
 Biçimsel kavram çözümlemesi ve Lattice Miner (teori ve araç)
 Bloom filtresi
 Bilgi akışı
 Sıralı optimizasyon
 Kuantum mantığı
 Medyan grafiği
 Bilgi alanı
 Düzenli dil öğrenimi
 Analojik modelleme

 Notlar 

 Kaynaklar 

Ücretsiz çevrimiçi monograflar:
 Burris, Stanley N., and Sankappanavar, H. P., 1981. A Course in Universal Algebra.  Springer-Verlag. .
 Jipsen, Peter, and Henry Rose, Varieties of Lattices, Lecture Notes in Mathematics 1533, Springer Verlag, 1992. .

Sınırlı matematiksel olgunluğa sahip olanlar için önerilen temel metinler:
 Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
 Grätzer, George, 1971. Lattice Theory: First concepts and distributive lattices. W. H. Freeman.

Standart çağdaş giriş metni, yukarıdakilerden biraz daha zor:


İleri düzey monograflar:
 Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society.
 Robert P. Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice-Hall. .


Serbest kafesler üzerine:
 R. Freese, J. Jezek, and J. B. Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America.
 Johnstone, P. T., 1982. Stone spaces''. Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.

Kafes teorisinin tarihi üzerine:

  Textbook with numerous attributions in the footnotes.
  Summary of the history of lattices.


Kafes teorisinin uygulamaları üzerine:
  Table of contents

 Dış bağlantılar 



 J.B. Nation, Notes on Lattice Theory , course notes, revised 2017.
 Ralph Freese, "Lattice Theory Homepage" .


Kategori:Sıra teorisi
Kategori:Kafes teorisi